前言
考前临时写的题解，希望会有帮助
2023
比赛回顾
分数是 100+50+0+0=150
比赛打的没什么问题，就是当时水平菜，写不出 DP 和大模拟。
密码锁
枚举每一个密码是否可能。
消消乐
记 \(f_i\) 为以 \(i\) 点为结尾的合法串数，则 \(f_i=f_{i-g_i}+1\)，\(g_i\) 为以 \(i\) 为右端点最短的合法串，目标转化为求 \(g_i\)。
可以发现一个性质：一个合法串去除头尾最多拆成 \(|\Sigma|\) 个合法串，对于 \(|\Sigma|\) 较小暴力跳是可以接受的。
跳的过程复杂度太高了，所以将其抽象成图问题，连接 \((i,g_i-1)\) 的单向边，从 \(i-1\) 开始总能跳到 \(g_i\)，这个可以用链表维护
结构体
sb 题，谁想写题解就去写吧。
种树
直接做我们发现树种好天数不固定，考虑二分。
对于一个情况，先二分处理出这些树种的时间 \(t_i\)，然后每次贪心的选择种的最久的树走过去种。
2024
比赛回顾
分数是 100+100+0+0=200
- 问题 1 ：没有养成保存暴力的意识，为了打 T3 假正解把暴力删了。
- 问题 2 : 在 T2 浪费了过多的时间(40 min)，理论上在 20min 内就应该解决。
决斗
排个序，从小到大依次加入战场，使用双指针维护。
超速检测
对于被判定超速的车：
- \(a>0\) 的会在一个后缀被判定
- \(a=0\) 在经过的所有被判定
- \(a<0\) 的会在一个前缀被判定
二分搜索判定的区间并贪心选取收费站。
染色
考虑从全部同色开始调整，记此时得分 \(s\)。
状态只和上一个染的颜色有关，记染颜色 \(i\) 的 max 为 \(f_i\)，有两种转移：
- 从最大的同色转移：\(f_i \leftarrow f_i - a_i \cdot [a_i=a_{i-1}] + a_i\)
- 从最大的转移：\(f_i \leftarrow \max_{j} f_j - a_i \cdot [a_i=a_{i-1}]\)
因为是调整，所以要加上原先的答案，所以答案为 \(\max_{i=1}^{n}f_i +s\)
擂台游戏
对每个不同树结构都做一次，这是 \(O(n)\) 的。
显然一个人能成为胜者的段是在每个点胜利的段的交，这个是一个前缀，在这之后会出现两种情况中的一种：
- 那个人太菜了
- 一个确定的对手太强了
第一个条件相对简单，能力值尚未确定的时候，他不会受到限制；能力值确定之后，他的能力值就要最少是所有当擂主比赛的最大值，线性处理即可。
记 \(t_u\) 以后 \(u\) 子树下 \(f_u\) 胜利，按照题意分讨转移。
但是最后查的时候要注意：不要从上往下直接查，而是把类似标记的东西丢下去。（复杂度爆炸预定）