ARC/AGC 部分题解

· · 个人记录

持续更新中...

\operatorname{AGC020E}

暴力 dp，dp_{i,state} 表示长度为 i，状态为 state 的串的答案。暴力枚举最后一个循环节转移即可。可以证明有用状态数不超过 n^3+2^{\frac{n}{8}}。

\operatorname{AGC020F}

先将最长的线段拿出来破环为链。发现由于小数部分严格 <1，所以弥补不了整数部分的差距。只有整数部分相等时才会影响大小关系。因此可以将长度为 1 的一段等分为 n 份，O(n!) 枚举小数部分相对大小关系，并状压 dp。dp_{i,j,state} 表示当前考虑左端点为 i 覆盖到 j，状态为 state 的方案数。枚举最后一段转移即可。实现中压掉了 i。时间复杂度 O(n!2^nn^2c^2)。

\operatorname{AGC021F}

令 f_{i,j} 表示共 i 行，j 列，强制每一行都有黑格子的方案数。显然 Ans=\sum \binom{n}{i}f_{i,m}。考虑 dp_{i,j}\rightarrow dp_{i+k,j+1}。

可以用 NTT 优化，时间复杂度 O(nm\log n)。

\operatorname{AGC022E}

考虑把 0 作为分隔符，那么就用序列 a 表示分割出的每一段 1 的长度。

目标是将序列变为单独的 1。

操作 2,3,4,5 可以整合为 将 x 和 y 合并为 x+y-1(x+y\ge 1)。考虑 dp_{i,j,k} 表示前 i 个位置中当前这一段长度为 j，当前状态为 k 的答案。根据第 i 位的值转移即可，时间复杂度 O(n)。

\operatorname{AGC022F}

发现这个 x 非常巨大，所以只有每一个数前面的系数会影响答案。考虑每次操作连边 B\rightarrow A，形成一棵内向树。每一个点的贡献是 a_i2^{d_i}，其中 a_i\in\{1,-1\}，d_i 为深度。a_{rt}=(-1)^{son_{rt}}。设 v 是 u 第 t 个儿子，那么 a_v=(-1)^{son_v+t}a_u。强制让同一层所有奇点的 a_i 相同。如果存在不同的就剥掉一个儿子并给另一个偶点，显然不会影响答案。设 dp_{i,j} 表示当前共选了 i 个点，最后一层有 j 个奇点。转移时枚举往后新加入的一层的总点数 k，可知如果不进行修改，与当前奇点符号相同的点个数为 \dfrac{k-j}{2}。再枚举新加入的一层修改后与当前奇点符号相同的的点数 l，那么进行修改的点互相之间符号一定相同。可得新加入的一层有 |\dfrac{k-j}{2}-l| 个奇点，并且符号依然全部相同。而当前这一层的贡献为 \dfrac{1}{l!(k-l)!}。最后乘上 n! 即可。时间复杂度 O(n^4)。

\operatorname{AGC023D}

如果剩下的所有人都在 S 同一边，那么答案显然。

否则考虑最左边的和最右边的两组人，设为 x,y。如果 x<y 那么 y 一定比 x 先回家，那么我们可以认为 x 的最优策略就是跟着 y 投，那么将 x 合并到 y 上即可。反之亦然。最后按照题意模拟即可。时间复杂度 O(n)。

\operatorname{AGC023E}

设 a_i 的排名为 b_i，考虑一对 i,j 的贡献。

令 a_i'=a_{b_i},S=\prod (a_i-b_i+1)。

w_{i,j}=\dfrac{1}{2}S\dfrac{a_i-b_i}{a_j-b_j+1}\prod_{k=b_i+1}^{b_j-1}\dfrac{a'_k-k}{a'_k-k+1} w_{i,j}=S-\dfrac{1}{2}S\dfrac{a_i-b_i}{a_j-b_j+1}\prod_{k=b_i+1}^{b_j-1}\dfrac{a'_k-k}{a'_k-k+1}

考虑按照 b_j 按照从小到大顺序枚举 j。需要维护的操作是单点修改，全局乘，区间求和。可以使用线段树优化。时间复杂度 O(n\log n)。

\operatorname{AGC023F}

考虑倒着做。两个连通块 i,j，i 在前面的代价是 w_{i,1}w_{j,0}，j 在前面的代价是 w_{i,0}w_{j,1}。所以应该把 \dfrac{w_{i,0}}{w_{i,1}} 小的放在前面，贪心合并即可。

\operatorname{AGC024E}

发现每次相当于往上一个序列中添加一个数，为了避免重复计数，我们令每次添加的数严格大于当前位置的数。设 dp_{i,j} 表示长度为 i 的序列，用了 j 种数的方案数。枚举第一个最小值，那么它后面的数一定都在它之后被加入。再枚举这个值被加入的时间 l，可得：

dp_{i,j}=\sum_k\sum_ldp_{k-1,j-1}dp_{i-k,j}\binom{i-l}{i-k}

容易进行优化。时间复杂度 O(n^3)。

\operatorname{AGC025D}

对所有距离为 \sqrt{D} 的点两两连边。

综上，这是一张二分图。对 D_1,D_2 分别进行操作，得到的图是 G_1,G_2。那么把点按照在两张图所处左/右分为 4 类，显然至少有一类 \ge n^2 个，从这一类点中选任意 n^2 个即可构成答案。

\operatorname{AGC025E}

设第 i 条边被覆盖的次数为 w_i，那么显然上界为 \sum\min\{w_i,2\}。考虑构造一种方案使得达到上界。每次考虑一个叶子节点 u。

由于 n,m 都只有 2\times 10^3，所以暴力模拟即可。时间复杂度 O(n^2)。

\operatorname{AGC025E}

分两种情况讨论：

于是令 dp_i 表示第 i 对及之后的字典序最大的答案，利用刚才的讨论转移即可。时间复杂度 O(n^2)。

\operatorname{AGC027D}

强化条件，把“都相等”改为“都为1”。

对格子黑白染色，对每一条白对角线乘一个质数。最终每个白格子都是 p_1p_2 的形式，此时令每一个黑格子都是四周的白格子的 \operatorname{lcm}+1。此时可能会超过 10^{15}，随机调整即可。

\operatorname{AGC027E}

显然最终的每一个字符都是一个区间，令 a =1，b =2，那么无论如何操作 \mod 3 都不变。如果一段区间 ab 交替，那么肯定不能动。否则容易归纳证明一定可以变为单独的一个字母。考虑构造一个固定的串的贪心策略，对于每一个 i 预处理出 posA_i,posB_i，表示从 i+1 开始第一个可以合并成 a 或 b 的段的右端点。最后可能剩下一段和为 0 的，我们强制它被合并进最后一段。所以令 dp_i 表示前 i 个字符的答案，dp_i\rightarrow dp_{posA_i},dp_{posB_i} 即可，时间复杂度 O(n)。

\operatorname{AGC027F}

如果存在某一个点没有被操作过，那么将这个点作为根。此时我们可以得到一些约束：

第一个条件直接判断，第二个条件建图判断是否有环即可。

如果所有点都被操作过，那么直接枚举第一次操作，转换为前一种情况。时间复杂度 O(Tn^3)。

\operatorname{AGC028C}

先将 \min\{a_u,b_v\} 转化为在 a_u,b_v 中取恰好一个。那么根据 a_u,b_u 的取舍情况可以对于 u 确定一个状态。00,01,10,11 之间有如下限制：

显然 00 与 11 一样多。那么如果有至少一个 00，就可以构造出 00\rightarrow (01)\rightarrow 11\rightarrow (10)\rightarrow (00\rightarrow 11) 这样的回路满足条件。否则一定不存在合法方案。将 a 和 b 合在一起排序，得到 c。贪心取 c_{1\cdots n}，如果当前已经合法就退出，否则用 c_{n+1} 代替 c_n。如果当前已经合法就退出，否则 c_n 和 c_{n+1} 一定属于同一个 u。再调整一步，用 c_{n+2} 代替 c_{n+1} 或用 c_n 代替 c_{n-1}。此时一定合法，两者中取小的即可。时间复杂度 O(n\log n)。

\operatorname{AGC028D}

考虑计算每一个连通块对答案的贡献，显然每一个连通块对应环上一段区间，区间内的点不能向区间外连边。设 f_{i,j} 表示 [i,j] 这一段区间所代表的连通块的贡献，g_i 表示 i 个未定点任意连边的方案数，h_{i,j} 表示 [i,j] 中未定点的个数。容斥可得：

f_{i,j}=g_{h_{i,j}}-\sum\limits_{k\in[i,j)}f_{i,k}g_{h_{k+1,j}} Ans=\sum f_{i,j}g_{n-2k-h_{i,j}}

暴力计算即可。时间复杂度 O(n^3)。

\operatorname{AGC028E}

首先字典序最小可以使用贪心逐位确定。接下来我们的问题就转化成了判断每一位是否可以填 0。把一个数称为好的当且仅当它是 p 中的前缀最大值。是否存在合法序列比较不好判断，我们可以增加限制：两个序列之一中的前缀最大值全部都是好的。如果不满足限制，就把序列中不好的的数交换，交换后这两个数一定会变为 好的，重复此操作即可。不妨设 x 满足限制。此时设 nwX,nwY 表示当前分别有多少前缀最大值，s 表示后面还剩下多少个好的数，t_1,t_2 表示 y 在后面取了 t_1 个好的数和 t_2 个 不好的 数。可得方程 nwX+s-t_1=nwY+t_1+t_2，移项得 nwX-nwY+s=2t_1+t_2。即判断是否可以取出一个上升子序列满足条件。容易发现如果能取出值为 w 的，一定可以取出值为 w-2 的。因此令 dp_{i,0/1} 表示 i 后面和为奇/偶的和的最大值，线段树优化转移即可。时间复杂度 O(n\log n)。

\operatorname{AGC028F}

考虑维护 L_{i,j,k},R_{i,j,k} 表示从 (i,j) 开始走到第 k 行能走到的最左/最右位置，容易递推求得。把所有左/上都是障碍的点变为障碍。此时 Ans_{i,j}=\sum\limits_x\sum\limits_{y\in [L_{i,j,x},R_{i,j,x}]} a_{x,y}。显然被挖掉的点一定是不能走到的点，我们只需要证明没被挖掉的点一定是能走到的点。如果存在 (x,y) 没被挖掉，那么一定存在 (p,q) 使得其在 (i,j) 之后被访问到并且能够走到 (x,y)。可以发现 (p,q)\rightarrow (x,y) 的路径一定与 (i,j)\rightarrow (x,L_{i,j,x}) 和 (i,j)\rightarrow (x,R_{i,j,x}) 中的至少一条相交，设交点为 (u,v)。那么我们就有 (i,j)\rightarrow (u,v)\rightarrow (x,y) 这一条路径，即 (i,j) 能走到 (x,y)。时间复杂度 O(n^3)。

\operatorname{AGC029E}

令 f(u,i) 表示从 u 开始往下走不能经过 >i 的点能走到的点个数，mx_u 表示 u 的祖先的最大值。分两类讨论：

可以直接用数据结构在 O(n\log n) 时间内求出 f。观察 f 的转移式：f_{u,i}=\sum\limits_{v\in son_u}[v<i]f_{v,i}。可以归纳证明对于某一个 u 只会用到 mx_u,mx_{fa_u},mx_{fafa_u} 这 3 个状态，因此可以直接记忆化搜索。时间复杂度 O(n)/O(n\log n)。

\operatorname{AGC029F}

将 [1,n) 中的点与所有集合做一个二分图匹配，如果没有完美匹配直接输出 -1。设集合 S 的点为 v_S。设当前点为 u（初始 =n）。枚举所有包含它的集合，选出还未被使用过的，设其为 S。连边 (u,v_S)。重复这个过程直到无法进行。如果还有集合没被使用过，那么根据完美匹配的性质（Hall）定理可知一定无解。否则已经求得答案，输出即可。时间复杂度 O(n\sqrt{\sum |E_i |})。

\operatorname{AGC030D}

令 f_{i,j} 表示 a_i>a_j 的概率。考虑增加一个操作时 f 的变化。设增加的操作为 (x,y)，那么 f'_{i,x}=f'_{i,y}=\dfrac{f_{i,x}+f_{i,y}}{2},f'_{x,i}=f'_{y,i}=\dfrac{f_{x,i}+f_{y,i}}{2}。最终的答案即为 Ans=\sum_{i<j}f_{i,j}2^q。时间复杂度 O(n^3)。

\operatorname{AGC030E}

在 01 中加一条红线，10 中加一条蓝线。每次操作相当于是把某条线移到相邻的空格中。不妨在边界处加上红蓝相间的无限长的线来避免边界情况。由于线之间相对位置不变，所以我们暴力枚举红蓝线之间的平移对应关系，直接求解即可。时间复杂度 O(n^2)。

\operatorname{AGC030F}

考虑从大往小填数，暂时不考虑 (-1,-1) 之间的顺序，dp_{i,j,k} 表示当前填到 i，当前有 j 个事先填好的 (-1,x) 和 k 个非事先填好的 (-1,x)。转移如下：

最终答案即为 dp_{1,0,0}\times c!。其中 c 是 (-1,-1) 的个数。时间复杂度 O(n^3)。

\operatorname{AGC032D}

显然每个数最多动一次，并且一旦动过就可以直接删掉。又可以发现不动的数一定是一个上升子序列。对于这个上升子序列相邻两项 b_i,b_{i+1} 之间的每一个数 x，显然 x\notin [b_i,b_{i+1}]。如果 x>b_{i+1} 就会产生 A 的代价，如果 x<b_i 就会产生 B 的代价。那么 dp_{i,j} 表示前 i 个数中子序列最后一个数 =j 的答案，直接转移即可。也可以线段树优化。时间复杂度 O(n^2)/O(n\log n)。

\operatorname{AGC032E}

考虑 x_i+y_i<M 的数对之间连接蓝线，\ge M 的数对之间连接红线。根据调整法可证明红线完全在蓝线右侧，且同色线之间只有包含关系。显然蓝线越多越好，因此二分红蓝之间的分界位置并暴力求解即可。时间复杂度 O(n\log n)。

\operatorname{AGC033D}

令 dp_{w,i_1,j_1,i_2} 表示凌乱度为 w，固定 i_1,j_1,i_2 时的最大 j_2。显然凌乱度不会超过 \log n+\log m。纵向可以直接暴力合并。横向合并可以根据数组的单调性用双指针优化。时间复杂度 O(n^3\log n)。

\operatorname{AGC033E}

不妨设 S_1=R，此时显然环上所有 B 连续段长度为 1，并且 R 连续段长度为奇数。设 S 中第 i 段连续的 R 长度为 len_i。对于 len_1，环上所有 R 连续段长度 \le len_1+1。对于 len_i(i>1)，如果 len_i 为偶数则没有限制，否则环上所有 R 连续段长度 \le len_i。直接根据这些性质 dp 即可。时间复杂度 O(n)。

\operatorname{AGC034E}

先枚举根 rt，表示最终元素所聚集到的节点。每次操作相当于把两个不为祖先后代关系的棋子往上挪一格。令 sz_u 表示 u 子树中棋子个数。s_u 表示 u 子树中棋子深度之和， dp_u 表示 u 子树中最多做多少次操作，w_u=s_u+sz_u-2dp_u。对于每一个 u 分两类讨论：

如果 dp_{rt}=\dfrac{s_{rt}}{2} 那么 rt 合法，计入答案。时间复杂度 O(n^2)。