不难猜想有解充要条件为 \(n \ge 5\) 且 \(\frac{n(n-1)}{2} \bmod 3 = 0\)。
发现如果钦定一个点的出边都为同一种颜色,那么条件 \(2\) 一定满足。
那么题目等价于把 \(\{0,1,...,n-1\}\) 分成 \(3\) 组使得每组的和相等。
这个东西可以随便 dp 做,也不难发现若满足有解的充要条件则一定能找到一组合法的分组方案。
code
// Problem: E - Christmas Wreath
// Contest: AtCoder - AtCoder Regular Contest 131
// URL: https://atcoder.jp/contests/arc131/tasks/arc131_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 55;
int n, m, g[maxn][410][410], a[maxn];
bool f[maxn][410][410];
void solve() {
scanf("%d", &n);
if (n <= 4 || (n * (n - 1) / 2) % 3) {
puts("No");
return;
}
m = n * (n - 1) / 6;
f[0][0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int x = 0; x <= m; ++x) {
for (int y = 0; y <= m; ++y) {
if (!f[i][x][y]) {
continue;
}
if (x + i <= m) {
f[i + 1][x + i][y] = 1;
g[i + 1][x + i][y] = 1;
}
if (y + i <= m) {
f[i + 1][x][y + i] = 1;
g[i + 1][x][y + i] = 2;
}
f[i + 1][x][y] = 1;
g[i + 1][x][y] = 3;
}
}
}
int x = m, y = m;
for (int i = n; i; --i) {
a[n - i + 1] = g[i][x][y];
if (a[n - i + 1] == 1) {
x -= i - 1;
} else if (a[n - i + 1] == 2) {
y -= i - 1;
}
}
puts("Yes");
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
putchar(a[i] == 1 ? 'R' : (a[i] == 2 ? 'B' : 'W'));
}
putchar('\n');
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Christmas AtCoder Regular Contest Wreathchristmas atcoder regular contest christmas beginner atcoder contest atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest builder