- CF710F 2400
- 看题之后10分钟排除了AC自动机（它的AC自动机是不断变化的，所有我们不能用这个直接进行维护）
- 一时间没想到怎么进行二进制分组，思考良久后发现我们可以对串进行二进制分组来构建的
- 加入/删除一个串（加 +1 删 -1）
- 构建一个大小为1的AC自动机
- 然后 "1+1=2,2+2=4" 这样不断地去合并
- 一个串最多参加合并 \(log\) 次故 \(O(N \log{N} 26)\) 可行。
- 思考代码怎么写最优+代码实现了70多min左右，算是回归OI的第一道题，写的很不熟，甚至是AC自动机的板子也很不熟。
- 实现的细节
- 开个 \(rt\) 当作二进制分组中每个AC自动机的根节点，合并的时候只合并节点信息 (tr数组,cnt(表示有多少个以当前节点为结尾的字符串)信息)，不用建AC自动机，最后没有可合并的了的时候，再拿我们这些信息合并成一个大的AC自动机
- P14980
- 几个环+几条链
- 发现一次操作就是断边，但是比较难以实现，故我倒着来合并即可
- 锻炼了下思维？用时比较短。
- P14981
- 很容易想到了要让尽量小的先合并，然后则对于任意 \(k\) 来说前 \(k\) 小的数都要挨在一起
- 然后就有点毫无头绪了，偷瞄了眼题解发现
- 当前 \(k\) 小的元素都挨在一起时，此时的序列是单谷的
- 一个数最终到谷底的左边或右边，若左，那么代价即为左边小于它的元素个数(因为它左边只能有比它大的数)，若右同理，这个东西可以用树状数组维护，选择代价小的方向即可。
- P14982
- 以为是左右两侧的距离 \(<=D\) 都行，结果是左侧 \(<=D\)，浪费了许多时间，读题，很显然的具有拓扑序，故DP
- 设 \(dp_i\) 为考虑前 \(i\) 个且 \(i\) 被选了的方案数
- \(o_i = 1\) 很显然 \(dp_i = \sum_{j<i} dp_j\)
- &o_i = 0& \(dp_i = \sum_{j<i,p_i-p_j<=D,o_j=1} 2^x \cdot dp_j\) (x为 \(j\) 和 \(i\) 之间的营员数)
- 直接上线段树优化转移DP即可。
- AT_abc440_e
- 很容易想到暴力记状态优先队列处理，但既然到这道题了不妨复习一下前 k 优方案这类问题
- https://www.luogu.com.cn/problem/P2541 很显然这是一道DMY暑假的题目
- 我们希望能够通过某种方法只会考虑到前 k 优的方案，并且做到不重不漏。
- 啊对，然后这题我没想出来这样的方法解决。
