1 - Problem - G - Codeforces

思路

其实是很明显的思路

不难发现我们可以随意选择蛇的顺序

并且需要的地图总长度只与每相邻两蛇的变化情况有关：

• 相邻两蛇在全过程中左蛇伸长量减去右蛇缩短量的最大值就是两蛇之间需要留出的空间
• 最左边蛇可以紧挨着原点
• 最右边蛇需要预留出其最后伸长量对应的空间

于是我们就可以考虑子集动态规划：

• 记录 $dp[S][j]$ 是已经前面考虑子集 $S$ 且最后一个为 $j$ 号蛇的所需空间
• 于是就可以 $O(n^2)$ 预处理，$O(2^n)$ 动态规划

收获 & 反思

子集动态规划的应用

对于题目的理解 & 建模

2 - Problem - E2 - Codeforces

思路

按照贪心的博弈论思路来转化

对于最后一个数，如果在选择了它之后必胜，那么所有最终胜利点可以进行如下贪心：

• 如果一个数的 右下方还有相同的数，那就不考虑，因为这个数可取的时候，右下方的数一定也可取

于是最后胜利的节点便会呈现单调性

然后看前一个数，同理，我们会选的位置也具有单调性，但是必胜与否就需要看后一个数：

• 如果能到达某个必胜位，则必败，否则必胜
• 不难发现可到达的后一个数的位置，是一段连续的区间
• 又因为当前这个数位置的单调性，这个区间可以用双指针来维护
• 是否包含必胜节点可以通过维护前一段的前缀和，$O(1)$ 计算区间和来判断

就做完了

收获 & 反思

很神秘的题目：

• 博弈论贪心，出单调性
• 单调性，出双指针
• 双指针，可以前缀和

我勒个豆

3 - Problem - 1437E - Codeforces

思路

需要用到个小技巧：

• 如果是严格上升，就把每一个值变为 $va{l}_i-i$ ，然后按照严格非降做就好了，可以少很多麻烦

然后不难发现只需要在相邻的 “不可修改点” 之间求 LIS 就是区间最多的不用修改的元素数量

需要注意：

• 那些超过上下界的元素一定要修改，所以在求 LIS 时不考虑
• 不可修改点一定要严格非降，否则必定无解

收获 & 反思

转化问题建模，考虑 “最少修改” 时不妨看看 “最多不修改”

4 - Problem - G - Codeforces

思路

拿祖先去倍增树上 DP

收获 & 反思

当无法直接带着自己转化（比如说会有重复或非法的贡献）的时候，就考虑把自己和祖先分开考虑

$dp$ 有的时候也需要推式子，比如说把答案的一部分放到 $dp$ 中去