CF1436B Prime Square 题解
思路就是dfs(x,y)枚举每一个数，找到一组解直接跳出
但是，我们发现这可能行不通:如何找到一组解直接跳出？
先贴代码,运行一下试试，说不定就可以了呢？：
#include<bits/stdc++.h>
#define N 100000
typedef unsigned long long ull;
using namespace std;
int n,cnt,m,t[N+5];
int a[105][105];
void dfs(int x,int y){//dfs
if(a[x-1][y]==-1) return ;//之前已经有解输出了，直接跳出即可
if(x==n+1&&y==n){
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++){
cout<<a[i][j]<<' ';
a[i][j]=-1;//有解，标成-1
}
cout<<endl;
}
return ;
}//达到要求，输出解
for(int i=1;i<=800;i++){//枚举每一个数
if(t[i]==0) continue;
if(x==n){//需要判断此列
int sum=i;
for(int j=1;j<n;j++) sum+=a[j][y];
if(t[sum]==1) continue;//不符合要求，continue
}
if(y==n){//需要判断此行
int sum=i;
for(int j=1;j<n;j++) sum+=a[x][j];
if(t[sum]==1) continue;//不符合要求，continue
}
if(t[i]){//不是素数（如题意）
a[x][y]=i;
if(y==n) dfs(x+1,1);//此行终结，下一行
else dfs(x,y+1); //下一个数
a[x][y]=0;//回溯
}
}
}
int main(){
cin>>cnt;
t[1]=1;//特判：1不是素数
for(int i=2;i<=sqrt(N);i++){
if(t[i]==0){
for(int j=i*2;j<=N;j+=i){
t[j]=1;
}
}
} //埃氏筛法求1~N的素数
while(cnt--){//cnt组数据
cin>>n;
dfs(1,1);
}
}
我们发现：第一组解永远有两种情况：
- 全是1，这种情况当n是素数下成立
- 形如：
这样的解。
所以，我们发现：
只要在
这里加return ;即可
就是说，只要i满足条件，解必定可以进行下去。
code：
#include<bits/stdc++.h>
#define N 100000
typedef unsigned long long ull;
using namespace std;
int n,cnt,m,t[N+5];
int a[105][105];
void dfs(int x,int y){//dfs
if(a[x-1][y]==-1) return ;//之前已经有解输出了，直接跳出即可
if(x==n+1&&y==n){
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++){
cout<<a[i][j]<<' ';
a[i][j]=-1;//有解，标成-1
}
cout<<endl;
}
return ;
}//达到要求，输出解
for(int i=1;i<=800;i++){//枚举每一个数
if(t[i]==0) continue;
if(x==n){//需要判断此列
int sum=i;
for(int j=1;j<n;j++) sum+=a[j][y];
if(t[sum]==1) continue;//不符合要求，continue
}
if(y==n){//需要判断此行
int sum=i;
for(int j=1;j<n;j++) sum+=a[x][j];
if(t[sum]==1) continue;//不符合要求，continue
}
if(t[i]){//不是素数（如题意）
a[x][y]=i;
if(y==n) dfs(x+1,1);//此行终结，下一行
else dfs(x,y+1); //下一个数
return ;
}
}
}
int main(){
cin>>cnt;
t[1]=1;//特判：1不是素数
for(int i=2;i<=sqrt(N);i++){
if(t[i]==0){
for(int j=i*2;j<=N;j+=i){
t[j]=1;
}
}
} //埃氏筛法求1~N的素数
while(cnt--){//cnt组数据
cin>>n;
dfs(1,1);
}
}
一道构造题我为什么要这样做
