题解：P12058 [THUPC 2025 决赛] 三元链

· · 题解

考虑令黑格在第一列平均分配，即把第一列的第 i 个黑格放在 (\lfloor\frac{i\cdot n}{k}\rfloor,1) 上。然后令第 i 列是第 i-1 列向下做一次循环移位后的结果。大胆猜测只要这样做出来的网格不合法就无解。

这样做可以非常自然地处理 corner case！

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int T, n, k;
int a[maxn][maxn];
void work() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = 0;
    for (int i = 1; i <= k; i++) a[i * n / k][1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < n; j++) a[j][i] = a[j + 1][i - 1];
        a[n][i] = a[1][i - 1];
    }
    for (int i = 1; i <= n - 2; i++)
        for (int j = 1; j <= n; j++)
            if (a[i][j] == a[i + 1][j] && a[i][j] == a[i + 2][j]) {cout << "No" << '\n'; return;}
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n - 2; j++)
            if (a[i][j] == a[i][j + 1] && a[i][j] == a[i][j + 2]) {cout << "No" << '\n'; return;}
    for (int i = 1; i < n; i++) {
        int p = 1, q = 1;
        for (int j = 1; j <= k; j++) {
            while (a[p][i] == 0) p++;
            while (a[q][i + 1] == 0) q++;
            if (abs(p - q) > 1) {cout << "No" << '\n'; return;}
        }
    }
    cout << "Yes" << '\n';
    for (int i = 1; i <= n; i++, cout << '\n')
        for (int j = 1; j <= n; j++)
            cout << (a[i][j] ? '#' : '.');
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) work();
    return 0;
}