ThinkofBlank

题解

未归档(4) 论文(10) 题单(1)

/ 注册

全部文章 / 题解（共75篇）

比赛题解

一开始以为求第0-12个问题的解决概率懵逼了很久一道简单的概率dp/dfs问题我们先求出每个问题的解决概率。我们运用正难则反的思想，先求出我们不能解决第i个问题的概率，即：然后，用1减去这个概率就是第i个题可以解决的概率了，设为那么，现在就可以随便乱搞了。注意到，n很小，可以直接dfs...

优化题解动态规划

2020-05-18

4 893

牛客小白月赛25 题解

一.闲话本来打的挺开心的，A题速度挺快的。然后。。。G题被疯狂卡精度。。。（绝望），罚时一大堆qwq。我好菜啊qwq 由于打比赛的时候，打的比较快，很多代码都比较粗糙，还请见谅~ 二.题解 A.AOE还是单体？明显是个单峰函数求极值问题（应该可以直接推式子，但是懒）~ 我们三分群体攻击次数，然后...

题解

2020-05-17

1 762

「土」秘法地震题解

本来打算只写一种解法的，不过感觉太水了，就多写点吧解法一.暴力按照题目说的模拟去做，复杂度,期望得分：70-100(数据有点弱啊qwq) 解法二.带优化的暴力我们设a[i][j]表示i,j点的正下面中，包含i,j的k格格子中是否至少存在一个1。这个直接暴力统计就好了，当然，你要把存在改成有几...

优化题解

2020-05-15

0 673

牛客练习赛63 题解

发现这个比赛忘写题解了，来补题解辣qwq A.牛牛的三角形总所周知，三条边可以拼出三角形的充要条件是：最小的两条边长度之和大于第三条边。看数据范围，n<=100,于是直接一个n^3枚举再判断就行辣！代码： #include<bits/stdc++.h> using namesp...

题解

2020-05-14

0 666

储物点的距离题解

这道题其实就是一道化式子的题，化完式子后就可以乱搞了/x 我们设pos[i]表示i号点的位置，特别的，pos[1]=0,那么，我们就可以根据i到i+1的距离，分别算出每个点的位置了。那么，我们就开始化式子吧。我们假设将i号点的物品搬到j号点去，那么代价就是：那么，如果将l-r号点的物品搬到...

优化题解

2020-05-14

2 917

maze 题解

这道题，因为传送阵需要3s，所以，我们如果打普通的bfs可能会挂，于是，为了满足正确性，就可以类比01bfs之类的，搞个优先队列做。。。但是，个人觉得有点麻烦，我们不妨从"这道题是一个搜索题"这个想法中解放出来，那么，这题就变成了一道明显的最短路问题啦！我们先利用网络图连边，然后再把传送阵的q条边...

题解

2020-05-13

1 892

牛客算法周周练6 部分题解

一.闲话这次比赛挺简单的，我就来写下其中有意思的题目的题解吧。。。（罚时太高，排名直降，我太菜了qwq）二.题解 C.Game 这道题明显是一道博弈论问题，那么，就需要搞sg函数之类的。。。算了吧！/xk 我们直接暴力dp吧。。。我们设dp[i]=0/1表示有i个石块的情况是必输/胜那么，...

题解

2020-05-12

1 677

加分二叉树题解

一道比较经典的区间dp题目首先我们设dp[i][j]表示我们用i-j这些点构造树的最大收益是多少首先dp[i][i]=a[i]（只有一个点，最大价值即点本身价值）现在，我们考虑转移：因为一颗子树的价值=左子树价值*右子树价值+根价值那么，如果我们知道了根，左子树，右子树后，就可以进行转移了...

题解动态规划

2020-05-12

1 726

模拟战役题解

很简单的一个联通块题目首先，我们把同一个阵营中，会相互波及到的大炮放进一个连通块中，这样的话，很容易可以发现，如果连通块中有一个大炮被攻击了的话，那么，整个连通块的大炮都会被波及。现在，假设我们将双方的联通块个数及大小求出来了，分别为：司机: 齐齐: 那么，对于齐齐来说，每次攻击就相当于用...

题解

2020-05-11

7 763

Moovie Mooving 题解

一.闲话英文题真难受，盯google盯了好久qwq，输入部分还是看样例解释看出来的qwq,英语菜鸡没人权qwq 二.题解这道题，题意是：有n场电影，每场电影都有若干场。给你每个电影的播放时间以及每场的开始时间，问你，要连续不断的看电影直到看到l为止，最少需要看几部电影（每部电影最多看一场） ...

题解动态规划

2020-05-09

0 705