又美美隐身坑队友了🐖。
A. North and South
注意到和不会改变，所以最后变成的值一定是 \(\frac{\sum_{i = 1}^n a_i}{n}\)，就可以把 \(a\) 转成相对大小，最后的目标变为全部值变为 \(0\)。
考虑到相邻的 \(+1, -1\) 对 \(a_i + a_{i + 1}\) 其实没有变化。
于是分析一次操作对 \(a_i + a_{i + 1}\) 的变化，能发现是 \(a_{l - 1} \gets a_{l - 1} + 1, a_r \gets a_r - 1\)。
而因为 \([l, r]\) 这段区间长度是偶数，所以 \(l - 1, r\) 其实是同奇偶的，于是把同奇偶的 \(a_i + a_{i + 1}\) 放到一起考虑，操作就是可以让一个靠前的值 \(+1\) 一个靠后的值 \(-1\)。
那么合法条件就是前缀和一定 \(\le 0\)，操作次数就是正数的和。
时间复杂度 \(\mathcal{O}(n)\)。
做这题的时候🐖了，把偶数位的正负反转了，代码长得不太一样，不过本质相同。
submission。
B. Operating Robot
每次操作 \(x + y\) 都会恰好 \(+1\)，所以能走到 \(x + y\) 一定是在恰好 \(z = x + y\) 步后走到的。
确定了总步数后就可以把整个序列分成两段：\([1, z\bmod n]\) 会经过 \(\lfloor z / n\rfloor + 1\) 次，而 \((z\bmod n, n]\) 会经过 \(\lfloor z / n\rfloor\) 次。
于是可以枚举第一段中 2 被替换成的 0,1 个数，然后可以根据和为 \((x, y)\) 算出第二段替换的 0,1 个数。
最小化字典序也就是每一段的 0 尽量靠前放，且优先最大化第一段中 0 的个数。
注意 \(z < n\) 第二段不会经过。
submission。
C. Palindromic and Balanced
一个合法括号串把 ( 视作 \(+1\)，) 视作 \(-1\) 后从前往后前缀和需要 \(\ge 0\)；也可以倒过来看，把 ( 视作 \(-1\)，) 视作 \(+1\)，从后往前后缀和需要 \(\ge 0\)。
又因为题目要求除开头的 ( 和最后的 ) 都要回文，很符合上面的判定。
于是考虑记 \(f_{l, r, x, y}\) 表示现在两个端点为 \(l, r\)，前半部分的前缀和为 \(x\)，后半部分后缀和为 \(y\) 的最大长度。
转移可以考虑在 \((l, r)\) 内加入一组回文括号，若 \(s_{l'} = s_{r'}\) 为 (，转移即为 \(f_{l, r, x, y} + 2\to f_{l', r', x + 1, y - 1}\)；同理若 \(s_{l'} = s_{r'}\) 为 )，转移即为 \(f_{l, r, x, y} + 2\to f_{l', r', x - 1, y + 1}\)。需要保证 \(x, y\) 时刻 \(\ge 0\).
初始状态即对于一对 \(l, r\) 满足 \(s_l, s_r\) 为 ()，有 \(f_{l, r, 1, 1} = 2\)。
因为 \(x + y\) 始终 \(= 2\)，所以状态可以压缩到 \(f_{l, r, x}\)。
转移时贪心的考虑，一定是选 \((l, r)\) 内最靠左的期望字符和最靠右的期望字符，所以 \(l', r'\) 不需要枚举而是确定的。
时间复杂度 \(\mathcal{O}(n^2)\)。
wa 了 3 发，我是🐖。
submission。
D. Qenerals
贪心的，占据的 \(a_j\) 一定是从小到大占据。
且如果确定了占据哪些 \(a_j\)，因为减少的值已经确定，一定是能占据就占据。
所以可以排序后枚举最后占据的 \(a_j\) 的前缀，从 \(j - 1\) 递推到 \(j\) 得到要占据 \(a_j\) 剩余的时刻和剩下的兵力，就可以计算答案了。
时间复杂度 \(\mathcal{O}(n\log n)\)。
submission。
E. Registration
这个题放在这感觉像是没题用了。
直接用 map 存下每个时刻的人数判断即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
submission。
F. Split Sticks
榜看起来是个巨难题导致三个人都没开这个题😅。
如果确定了最后每一段的值是 \(v\)，因为每个段的相对顺序并没有改变，所以最终的分界线一定是能够确定的。
接下来就考虑怎么判定能否把初始状态的分界线变为最终的分界线且最小化操作次数。
考虑刻画一次操作，把其当作是可以选择两条相邻的分界线，把这两条分界线变为一条在这两条分界线之间的分界线，对于开头和结尾会有点小差异，在变化后会重新出现一条开头 / 结尾的分界线。
记 l 为初始分界线，x 为最终分界线，手玩一下会发现当存在 l x l x l 或 l x x l 时无解，否则整个结构会形如 l x l l x l l l x l ... 一定有解。
除了操作开头和结尾分界线数都会 \(-1\)，所以至少操作初始分界线减最终分界线数次，其次如果在开头或结尾形成了 l x l 会恰好多操作 \(1\) 次。
于是 check 可以做到 \(\mathcal{O}(n)\)。
但是外层还要枚举 \(v\)，但是想一下最后的段数一定 \(\le n\)，所以 \(\sum\limits_{i = 1}^n a_i \bmod v = 0\) 且 \((\sum\limits_{i = 1}^n a_i) / v\) 应当是 \(\le n\) 的数。
所以这样的 \(v\) 应当不会太多，直接枚举即可。
时间复杂度 \(\mathcal{O}(cnt(v) \times n)\)。
submission。
H. Unreachable Land
看到这个题本能反应就是整除分块一下，然后秒了，？
考虑到若当前模数 \(p\) 是 \(> a\) 的，则 \(\bmod\ p\) 和啥也不做是一样的。
于是考虑设计 dp，\(f_i\) 表示当前值为 \(i\) 且模数还有 \([1, i]\) 没考虑的方案数。
因为初始模数的界被卡在了 \(m\)，所以先特殊处理第一次取模，\(\mathcal{O}(m)\) 枚举即可。
转移也是类似的考虑枚举模数从 \(i\) 往下第一次选择取模是 \(j\)，那么有 \(f_{i}\times 2^{j - (i\bmod j) - 1}\to f_{i\bmod j}\)（因为 \((j, i\bmod j)\) 这一段的模数是随意执行的，所以带个 \(2\) 的次幂的系数）。
首先这个 \(2^{j - (i\bmod j) - 1}\) 可以拆成 \(2^j / 2^{i\bmod j + 1}\)，所以可以认为转移就是 \(f_i\times 2^j\to f_{i\bmod j}\)。
然后考虑把 \(i \bmod j\) 拆成 \(i - \lfloor i / j\rfloor j\)，这样的话根据整除分块的结论，会有 \(\mathcal{O}(\sqrt{i})\) 段 \([l, r]\)，满足内部的 \(j\) 的 \(\lfloor i / j\rfloor\) 都是相等的。
于是记 \(k = \lfloor i / l \rfloor\)，转移贡献到的下标是以 \(i - kl\) 为首项，\(-k\) 为公差的 \(\ge 0\) 的所有下标，贡献的值分别为 \(f_i 2^l, f_i 2^{l + 1}, \cdots\)。
考虑到 \(k = \lfloor i / j\rfloor \le \lfloor n / j\rfloor < \lfloor n / (i\bmod j)\rfloor\)，这说明对于下标 \(i'\) 来说可能对其产生贡献的下标等差数列的公差一定是在 \([- \lfloor n / i'\rfloor, -1]\) 间的，也就只有 \(\lfloor n / i'\rfloor\) 种公差要考虑。
所以总共要考虑的公差是 \(\mathcal{O}(n\ln n)\) 级别的。
对于 \(2^l, 2^{l + 1}, \cdots\) 的系数，会发现其实就是等差数列每往下递推一次系数 \(\times 2\)。
时间复杂度瓶颈在整除分块，\(\mathcal{O}(n\sqrt n)\)。
submission。
I. VIP Coupon
\(b_j \ge c_j\) 的优惠券一定是没用的，因为不如直接买。
接下来考虑把商品 \(a_i\) 看作是一个 \(b_i = a_i, c_i = 0\) 且强制要求购买的优惠券。
假设现在已经知道了要使用的优惠券，考虑怎么算答案。
首先把商品对应的优惠券加入一起考虑，然后贪心的考虑，对于优惠券一定尽量想让 \(c_j\) 能被减完，所以把 \(b_j, c_j\) 分别拉出来从小到大排序，然后依次匹配产生 \(\max(b_j - c_j, 0)\) 的代价。
会发现这其实就是根据 \(b_j, c_j\) 匹配关系连边连出了若干个环，若环中存在商品对应的优惠券则就对应着购买这个商品的优惠券选取路径，若环中不存在商品则代价一定为 \(0\)（可以反证排序后的关系）。
于是会发现直接把所有 \(b_j < c_j\) 的优惠券都放进来算算出来的就是答案。
时间复杂度 \(\mathcal{O}((n + m)\log (n + m))\)。
submission。
J. Would You Make a Convex?
极端情况就是 \(3\) 条边的情况，所以判断集合是否合法只需要判断最小值 \(+\) 次小值 \(\le\) 最大值。
然后根据调整法，选中的集合一定是排完序后的一段区间，因为如果不是一段区间找到那个断点让左边的部分都往右移一定不劣。
于是可以固定 \(r\) 找最远的 \(l\)，双指针即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
submission。
K. XOR and LCA
感觉很巧妙啊。
首先 \(u, v, w = u\oplus v\) 的 \(\operatorname{lca}_w(u, v)\) 其实就是满足 \(u, v, w\) 分别在不同子树中的点 \(p\)（特殊的，单独的点 \(p\) 也被认为是 \(p\) 的子树）。
因此可以知道 \(\operatorname{lca}_w(u, v) = \operatorname{lca}_u(w, v) = \operatorname{lca}_v(u, w) = p\)，又因为求的答案是 \(\oplus\) 有抵消的性质，只需要能够在 \(p\) 处能够抵消出 \(p\) 而其他点都抵消出 \(0\) 即可。
会发现把 \(p\) 两两子树内的点对匹配即可，若 \(u, v, w\) 各自在不同的子树会算 \(3\) 次，若 \(u, v, w\) 在相同的子树则会算 \(0\) 次，若有两个点在相同的子树会算 \(2\) 次，抵消后只有在不同的子树会被算入了。
需要特殊注意 \(u = 0, v = w\) 的时候被错误抵消了，因为 \(v = w\) 所以永远不可能被抵消出 \(v\) 这个点，而实际上是应该计算的。
时间复杂度 \(\mathcal{O}(2^n)\)。
submission。
L & M. Yesterday Once More
😂。
手玩了一会把自己玩晕了。
对着手玩一会感受一下，答案大概就是把几个串复制 \(n\) 次后拼接在一起。
并且自己可以写一个 \(\mathcal{O}(n! \times |ans|)\) 的 checker 判断正确性，且 hard ver. 已经明示了或许是存在基础串长和 \(\le 10\) 的方法的。
于是考虑直接写个搜把这个结构搜出来，判断合法性时可以让 \(n\) 从 \(2\) 不断增大（因为 checker 的耗时随着 \(n\) 增大会大很多），若到 \(6\) 也合法就认为是对的构造。
本机跑了 1.5min 就跑出来了一组解。
代码里面也有具体搜索和 checker 的实现。
submission。
N. Zebra Crossing
写题解的时候发现自己写挂了，hack 一下发现 std 也挂了，难绷。
跳跃不太好考虑，把问题转换成存在一个体力值 \(x\) 表示还能继续走的距离，这样就可以把问题转为在树上行走同时维护这个 \(x\)。
具体来说，每走一步 \(x\gets x - 1\)，若 \(x = -1\) 则说明必须要跳一次，贪心的肯定是跳到上一个节点，令 \(ans\gets ans + 1, x\gets k - 1\)，每次遇到白点时便可以重置体力值，\(x\gets k\)。
会发现 \(1\to x\) 的路径一定是基本按照树上路径走的，唯一走出去可能是为了在外部重置体力值。
于是考虑先 dfs 一次对每个点 \(u\) 求出从 \(u\) 到子树内白点的最小距离 \(f_u\)。
接下来求解答案时就可以按照主路径 dfs，然后再来考虑往外走的贡献。
具体来说，维护走到 \(u\) 时的 \(x\)，还是同样的往下走一条边则 \(x\gets x - 1\)，若 \(x = -1\) 则 \(ans\gets ans + 1, x\gets k - 1\)。
唯一不同的是此时可以往外走，也就是若 \(x\ge f_u\) 时，可以走到最近的白点再走回来，所以有 \(x\gets \max(x, k - f_u)\)。
注意终点的贡献并不应该算入主路径的 \(ans\)。
时间复杂度 \(\mathcal{O}(n)\)。
submission。