更新历史

更新历史

2023-09-06

发布博客

洛谷传送门

CF 传送门

题意

给你 n2n^2 个数，用这些数构成一个 nn 阶幻方，保证有解。

nn 阶幻方的定义：一个 nn 阶矩阵，满足每一行，每一列，每一条对角线的和都相等。

思路

注意到 n≤4n \le 4，自然想到爆搜。但普通爆搜是 (n2)!(n^2)! 的，肯定过不了，所以想到剪枝。

先是一个最能够想到的剪枝：

由于保证有解，所以可以算出每一行，每一列，每一条对角线的和。

那么每一行和每一列的最后一个数都不需要搜索，而是直接通过前面的算出。

于是我们爆搜的区域就从 n2n^2 变成了 (n−1)2(n-1)^2。

然后你写出了代码，满怀信心地交上去，发现你成功的在第 18 个点 T 掉了。

通过获取第 18 个点的数据放在本地跑， 我们发现它 T 的不是太严重，就多了不到一秒，所以需要一些玄学的优化。

设最终幻方为 pp，由于 ∑i=1npi,1=∑i=1npi,n−i+1\sum_{i=1}^{n} p_{i,1}=\sum_{i=1}^{n} p_{i,n-i+1}，即第一列的和等于副对角线的和，那么 ∑i=1n−1pi,1=∑i=1n−1pi,n−i+1\sum_{i=1}^{n-1} p_{i,1}=\sum_{i=1}^{n-1} p_{i,n-i+1}，从而 pn−1,2=∑i=1n−1pi,1−∑i=1n−2pi,n−i+1p_{n-1,2}=\sum_{i=1}^{n-1} p_{i,1}-\sum_{i=1}^{n-2} p_{i,n-i+1}。

也就是说 pn−1,2p_{n-1,2} 的值也是确定的，那就可以少枚举一个点，然后就可以顺利 A 掉这道题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[20],sum;//sum代表每一行，每一列，每一条对角线的和 
int vis[114520];//哈希后的桶 
int p[10][10];//最终矩幻方 
int Hash(int x){//恶臭的哈希函数 
    return ll(1ll*(x+1e8)*(x+1e8))%114514;
}
void dfs(int x,int y){
    if(x==n){//最后一行的填数 
        int tmp1=0,tmp2=0,tmp3=0,tmp4=0;//分别代表：忽略第n行的数，主对角线的和，副对角线的和，第一列的和，第n列的和
        for(int i=1;i<n;i++){
            tmp1+=p[i][i],tmp2+=p[i][n-i+1],tmp3+=p[i][1],tmp4+=p[i][n];
        }
        if(tmp1!=tmp4||tmp2!=tmp3){//判断不可能情况 
            return;
        }
        for(int i=1;i<=n;i++){//填最后一行的数 
            int tmp=sum;
            for(int j=1;j<n;j++){
                tmp-=p[j][i];
            }
            int tmpp=Hash(tmp);
            if(!vis[tmpp]){//找不到，回溯 
                for(int j=1;j<i;j++){
                    vis[Hash(p[n][j])]++;
                }
                return;
            }
            vis[tmpp]--,p[n][i]=tmp;
        }
        printf("%d\n",sum);//成功找到解 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                printf("%d ",p[i][j]);
            }
            printf("\n");
        }
        exit(0);
    }
    if(y==n){//最后一列的填数 
        int tmp=sum;
        for(int i=1;i<n;i++){
            tmp-=p[x][i];
        }
        int tmpp=Hash(tmp);
        if(!vis[tmpp]){//找不到，回溯 
            return;
        }
        vis[tmpp]--,p[x][n]=tmp;
        dfs(x+1,1);
        vis[tmpp]++;
        return;
    }
    if(x==n-1&&y==2){//位置(n-1,2)的填数 
        int tmp=0;
        for(int i=1;i<n;i++){
            tmp+=p[i][1];
        }
        for(int i=1;i<n-1;i++){
            tmp-=p[i][n-i+1];
        }
        int tmpp=Hash(tmp);
        if(!vis[tmpp]){//找不到，回溯 
            return;
        }
        vis[tmpp]--,p[x][y]=tmp;
        dfs(x,y+1);
        vis[tmpp]++;
        return;
    }
    for(int i=1;i<=m;i++){
        int tmpp=Hash(a[i]);
        if(vis[tmpp]){
            vis[tmpp]--,p[x][y]=a[i];
            dfs(x,y+1);
            vis[tmpp]++;
        }
    }
}
int main(){
    scanf("%d",&n);
    m=n*n;
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
        vis[Hash(a[i])]++;
    }
    sum/=n;
    dfs(1,1);
    return 0;
}