AtCoder Grand Contest 034 题解

AutumnKite

题解AtCoder

发布于：2020年10月7日

次浏览

比赛地址

A - Kenken Race

题意

有 $N$ 个方格从左到右排列，编号 $1$ 到 $N$。有些位置上有障碍。

有两个不同的棋子，分别在格子 $A,B$。你可以执行以下操作若干次：

• 选择其中一个棋子，向右跳一格或两格，要求目标位置不是障碍且没有其他棋子。

判断是否可以使得最后两个棋子分别在 $C,D$。

$N\le 2\times 10^5,A<B$

题解

若 $C<D$，那么我们显然可以先跳第二个棋子使得两个棋子互不影响。

此时显然只需要 $A$ 到 $B$ 和 $C$ 到 $D$ 之间都没有连续两个障碍即可。

若 $C>D$，此时我们需要让第二个棋子在某个位置停留，将第一个棋子跳到终点，再将第二个棋子跳到终点。

为了使第一个棋子顺利跳到终点，我们需要让第二个棋子停留的位置满足把该位置当做障碍后 $A$ 到 $C$ 之间仍然不存在连续两个障碍。

那么只需要满足 $B$ 到 $D$ 之间（包含 $B$ 和 $D$）存在左右两边都是非障碍格子即可。

时间复杂度 $O(N)$。

代码

B - ABC

题意

给定一个字符串 $S$，只包含 A，B 和 C。

你可以执行若干次以下操作：

• 选择一个 $s$ 的一个等于 ABC 的子串，替换为 BCA。

求最多执行的操作次数。

$|S|\le 2\times 10^5$

题解

考虑对于一段 AA..AABC，假设 A 有 $c$ 个，那么可以操作 $c$ 次使得这一部分变为 BCAA..AA。

于是我们从前往后，有这样一段就操作。这样做一定是最优的，因为 A 仍然连续并且到了后面，可能会与后面的 AA..AABC 组成一个更长的段。

时间复杂度 $O(N)$。

代码

C - Tests

题意

A 和 B 参加 $N$ 场考试。对于第 $i$ 场考试，A 可以规定一个 $l_i$ 到 $u_i$ 之间的整数 $c_i$ 作为该考试的价值。

已知 B 第 $i$ 场考试的分数为 $b_i$。假设 A 第 $i$ 场考试的分数为 $a_i$，A 的目标是使得 $\sum_{i=1}^{N}a_ic_i\ge \sum_{i=1}^{N}b_ic_i$。

A 可以花费一单位的时间来使得自己某场考试的分数加 $1$。已知考试的满分为 $X$，A 不能将已经满分的考试分数加 $1$。

求 A 达到目标最少花费的时间。

$N\le 10^5$

题解

假设 $c_i$ 已经确定，那么 A 一定是按 $c_i$ 从大到小依次加，直到比 B 的总分高。那么显然按 $c_i$ 从大到小排序后一定是一个前缀满分，一个后缀没分，只有中间一个有部分分。

注意到对于 $a_i > b_i$ 的考试，我们可以把 $c_i$ 调整成 $u_i$ 使得自己比 B 的优势更大；对于 $a_i < b_i$ 的考试，我们可以把 $c_i$ 调整成 $l_i$ 使得自己与 B 的差距更小。

于是我们可以强制对于第 $i$ 场考试，分数小于等于 $b_i$ 的部分按价值 $l_i$ 计算，大于 $b_i$ 的部分按价值 $u_i$ 计算，那么 B 的分数即为 $S=\sum_{i=1}^{N}b_il_i$。

考虑二分答案 $M$，枚举不是满分也不是零分的考试，该考试的分数是已知的；而满分的考试数量也唯一确定，所以只需要把剩余的考试按满分得到的价值 $b_il_i+(X-b_i)u_i$ 从大到小排序后选取即可。

时间复杂度 $O(N\log NX)$。

代码

D - Manhattan Max Matching

题意

在平面上有若干个红球和蓝球。有 $N$ 个位置有红球，第 $i$ 个位置为 $(RX_i,RY_i)$，有 $RC_i$ 个红球；有 $N$ 个位置有蓝球，第 $i$ 个位置为 $(BX_i,BY_i)$，有 $BC_i$ 个蓝球。保证 $\sum RC_i=\sum BC_i$，令该值为 $S$。

你需要将这 $S$ 个红球和 $S$ 个蓝球匹配，每个球最多被匹配一次。一对匹配的权值为这两个球的曼哈顿距离。

求每对匹配的权值之和的最大值。

$N\le 1000,RC_i,BC_i\le 10$

题解

考虑曼哈顿距离的式子，把两个绝对值分别拆开，共有 $4$ 种状态，然后两个球的贡献独立。

因为最后求的是最大值，所以最终一定会取到两个都为正的情况。

对于一个匹配，若我们确定了红球的两个坐标的正负性，我们就可以唯一确定蓝球坐标的正负性。

于是可以建立费用流模型，源点向红球连流量为 $RC_i$，费用为 $0$ 的边，限制数量；在红球与蓝球中间建立四个点表示四种状态，每个红球向四种状态连对应流量为无穷大，费用为对应贡献的边。蓝球同理。

直接跑费用流即可。貌似可以用模拟费用流做到更优的复杂度。

代码

E - Complete Compress

题意

给定一个 $N$ 个点的树，有些节点上有一个棋子。每次可以执行以下操作：

• 选择两个有棋子且距离不小于 $2$ 的点 $u,v$，在这两个点上各取一个棋子向靠近另一个点的方向移动一条边。

求使得所有棋子到同一个点的最少操作次数。

$N\le 2000$

题解

枚举最后棋子到达的点 $t$，将 $t$ 作为该树的根。

显然对于两个棋子，如果操作这两个棋子后其中一个深度变大了，那么一定不优。所以若合法，操作次数一定是所有棋子深度之和除以 $2$。接下来考虑如何判断合法。

对于 $i$ 的子树，我们分别维护 $L_i$ 和 $R_i$ 表示对 $i$ 的子树内的棋子执行若干次操作后，这些棋子到 $i$ 的距离之和的最小值和最大值。那么可以取到的距离之和一定是在 $[L_i,R_i]$ 之间与 $L_i,R_i$ 奇偶性相同的数。为方便描述，我们令 $C_i$ 为 $i$ 子树内棋子数量。

显然最大值为子树内的棋子到 $i$ 的距离之和。考虑如何求出最小值。

我们先把每个子树内部的操作处理完，然后考虑子树之间的操作。假设每个儿子子树内的棋子到 $i$ 的距离之和分别为 $d_1,d_2,\ldots,d_k$。现在的操作相当于每次选两个 $d_j$ 减 $1$。我们要使得最终的 $\sum d_j$ 最小。

令最大的 $d_j$ 为 $d_{\max}$，$S$ 为所有 $d_j$ 之和减去 $d_{\max}$ 的值。那么可以证明最终 $\sum d_i$ 的最小值为 $\max(d_{\max}-S,0)$。

令 $i$ 的儿子 $v$ 中 $R_v+C_v$ 最大的为 $x$。若 $L_x+C_x$ 小于等于除 $x$ 以外儿子的 $R_v+C_v$ 最大值，那么我们可以将除 $x$ 以外的 $d_j$ 置为 $R_v+C_v$，将 $x$ 对应的 $d_j$ 置为除 $x$ 以外的 $R_v+C_v$ 最大值，此时显然有 $d_{\max}-S\le 0$，所以最小值就是 $0$。

否则，无论 $d$ 取何值，$x$ 对应的 $d_j$ 一定是 $d_{\max}$，那么我们一定会将 $x$ 取 $L_x+C_x$，其他儿子 $v$ 取 $R_v+C_v$，这样才能使 $d_{\max}-S$ 最小。

综上，最小值即为 $\max(L_x+C_x-((\sum (R_v+C_v))-(R_x+C_x)),0)$。注意判断该值与最大值奇偶性不同的情况。

最后只需要判断根节点的最小值是否是 $0$ 即可。

时间复杂度 $O(N^2)$。

代码

F - RNG and XOR

题意

有一个随机数生成器，可以生成 $0$ 到 $2^N-1$ 之间的整数，其中生成 $i$ 的概率为 $\frac{A_i}{S}$，其中 $S=\sum A_i$。

有一个变量 $x$，初始为 $0$，每次会异或一个用上述随机数生成器生成的整数。

对于每个 $0\le i < 2^N$，求 $x$ 第一次变成 $i$ 的期望次数。对 $998244353$ 取模。

$N\le 18$。

题解

考虑倒着做，求 $i$ 第一次得到 $0$ 的期望次数，显然与原答案相等。那么有 $f_i= \begin{cases} 1+\sum\limits_{j=0}^{2^N-1}f_jp_{i\oplus j} & \text{ if }i>0 \\ 0 & \text{ if }i=0 \end{cases}$

我们可以把上式写成卷积的形式： $(f_0,f_1,\ldots,f_{2^N-1})\oplus(p_0,p_1,\ldots,p_{2^N-1})=(c,f_1-1,f_2-1,\ldots,f_{2^N-1}-1)$ 其中 $c$ 是一个未知的常数。

注意到上式要满足条件，必须有 $\left(\sum_{i=0}^{2^N-1} f_i\right)\left(\sum_{i=0}^{2^N-1} p_i\right)=c+\sum_{i=1}^{2^N-1}(f_i-1)$

所以有 $c=f_0+2^N-1$。那么上面的卷积式子可以写成 $(f_0,f_1,\ldots,f_{2^N-1})\oplus(p_0,p_1,\ldots,p_{2^N-1})=(f_0+2^N-1,f_1-1,f_2-1,\ldots,f_{2^N-1}-1)$

可以把 $p_0$ 减 $1$ 去掉等式右边的 $f_i$，即 $(f_0,f_1,\ldots,f_{2^N-1})\oplus(p_0-1,p_1,\ldots,p_{2^N-1})=(2^N-1,-1,-1,\ldots,-1)$

那么只要将 $(2^N-1,-1,-1,\ldots,-1)$ 和 $p$ 做 FWT 后对应位置做除法，再 IFWT 回去即可。

注意 $(2^N-1,-1,-1,\ldots,-1)$ 和 $p$ 做 FWT 后有且只有 $0$ 位置的值为 $0$，不能直接做除法。可以先取任意数，最后根据 $f_0=0$ 对所有数整体加即可。

时间复杂度 $O(2^N(N+\log P))$。

代码

更新于：2021年5月29日

贪心

DP

二分

网络流

费用流

集合幂级数

FWT