AtCoder Grand Contests 杂做

感觉 AGC003 及以前的题做了大部分，所以从 AGC004 开始，选一些我觉得合适的题做。

AGC004E - *3200

一直在往静态的几何（或者代数）限制想，结果没想到可以动态规划。

为了更加直观可以看作出口在移动，然后到过的点加分，某些出界的点就被 ban 掉了。我们可以直接考虑定义 \(f_{l,r,u,d}\) 表示往四个方向扩展的最大距离的最大分数。很容易发现只记录四个方向的最大距离就可以表示了。转移也很简单，尝试往四个方向扩展一个单位距离就可以了。时间复杂度是 \(\mathcal O(n^2m^2)\) 的。

AGC005D - *2900

简单题，容斥一下，发现可以根据模 \(k\) 的值分类进行动态规划，记录一下相邻位置选的状态即可。时间复杂度是 \(\mathcal O(n^2)\) 的。

AGC005E - *3300

博弈还是会不了一点啊。考虑如果先手在一条边上来回晃荡，而在蓝树上这条边的两个点的距离大于 \(2\)，那么游戏将会永远进行下去。同时就可以知道在到达这样的局面之前走的每一条边在蓝树上距离只能是 \(1\) 或 \(2\)。两棵树分别以起点建有根树，就可以知道哪些点是先手不可能去到的，就在剩下的点里去看，做法也很单一。时间复杂度是线性的，只需要遍历两棵树就可以了。感觉还是很神奇。

AGC005F - *3400

其实是简单题，难点是不是在于识别出模数是 NTT 模数？我们可以拆贡献，每个点有很显然的容斥。答案就可以写成 \(\sum\limits_{x=1}^n a_x\dbinom{x}{i}\)，其中 \(a\) 数组也是容易得到的。故时间复杂度就是 \(\mathcal O(n)\) 次多项式做 NTT 的复杂度。

AGC006C - *3000

我们很容易推出单次操作后 \(E(x)\) 的变化，即 \(E(x)=E(x-1)+E(x+1)-E(x)\)，但是这似乎并不是特别好做。但是由方差（虽然这题还没补），我们可以知道这个变化，实际就是交换 \(x\) 和 \(x+1\) 的差分数组。然后就是求 \(k\) 轮操作过后某个点的差分被交换到了哪里。暴力求出单轮操作的结果后，倍增求即可。时间复杂度是 \(\mathcal O(n\log k)\) 的。但是实际上就是若干个置换环，所以可以直接线性。

AGC006D - *3100

见过二分的 trick 就很简单了。手玩发现长度不为 \(1\) 的连续颜色段可以一直保留，并往两边的的单独段扩展。那么过程分析得很简单了，直接模拟即可。时间复杂度是 \(\mathcal O(n\log n)\) 的。

AGC006E - *3100

可以抽象为 \(n\) 个数，每个数有黑白两种的情况。判掉一些不合法的情况。我们发现，把数字（不包括颜色）归位后，对于奇数或偶数位置，颜色异常的位置只能有偶数个。然后我们对于任意排列要交换若干次变成有序的，就要经历逆序对次，这会对另一种奇偶性颜色异常的位置奇偶性造成改变。所以还要知道奇偶位置的逆序对数的奇偶性。这可以树状数组。更厉害的方法是将逆序对数与置换环联系起来，这样就是 \(\mathcal O(n)\) 的了。

AGC006F - *3500

感觉还是对我来说有一点困难了。我们考虑把点 \((x,y)\) 转化为 \(x\) 向 \(y\) 连的一条边。对一个弱连通块，我们考虑对其染色，红连向蓝，蓝连向绿，绿连向红。如果能够完成染色，再讨论：如果不足 \(3\) 种颜色，则不会有任何额外的边，否则任何红连蓝，蓝连绿，绿连红的边都是可以得到的。如果不能完成染色，则可以证明任意两点之间的边都能得到。则可以线性简单解决这个问题。

AGC007C - *3400

会不了一点，并且感觉考不了一点。最后式子很好算，有点抽象。关键点在于考虑一个点进洞后每个点的位置期望还是等差数列。

AGC007D - *2800

很简单，考虑从走的路线一定是分成若干段，每一段形如“右，左，（等待），右”，直接分类讨论简单动态规划就可以了。我写的 \(\mathcal O(n\log n)\) 的做法，不知道有没有线性的写法。

AGC007E - *3900

套路考虑二分，显然是探完一个子树再探另一个。那么我们就可以记录 \(f_{x,y}\) 表示从子树内深度为 \(x\) 的某个点开始，以某个深度为 \(y\) 的点结尾可不可行，转移很简单。发现我们只需要对于每个 \(x\) 记录 \(g_x\) 满足 \(f_{x,y}=1\) 的最小 \(y\)。然后转移就可以用双指针来做。把每个点的所有状态暴力记录下来，并只保留成随 \(x\) 增加，\(g_x\) 减少的一部分。状态数是 \(\mathcal O(n\log n)\) 的，可以用树上启发式合并那一套证明。粗略实现是三只 log 的，把 sort 改成归并就是两只 log 的了。

AGC007F - *3600

我们考虑直观的贪心，就是假如已经钦定了每个点扩展到了哪个区间，我们就可以简单地贪心：从右往左，每个点挨着右边走，走到目标上面就垂直下去。这样这个就可以用双端队列之类的东西来维护了（维护拐点位置）。时间复杂度可以做到线性。

AGC008E - *3600

分类讨论情况很多。主要就是对每一个基环树分类讨论，然后把贡献拼起来。

AGC008F - *4000

考虑被重复计数的状态只保留 \(d\) 最小的那一个。经过分析可以推出每个点的 \(d\) 的取值范围是一个区间，可以用换根快速算出来。复杂度线性。

AGC009D - *3400

考虑是给每个点标号，然后相同标号的点之间必须存在比它标号大的点。可以考虑到答案是 \(\mathcal O(\log n)\) 级别的，所以可以直接用整数维护可选标号集合。然后遍历树的时候安排即可。

AGC009E - *3400

考虑转化题目中的计数方式，看成 \(k\) 叉树上的操作。那么可以发现会算重的方案只需要进位就能解决。然后就能看成简单的背包计数就好了。因为层数是 \((n+m-1)/(k-1)\) 所以时间复杂度没有问题。

AGC010D - *2800

一步步地分析应该就不难。考虑有 \(1\) 则很好判断。没有 \(1\) 也至少有一个奇数。若当前偶数数量为奇数个，那么显然你操作一个偶数使其变为奇数，除以的最大公约数肯定是奇数，故所有数的奇偶性不变。所以这种情况先手必胜。若有偶数个，则判断奇数数量，若大于一个则同上，先手必败。否则我们只能考虑操作唯一的奇数来造成可能的翻盘。这样所有数都会至少除以 \(2\)。递归地判断，复杂度是 \(\mathcal O(n\log V)\) 的。

AGC010E - *3900

感觉比较厉害的步骤挺多的，能够都想到的应该不多。首先我们假定先手把序列变成了 \(b\)，那么对于 \(i<j\) 并且 \(b_i\) 和 \(b_j\) 互质的情况连一条有向边。那么所有合法的最终序列就是所有合法的拓扑序。这一点还是比较直观的。而字典序最大就只需要用优先队列来跑拓扑排序。然后我们就只需要考虑先手应该怎么做了。贪心地考虑就是小的元素作为连通块的根往下递归。由于我们可以用 dfs 树来表示一整个图，所以时间复杂度是 \(\mathcal O(n^2)\) 的。