T1 BS5463【NOI2018模拟7】xiz

考场A了，猜的结论。

求出每个位置上一个和他相同的数的距离，进行 KMP。但是每个数在 \(B\) 中第一次出现的位置不好处理，就猜了个结论——KMP 的两个循环中相等的判断方式相同就可以了（至今不知道是否一定是这样），改动一下两个数相等的判断就完了。

T2 BS5471【NOI2018模拟9】path

考场打的最高档部分分，正解需要一个之前没接触过的知识。

由题目中限制可知原图是一个平面图。平面图上最短路等于其对偶图的最小割。然后将颜色限制加入，对每种颜色建一个虚点，从对偶图上的每个点向其覆盖区间中其儿子（对偶图可以看作一棵树的形式）没有覆盖到的点的颜色的虚点连 \(INF\) 双向边，最后求对偶图最小割即可。

考场打的最高档部分分，想出了正解但是清楚地知道时间不够，调不出来。

每个数取对数，将相乘转为求和。最初对每个点建权值线段树，排序就先将两端不完整的线段树分裂，区间内线段树合并。再开一个大的线段树维护每个权值线段树，求和。