ARC 131 题解

KING_OF_TURTLE · 2021-12-06 08:24:51 · 个人记录

ARC131 题解

直接因为考场上没想到 C 而输麻。

A,B:

略

C:

你有一个长度为 n 的数组 a , 现在进行一次博弈：

每个人可以删除其中一个数，若剩下的数异或和为 0 则胜利，问最后先手胜负。

分析：

下设 n 个数的异或和为 sum

先给出结论：若 n 为奇数，则先手必胜，否则若 \exist i ，使得 sum = a_i ，则先手胜，否则后手胜。

• 对于 n 为奇数的情况：

  首先证明游戏不会在刚好两轮结束：

  反证若可行，则对任意 a_i ，都可以找到 a_j 使得 a_i \bigoplus a_j = sum。

  若是两两配对，那么会有一个落单使得出现重复。所以只考虑有重复的情况，即：

  所以，推广可以得到游戏会在奇数次内结束，即先手胜利。

• 对于 n 为偶数的情况：

  如果先手不能一次取胜，那么就相同与奇数的情况。

  故先手必须一次取胜。

时间复杂度 O(n) 或 O(n \log n) 。

D:

有 n 支箭和 2m+1 种区域，分割点从左到右为 r_i ，r_i 与 r_{2m-i+1} 在数轴上关于对称。这 n 支箭的距离至少为 d 。

给定 r_{m+1} 到 r_{2m} ，以及每种区域的分值 s_i（也是对称的）。

分析：

首先，所有射出去的箭尽量挨在一起，由于 s 的单调性，不会更劣。

注意到靶子是左右对称的，所以我们分左右考虑。对于每一个区域，按照模d的余数将其分成d个区域，只需计算哪个区域最大。两个区域有差别当且仅当有一个区域贴到了边界。我们钦定第一支箭在原点，看偏移 x 位后多出的得分即可。

使用差分，计算的时候更方便。一个区域最多有两种通过箭数的情况，一定最优。

最后再枚举中间箭的位置，看正部分多算的分和负部分的分加起来最大值即可。

时间复杂度 O(m+d) 。

E:

给定一个 n ，构造一个完全图染色方案，满足下列性质：

• 不存在异色三角形（即三条边颜色都不同）
• 每种颜色数量相等

分析：

首先因为第二条性质，若 n \equiv 2 \pmod 3 ，则不满足条件。

对于剩下的，除了 n \leq 4 都满足条件。方案如下（ 以n = 9为例子 ）：

我们设两种颜色为主要颜色，比如上图的红和黑。按照如下的方式进行构造：

• 从 1 号点，黑色开始 , 向每个点连边，颜色换着来。
• 如果还有剩余边则跳过。否则进入特判。

特判：注意一定是黑色先连完。设最后一次黑色连了 x 条，还差 y 条，在上图中 x=4,y=2 。那么用红色边分别填充两部分，连过的和没连过的。最多可以连

（那为什么数据范围是 50 ??? ，学习 Topcoder 了属于是）

F:

不会。

总体评价：

感觉E题明显比D题简单的多？