Solution Set #4

标签：AtCoder Set Submission Contest 可以 Solution Grand 考虑

最近写了不少 AGC，感觉高一的时候做挺合适的，不过高一出于对 ad-hoc 和外星人题的恐惧一直没怎么写。其实古早题还是有不少能做的，希望学弟不要像我一样。

36 2nd ucup Stage 13 Shenyang F Ursa Minor

首先显然用区间内的操作可以组成它们的 gcd 对应的操作。由于序列是环形的，所以还可以和长度取 gcd。所以只需要考虑 \(m=1\) 的情况，假设为 \(b\)。

考虑模 \(b\) 的所有同余类，一次操作恰好给每个同余类的和加上 \(x\)，所以充要条件是每个同余类的和相等。

对于 \(b\) 较小的情况，可以直接维护。否则看起来不是很好维护。考虑哈希。原条件等价于相邻两个同余类的差分均为 \(0\)，不妨给每类带上一个伪随机系数，这样条件相当于加上系数后的代数和为 \(0\)。

考虑随机系数怎样才比较好维护。一个想法是直接带上 \(i\bmod b+1\)，拆成 \(i+1-b\lfloor \frac{i}{b}\rfloor\)，然后枚举 \(\lfloor\frac{i}{b}\rfloor\) 维护。但这样不够随机。编一下可以发现取随机值为底数之后令系数为 \(g^{i\bmod b+1}\) 就可以了。

注意模数要大于 \(10^9\)，取 \(998244353\) 会出现不可预料的问题。场上因为这个交了 11 发罚时。

Submission #280626 - Universal Cup Judging System (ucup.ac)

37 AGC008D K-th K

可以建立二分图模型：对于每个数建立 \(n\) 个点，前 \(i-1\) 个向 \([1,x_i)\) 连边，后 \(n-i\) 个向 \((x_i,n^2]\) 连边，中间向 \(x_i\) 连边。

注意到形式比较优美，所以可以贪心匹配，每次找到限制最紧的匹配当前点即可。

Submission #48333602 - AtCoder Grand Contest 008

38 AGC020D Min Max Repetition

先分析一下 \(f(A,B)\) 的连续段长度。不妨设 \(A\geq B\)，那么考虑判断 \(len\) 是否合法，有 \(\lceil\frac{A}{len}\rceil-1\leq B\)，可以得到 \(len\geq \lceil\frac{A}{B+1}\rceil\)。

分析一下字典序最小的串的形态，发现一定是：\((len,1)^X A^YB^Z(1,len)^W\) 的形式，其中 \((x,y)\) 表示 \(x\) 个 A 和 \(y\) 个 B 的串。\(X,Y,Z\) 均可以二分得到。

Submission #48335770 - AtCoder Grand Contest 020

39 AGC024D Isomorphism Freak

注意到同构的限制比较紧，所以可以考虑分析一下性质来构造下界。对于两个点 \(u,v\)，假如它们同构，那么考虑路径 \((u,v)\) 上离 \(u\) 最近的点 \(x\) 和离 \(v\) 最近的点 \(y\)。那么 \(v\) 为根的时候匹配 \(x\) 的点一定是 \(y\)，否则会出现 \(x\) 和 \(x\) 的子树同构的诡异情况。如此可以找到一条边或者一个点，使得它们两边子树同构。

假设是边，考虑枚举这条边，树被分成两棵树，此时假设两边深度最大值分别为 \(Dx,Dy\)，\(\max(Dx,Dy)\) 是答案的下界。所以答案下界是直径的一半。构造也是可行的，只需要不断加点使得每层的子树都同构即可。注意到这样的子树可以和序列 \(d_i\) 构成双射，\(d_i\) 为第 \(i\) 层点的儿子个数，而 \(d_i\) 合法当且仅当 \(d_i\geq deg_u\)，所以可以得到叶子个数的下界。

点的情况同理。容易发现答案上界是 \(3^{\frac{n}{3}}\)。

Submission #48337541 - AtCoder Grand Contest 024

40 AGC025D Choosing Points

考虑 \(D_1=D_2\)，要求构造一个大小大于 \(\frac{1}{4}|V|\) 的独立集。

猜测图是二分图，证明：

• \(D\bmod 2=1\)，因为满足 \(x^2+y^2=D\) 的 \(x,y\) 一定满足 \((x+y)\bmod 2=1\)，所以 \(x+y\) 奇偶性相同的点一定没边。
• \(D\bmod 4=2\)，此时 \(x\bmod 2=y\bmod 2=1\)，\(x\) 奇偶性相同的点一定没边。
• \(D\bmod 4=0\)，此时一定满足 \(x\bmod 4=0\) 且 \(y\bmod 4=0\)，那么只有 \(x\bmod 4,y\bmod 4\) 都相同的点之间右边，除以 \(4\) 之后可以规约到上面的情况。

所以建立二分图，取点多的一侧即可。

回到原题，可以分别对两个 \(D\) 建立二分图，点被分成四类，取点最多的一类即可。

Submission #48355595 - AtCoder Grand Contest 025

我发现我很不会找这些数论性质啊，省选 D1T2 那个题也没看出来根号结论。

41 AGC029F Construction of a tree

尝试一些构造方式，比如一个一个集合加边，那么一个集合加边的时候需要保证它对应的集合不连通。以此为动机可以得到一个无解的必要条件：对于任意集合 \(S\)，有：

\[|\bigcup_{x\in S}E_x|> |S| \]

如果不满足，左边集合的导出子图必然存在环。

形式很像最大权闭合子图，但其实做不了。考虑 Hall 定理的形式就是把上面的大于改成大于等于，尝试一些构造使得它贴近 Hall 定理的形式。一种办法是把左边的集合删去一个点，所以可以得到必要条件的转化形式：删去任意右部点，二分图存在完美匹配。

所以存在快速判断这个条件的算法：跑二分图匹配，检查右部是否有必要点。

可以得到一个思路：不断删去集合中的点，判断合法，可以得到 \(\mathcal{O}(n^{2.5})\) 的算法。根据判断必要点的方法可以得到一个转化：残量网络上每个左部点保留完美匹配的边和另一条边，使得所有右部点和汇点强连通。据此可以得到一个构造：以右部唯一没有匹配的点为根 BFS，每次找到一条边，并把对应点加入集合。可以证明在满足必要条件的情况下一定能找到合法点（否则剩余点集合不合法）。于是我们证明了条件是充分的，并给出了构造。

Submission #48358399 - AtCoder Grand Contest 029

42 AGC037E Reversing and Concatenating

考虑怎么构造出全 a 串，发现可以找到一个 a 把它放在末尾，然后每次倍增它，可以在不超过 \(1+\log n\) 次操作之后构造出来。

考虑 \(k<1+\log n\) 咋做，依然是上面的策略，找到最长的一段 a，把它放在后缀，然后每次倍增它。实际上这个策略就是最优的。

大概是可以直接暴力求的，但实际上有更好的做法。注意到最后的结果一定是若干个 a 加上一段不是 a 的后缀翻转后的结果，所以可以直接比较 a 的个数和字典序大小得到第一步最优的串。

Submission #48386872 - AtCoder Grand Contest 037

43 AGC021D Modulo Matrix

很久之前看过这题来着，今天重新编了下做法。

考虑钦定大小关系来忽略 \(\max\) 和 \(\min\) 的限制，容易想到黑白染色。一种直接的想法是，把每个黑格子里面塞个素数，然后白格子就是四个素数相乘。

这样不太优秀，不妨把黑格子里面塞两个素数的乘积，保证每个主副对角线都有公共的素数。这样白格子仍然是四个素数相乘，但是素数要更小一点。

安排一下素数的位置可以卡进 \(10^{15}\)。

Submission #48416058 - AtCoder Grand Contest 027

44 AGC035C Skolem XOR Tree

样例给出了 \(n=3\) 的构造，推广它其实可以得到 \(n\bmod 4=3\) 的构造：每四个点连一条链。

\(n\bmod 4=1\) 的构造是简单的，先用上面的策略解决前面的点，再处理 \(n-1,n\)，处理方法是把它们的链中间插入一个 \(1\)。

\(n\bmod 4=2\) 的构造，考虑沿用 \(n=1\) 的构造，再特殊处理 \(n\)。构造策略是把 \(n\) 接到 \(n-2\) 上然后把 \(2n\) 接到 \(n+2\) 上。

\(n\bmod 4=0\) 的构造，可以发现 \(n\) 是 \(2\) 的整数次幂的时候无解，否则把最后 \(5\) 个数拆成一个 \(2\) 和一个 \(3\)，然后把 \(n,n-1\) 中间插入一个 \(n\oplus (n-1)\) 即可。

Submission #48416849 - AtCoder Grand Contest 035

45 AGC030C Coloring Torus

离谱铜牌构造。

有个显然的构造：

1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

但是不太行，可以得到另一组构造：

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

思路是按照斜线构造。考虑怎么让斜线增加 \(1\)，可以选择一个斜线，然后交替放一个新颜色：

1 2 3 4
2 3 5 1
3 4 1 2
5 1 2 3

找多个斜线也是合法的，所以做完了。

Submission #48418274 - AtCoder Grand Contest 030

46 gym103260A Assignment Problem

可以证明最优方案中一定有一个选 \(p_{i,1}\)，证明如下：假设第 \(i\) 个选的是 \(h_i\)，那么连边 \(h_i\to p_{i,1}\)，以任意有出度的点出发，最终会到达一个没有出度的点或者一个环，按照路径调整可以得到更优解。

所以直接暴搜哪个是第一个，复杂度是阶乘。

Submission #236758133 - Codeforces

47 gym103260C Multiple?

首先发现序列是有绝对众数的，并且绝对众数和 \(n\) 互质（这个不知道咋发现的，感觉只能打表）。那么把绝对众数乘上 \(x^{-1}\) 变成若干个 \(1\)，所有数的和是不能超过 \(n\) 的，否则我用剩余数走到 \([\frac{n}{2},n]\) 的位置然后全用 \(1\) 就构造出了倍数。所以插个板，答案就是 \(\varphi(n)\binom{n-1}{k-1}\)。

关于结论的证明：如果不存在绝对众数，那么我们可以找到 \(\frac{n-k}{2}\) 对互不相同的数，任意排成一排并考虑其前缀和，可以得到 \(n-k+1\) 个前缀和。如果交换两个数的位置，可以得到 \(n-k+1+\frac{n-k}{2}\) 个不同的前缀和。因为 \(k\leq \frac{n}{4}\)，所以前缀和的数量必然超过了 \(n\)。

感觉证明非常难想，做这个的动机可能是打表发现结论吧。

Submission #236771875 - Codeforces

fun fact：笔者写这题的时候不会线性求单个阶乘的逆元，他使用的是线性求逆元之后乘起来。

怎么这场这么神秘的，感觉不如宇宙杯子。

48 ARC103B Robot Arms

考虑一维怎么做。不妨固定最小的值为坐标 \(0\) 点，那么一次操作是选择一个子集加上 \(2c_i\)。取 \(c_i=2^k\) 可以得到一个 \(\log V\) 的构造。

考虑二维，注意到问题是二维平面上随机游走，经典地旋转坐标系就可以转化为一维问题。

My Submissions - AtCoder Regular Contest 103

49 CF578E Walking!

等价于最小化 \(p_i<p_{i+1}\) 的连续段数。

假设我们从前往后把这些链构造出来，考虑能够把它们接成一条链的充要条件。首先，如果存在 R-R 这样的链一定可行，构造方法是先把 L-R 和 R-L 全部消掉，然后一一匹配 R-R 和 L-L 即可。对于剩下的情况，如果链的起点字符全部相同也可以构造出来，剩下的情况均不能构造。

据此可以 \(\mathcal{O}(\text{poly}(n))\) DP，但是次数有点高。考虑贪心。我们只考虑存在 R-R 或者 L-L 的情况。如果 \(n\) 是奇数，那么从前往后能接就接一定是合法的。否则，先构造 \(n-1\) 的最优解，然后 \(n\) 自成一段一定是合法的。所以最优解不会超过上述贪心策略得到的解 \(+1\)。这说明我们不会通过额外新增链来保证合法。于是考虑接到哪条链后面更优。不妨设当前字符是 L，那么接一个 L-R 会使得 L-L 段 \(+1\)，否则会使 R-R 段 \(-1\)，对比可以发现前者更优。于是我们构造出了唯一的贪心策略。

Submission #236845316 - Codeforces

50 CF538G Berserk Robot

跟 48 一样，旋转坐标系之后转化为一维问题。

先判掉奇偶性的问题。现在任务是构造长度为 \(L\) 的序列 \(a_{0\sim L-1}\) 和 \(\Delta\) 使得：

• \(x_i=\lfloor\frac{t_i}{L}\rfloor\Delta+a_{t_i\bmod L}\)。
• \(|a_i-a_{i-1}|=1,|a_{L-1}-delta|=1\)。

先处理掉 \(t_i\bmod L\) 相同的点，然后考虑 \(t_i\bmod L\) 相邻的两个点的限制。限制就是坐标差不超过模数差，这个可以解一个不等式解出 \(\Delta\) 的范围。

Submission #236873197 - Codeforces

坑：处理余数相同的时候要判一下得到的 \(delta\) 不相同的情况。

51 CF566E Restoring Map

考虑剥叶子。经过若干次对拍和试错可以得到下面的构造：

• 找到一个点，使得删去与它相连的所有叶子之后它会变成叶子。
• 删去与它相连的所有叶子结点。
• 如果图是菊花图，特判。

找这个点的方法是：找到 \(x\) 个完全相同的集合，使得集合中恰好有 \(x+2\) 个元素（需要判一下长度为 \(4\) 的链）。

注意到剩下两个点我们不能确定谁是父亲。可以先不管，看这两个点哪个先变成叶子。

判断集合相同可以 XOR-hashing。

复杂度是 \(\mathcal{O}(n^2\log n)\) 的。

Submission #236965429 - Codeforces

开始我尝试考虑集合的交，但是只考虑了 \(\text{dist}\leq 2\) 的，没啥收获就对叶子节点的集合想了。

唉。

52 loj2866. 「IOI2018」机械娃娃

如果不考虑所有开关都回到初始状态的问题，容易得到一个 \(S=n\) 的构造：建立一个线段树，所有非叶子结点是一个开关，然后按顺序填进去。

考虑怎么还原，注意到 \(n=2^k\) 的时候是不会有问题的，考虑把原线段树补成 \(n=2^k\) 的形状，这样结点数是 \(2n\) 的。但是可以发现如果一个子树的结点都是开关的话，只需要建立一个结点。容易分析出这样的结点个数是 \(\log n\) 级别的。所以总结点数为 \(n+\log n\)。

提交记录 #1953671 - LibreOJ (loj.ac)

53 uoj446. 【集训队作业2018】传送门

可以组合出一个操作：使用{dec(x),inc(x)}，可以让 \(a_{a_i-1}\) 减 \(1\)，\(a_{a_i}\) 加 \(1\)。

考虑利用这个操作来逐位构造。我们先把 \(a_0\) 置为 \(n-1\)，然后逐位还原。最后只剩下 \(a_0\) 和 \(a_1\) 没有还原。此时只需要还原 \(a_0\) 即可。那么如果直接大力操作的话会让 \([1,b_0-1]\) 中的所有数都 \(-1\)，那么让这些数初始的时候 \(+1\) 即可。

注意到如果 \(a_x=x\) 的话上面组合操作没有任何用处，所以需要判一下，然后找一个 \(a_x\neq x\) 的数 rotate 到 \(a_0\)。

提交记录 #668002 - Universal Online Judge (uoj.ac)

54 AGC029C Lexicographic constraints

二分之后在笛卡尔树上考虑。设 \(f_u\) 表示结点 \(u\) 必须往下进位的数量，那么 \(f_u=(f_{ls}+f_{rs}+[ls\neq 0])/x^{a_u-a_{fa_u}}\)，判断 \(f_{rt}\) 是否为 \(0\) 即可。

Submission #48479718 - AtCoder Grand Contest 029

55 AGC032D Rotation Sort

转述一下操作：把一个数删除之后插入到序列任意位置，往后插贡献是 \(A\)，往前插贡献是 \(B\)。

注意到一个数只有两种可能：自己插入到对应位置或者被其它元素推到对应位置，那么考虑 DP 所有不动的点。对于一个区间里面的数，如果它的目标点在两个端点右侧那么贡献为 \(A\)，否则为 \(B\)。容易平方。

Submission #48480870 - AtCoder Grand Contest 032

56 ARC096C Everything on It

容斥转化问题。钦定集合 \(S\) 中的数出现不超过 \(1\) 次，构造方法是把 \(S\) 集合中出现恰好一次的数分到无标号盒子里面，然后对于每个盒子构造其余数，可以列出式子：

\[\sum_{s=0}^n\binom{n}{s}(-1)^s\sum_{t\leq s}\binom{s}{t}\sum_{j\leq t}{t\brace j}2^{2^{n-s}}(2^{n-s})^j \]

考虑枚举 \(t\) 的意义，实际上是以此为媒介试图计算在 \(s\) 里面选若干个数并分到恰好 \(j\) 个非空盒子的方案数，设其系数为 \(f_{s,j}\)，可以利用 DP 计算，于是优化到平方。

Submission #48481402 - AtCoder Regular Contest 096

57 AGC028C Min Cost Cycle

人为增加决策，每条边可以选择 \(a_u\) 或者 \(b_v\) 作为权值。观察每个 \(u\) 的贡献，贡献有四种：\(0,a_u,b_u,a_u+b_u\)。类似 49 分析可以得到贡献的分配能形成环的充要条件：要么全选 \(a/b\)，要么 \(0\) 和 \(a_u+b_u\) 的个数相等。利用 Cardboard Box 的技巧结合凸性可以得到 \(\mathcal{O}(n\log^2 n)\) 做法。

当前的题意难以优化，考虑一个转述。注意到答案是对 \(n\) 个互不相同的元素求和，元素在 \(\{a_u\}\cup \{b_u\}\) 间。仿照上面的分析可以得到合法条件：选择的元素的标号集合不恰好为 \([1,n]\)。先排序，然后可能的集合实际上只有 \([1,n],[1,n-1]\cup\{n+1\},[1,n-1]\cup\{n-2\},[1,n-2]\cup \{n,n+1\}\) 这四种，于是可以做到 \(\mathcal{O}(n\log n)\)。

Submission #48480593 - AtCoder Grand Contest 028

58 AGC035F Two Histograms

首先考虑怎么判断一个序列是合法的。

假如我们只保留行的操作，那么会得到一个只有 \({0,1}\) 的网格，\(1\) 的形状形似“山峰”；只保留列的情况同理。那么可以得到一个判断合法的思路：在网格中删去列所对应的“山峰”，判断剩下的是否是一个合法的山峰图形。

分析格子，可以发现一些点是必须被删去的：

• 重复格子：\(a_{i,j}=2\) 的格子。
• 悬浮格子：\(a_{i,j}=1\) 且 \(a_{i,j-1}=0\) 的格子。

可以得到一个判定合法的方式：从 \(1\sim m\) 枚举每一列，找到必须被删去的最远的格子，假设为 \(a_{x,i}\)，那么令 \(l_i=x\)，并删去这些格子。注意删去这些格子可能形成新的悬浮格子。如果不能删除，则不合法。（容易发现，只需要删到最远的必删格子，删多了是不优的）

注意到我们的判断过程是唯一的，这说明：每个合法的方案可以和上述判断方式构成双射。所以不妨计数有多少种局面的判断过程是某个确定的过程，我们用序列 \(l_i\) 表示这个过程。

注意到，如果我们依次考虑某一行 \(x\)，找到 \(l_i=x\) 的所有 \(i\)，那么 \(a_{x,i}\) 为重复格子的 \(i\) 必定是一个前缀。这是因为这一行的行山峰会覆盖这些格子，而除开行山峰覆盖的格子，剩下格子的摆放方式是唯一的，可以根据悬浮格子的位置来还原。所以所有局面和每行行山峰的格子数量构成双射，只需要考虑行山峰的长度是否合法。这是简单的，行山峰的长度合法当且仅当它后面的一个格子不是悬浮格子，所以假如 \(l_i=x\) 的 \(i\) 有 \(s\) 个，那么行山峰长度的方案数就是 \(m+1-s\)。

所以，问题被我们转化成了如下形式：对于序列 \(b_{0\sim n}\)，\(b_x\) 表示 \(l_i=x\) 的数量，保证 \(b\) 的元素和为 \(m\)，序列的权值为 \(\binom{m}{b_0,b_1,\cdots,b_n}\prod_{i=1}^n (m+1-b_i)\)，你需要求所有序列的权值和。写成生成函数的形式就是：

\[[\frac{x^n}{n!}]e^x((m+1-x)e^x)^n \]

可以多项式快速幂，实际上把幂次里面的 \(e^x\) 提出来就可以线性算单项系数了。然而我脑抽了还是写了个多项式

Submission #48492347 - AtCoder Grand Contest 035

59 AGC033D Complexity

暴力 DP 是五方的，但是注意到答案不超过 \(\log n\)，所以考虑把 DP 一维换成答案。

设 \(f_{ans,k,i,j}\) 表示答案不超过 \(ans\)，左边界为 \(k\)，上下边界为 \(i,j\)，右边界的最大延申长度。那么转移有两种：

• 竖着割，那么跳到 \(k+f_{ans-1,k,i,j}-1\) 然后再跳一次。
• 横者割，那么 \(f_{ans,k,i,j}=\max_p\min\{f_{ans-1,k,i,p},f_{ans-1,k,p+1,j}\}\)，因为函数是单峰的，决策是单调的，所以双指针一下决策点就行了。

复杂度是 \(\mathcal{O}(n^3\log n)\)。

Submission #48485573 - AtCoder Grand Contest 033

60 AGC038F Two Permutations

考虑排列 \(P\) 的一个置换环上的元素集合 \(S\)，那么在排列 \(A\) 中，\(S\) 集合中的数要么全部取 \(i\)，要么全部取 \(P_i\)。\(Q\) 和 \(B\) 同理。

给环编号，设 \(x_u\) 表示环 \(u\) 上的点全部取 \(i\) 还是全部取 \(P_i\)，考虑下标 \(i\) 是否满足 \(A_i=B_i\)：

• \(P_i\neq i,Q_i\neq i\)。
  • \(P_i=Q_i\)，贡献是 \(x_ux_v+(1-x_u)(1-x_v)\)。
  • \(P_i\neq Q_i\)，贡献是 \((1-x_u)(1-x_v)\)。
• \(P_i=i\)，贡献是 \(1-x_v\)。
• \(Q_i=i\)，贡献是 \(1-x_u\)。

令 \(y_u=1-x_u\)，代入可以发现贡献是最小割的形式。直接建立最小割模型即可。

Submission #48487461 - AtCoder Grand Contest 038

61 AGC037D Sorting a Grid

把 \(a_{i,j}\) 看作 \((a_{i,j}-1)/m+1\)，那么限制是：

• \(C\) 的每行所有数相同。
• \(B\) 的每列所有数互不相同。

一眼琪露诺的符卡变换。依次还原 \(B\) 的每一列，将列和颜色连边。由于正则二分图一定有完美匹配，所以一定有解。跑二分图匹配即可。复杂度 \(\mathcal{O}(n^4)\)。

Submission #48485913 - AtCoder Grand Contest 037

62 AGC038E Gachapon

下文用 \(s(S)\) 表示集合 \(S\) 的 \(a\) 的和。

min-max 容斥一下，考虑怎么算一个集合 \(S\) 的 \(E(\min(S))\)。

枚举在 \(S\) 中的步数 \(l\)，那么构造长度为 \(l\) 的序列 \(c\)，序列中第 \(i\) 个元素表示 \(S\) 集合中第 \(i\) 个摇出来的是 \(c_i\)。序列的权值是 \(\prod\frac{a_{c_i}}{s(S)}\)。然后发现可以直接找每个数的出现次数然后多重组合算一下。

考虑步数 \(l\) 在整体对应的期望步数，发现其实就是 \(\frac{l\cdot s([1,n])}{s(S)}\)。

所以可以设 \(f_{i,j}\) 表示 \(a\) 的和是 \(i\)，总的步数是 \(j\)，枚举每个数是不是在集合中，如果是，枚举在集合中出现几次。可以分析出 DP 的复杂度是 \(\mathcal{O}(n^3)\)（视 \(n,\sum a_i,\sum b_i\) 同阶）。

Submission #48488943 - AtCoder Grand Contest 038

63 AGC034E Complete Compress

枚举最后的点在哪里。那么如果每次操作不同子树的棋子那么就相当于判一下每棵子树深度和的绝对众数（其实就是超过和一半的数，不知道这东西有没有名字）。

但这样还是不行，试一下发现还可以操作同一棵树里面的结点使得深度和减小。那递归下去做，判断能不能操作到根即可。

Submission #48500224 - AtCoder Grand Contest 034

64 AGC034D Manhattan Max Matching

首先切比雪夫拆一拆，可以得到一个 \(2n+4\) 个点的费用流模型：

• \(n\) 个点表示蓝点，蓝点向中间四个点连边，边权分别是 \(x,-x,y,-y\)。
• 中间四个点用来优化建图。
• \(n\) 个点表示红点，中间四个点向红点连边，边权分别是 \(-x,x,-y,y\)。

考虑模拟流一下。注意到中间四个点每个点最多只会经过一次，所以可以用堆来维护两个点之间的路径，然后跑最短路处理。实现上大概需要维护 20 个堆。

Submission #48501180 - AtCoder Grand Contest 034

65 AGC033E Go around a Circle

考虑判合法，平方的 DP 做法是显然的，除此之外没什么好的办法。注意到这个限制非常紧，考虑找充要条件。

先判掉一些一定不合法的。从几个角度分析：

• 考虑第一个字符，不妨设是 R，则答案里面没有相邻的两个 B，否则中间的数不合法。
• 考虑 R 连续段的奇偶性。假设字符串第一个 R 连续段的长度为奇数，那么环上 R 连续段长度如果是奇数的话，那么放第一个和第二个之间它一定在奇数步内走不到 B；假设第一个 R 连续段的长度是偶数，那么放第一个字符前面，它也走不到 B。所以所有 R 连续段的长度都是偶数。

这已经是比较强的约束了，考虑是否合法。首先，我们需要从 R 连续段走出来，走到与 B 相邻的地方，这给连续段的长度 \(r_i\) 设定了上界。假设第一个 R 连续段的长度是 \(k\)，那么 \(k\) 是偶数时，\(r_i\leq k+1\)，\(k\) 是奇数的时候，\(r_i\leq k\)。对于字符串后面的 R 连续段，如果长度是偶数，我们可以反复横跳使得当前位置仍然与 B 相邻，否则我们需要走到连续段的另一端，假设连续段长度是 \(l\)，那么 \(r_i\leq l\)。

所以字符串的限制相当于给最长的 \(r\) 连续段设定了上界。链上的情况是好做的，环上的情况只需要枚举第一个 \(1\) 和最后一个 \(1\) 之间的长度 \(l\)，然后把答案累加上 \(f_{l}(n-l+1)\) 即可。

注意特判只有一种字符的情况。

Submission #48506087 - AtCoder Grand Contest 033

66 AGC026D Histogram Coloring

此处的判断合法是简单的，但是不容易直接计数。尝试观察一些合法的必要条件来进一步约束。考虑 \(2\times n\)，如果一列中的两个格子同色，那么只有可能是一竖条一竖条的情况。否则就一定是取补集。所以我们找到了由一行递推到下一行的方式：

• 如果当前行是奇偶交错同色的形态，那么下一行可以与当前行相同，或者相反。
• 否则，只能相反。

拓展到原问题，在广义笛卡尔树上考虑。设 \(f_{0/1}\) 分别表示是奇偶交错 / 不是奇偶交错的情况。是奇偶交错的情况很好考虑，填当前行的方案数是 \(2\)，儿子需要满足奇偶交错。否则用总方案容斥，总方案中只要保证儿子对应下来的位置满足规则，剩下的随便填。求出 \(f\) 之后填下面的矩形，如果奇偶交错方案数是 \(2^{n-1}\)，否则方案数是 \(1\)。

复杂度 \(\mathcal{O}(n\log V+n\log n)\)，当然用光速幂搞一下再线性建笛卡尔树什么的应该是可以线性的。

Submission #48507339 - AtCoder Grand Contest 026

67 AGC030E Less than 3

神必 ad-hoc。

考虑往 \(01\) 中间插入一个 \(<\)，\(10\) 中间插入一个 \(>\)，那么合法操作可以看成符号的移动，或者在最左侧和最右侧插入一个符号。

然后就好办了，枚举一下符号配对的平移量 \(d\)，显然 \(d\) 的级别是 \(\mathcal{O}(n)\) 的，然后可以算出这个配对的最小答案，即每一对的距离和。

注意特判全 \(0\) 和全 \(1\) 的情况。

Submission #48512107 - AtCoder Grand Contest 030

标签：AtCoder,Set,Submission,Contest,可以,Solution,Grand,考虑
From： https://www.cnblogs.com/yllcm/p/17905103.html