AGC 的题

AGC025 D Choosing Points

对于一个，我们把距离为的点连边。考虑证明这是一个二分图。

如果是奇数，那么显然，做一个黑白染色即可。

如果是偶数，就把图旋转 45 度，变成两个错开的图，把单位设为，即把距离除以。那么相当于除以 2。由于这两个错开的图互不相关（因为两个图之间的点距离为奇数），因此递归下去直到为奇数，就完成了证明。

那么我们对每个点开一个 pair，分别记录两个距离下的颜色。根据抽屉原理，一定存在一个 pair 的出现次数大于。那么就求出答案了。

时间复杂度。

代码

AGC024 F Simple Subsequence Problem

定义标记表示的子序列集合。考虑构建一个子序列自动机。设二元组状态表示，那么我们找到中 0 和 1 第一次出现的位置，可以贪心地转移到和。其中和分别是去掉第一个 0 的前缀、去掉第一个 1 的前缀得到的字符串。这样建出来的是一个 DAG。

于是我们设表示长度为的字符串，以第位为分界，右边是中括号的走到这个状态的方案数。显然，把所有的 DP 值设成 1，然后在 DAG 上转移一下，那么就可以得到是多少个串的子序列了，即的 DP 值。

时间复杂度。

代码

AGC026 D Histogram Coloring

注意到，如果第一列里有两个相邻同色方格，那么第二列之后的一定只有一种填色方法。而如果第一列是红蓝交错，那么第二列就有两种填色方法，之后同理。

因此我们考虑一个类似删行的思路。设表示只考虑区间的高度大于等于的部分（即把高度减掉），填色的方案数。表示无限制，而表示最底下的一行必须红蓝交错。

转移的时候枚举第一列下两行的方格是否同色，那么可以得到

在边界情况（比如第一列的高度为 1）的时候可以缩短区间的长度，如果中间的有一个高度为 1 的，那么分两边求，然后乘起来即可。

由于不同的高度差只有种，因此对于高度相同的一段可以矩乘优化。这样就做完了，但是难写。

另一个做法是考虑横着做。设表示考虑前列，其中后列的最底下一行是一段极长的红蓝交错段，这样的方案数。

转移的时候，考虑内有几个完整的以结尾的极长段，假设有个。

每一段都有两种填色方案，因此有。

另一方面，考虑的情况。这时和同色，由于上面部分的颜色我们还未确定，因此我们强制同色后可以直接枚举的和，再乘上来转移。

时间复杂度，可以预处理。

代码

AGC026 E Synchronized Subsequence

我们考虑将序列分成若干个 a,b 个数相等的段。对每一段分别考虑。

如果这一段的第一个字符是 a，那么我们可以贪心地选择最长的形如ababab的串。

如果第一个字符是 b，那么假设我们选了一对 (b,a)，那么我们选择这一对 ba 的下一对一定不会变劣。因此我们枚举一个后缀 pair 的方案，取字典序最大即可。

对于每一段的最优解，显然我们是要么选要么不选。因此倒着取最优即可。

时间复杂度。

代码

AGC025 E Walking on a Tree

首先猜结论：限制都可以达到。

考虑我们用归纳法证明这个结论。对于一个叶子结点，如果经过它的边数小于 2，我们显然可以直接删掉这个点。因为它的贡献一定是 1。如果有大于等于 2 条边经过它，那我们就随便选两条边，假设为，那么我们把删掉，加入一个进去，把路径交上的限制都减 2，然后删掉这个 u 即可。这样我们就归约到了一个更小的问题。因此根据数学归纳法，就证明了这个结论。

难点在于方案的构造。思考可以发现，上述过程实际上是规定了这两条边的方向状态。两条边中要改变一条的方向，或者说两条边要么都不改变，要么同时改变。因此我们想办法这些规定建成一个图，然后做一个类似染色的事情即可。

具体地，我们类似删叶子的过程，我们在 DFS 的过程中先建立子树的规定，然后考虑当前 u 的父边的限制。如果限制小于 2 就不用管了。否则我们需要找到两条不冲突的边来规定状态。

如果是子树延伸上的两条边，我们显然可以选。因对于这组边，为我们建立的规定始终是一样的，不会冲突。

否则，我们可以选择两个不同子树的边。两个不同子树的边是互不相关的，因此也可以选。

选完了就规定一下状态，然后记录一下当前结点有没有选，选了哪两条边，然后回溯即可。

时间复杂度。

代码