8.31
P7078 贪吃蛇：
结论：若一条最强蛇吃了最弱蛇后不是最弱蛇，那么它一定会选择吃。
证明：若这条蛇吃了最弱蛇后不会变成最弱蛇，那么下一条蛇在吃了最弱蛇后一定比这条蛇更弱，而下一条蛇一定会想办法不死，所以这条蛇也一定不死，因此它可以吃。
接下来考虑如果最强蛇吃了最弱蛇后会变成最弱蛇，那么这条蛇该不该吃。
考虑向后递推：若下一条蛇吃了最弱蛇后不会变成最弱蛇，那么根据先前的结论，下一条蛇肯定会吃，所以这条蛇为了自保就不会选择吃。否则继续考虑下一条蛇。
这样可以发现，游戏会一直进行到某条蛇吃了之后不是最弱蛇或只剩两条蛇为止。这样，当前蛇的选择就与最后一条蛇的奇偶性有关了，我们便可以据此设计两个阶段：
1.最强蛇吃了之后不是最弱蛇，此时可以吃；
2.最强蛇吃了之后是最弱蛇，此时判断它与最后一条能吃的蛇之间的奇偶性判断它还能不能再吃一次。
拉格朗日插值
证明太麻烦了，记住结论：
\(f(k)=\sum _{i=1}^{n}y_i \prod _{j \ne i}\frac{k-x_j}{x_i-x_j}\)
P5021 赛道修建
看到最小值最大，首先想到二分。二分答案，判断满足当前答案的道路是否够 \(m\) 条。
思考如何让最短的道路最长。考虑贪心，对于一个节点，我们将与其相连的所有边按从大到小排序，显然，我们为其找一条最小的使其能 \(\ge\) 当前答案的边是最优的。
我们维护一个 \(multiset\) 表示那些需要匹配的边。每次取出最小的边，判断它能否与子树中的其它边匹配，如果能，就将与其匹配的边也消去，并将答案 \(+1\)，最后加上那些原先就满足要求的边，判断是否足够即可。
9.1
P8632 居民集会
设 \(f_{i,j}\) 表示将第 \(j\) 个集会放在第 \(i\) 户人，前 \(i\) 户的最小代价。
则 \(f_{i,j}=\min_{k=0}^{i-1}\) { \(f_{k,j-1}+\sum_{p=k+1}^{i}t_p*(d_i-d_p)\)}。
直接做会 \(T\)，考虑前缀和优化。设 \(cnt_i=\sum{t_i}\)，\(pre_i=\sum{t_i*d_i}\)，则原状态转移方程可表示为 \(f_{i,j}=\min_{k=0}^{i-1}\) { \(f_{k,j-1}+d_i*(cnt_i-cnt_k)-(pre_i-pre_k)\) }。
将括号拆开，整理可得：
\(f_{i,j}=\min_{k=0}^{i-1}\) { \(f_{k,j-1}+pre_k-d_i*cnt_k+d_i*cnt_i-pre_i\) }。
发现这个式子很能斜率优化，于是去掉 \(min\)，移项，得：
\(f_{k,j-1}+pre_k=d_i*cnt_k+pre_i-d_i*cnt_i+f_{i,j}\)。
令 \(y=f_{k,j-1}+pre_k\)、\(k=d_i\)、\(x=cnt_k\)、\(b=pre_i-d_i*cnt_i+f_{i,j}\)。单调队列维护下凸壳即可。
P5023 填数游戏
学会打表找规律！！！
9.2
P4370 组合数问题2
首先可以发现，\(C_n^m > C_{n-1}^{m}\)，所以我们可以用优先队列存下初始所有的 \(C_{n}^{i}\)，更新答案时顺便将 \(C_{n-1}^{i}\) 加入优先队列即可。
问题在于如何比较两个组合数，由于取模，原先大的数变得不一定仍然大了，直接写高精度会 \(T\) 飞，所以我们需要考虑如何优化。
根据高中数学知识可得：
1.若 \(a>b\)，则\(log_2a > log_2b\)。
2.\(log_2a+log_2b=log_2ab\)。
我们还能发现，每个数的 \(log\) 值会很小，所以我们可以对于每个组合数，预处理出它的 \(log\) 值，到时候直接比较 \(log\) 值即可。
考试T1
考虑每个数作为最大值时的贡献次数，形如 \(1,2,3,...,x,x,...,x,x,x-1,x-2,...,2,1,0,0,0,...\)。
维护二阶差分，维护两个转折点 \(R-i+1\) 和 \(i-L+1\) 即可。
复杂度 \(O(n)\)。
P8386 Od deski do deski
难点全在于状态设计。
考虑所有删除区间之间的关系。首先肯定不可能有交，若为包含，直接删最大区间即可，所以只能是不交。
设 \(dp_{i,j,0/1}\) 表示考虑到第 \(i\) 个点，填多少种数会使状态合法，当前状态是否合法的方案数。则可以列出转移方程：
\(dp_{i,j,1}*j \to dp_{i+1,j,1}\)
\(dp_{i,j,1}*(m-j) \to dp_{i+1,j+1,0}\)
\(dp_{i,j,0}*j \to dp_{i+1,j+1,1}\)
\(dp_{i,j,0}*(m-j) \to dp_{i+1,j,0}\)
时空复杂度均为 \(O(n^2)\)。
考试T4
Full_Speed 的原创题，让我们一起来膜拜他罢！
考虑对 \(x\) 有贡献的时间为从 \(x\) 开始的上升子序列，对于每个点，我们又它向后面第一个大于它的点连边，表示它会对当前点造成贡献，这样就形成了一棵树。
我们发现，对于两个点 \(x\)，\(y\)，两个点之间的公共事件实际上就是他们的 \(LCA\) 到根路径上的所有点，主席树维护这条路径上所有 \(\ge k\) 的数的个数及其和即可。
P3953 逛公园
记忆化搜索。设 \(dis_i\) 表示 \(1\) 号点到其他点的最短路。
设 \(f_{i,k}\) 表示一号点到 \(i\) 号点花费 \(dis_i+k\) 的时间的边数。设当前点为 \(u\)，则 \(f_{u,k}=f_{v,dis_u-dis_v+k-w}\)，\(dfs\) 时记忆化一下即可。判断无穷的方式也很简单，直接判断是否存在边权全为 \(0\)的环即可。