Home

https://ac.nowcoder.com/acm/contest/23106/K 题意 ​ 我们得到一个数组，该数组的第 i 位表示从该位起，往前三位的颜色中红色和绿色那种更多，若相等则为黑色。我们需要求出来最终绿色数量最多的一种情况。 ​ 思路 ​ 我们可以发现，如果我们确定其中三座岛屿的话，那么我们便可以准确推断出来我们的最后一位的岛屿的颜色是怎么样的，如果我们这些岛屿颜色正确的话，那么我们寻找其前几位的颜色即可。 ​ 因此我们定义这样的状态 f[n][i][j][k] 表示目前在第 n 座岛屿上，并且第 n位的颜色为i ，n-1 位的颜色为 j , n - 2 位的颜色位 k 时绿色最多时候的情况，那么我们就可以得到这样的方程了。 ​ \(f[n][i][j][k] = ...

https://ac.nowcoder.com/acm/contest/23106/A 对于每个人来说，他们都有一个数，并且这些数的范围是 [0 , 9] 我们很容易的想到使用DP的思路来解决问题。 我们设 f[n , m] 表示前 n 个人一共可以组合出来多少个结果为 m 的个数。 那么我们便可以得到这样的转移式子对于第 i 个人来说，其本身就是一种情况，因此 f[i , v[i]] ++ 是必要的。那么对于前一个位的 10 种情况而言假设原根为 g(x) ,那么状态转移方程如下所示 \[f(i,j) = \sum_{g(v[i]+k)=j} f(i-1,k)\] 转化为代码 1 2 3 4 5 6 for (int i = 1 ; i <= n ; i ++) {...

https://ac.nowcoder.com/acm/contest/23106/F 和其他方法比起来，我写的方法可能不是那么优，但也不妨作为一种思路。 我们将比 $m$ 小的数设为 $1$，反之设为 $0$。 那么我们就将得到一个只包含 01 的数组。我们将这个数组求出其前缀和$S$。 对于区间 $(l ,r]$ 而言。只要我们满足 $S[r] - S[l] <= \frac{(r - l - 1)}{2}$ 条件即可。其中 $0 \le l < r \le n$。 我们将这个式子化简便可以得到这样的关系。 $(2 * S[r] - r) + 1 <= (2 * S[l] - l)$ 对于一个 $r$ 而言，我们需要求出所有满足上述情况的 $l$ 中我...

https://ac.nowcoder.com/acm/contest/23106/G 题意 我们得到一个数组 f[n] 。同时我们定义 local minimum 为 $f[i] < \min(f[i - 1] , f[i + 1])$ 。 我们可以选择一个整数 b并将这些 f[n] 变为 |f[n] - b| + b。求解，最终得到的数组中 local minimum 最少的个数。 思路 首先，对于一个这样的一个方程我们可以发先，$\lvert a-b \rvert +b=\max(a , 2 * b - a)$ 我们发现，对于 $b \le a $ 来说，原数组的大小时不会变化的，因此我们只有 b 的取值大于 a 的时候才会对数组产生影响。 然后我们考虑这样的一个...

https://codeforces.com/problemset/problem/24/D 题意 ​ 我们有 $N \times M$ 大小的网格。我们有一个点，他可能会向左中右下(不会突破边界)，这四个方向走动。我们的目标是最后一行，求解从点 (x , y) 走到最后一行的期望步数是多少。 ​ 思路 ​ 假设我们当前处于第 $i$ 行。我们可以得到如下的方程 ​ \(\begin{aligned} & F[i , 1] = (F[i + 1 , 1] + F[i , 1] + F[i , 2])\times \frac{1}{3} + 1 \\ & F[i , M] = (F[i + 1 , M] + F[i , M] + F[i , M - 1]) \times...

https://www.luogu.com.cn/problem/P1272 题意 给出一颗有 n 个节点的树，求问分解出一个含有 p 个节点的子树最少需要删去多少条边。 思路 假设我们要以一个节点为根，那么我们不妨定义 f[i , j] 用以表示节点 i 包括其根形成了具有 j 个结点的子树。 那么对于一个节点 u，我们可以直接得到f[u ,1] 的值为节点 u 所连接子树的 个数，也就是说，我们将这个节点所连接所有的子树都给删去所得到的最小边。 在已经加入一定的节点的情况下。我们加入u 的一个子树 x 我们就可以得到一个转移方程 f[u ,i + j] = min(f[u ,i] + f[x ,j] - 1)。 那么我们只需要遍历一遍即可得出答案。 Code 1 ...

https://www.luogu.com.cn/problem/P1856 题意 给出许多矩形，给出的数据为左下角和右上角，求解这些矩形并的周长。 思路 同求解矩形的面积一样，我们采取扫描线的手段来获取当前的线段长度。 一个线段一定为产生两个端点。因此我们同样也需要求解出段数，对于一个线段树来说，我们的段数还算很好维护的。 我们一个线段我们需要维护一些信息 L , R , len , cnt , block。 其中 L 表示这个线段的左端点我们取得到，R 同理。 len 表示线段的长度。 cnt 表示线段被加入的次数 , block。表示线段的段数 对于这样的节点，得到以下结论是显然的 L[p] = L(Lson(p)) R[p] = R(Rson(p)...

https://www.luogu.com.cn/problem/P2495 题意 我们有一个树，它的根节点为 1 ，它的每条边都有相应的权值，我们每次都会产生一些点，要求如果要将这些点通过删边的方式使之不与根节点相连，求删去边权和的最小值。 思路 暴力 如何暴力做？ 设 f[i] 表示所有的处理完这点的最小值 第一步，当我们输入我们所有的点之后，我们将所有的点都标记上，然后将 f[n] 初始化为 0 。如果我们遇到这些标记，那么我们只需要将 f[i] 设置为 +inf 随后返回即可。对于每个节点我们只需要写f[i] += min(w , f[j]) 即可求出来。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21...