t1

枚举所有密码作为正确密码，检查该密码经过一次转动后是否有可能得到全部 $n$ 个状态。

另一种思路是注意到转动是可逆的，所以枚举第一个状态转动后所有可能的密码状态，并检查这些密码状态是否可以是正确密码。这样复杂度更优秀。

t2

简要题解：

维护一个栈，每次新加的字符和栈顶相同就弹栈，否则入栈。用 trie 树上的点表示这个栈序列，只需计算每个点的经过次数 $c_x$ 再计算 $\sum_x\binom{c_x}{2}$ 即可。

证明：

考虑如何判断一个字符串合法。能删就删一定是优的。这是因为，考虑一次删除，这等价于删除所在连续段中最早相邻的两个字符。而这不优于在这两个字符刚相邻的时候就删除。

考虑建一棵字典树，每次新增字符时能跳父亲就跳父亲，不能跳父亲就跳儿子。一个前缀合法当且仅当它的路径结尾在根。由于把 trie 当成无根树后任意选一个点为根都同构，那么一个子串合法当且仅当它的开头和结尾在同一个点。

yummy 考场做法：

定义 $pre(x)$ 为从 $p$ 到 $x$ 子串可消时最大的 $p$。

接下来进行了一点猜测：$l$ 到 $r$ 可消当且仅当对每个字符 $i$ 要么之前没有相同的字符，要么 $pre(i)\ge l$。感性理解了一下似乎是对的。

然后我有了一个很合理的想法。

• 一开始 $pre(x)=x-1$。
• 如果此时 $s_{pre(x)}\ne s_x$，那么下一个可能 $pre(x)$（记为 $pre'(x)$） 就必须包含当前 $pre(x)$ 所在最小可消串，$pre(x)$ 可以直接跳到 $pre(pre(x))-1$。

$s$ 大概就是这么一个情况（$[]$ 表示可消）： $ pre'(x) [pre(pre(x)) \ldots pre(x)][pre(x-1)\ldots x-1] x$

t3

（以下为 yummy 的考场做法）

注意到本题数据范围很小，为省事（避免离散化）可以直接使用字符串作为中间过程的存储方式。

考虑一个类型里需要记录什么，显然本身的大小和对齐要求是需要记录的；然后我注意到更多的情况下我们需要给出一个变量名求其类型和起始位置（只有 4 操作是反过来的），所以我以成员名称为下标建了个 map。

然后关于对齐，注意到对齐要求其实不会超过 $8$，所以为了避免在取整方面栽跟头我直接 while(begin%req)begin++;。

接下来考虑对于变量要记录什么——显然地，类型和起始位置，我把这个结构体起名 var，然后发现这个 var 也可在 map 中当做值。

剩下的活就是字符串模拟了。我考场上花了 100 分钟写完，为的就是弥补 2020 年儒略日的遗憾。

t4

二分答案 $T$，容易算出每个点最迟需要在哪个时刻被种树。

取出最小的时刻 $t_i$ 以及对应的点 $i$。考虑一个合法方案在 $i$ 被种树之前被种树的点集 $S$，由于没有点在 $i$ 之前必须被种树，所以 $S$ 中每个点被种树的时刻是不重要的。又因为 $i$ 到根的路径上除了 $i$ 以外的所有点（设为 $S'$）必须被种树，所以可以钦定 $S'$ 是首先被种的树的集合。

进一步地，由于 $|S| < t_i$（否则 $i$ 就无法在规定时间内被种树），所以就算在 $S'$ 种完之后立刻种 $i$，也不会让 $S$ 中每个点被种树的时间超过 $t_i$，再由 $t_i$ 的最小性和原方案的合法性保证了调整后的方案总是合法的。

综上，得如下算法：取出未被种树的点的最小的时刻 $t_i$ 以及对应点 $i$，从 $i$ 的最浅的未被种树的祖先向 $i$ 不断种树。不断重复该过程，直到所有点都被种树，此时答案不超过 $T$；或者有一个点超出了时间限制，此时答案大于 $T$。

二分答案内层需要一次排序，所以时间复杂度 $\mathcal{O}(n\log n\log T)$，其中 $T$ 是答案的范围。

$t_i \geq n$ 的 $i$ 一定可以在时间限制内种树，对 $t_i < n$ 的 $i$ 桶排，时间复杂度 $\mathcal{O}(n\log T)$。