ARC120 题解

[toc]

AC代码

A – Max Add

题意很迷惑，看晕了，不想翻译了。。。看懂了就会做的题。。。

B – Uniformly Distributed

给定一个 $H\times W$ 的网格图，每个单元格中要么被染为红色或蓝色，要么未染色。现在你要从 $(1,1)$ 走到 $(H,W)$ ，只能向右或者向下移动一个单位，询问有多少种染色方法（所有未染色的方格都必须上色）使得所有走法遍历到的红色格子数量相同。

$H,W\leq 500$ 。

画一画就不难发现：所有 $i+j=k(k=0,1,\ldots,h+w-2)$ 的单元格 $(i,j)$ 的颜色都必须一样，因此只需要枚举 $k$ ，然后扫一遍是否存在已经染色的格子：

两种颜色都存在：无解，直接退出。
只存在一种颜色：对答案无影响。
未染色：答案乘二。

C – Swaps 2

给定两个大小为 $N$ 的数列 $A,B$ ，询问你能否通过下方操作在有限次操作内将 $A$ 变为 $B$ ：

选择一个 $i$ ，然后交换 $A_i,A_{i+1}$ ；

当前的 $A_i$ 加 $1$ ；

当前的 $A_{i+1}$ 减 $1$ 。

上方三个操作必须依次执行。如果可以，求出最少操作次数。

$2\leq N\leq 2\times 10^5$ 。

上述操作相当于将 $(A_i,A_{i+1})$ 变换为 $(A_{i+1}+1,A_i-1)$ ，因此我们构造 $A’i=A_i+i,B’_i=B_i+i$ 。这样 $(A’_i,A’{i+1})$ 变换后就是 $(A’_{i+1},A’_i)$ 。

因此只需要解决一个简单的问题：数列 $A$ 交换几次相邻的元素能够得到数列 $B$ ，离散化后求逆序对即可解决。

D – Bracket Score 2

给定一个大小为 $2N$ 的数列 $A$ ，构造一个大小为 $2N$ 的合法括号序列 $S$ （所有括号都有单独对应的匹配括号）使得其权值最大。括号序列的权值定义为：$S$ 中 $N$ 对匹配的括号 $(i,j)$ 在数组 $A$ 中元素差值的绝对值 $|A_i-A_j|$ ，例如 $A=(1,2,3,4);S=(())$ ，那么 $S$ 的权值就是 $|1-4|+|2-3|=4$ 。

$N\leq 2\times 10^5$ 。

本题的核心在于：如果我们能让较大的 $N$ 个元素和较小的 $N$ 个元素匹配，那么该括号序列的权值一定是最大的。

因此我们将数组 $A$ 中较大的 $N$ 个元素染为白色，较小的 $N$ 个元素染为黑色，设法将 $N$ 对括号都设置为一白一黑。从 $i=0,1,2,\ldots,2n-1$ 开始遍历，并用一个栈 $stk$ 维护以下操作：

如果 $stk$ 为空，则直接入栈。
如果 $stk$ 非空，且 $A_i$ 与栈顶元素的颜色相同，则 $A_i$ 入栈。
如果 $stk$ 非空，且 $A_i$ 与栈顶元素的颜色不同，则栈顶元素对应位置设置为 ( ，$S_i$ 设置为 ) ，栈顶元素弹出。

由于黑白元素数量相等，这样构造的括号序列一定是合法的，并且绝对值差值之和一定最大。