质量很高的一场省赛。
比赛链接。
没有代码的题是队友写的。
I Essentially Different Suffixes
字典树板子题。
把每个串的所有后缀加入字典树，答案就是字典树的边数。
时间复杂度 \(O(\sum S_i)\)。
F Inversion Pairs
注意到填的形式一定是一段 \(1\) 一段 \(0\)，因为如果有 \(0\) 在 \(1\) 前面交换一下肯定更优。
枚举分界点统计答案即可。
时间复杂度 \(O(n)\)。
H Hututu
计 \(S=\text{max}(|X-x|,|Y-y|)\)。
当 \(S \leq 2\) 时枚举，否则答案就是 \(\lceil \frac{S}{2} \rceil\)。
时间复杂度 \(O(1)\)。
（注：官方题解的讨论是不是写错了，应该是上取整）。
A Minimum Product
通过分析值域范围可以设计状态 \(dp_{u,S}\) 表示在节点 \(u\) 且 \(\sum a_i=S\) 的状态下最小的 \(\sum b_i\)。
先枚举 \(S\)，再按照边的顺序更新即可。
AC记录。
时间复杂度 \(O(200nm)\)。
J Sichuan Provincial Contest
比较常规的树形 \(dp\)，
设 \(f_{u,i}\) 表示从下到上到 \(u\) 匹配前 \(i\) 个字符的方案数，
\(g_{u,i}\) 表示由 \(u\) 从上到下匹配后 \(i\) 个字符的方案数。
转移即可，在合并子树的时候统计答案，答案即是 \(\sum \limits_{u=1}^n \sum \limits_{i=0}^3 f_{u,i} \times g_{v,3-i} + f_{v,i} \times g_{u,3-i}\)。
AC记录。
K Point Divide and Conquer
比较不错的题。
正着做太困难，考虑反着。
此时相当于将若干棵子树合并，并将根设为 \(x\)。
并查集即可。
AC记录。
C Optimal Time
有点神秘，但可以猜到。
如果设 \(dp_x\) 是 \(x\) 走到 \(0\) 的期望时间，
那么 \(dp_x = \text{min}(dp_{x-1}, \frac{1}{|S(x)|}\sum \limits_{y \in S(x)} dp_y)+1\)。
这个东西是有环的，没法直接 \(dp\)。
但是可以初始让 \(dp_x \rightarrow x\)，然后跑若干轮，猜测这个值会收敛。
为什么会收敛？不知道。题解告诉我们约 100 轮就会收敛。
AC记录。
B Ternary
需要无比深刻观察的题目。
交互次数很少，意味着我们没有太多的切入点，因为运算始终是在映射的状态下，唯一能用到的只有相等这个信息。
观察三进制下的加法：
在无进位的情况下：
\(0+1=1\)
\(0+2=2\)
\(1+2=0\)（进位）
第一种和第二种情况都有数相等，可以确定 \(0\) 的位置。依据排除法，也可以确定第三种情况 \(0\) 的位置。
同时只有第三种情况会导致进位，可以判断这一位是否产生了进位。
有进位的情况下类似，可以确定 \(2\) 的位置以及是否继续进位。
以上的信息可以通过交互一次获得（交互 \(00...0\) 和 \(11...1\)）。
每一位还剩下两个数没有确定，比起第一次我们多掌握了一个数的信息。
如果这一位还需确定的是 \(1,2\)，比较棘手的是判断进位的情况：
\(0+1+1=02\)，
\(0+2+2=11\)，
\(1+1+1=10\),
\(1+2+2=12\)，
可以发现，第三第四种情况是可以通过已有信息推断出来的，而这正好是这一位有上一位产生的进位的两种情况。
换言之，如果这一位不是第三第四种情况，那么一定没有上一位来的进位。因此能推断出这一位有没有上一位产生的进位。
而情况一和二正好是（不）产生进位的两种情况，只要根据下一位有没有受到进位，就可以区分出。
还需确定的位为 \(0,1\) 时同理，读者自行推导。
所以再交互一次两个一样的数就得出了答案（每一位取一个还未确定答案的）。
AC记录。
L abc
神题。
\(\text{max}(a,b,c) - \text{min}(a,b,c)=\frac{|a-b|+|a-c|+|b-c|}{2}\)。（当然这个的最小值可以为 \(0\)）。
先把这个值算出来，再补充少算的贡献。
对于有两种字符的区间，需要计算出 \(\sum \text{max}\) 和 \(\sum \text{min}\)。
\(\sum \text{max}+\text{min}\) 就是所有子区间的长度和, \(\sum \text{max}-\text{min}\) 按照和三个数一样的转化方法计算就可以。
贡献已经算上了 \(\sum \text{max}\)，减去 \(\sum \text{min}\) 即可。
对于只有一种字符的区间，多算的是所有子区间的长度和，减去即可。
AC记录。