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);
}
}
一道构造题我为什么要这样做