ARC 补题目录

前言

翻译有误，给边染色应当是 RBW 三色，而不是 RGB 三色。
我码风较为抽象，所以添加了一些注释。
发现题解区只有一份和我思路相同的题解，但讲解得不是很详细，所以我又写了一篇 QwQ。

一道非常巧妙的构造题。不敢相信这是自己手推出来的。

题目翻译

给定一个完全无向图，要求用 RBW 对每条边进行染色，使得三种颜色的边数一样，且不存在三个点使得对应的三条边颜色均不相同。

题目讲解

分两类情况讨论——有解和无解。

无解判定

注意到总边数是 $\frac{n(n-1)}{2}$，而又需要保证 RBW 三种颜色数量相同，所以边数必须是 $3$ 的倍数，因此 $n \equiv 2 (\bmod 3)$ 的时候无解。
另外 $n \leq 4$ 的时候也无解，这个手推一下就知道了。

构造思路

我是先想到构造方法再证明的……
构造方法：对于每一个点 $i$，向 $[1,i)$ 中所有点连相同颜色的边。
它为什么是对的？原因是对于一个点 $i$，它与它前面两个点 $j,k$ 组成三元环。但由于 $(j,i)$ 和 $(k,i)$ 同色，所以一定不会出现三条边颜色不同的情况。

发现 $i$ 需要往前面连接 $i-1$ 条边。那么问题就转化为：你需要把 $[0,n-1]$ 总共 $n$ 个数分成 $3$ 组，使得每一组的和相等。

如何分组

看到数据范围 $n \leq 50$ 大喜。你会发现总边数是 $\frac{n(n-1)}{2} = 1225$。
我们使用最暴力的分组想法：设 $f_{i,j,k}$ 表示给前 $[0,i)$ 分配完了，第一组之和 $j$，第二组之和 $k$，第三组之和 $\frac{i(i-1)}{2}-j-k$，是否可行。

会发现这样的空间复杂度是 $O(n^5)$ 的，但是由于有 $\frac{1}{4}$ 的常数能开的下。时间复杂度也能过。

然后我们考虑主动转移，并且记录 $pre_{i,j,k}$ 表示哪一组加入了数字 $i$。
最后倒着推回去就可以求出方案，于是乎问题就解决了。

注意事项

要输出 Yes 再输出方案，不然会喜提 WA。

代码

由于调试的时候心态比较崩，所以码风较为抽象。
大家凑合着看吧 QwQ。

#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = 1300;
bool f[N][M][M];
struct node {
    int a, b, c;
} pre[N][M][M];
int a[N], b[N], c[N];
int x, y, z;

int ans[N][N];

char get(int x) {   //输出对应字符（是 RBW 不是 RGB）
    if (x == 1) return 'R';
    if (x == 2) return 'B';
    if (x == 3) return 'W';
}

int main() {
    int n; cin >> n;
    if (n % 3 == 2 || n <= 4) return puts("No"), 0; //特判无解
    f[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        int s = (i - 1) * i / 2;
        for (int j = 0; j <= s; j++)
            for (int k = 0; k <= s; k++) {
                if (!f[i][j][k]) continue;
                //主动转移。条件当然是 f[i][j][k] 可行。
                f[i + 1][j + i][k] |= 1, pre[i + 1][j + i][k] = (node){i, 0, 0};
                f[i + 1][j][k + i] |= 1, pre[i + 1][j][k + i] = (node){0, i, 0};
                f[i + 1][j][k] |= 1, pre[i + 1][j][k] = (node){0, 0, i};
                //根本不用担心 pre 会被重复覆盖，毕竟只要有一条合法路径就可以了。
                // if (f[i][j][k]) cout << '\t' << i << ' ' << j << ' ' << k << ' ' << i * (i - 1) / 2 - j - k << endl;
            }
    }
    int s = (n - 1) * n / 2;
    if (s % 3 != 0) return puts("No"), 0;   //保险特判无解
    else {
        // cout << f[n][s / 3][s / 3] << endl;

        //a, b, c 表示每一组分配到了哪些数。
        //x, y, z 表示每一组有多少个数。
        int A = s / 3, B = s / 3, C = s / 3, cnt = n;
        //A, B, C 表示当前每一组之和。
        while (A || B || C) {
            node now = pre[cnt][A][B];
            if (now.a) A -= now.a, a[++x] = cnt - 1;
            else if (now.b) B -= now.b, b[++y] = cnt - 1;
            else C -= now.c, c[++z] = cnt - 1;
            //模拟现在从每一组中“删除”数字。
            cnt--;
        }
    }
    //把每一组的数字转化为图。
    for (int i = 1; i <= x; i++) {
        int p = n - 1 - a[i] + 1;
        for (int j = 1; j <= n - p; j++) ans[p][j] = 1;
    }
    for (int i = 1; i <= y; i++) {
        int p = n - 1 - b[i] + 1;
        for (int j = 1; j <= n - p; j++) ans[p][j] = 2;
    }
    for (int i = 1; i <= z; i++) {
        int p = n - 1 - c[i] + 1;
        for (int j = 1; j <= n - p; j++) ans[p][j] = 3;
    }
    puts("Yes");    //因为这个 WA 了一发。
    for (int i = 1; i < n; i++, putchar('\n'))
        for (int j = 1; j <= n - i; j++) putchar(get(ans[i][j]));
    return 0;
}