Codeforces - 1208 - Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

http://codeforces.com/contest/1208

C. Magic Grid

一开始想着直接排，结果20的时候纵向就翻车了。但4个连续自然数一组的思路是没问题的。一个偶然的机会，发现其实相差是纵向4的几个异或起来也是0。所以就是16个连续自然数一组自由构造。

来一个迷惑性极强的构造法：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int tg[5][5];
int g[1005][1005];

void Init() {
    int cnt = 0;
    for(int i = 1; i <= 4; ++i) {
        for(int j = 1; j <= 4; ++j) {
            tg[i][j] = cnt++;
        }
    }
}

void Random() {
    int r = rand() % 4 + 1;
    for(int i = 1; i <= 4; ++i) {
        swap(tg[i][1], tg[i][r]);
    }
    r = rand() % 4 + 1;
    for(int i = 1; i <= 4; ++i) {
        swap(tg[i][2], tg[i][r]);
    }
    r = rand() % 4 + 1;
    for(int j = 1; j <= 4; ++j) {
        swap(tg[1][j], tg[r][j]);
    }
    r = rand() % 4 + 1;
    for(int j = 1; j <= 4; ++j) {
        swap(tg[2][j], tg[r][j]);
    }
}

int Draw(int x, int y, int b) {
    Random();
    for(int i = 1; i <= 4; ++i) {
        for(int j = 1; j <= 4; ++j) {
            g[x + i - 1][y + j - 1] = tg[i][j] + 16 * b;
        }
    }
}

int bs[1000 * 1000 / 16 + 5];

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int n;
    Init();
    while(~scanf("%d", &n)) {
        int c = n * n / 16;
        for(int i = 1; i <= c; ++i) {
            bs[i] = i - 1;
        }
        random_shuffle(bs + 1, bs + 1 + c);
        int cnt = 1;
        for(int i = 1; i <= n / 4; ++i) {
            for(int j = 1; j <= n / 4; ++j) {
                Draw(4 * (i - 1) + 1, 4 * (j - 1) + 1, bs[cnt++]);
            }
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                printf("%d%c", g[i][j], " \n"[j == n]);
            }
        }
    }
}

效果如下图，太有趣liao。

Codeforces - 1208 - Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

原文：https://www.cnblogs.com/Inko/p/11411315.html