第一题 789C

CF 789C
题意：求满足题意最大的子段和。
解：对每个$i$存$a_i - a_{i+1}$，然后对于题目-1的限制，序列是正负正负或者负正负正的。最大的子段和可以想到DP做，所以预处理两个正负正负，负正负正的数组，在上面做字段和DP即可。
子段和DP最优解在每一步取。$dp(i)=max(dp(i-1)+c, 0)$有负数的情况，没有就直接$dp(i)=max(dp(i-1)+c, c)$，最后的$dp(n)$不是答案，注意
知识点：写题目一定要把题意抽象化完再做

Codeforces 459E
题意：一个有向图，找出一条最长的路径，这条路径上的每条边权重都严格递增，问最长的长度是多少？

这题要求每条边权重都严格递增，那么直接把所有边权存起来按照大小排序，之后每种边权进行加边，就可以做 DP 了，因为排序保证了每条边权重都严格递增，只需要 DP 算出最优解即可。

本题求边权严格递增的路径，把边按照大小排序，把选择化为添加边，和CF 841D异曲同工。

Codeforces 518D
题意：有$n$个人，每秒有$p$的概率有一个人进电梯，问$t$秒后电梯里的人数的期望。

设$dp(i,j)$为前$i$秒进$j$个人的概率。则
$$dp(i,j)=dp(i - 1, j - 1) \cdot p + dp(i - 1, j) \cdot (1 - p)$$
但是如果$j=n$，则
$$dp(i,j)=dp(i - 1, j - 1) \cdot p + dp(i - 1, j)$$
因为这样可以继承之前的值。如果没有人数限制，就可以设$dp(i, 0/1)$表示前$i$秒进的/没进的人数期望值。因为这样设会无法处理人数限制的情况

知识点：期望DP不一定DP方程要设期望，也可以设概率。

Codeforces 527D
题意：给一些点坐标$x_i$，每个点都有一个权值$w_i$，求最大的子集大小，该集合中任意两点满足$|x_i - x_j| \geq w_i + w_j$

考虑按照$x_i$升序遍历，则式子$|x_i - x_j| \geq w_i + w_j$可以拆成$x_i - x_j \geq w_i + w_j$，一样的移项，得$x_i - w_i \geq w_j + x_j$，然而做到这里我还是不会qwq。。

观察式子可以发现我们只用维护$x_i - w_i, x_i + w_i$，数形结合，$x_i - w_i, x_i + w_i$代表了一个长$2w_i$，以$x_i$为中点的线段。

然后考虑$x_i - w_i \geq w_j + x_j$和$x_j - w_j \geq w_k + x_k$，则$x_i - w_i + x_j - w_j \geq w_j + x_j + w_k + x_k$
那么$x_i-w_j \geq 2w_j+w_k+x_k$，可以得到$x_i-w_j \geq w_k+x_k$
这样说明如果$i,j$满足条件，$j,k$满足条件，则$i,k$也满足条件。

那么现在满足条件在数轴上表示为每个点代表线段不相交。那么贪心选最多不相交区间即可。

知识点：
绝对值方程可以拆，拆出来的数相同放一边，式子多数形结合，比如本题“$x_i - w_i, x_i + w_i$代表了一个长$2w_i$，以$x_i$为中点的线段。”就是一个很好的方法。

Codeforces 510D
题意：给出$n$张卡上有数字$l_i$，每张卡可以用无限次，每种卡需要$c_i$的花费，问最少用多少花费，能够组成所有的自然数。

能组成所有的数字则这些选的数字$gcd$为1。CF 1011E可以由拼数想到gcd，那么这题也一样。显然得出以上的结论。
那么这样的话，我们只需要用最少的钱找出几个数$gcd=1$即可。我们可以设$dp(i)$为$gcd=i$时最小花费，初始值为$dp(0)=0$，因为$0$与任何数$gcd$等于任何数。不能将所有$l_i$直接加进来，考虑重复的$l_i$。转移方程即为$dp(i)=dp(j)+c_x$，并且能有一个数$x$使得$gcd=j$可以转移到$gcd=i$。
但是数据很大开不了数组啊，由于总数小，就可以用map。

知识点：
超限但是总数小：vector->二维数组压第二维，map->一维数组压第一维
拼数问题和 $ gcd $ 有关系

Codeforces 1020C
题意：$n, m$代表选民和党派下面$n$个选民, $p_i$是他原本打算投的人, $c_i$是你花费这么多可以让他投你, 求最少花费

因为这题最大的麻烦之处就是如果把别的党派的弄到1去，别的党派会少1票，而1党派会多1票，形成了2的差。并且党派初始最大的可能有很多个，难以判断党派1要有多少票。
所以我们可以枚举党派1得的票，相当于枚举一个标准值，让1党派必须达到这个标准值。这与二分判定有类似的地方，我们只需要考虑1党派每种票数的最优解即可
对于处理党派票数，如果其他党派有不小于1党派的，切掉最小的那几个直到其他党派能够比1党派票数小。这个可以用multiset来维护。

知识点：对于这种无法确定个数的题目，不要乱贪心DP，可以枚举一个标准值，然后让无法确定个数变为能够确定个数，从而解决问题

Codeforces 463D
题意：求$k$个序列的最长公共序列长度。

如果是两个序列，则为经典 DP 问题。对于最长与 DP ，可以联想到 DAG 图最长路。
对于每个序列，如果一个数在另一个数前面，并且每个序列都存在这样的关系，就在他们之间连上有向边，显然是一个 DAG 图，然后求一个 DAG 图最长路长度+1即为答案。

本题采用了 DAG 图最长路模型，其核心为 DP 与 最长。

Codeforces 588E
题意：给一棵树$n$个点，再给$m$个人，$m$个人所在的点同时每个人都有一个编号$i$，
你的任务就是找到$uv$这条路的前$k$个人，输出其编号。

直接倍增，每个倍增记录$i$点到$2^j$个祖先的前10最小的点，然后合并信息即可。
如何合并信息呢？我们让两个数组都为有序的，用归并排序实现$O(20)$合并。

注意卡常题, 代码中标注了卡常的地方

Codeforces 734E
题意：有一棵树被黑白染色，同色的为一个联通块，每次可以让一个联通块变色，然后和周围颜色相同的联通块组成大的联通块，求最少多少次能让所有联通块变为同色

联通块直接 DFS 缩点, 然后新图变为黑白相间的树。考虑树的直径有下列性质：

以树的直径中点上的一点为根，将这颗无根树转化为有根树的话，这样做会使树的深度最小，且为树的直径的一半（向上取整）(因为如果有一个叶子节点比直径更深的话，那么就可以构成一个更长的直径，与假设矛盾。)

所以答案是$(d+1)/2$, $d$为直径长。因为按照树的直径中点为根，每次操作直径中点改变颜色，改变$(d+1)/2$次就能改为同色。画图理解。

不要犯了老错误, CF 909E就误以为0点只有一层而错误。此题因为没有考虑到“一个联通块变色，然后和周围颜色相同的联通块组成大的联通块”，以为比较黑白联通块个数，造成了错误。

Codeforces 600E
题意：一棵树$n$个节点，已知点权$ci \leq n$，根为1 对于每个节点，求出对应子树中，出现次数最多（或之一）的点权的和

这题询问子树可以用 DFS 序，然后在 DFS 序上维护出现次数最多（或之一）的点权的和即可。
可以使用莫队对每个子树进行维护。
开数组
col1 每种颜色出现的次数
col2 每种次数的答案
然后更新即可，具体看代码的adjustAdd扩充当前区间，和adjustSub缩小当前区间