五一集训题目总结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/17362361.html

P4104 [HEOI2014] 平衡

dp

题意就是求 $f(s,k)$，满足选 $k$ 个互不相同范围在 $[1,n]$ 内的数使其和为 $s$

一个一个数来确定

思想：

1. 从小到大填
2. 保证单调递增，可以确定某个数和整体+1
3. 保证不溢出 $n$，我们可以减去溢出的情况。先钦定最后一个数溢出，然后求 $f(s-(n+1), k-1)$ (这里面可能包含其他数溢出的情况)

P4101 [HEOI2014] 人人尽说江南好

博弈论

考虑每人都把1合并到最大

对于最大那堆考虑 $m-1$ 和非 $m-1$ 的情况

显然，对于当前这个人无论怎么操作，后手都可以回到正轨

所以就是计算总共最多有多少步

CF1107E Vasya and Binary String

dp

考虑删除是删除最后的段

设 $dp(l, r, k)$ 表示 $[l, r+k]$ 区间的最大价值，且 $[r, r+k]$ 全部相同

要么是后面全部删，要么是前面找一个连起来

CF1103B Game with modulo （unsloved）

二分

先二分出大致范围，再具体二分出数

P7214 [JOISC2020] 治療計画 （unsloved）

从左到右考虑dp

推一推两个能够合并的情况，拆绝对值，发现可以在主席树上跑最短路

因为权在点权上，所以每个点只会入队一次

似乎可以改成线段树？

CF123D String （unsloved）

SAM模板

ABC299F

dp

考虑本质不同，必然开头不同，枚举两个开头

钦定假如下一个选某种字母，必然选最前的

为了不算重，可以钦定统计答案只统计当前结尾大于上一次枚举的开头