CTS2024

Day1 T1 水镜

WC 赛时做法

考虑对于相邻的两个位置 \(i\) 和 \(i+1\)，他们之间的连通性可以用一个 \(2\times 2\) 的矩阵描述，即 \(i\) 对应的两个位置是否和 \(i+1\) 对应的位置可以连接。

发现这个 \(2\times 2\) 的矩阵只会变化一次，且变化的时刻就是 \(\dfrac{h_i+h_{i+1}}{2}\) 的时刻，那么总共变化的时刻也只有 \(O(n)\) 次。

我们在初始的时候和每一次修改一个位置的时候，可以使用线段树上二分向左右拓展，看能够拓展到哪里，每一次会得到 \(O(1)\) 个极长的区间。

把这所有 \(O(n)\) 的区间包含的区间数统计出来即可。时间复杂度 \(O(n\log n)\)。

题解做法

记 \(p_i=\max(h_i,2L-h_i)\)，发现如果段区间 \([l,r]\) 合法，说明 \(p\) 的结构形如 \(p_l>p_{l-1}>\dots>p_{k-1} ? p_{k}<\dots p_{r-1}<p_r\) 的单谷结构。

发现存在这个结构就等价于不存在 \(p_{i-1}\le p_i\ge p_{i+1}\)，考虑对于 \(h_{i-1},h_i,h_{i+1}\) 之间的大小关系讨论，可以得到 \(L\) 不能属于的区间：

每一种情况都对应着值域的一个前缀或者后缀，那么一个区间 \([l,r]\) 不能取的 \(L\) 的集合是一个 \((-\infty,L]\cup [R,+\infty)\) 的结构，可以直接维护 \(L\) 和 \(R\)。

我们要统计所有满足条件的区间的数量，考虑双指针，但是发现双指针不好维护删除。所以考虑使用 baka's trick 可以做不删除扫描线，时间复杂度 \(O(n)\)。

Day1 T2 线段树

发现线段树等价于一组三角剖分，而一个区间 \([l,r)\) 的值已知就是在 \(l\) 和 \(r\) 之间连接一条边。如果区间 \([L,R)\) 可以被表示，等价于 \(L\) 和 \(R\) 之间联通。

由此我们可以根据连通性设计 DP。

记 \(f_{i,j}\) 被线段树 \(i\) 节点（对应区间 \([l,r)\)），其中和 \(l\) 联通的编号最大的点为 \(j\) 的方案数；\(g_i\) 为线段树 \(i\) 节点，只考虑下面的边，\(l\) 和 \(r\) 联通的方案数

通过枚举 \([l,r)\) 是否连接，可以得到如下 DP：

• \(2g_{ls}g_{rs}\to g_i\)
• \(g_{ls}f_{rs,j}\to g_i,g_{ls}f_{rs,j}\to f_{i,j}\)
• \(f_{ls,j}g_{rs}\to g_i,f_{ls,j}g_{rs}\to f_{i,j}\)
• \(f_{ls,j}f_{rs,k}\to g_i,f_{ls,j}f_{rs,k}\to f_{i,j}\)

但是在第四种转移中 \((j,k]\) 这一段不和外界联通，这也就意味着题目中要求联通的所有区间都需要满足和 \((j,k]\) 要么包含，要么不交。

考虑使用异或哈希来检验，将下标在 \([L+1,R]\) 的所有数异或上一个随机值 \(val\)，如果 \(j\) 和 \(k\) 处的权值 \(V_j=V_k\)，我们才能够合并。

由于需要将 \(V\) 相同的 DP 值合并，所以可以使用线段树合并来维护，时间复杂度 \(O(n\log V)\)。

Day1 T3 众生之门

通过打表发现，在 \(n\) 较大，且他的结构不是菊花的时候，答案基本都是 \(0\) 或 \(1\)，而我们可以证明答案的奇偶性，也就可以大胆猜测，答案就是 \(0\) 或者 \(1\)。

所以考虑特判掉这两种情况，然后其他的情况直接随机交换检验。

考虑正确性，我们可以认为答案在 \(0\) 到 \(O(n)\) 中随机分布，那么我们期望检验 \(O(n)\) 个就可以得到一个 \(0\) 或者 \(1\) 的结果了。

Day2 T1 多方计算

考虑一个比较直接的做法：在第一次传输的时候，第 \(0\) 个人将最低位传给第 \(1\) 个人，第一个人将这一位加在自己的数上。第二次传输的时候，第 \(0\) 个人传第二位，第 \(1\) 个人传最低位。

这样最终得到的数会是一个 \(m+\log n\) 位的数，由于最后一个人收到有 \(n\) 个时刻的延时，所以需要的时刻数为 \(n+m+\log n\)。

发现在前面的时刻，后面很多的人都没有操作，所以我们可以让后面的人在这个空闲的时候也处理一些运算，比如将后面的一部分的最后几位提前加上。

原本第 \(i\) 个人在第 \(r\) 轮要传递信息是第 \(r-i-1\) 位，如果 \(r-i-1<0\)，我们就然他传递第 \(r-i-1+m+\log n\) 位，发现这样我们第一轮传递的数的位数变成了 \(m+\log\log n\)，只需要 \(n+m+\log\log n\)，大概是 \(n+m+4\) 次传递即可。

发现距离满分差 \(1\)。既然我们可以加一轮，那么也可以加两轮，所以通过调参之后再加一轮，变成三轮加法即可。

Day2 T2 投票游戏

我们需要想一个方法快速比较两个人谁先被票出去。发现如果有一个人被票出，那么所有人的票数都不会增加，那么如果我们记录每一个人被票出的时候他的票数 \(f_i\)，那么我们就可以确定那个人先被票了。

发现一个人的状态之和他的所有儿子有关，假设我们确定了当前点 \(u\) 的所有儿子的票数 \(f_i\)。将其从大到小排序，就是儿子被票出的顺序。记第 \(1\) 到 \(i\) 个儿子的 \(b\) 值之和为 \(sum_i\)，那么这个人被票出的时刻就是找到最小的 \(j\)，使得的 \(a_u+\sum\limits_{v\in son_u} b_v-sum_{j-1}>f_j\)，那么 \(i\) 最终的票数就是 \(a_u+\sum\limits_{v\in son_u} b_v-sum_{j-1}\)，信息等价于找到第一个 \(a_u+\sum\limits_{v\in son_u}b_b>f_j+sum_{j-1}\) 的位置。使用平衡树维护所有儿子的顺序，同时维护 \(\min\{f_j+sum_{j-1}\}\) 就可以二分找到该位置。

这样做时间复杂度是 \(O(n\log n+qD\log n)\) 的，其中 \(D\) 为树的深度。瓶颈在修改，考虑使用树链剖分优化。

那么我们只用平衡树维护轻儿子，将重儿子 \(bs\) 单独拿出来讨论：我们将 \(a_u+\sum\limits_{v\in son_u}b_v\) 扔进平衡树中二分，记得到的答案为 \(ans\)。如果 \(f_{bs}<ans\) 说明重儿子不会影响到该节点被票出时的票数；否则，说明 \(bs\) 必然在 \(u\) 之前票出，票数也就会是 \(a_u+\sum\limits_{v\in son_u}b_v-b_{bs}\) 的答案。

发现当前节点的票数关于重儿子的答案，是一个分两段的常函数，可以直接维护。

发现这样每一次修改只会变化 \(O(\log n)\) 个平衡树，这样复杂度就是 \(O(n\log^2n)\) 的。

Day2 T3 字符串游戏

将字符串反转，记 \(occ(l,r)\) 为 \(S[l,r]\) 在 \(S[1,r]\) 中的出现次数。记 \(f_i\) 在字符串 \(S[1,i]\) 的答案，我们容易得到 DP：\(f_r=\max\limits_{1\le l\le r}(occ(l,r)-f_l)\)。

对于 \(l_1<l_2\)，有 \(occ(l_1,r)\le occ(l_2,r)\)，则如果 \(f_{l_1}\ge f_{l_2}\)，那么 \(l_1\) 处转移必然不优于 \(l_2\)，这也就意味着，可能转移的决策点可以用一个单调栈维护，每一次压入 \(f_i\)，将所有 \(f_j>f_i\) 弹出。

但是单调栈的大小仍然可能是 \(O(n)\) 量级的，没有对复杂度有实质上的优化。

考虑再发现一点性质。

对于 \(f_p<f_i\) 我们假设 \(i\) 的决策点为 \(q<p\)，不难发现，\(f_p\ge occ(q+1,p)-f_q\ge occ(q+1,i)-f_q=f_i\)，这与 \(f_p<f_i\) 矛盾，说明我们从单调栈的栈顶转移到 \(f_i\)，如果当前栈顶 \(p\) 有 \(f_p<f_i\)，那么后面的转移都不需要考虑了；否则意味着 \(f_p\ge f_i\)，\(p\) 需要从单调栈中弹出。

这样转移的次数就被减少到了 \(O(n)\) 次，加上计算 \(occ(l,r)\) 需要后缀树上倍增定位位置，最终复杂度为 \(O(n\log n)\)。