一些想法
T1 感觉是一道很有意思的题，不过没下发 checker 确实有点慌，我反正是没写 checker 肉眼查了几组小数据就不管了。 听说一堆人没有拿到 25 分怀疑部分分设置问题，我也不知道是不是真的，如果是真的那确实不应该。
T2 么，送分好像是送出去了，但是赛时由于环境差异会让人觉得很卡常也是事实。 不过如果是线下本机评测的话应该会好很多。 本来以为 lxl 会有什么高妙做法，结果最后也只有根号和两 log。
T3 似乎槽点很多。 首先这个分值分布感觉不太合理，随便写就有 80 的样子。 然后是关于交互的。首先出题人纯 c 的接口我觉得是合理的，毕竟实际中大部分为了通用性一般都是 c 风格的。 然后就是返回字符串的 zero terminate，听到不少人都是因为这个挂了的。这种东西虽然属于常识，但事实上 OI 群体中的大部分人都是不知道或没有这个意识的。 虽然这肯定算是选手的问题，但是这样大规模的不合理区分总觉得不太好，出题人只要题面里简单提一句就不会这样。 我个人的观点是这种知识（包括ubsan，valgrind 等工具的使用还有一些底层的知识）在 OI 中是不应被忽略的，如果这次 WC 能让更多的 OIer 认识到这点那也算不错。
总的来说作为一场成绩没什么用的比赛还是挺好的，比什么摆烂之星不知道高到哪里去了。
题目
A 序列变换
你需要通过如下操作将括号序列 s 变为等长的括号序列 t。
p(((A)B)C)q -> p((A)B)(C)qp((A)(B)C)q -> p((A)B)(C)qp(A)((B)C)q -> p((A)B)(C)qp(A)(B)(C)q -> p((A)B)(C)qpq -> p()qp()q -> pq
其中 A B C 均为合法括号序列。后两种操作每种最多用 2 次。假设 s 和 t 的长度均为 $2n$，要求总步数不超过 $3n$。
出题人的做法比较 tricky 且不方便求操作位置。这里写一下我的做法。
对于这种 s 到 t 的题目，一般的想法是选一个结构简单的 r，构造 s -> r -> t。 此题中 r 取等长的 ()()... ，也就是先拍平再重建。
首先是拍平。为了保证复杂度肯定是从外往里拆。先看一操作，一操作实际上是让最外层的括号把第一个子括号序列吐出去，但要求这个子括号序列长度至少为 4。 在看第二个操作。这个操作相当于吐出两个，然后第一个再把第二个给吃掉。然后就可以往两边递归下去。
做完这些操作以后只会剩下若干个 () 和 (()) 。 接着考虑使用 3 操作。那么一个 ()(()) 就会变成 (())() ，相当于把套了两层的括号往前移。 如果遇上了 (())(()) ，那么就会变成 ((()))() ，再使用一次一操作，相当于干掉了一个 (()) 。
此时只有可能剩下 (())()()... ，也就是说套了两层的只会出现在第一个。此时分别用一次 5 6 操作即可完成展平。
重建是比较方便的。4 操作相当于第二个括号把第一个括号给吃进去，并且要求后面非空。 那么可以先用 5 操作往最后加上一个，按照后续遍历建出整个括号序列再把那个多的删掉。
分析一波复杂度。1 2 4 操作都对应着括号树上加边于删边，所以这三个操作总数不会超过 $2n-2$。 然后是操作 3，不难发现它最多只会发生 $n-2$ 次。 算上 2 次 5 6 操作，$3n$ 步正好。
然后是一些实现细节上的问题。直接模拟上述过程的话，涉及括号序列的整体平移，不方便实现。 考虑对原序列进行 hack，即需要平移的时候不平移，保持大体不变只做 O(1) 的修改，在记录操作的时候加上偏移量。
时间复杂度 $O(n)$ 。
B 秃子酋长
和去年暑假毛营 D7 一模一样，但估计只是撞了。
两个做法，根号或者俩 log，都能过但都要卡常。
根号的做法较为简单。使用回滚莫队，只删除不插入，那么就可以通过链表维护相邻的值。
俩 log 的做法常数较大，可能还跑不过根号，我被卡成了 95 分。 加入我们把询问的区间从某个位置劈开，那么可以分别计算左右两边的贡献。 以左边为例，左边的两个值相邻的数，如果右边没有数在这两个数中间，那么这两个数的贡献就是这两个数位置差的绝对值。 如果右边有数，那么这两个数的贡献就是两个位置到劈开位置距离的和。 那么只要对于左边所有相邻的数，求出右侧最靠左满足值在这两个数之间的位置，在这个位置上记录第二种贡献减去第一种贡献的差，每次询问就是求前缀和。 套上一个 cdq 即可。
C 猜词
一个乱搞题。
出题人给的做法是直接 dp 求出每个时刻的最优决策，然后用一些启发式的方法优化 dp 复杂度 常数。毕竟 $2^{5 \times 26}$ 次方也是常数。
然后说一些不用 dp 获得高分的方法。朴素的做法是每次在还有可能的集合中随机抽取一个，但是这样不优。 在前几次的时候，哪怕已经够确定这个位置的字母，我们也可以天别的字母来获得更多的信息。 比如第一次猜词就中的概率可以忽略不计，所以第一次猜词的时候就没必要把首字母填对。
还有一些结合信息量的做法，即选取单词的时候选期望获得信息量最大的那个，应该可以获得 98 分。
