【UVA-10087】The Tajmahal of ++Y2k【幻方构造】

【UVA-10087】The Tajmahal of ++Y2k【幻方构造】

问题链接:https://vjudge.net/problem/UVA-10087

Solution:

关于幻方构造,阅读:幻方的构造方法

除了二阶幻方不存在外,这道题只要在判断要求的一个方向上所有数的和减去标准幻方一个方向上所有数的和【标准幻方求和公式,对于n阶幻方,\(Sum = \frac{n * (n^2 + 1)}{2}】后是否是[latex]n^2\)的倍数就好,如果是,则可以通过给每个方格加上相同的一定数,获得要求的方阵。

#include <iostream>

using namespace std;

typedef long long LL;
const int LIM = 101;
struct Matrix {
    int v[LIM][LIM];
    int size;
};

inline LL getSum(LL n) {
    return n * (n * n + 1) / 2;
}

Matrix odd_msquare(int n) {
    Matrix ret = {{0}, n};
    int lim = n * n;
    int r = 0, c = n / 2;
    for (int i = 1; i <= lim; i++) {
        ret.v[r][c] = i;
        int nr = (r - 1 + n) % n;
        int nc = (c + 1 + n) % n;
        if (ret.v[nr][nc]) r++;
        else r = nr, c = nc;
    }
    return ret;
}

inline void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

Matrix m4_msquare(int n) {
    Matrix ret = {{0}, n};
    int crt = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ret.v[i][j] = crt;
            crt++;
        }
    }
    int lim = n / 2;
    for (int i = 0; i < lim; i += 4) {
        for (int j = 0; j < n; j += 4) {
            if (i + 2 == lim && j > lim) break;
            if (j + 2 == lim && i + 2 == lim) {
                for (int k = 0; k < 2; k++) {
                    for (int m = 0; m < 4; m++) {
                        if (k == m || k == 4 - m - 1)
                            swap(ret.v[i + k][j + m], ret.v[n - 1 - (i + k)][n - 1 - (j + m)]);
                    }
                }
            } else {
                for (int k = 0; k < 4; k++) {
                    for (int m = 0; m < 4; m++) {
                        if (k == m || k == 4 - m - 1)
                            swap(ret.v[i + k][j + m], ret.v[n - 1 - (i + k)][n - 1 - (j + m)]);
                    }
                }
            }
        }
    }
    return ret;
}

Matrix m4p2_msquare(int n) {
    int m = (n - 2) / 4;
    Matrix tmp = odd_msquare(n / 2), ret = {{0}, n};
    for (int i = 0; i < tmp.size; i++)
        for (int j = 0; j < tmp.size; j++)
            tmp.v[i][j] = tmp.v[i][j] * 4 - 4;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j < tmp.size; j++) {
            ret.v[i << 1][j << 1] = 4 + tmp.v[i][j];
            ret.v[i << 1][(j << 1) + 1] = 1 + tmp.v[i][j];
            ret.v[(i << 1) + 1][j << 1] = 2 + tmp.v[i][j];
            ret.v[(i << 1) + 1][(j << 1) + 1] = 3 + tmp.v[i][j];
        }
    }
    ret.v[m << 1][tmp.size - 1] = 1 + tmp.v[m][tmp.size >> 1];
    ret.v[m << 1][tmp.size] = 4 + tmp.v[m][tmp.size >> 1];
    ret.v[(m << 1) + 1][tmp.size - 1] = 2 + tmp.v[m][tmp.size >> 1];
    ret.v[(m << 1) + 1][tmp.size] = 3 + tmp.v[m][tmp.size >> 1];
    for (int j = 0; j < tmp.size; j++) {
        ret.v[(m + 1) << 1][j << 1] = 1 + tmp.v[m + 1][j];
        ret.v[(m + 1) << 1][(j << 1) + 1] = 4 + tmp.v[m + 1][j];
        ret.v[((m + 1) << 1) + 1][j << 1] = 2 + tmp.v[m + 1][j];
        ret.v[((m + 1) << 1) + 1][(j << 1) + 1] = 3 + tmp.v[m + 1][j];
    }
    ret.v[(m + 1) << 1][tmp.size - 1] = 4 + tmp.v[m + 1][tmp.size >> 1];
    ret.v[(m + 1) << 1][tmp.size] = 1 + tmp.v[m + 1][tmp.size >> 1];
    ret.v[((m + 1) << 1) + 1][tmp.size - 1] = 2 + tmp.v[m + 1][tmp.size >> 1];
    ret.v[((m + 1) << 1) + 1][tmp.size] = 3 + tmp.v[m + 1][tmp.size >> 1];
    for (int i = m + 2; i < tmp.size; i++) {
        for (int j = 0; j < tmp.size; j++) {
            ret.v[i << 1][j << 1] = 1 + tmp.v[i][j];
            ret.v[i << 1][(j << 1) + 1] = 4 + tmp.v[i][j];
            ret.v[(i << 1) + 1][j << 1] = 3 + tmp.v[i][j];
            ret.v[(i << 1) + 1][(j << 1) + 1] = 2 + tmp.v[i][j];
        }
    }
    return ret;
}

int main(void) {
    LL s;
    int n;
    Matrix ans;
    while (~scanf("%d%lld", &n, &s)) {
        if (n == 1) printf("%10lld\n", s);
        else if (n == 2) printf("You can't be like Shahjahan!\n");
        else {
            LL diff = s - getSum(n);
            if (diff % n) printf("You can't be like Shahjahan!\n");
            else {
                LL add = diff / n;
                if (n % 2) {
                    ans = odd_msquare(n);
                } else {
                    if (n % 4) ans = m4p2_msquare(n);
                    else ans = m4_msquare(n);
                }
                for (int i = 0; i < ans.size; i++) {
                    for (int j = 0; j < ans.size; j++) {
                        if (j) putchar(' ');
                        printf("%10lld", ans.v[i][j] + add);
                    }
                    putchar('\n');
                }
            }
        }
        putchar('\n');
    }
    return 0;
}