ARC119 题解

[toc]

AC代码

A – 119 × 2^23 + 1

B – Electric Board

给定两个长度为 $N$ 的字符串 $S,T$ ，字符串只含有 0, 1 两种字符。现在有两种操作：

操作一：选择一段区间 $[L,R]$ ，该区间满足 $S_L=0,S_{L+1,L+2,\ldots,R}=1$ ，翻转这个区间。

操作二：选择一段区间 $[L,R]$ ，该区间满足 $S_{L,L+1,\ldots,R-1}=0,S_R=1$ ，翻转这个区间。

询问将 $S$ 转变为 $T$ 最少的操作次数。

$N\leq 500000$ 。

利用了一个经典的性质：假设我们想将所有的 $0$ 翻转到对应位置（$1$ 也是一样的），那么所有 $0$ 变换前后的相对顺序不变。因此我们只需要找到 $S$ 中所有 $0$ 的位置序列 $X_0,X_1,\ldots,X_m$ ，和 $T$ 中所有 $0$ 的位置序列 $Y_0,Y_1,\ldots,Y_M$ 。如果 $X_i\neq Y_i$ ，那么就需要花费一次翻转，否则不需要翻转。

C – ARC Wrecker 2

给定一个大小为 $N$ 的数列 $A_N$ ，你可以在数列 $A$ 中选择一段连续区间 $[L,R]$ ，然后执行以下两种操作任意次：

操作一：在区间内选择两个相邻位置 $x,x+1$ ，将这两个位置上的数 $+1$ ；

操作二：在区间内选择两个相邻位置 $x,x+1$ ，将这两个位置上的数 $-1$ ；

询问可以选出几个连续区间 $[L,R]$ ，使得有限次操作后整段区间都变成 $0$ 。

$N\leq 10^9$ 。

因为不管哪种操作都一定会同时对一对奇偶位置加减一，因此一段区间 $[L,R]$ 中，我们考虑对奇偶位置分别求和，奇数和减去偶数和是一个定值，因此只需要求出奇数和-偶数和为零的所有区间即可。

D – Grid Repainting 3

给定一个 $H\times W$ 的网格图，每个单元上初始有一个字符 R 或者 B ，分别代表这个单元格被染成了红色和蓝色。现在你可以执行以下操作任意次：

操作一：选择一个红色单元格，然后将该单元格所在的行全部染成白色。

操作二：选择一个红色单元格，然后将该单元格所在的列全部染成白色。

构造一种合法染色方案使得网格图中最后的白色方格最多。

$H,W\leq 2500$ 。

这题的核心思路和自己出过的题居然是类似的（~~虽然idea来自ELMO2010C6 Rook’s tour with constraints~~）！

这两题最关键的转化就是因为每次行动都只是在一行或一列上进行，因此行和列可以看作一个二分图，具体来说用点来代表行和列，用边代表某个单元格。本题中构造一个 $N\times M$ 的二分图，左半部的 $N$ 个点代表行，右半部的 $M$ 个点代表列，那么行 $i$ 到列 $j$ 的一条边就是单元格 $(i,j)$ ；由于本题对于某个单元格有两种操作，因此我们规定从行 $i$ 走到列 $j$ 的有向边代表将 $(i,j)$ 所在行涂白，从列 $j$ 走到行 $i$ 的有向边代表将 $(i,j)$ 所在列涂白。

对于所有的红点先建立上述的二分图，然后很容易发现本题中的二分图还应该满足两个性质：

二分图上任意一个点的出度 $<2$ 。
二分图上不能成环。

一个合法的构造方案只需要满足上方的两个条件即可（但是方案的构造需要满足一定顺序，后文会提到），然后我们思考本题另一个难点：如何最大化白色块的数量。

注意到二分图上不能成环，这说明对于二分图上的每个连通块而言，最优解一定是一棵生成树。然后我们尝试用代数方法解释本题的贪心构造方法：假设最终的网格图中有 $A$ 行被涂白，$B$ 列被涂白，就可以得到最终的白格数量为 $HW-(H-A)(W-B)$ 。由于我们判断本题的最优解是一棵生成树，因此 $A+B$ 的数值是确定的，不妨令 $C=A+B$ ，那么我们的目标就是最大化 $HW-(H-A)(W-(C-A))$ 。

\begin{aligned} HW-(H-A)(W-(C-A))&=HW-(H-A)(W-C+A)\\ &=HW-(-A^2+(H-W+C)A+H(W-C))\\ &=A^2-(H-W+C)A+HC \end{aligned}

这显然是一个开口朝上的二次函数，因此该二次函数的最大值一定在 $A=0$ 或 $B=0$ 时取到！因此我们需要做的就是根据不同情况最大化 $A-B$ 或者 $B-A$ （可以把两种方案都跑一遍取 $\max$ ，也可以推一下分类讨论，边界条件是二分图两边的独立点个数）。

假设我们需要最大化 $A-B$ （$B-A$ 同理）由于是在二分图上最大化 $A-B$ ，因此我们只需要尽可能让每个左半部（行）的点都去指向右半部，最后再让右半部的点补上缺失的连边。但是这么做会导致一些问题（正常人应该都不会犯这个问题，我因为这个wa了半天），例如样例中的构造是：

但是我们可能构造出：

看起来没什么区别，但是！如果我们先涂白两个横行，那么剩下的那一列就不能涂了，Y 4 3 这一步操作时 4 3 所在单元格已经不是红色了。因此构造方案需要考虑dfs序（dfs序一定不会出现颜色被提前覆盖的情况），如果是最大化 $A-B$ ，我们直接从每一个列所代表的点开始dfs，最后回溯时建立反向边即可。