3 月 23 日 AtCoder Grand Contest 032
比赛链接:https://atcoder.jp/contests/agc032

B – Balanced Neighbors

思路:
当 $n$ 为偶数时,可以把点 $(i,n-i+1)$ 配对,然后每个点向与它一对之外的所有点连边;当 $n$ 为奇数时,把点 $(i,n-i)$ 配对,同样每一点向与它一对之外的所有点连边(包括 $n$ )。

代码链接

C – Three Circuits

思路:

因为是连通图,你可以把三个环拼成一条欧拉回路,因此如果这张图含有奇度数的点,则一定不存在构造方案。如果有一个点的度数大于等于 $6$,代表着这条欧拉回路经过了这个点至少 $3$ 次,而每一次都可以形成一个环,所以这样是一定存在构造方案的。

经过上面讨论后,剩下的图只有度数为 $4$ 和度数为 $2$ 的点。如果一张图度数为 $4$ 的点大于等于 $3$ 个,那么所有构成环的情况分为下面两种:存在一条路径从一个度数为 $4$ 的点出发,不经过其他度数为 $4$ 的点并且回到出发点;一条路径经过两个度数为 $4$ 的点一次,并形成了环。可以发现这样的图至少存在 $3$ 个环。

剩下的情况中如果度数为 $4$ 的点少于两个,那么显然是不存在构造方案的。如果度数为 $4$ 的点恰有两个,就只有下图两种情况,只有这张图的最小割为 $2$ 时才存在构造方案。所以可以用一个 BFS,模拟一下最大流的过程判断这张图的割。

AtCoder Grand Contest 032 解题报告 1

代码链接

D – Rotation Sort

思路:

首先转换一下题意,题目中的一次操作可以看成:从序列中取出一个元素,将它插入前面或后面的一个位置,分别花费 $A$ 或 $B$ 的代价。不难发现每一个元素最多会被操作一次,且有些元素不会被操作。我们就可以从这入手设计 DP 状态。设 $f_{i,j}$ 表示处理完前 $i$ 个数且最后一不会被操作的数为 $j$ 所花费的最小代价,然后根据题意简单地转移一下就好。

代码链接

E – Modulo Pairing

思路:

假设 $lim$ 已知,考虑对于数 $x$,我们要找到一个 $y$ 与它配对,使得 $x+y$ 在模 $m$ 意义下不超过 $lim$。如果 $x+y<m$,那么 $y$ 最大可以取 $lim-x-1$;如果 $x+y>m$,那么 $y$ 最大可以取 $lim+m-x$。我们让 $y$ 在对应的取值范围内选尽量大的数一定不会更劣,所以假如对于一个 $x$,我们决定了与它配对的 $y$ 与 $m-x$ 的关系,那么 $y$ 的值我们也可以确定。

考虑这样一个结论:将所有数排好序后,设最大值为 $x_{max}$,如果一个数 $x$ 大于 $m-x_{max}$,那么与它配对的 $y$ 就一定比 $m-x$ 大;否则一定比 $m-x$ 小。这样以来我们就可以二分出一个位置 $pos$,在 $pos$ 左边的数两两配对小于 $m$,在 $pos$ 右边的数两两配对不小于 $m$。确定出 $pos$ 后,答案就可以跟着确定下来。

对于结论的正确性,我们可以对所有情况进行讨论。设蓝色的线为小于 $m$ 的匹配,红色的线为不小于 $m$ 的匹配,根据下图可以发现该结论对于所有情况均成立:

AtCoder Grand Contest 032 解题报告 2

代码链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注