NOIP1997数字方阵
题目描述
在N*N的棋盘上（1＜N≤10）填入1,2,…N*N共N*N个数,使得任意两个相邻的数之和为素数.例如,当N=2时,有 ：
|
1
|
2
|
|
4
|
3
|
其相邻数的和为素数的有:1+2,1+4,4+3,2+3。
当N=4时,一种可以填写的方案如下:
|
1
|
2
|
11
|
12
|
|
16
|
15
|
8
|
5
|
|
13
|
4
|
9
|
14
|
|
6
|
7
|
10
|
3
|
在这里我们约定:左上角的格子里必须放数字1。
输入
一个正整数N。
输出
若有多种解,则需输出第一行之和最小，若第一行和相同，则输出第一列之和最小的排列方案;若无解,则输出”No solution”。若有解，第一行为空格分割的两个正整数，分别是该排列方案的第一行、第一列各数字之和。以下n行输出该排列方案，每个数字占4个字符，不足4位的在数字前用空格补齐。
样例输入
2
样例输出
3 5 1 2 4 3
代码
最傻逼的回溯，显然超时
|
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 |
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int n; bool ans=0,used[101]={0}; int a[11][11],b[11][11],h=0x7fffffff,s; bool pm(int x) { if(x%2==0&&x!=2)return 0; if(x%3==0&&x!=3)return 0; if(x%5==0&&x!=5)return 0; if(x%7==0&&x!=7)return 0; if(x%11==0&&x!=11)return 0; return 1; } bool pd(int x,int y,int i) { if(y!=1&&!pm(i+a[x][y-1]))return 0; if(x!=1&&!pm(i+a[x-1][y]))return 0; return 1; } void search(int x,int y) { if(x==n&&y==n) { ans=1; int h1=0,s1=0; for(int i=1;i<=n;i++) { h1+=a[1][i]; s1+=a[i][1]; } if((h1<h)||(h1==h&&s1<s)) { h=h1;s=s1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) b[i][j]=a[i][j]; } } if(x>n||y>n)return; if(y<n)y++; else{x++;y=1;} for(int i=2;i<=n*n;i++) { if(pd(x,y,i)&&!used[i]){used[i]=1;a[x][y]=i;search(x,y);used[i]=0;} } } int main() { cin>>n; a[1][1]=1; search(1,1); if(ans==0)cout<<"No solution"; else { cout<<h<<' '<<s<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) printf("%4d",b[i][j]); cout<<endl; } } return 0; } |
改进一下素数判断和增加剪枝160ms
|
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 |
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n,isprime[201],ansr=10000,ansc=10000,row=1,col=1,mp[11][11],ansmp[11][11]; bool used[101]={0},found=0; bool prime(int x) { if(x%2==0&&x!=2)return 0; if(x%3==0&&x!=3)return 0; if(x%5==0&&x!=5)return 0; if(x%7==0&&x!=7)return 0; if(x%11==0&&x!=11)return 0; return 1; } void trymid(int x,int y) { if(found) return; if(x>n) {ansr=row;ansc=col; for(int i=1;i<=10;i++) for(int j=1;j<=10;j++) ansmp[i][j]=mp[i][j]; found=1;return;} else for(int i=2;i<=n*n;i++) if(isprime[mp[x-1][y]+i]&&isprime[mp[x][y-1]+i]&&used[i]==0) { used[i]=1; mp[x][y]=i; if(y==n) trymid(x+1,2); else trymid(x,y+1); used[i]=0; } return; } void trycol(int x) { if(x>n) if(row<ansr||row==ansr&&col<ansc) {found=0;trymid(2,2);found=0;} else return; else { for(int i=2;i<=n*n;i++) if(isprime[mp[x-1][1]+i]&&used[i]==0) { used[i]=1; col=col+i; mp[x][1]=i; trycol(x+1); col=col-i; used[i]=0; } } } void tryrow(int y) { if(y>n) if(row<=ansr) {trycol(2);} else return; else { for(int i=2;i<=n*n;i++) if(isprime[mp[1][y-1]+i]&&used[i]==0) { used[i]=1; row=row+i; mp[1][y]=i; if(row<=ansr) tryrow(y+1); row=row-i; used[i]=0; } } return; } int main() { cin>>n; for(int i=1;i<=2*n*n;i++) isprime[i]=prime(i); mp[1][1]=1;used[1]=1; tryrow(2); if(ansr==10000) { cout<<"No solution"<<endl; return 0; } cout<<ansr<<" "<<ansc<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) printf("%4d",ansmp[i][j]); cout<<endl; } return 0; } |
计数器 9734105
OI 课件=>
OI 课件=>
学长解释一下啊，现在的程序就是过不了。
忘了。。