题解：P17220 [ICPC 2017 Nanning R] Rearrangement

· · 题解

题解：P17220 [ICPC 2017 Nanning R] Rearrangement

啊哈哈哈，比赛当天我因为【数据删除】没做这个比赛。

题意

在一个 2×n 的数组中，重新排列这些整数，有没有可能使得任意相邻俩数之和不能被 3 整除。

思路

首先，我们将所有数字对 3 取模，余数只可能是 0,1,2。

题目要求相邻两数之和不能被 3 整除，这意味着：

由于 1 和 2 不能相邻，而 0 可以和 1、2 相邻，我们可以把 0 当墙。

[1] [1] ... [1] [0] [0] ... [0] [2] [2] ... [2]
[1] [1] ... [1] [0] [0] ... [0] [2] [2] ... [2]

条件：

  1. 但 0 不能太多，不然根据鸽巢原理 0 和 0 就会相邻，显然 NO。

  2. 如果矩阵中既没有 1 也没有 2，或者只有 1，或者只有 2，那么只要满足条件一，就一定能构造成功，输出 YES。

  3. 如果既有 1 又有 2，我们就必须用 0 来隔离它们。

    • 如果 cnt_0 \le 1：墙不够，输出 NO。
    • 如果 cnt_0 \ge 3：墙足够，输出 YES。
    • 如果 cnt_0 = 2：两个 0 最多能形成 3 个区域（左、中、右）。为了不让 1 和 2 碰面，必须把 1 全放左边，2 全放右边。

    此时，上下两行是对称的。如果 cnt_1 是偶数且 cnt_2 是偶数，那么左右两侧的 1 和 2 都能完美填满上下两行。这会导致两个 0 必须放在同一列的上下位置才能隔开左右，但 0 和 0 上下相邻是不合法的！因此，当 cnt_0=2 且 cnt_1 和 cnt_2 都是偶数时，输出 NO，其余情况输出 YES。

代码

#include <stdio.h>
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        int a = 0, b = 0, c = 0;
        for (int i = 0; i < 2 * n; i++) {
            int x;
            scanf("%d", &x), x % 3 ? x % 3 > 1 ? c++ : b++ : a++;
        }
        int o;
        o = a > n ? 0 : a < 2 ? b == 0 || c == 0 : a == 2 ? !(b % 2 == 0 && c % 2 == 0) : 1, puts(o ? "YES" : "NO");
    }
    return 0;
}