In the square below, each row, each column and the two diagonals can be read as a five digit prime number. The rows are read from left to right. The columns are read from top to bottom. Both diagonals are read from left to right.
+---+---+---+---+---+ | 1 | 1 | 3 | 5 | 1 | +---+---+---+---+---+ | 3 | 3 | 2 | 0 | 3 | +---+---+---+---+---+ | 3 | 0 | 3 | 2 | 3 | +---+---+---+---+---+ | 1 | 4 | 0 | 3 | 3 | +---+---+---+---+---+ | 3 | 3 | 3 | 1 | 1 | +---+---+---+---+---+
A single line with two space-separated integers: the sum of the digits and the digit in the upper left hand corner of the square.
11 1
Five lines of five characters each for each solution found, where each line in turn consists of a five digit prime number. Print a blank line between solutions. If there are no prime squares for the input data, output a single line containing "NONE".
The above example has 3 solutions.
11351 14033 30323 53201 13313 11351 33203 30323 14033 33311 13313 13043 32303 50231 13331
序言：总算AC了。我花了一个半小时编完了程序，又花了两个小时调试程序，眼睛都花了。尽管在种种挫折前，我屡次萌生“放弃此题，随便贴个代码”的想法，但最终还是挺过去了。
这种方阵题很是多见。原来我都是直接暴力地顺序枚举（准确地说是有顺序枚举）。在这个题目面前，效率显然是非常低的。经过很长时间的探索，我总结出了一张枚举顺序的图。
枚举的顺序要遵循3个原则：①控制位置多的先来，以便剪枝。②相对有些规律，不要杂乱无章。③有些数字可以通过计算出来，无需枚举。（即图中的粉红数字，共12个）
但是问题很快就出来了：这样不就不能有规律地递归了吗？
为了不TLE，我毅然打起了13（25-12）个循环。
刚开始的时候，我开了xie1-xie2，hang1-hang5,lie1-lie5这些变量来分别记录各块的数字和。（以下为某处代码）
for (i2=1;i2<=5;i2++)
{
a[5][1]=mei[i2];lie1=a[1][1]+a[5][1];hang5=a[5][1]+a[5][5];if (hang5>sum||lie1>sum) break;
这个很实用。举个例子，xie1代表从左上到右下的（部分）数字和。这样，我不仅第6次枚举时把第8块的区域值算出来，还可以在之前的某处来个剪枝（比如，枚举到第5块方格时，若xie1=a[1][1]+a[5][5]+a[3][3]>sum(sum为给定的各块的数字和）时，直接跳掉）。我们还能看出这个剪枝很有效——由样例输出可知，大的个位数字几乎不曾出现。
然而这是有问题的。假设xie1累加后在某处直接break掉，它的值是不会改变的。下一次枚举另外一个数字时，xie1会继续加上。要避免问题，不能在循环里改变值，而要在函数里带入形参。很明显，这是不现实的。
就没有解决方案了吗？我想了一会，改了一些地方。如刚才的代码：
for (i1=1;i1<=5;i1++)
{
a[5][5]=mei[i1];xie1=a[1][1]+a[5][5];if (xie1>sum) {xie1=0;break;}
for (i2=1;i2<=5;i2++)
{
a[5][1]=mei[i2];lie1=a[1][1]+a[5][1];hang5=a[5][1]+a[5][5];if (hang5>sum||lie1>sum) {hang5=0;lie1=0;break;}这好像递归中的回溯操作。
但是问题又来了：如果当时i1的值是5,而且到i2时被break掉了，那么xie1的值不能被减掉！
思考再三，我只好采用直接赋值的方法，放弃每次+=的优化方法，也减掉了一些剪枝。
还好，我最终成功了！
代码：
/* PROG:prime3 ID:juan1973 LANG:C++ */#include<stdio.h> #include<cstring> #include<cmath> using namespace std; const int maxn=500+5; int mei[6]={0,1,3,5,7,9}; int a[6][6],i1,i2,i3,jj,j2,j3,j4,k1,k2,p1,p2,p3,p4,p5,p6,sum,p,up,cnt,i,j,k,min,ans[maxn][6][6],num[maxn]; int hang1,hang2,hang3,hang4,hang5,lie1,lie2,lie3,lie4,lie5,xie1,xie2; bool f[10][10][10][10][10],flag[maxn]; void first() //预处理10000-99999之间的质数 { int w1,w2,w3,w4,w5,s; memset(f,1,sizeof(f)); for (int i=2;i<=trunc(sqrt(99999));i++) for (int j=10000/i;j<=99999/i;j++) { s=i*j;w5=s%10;s=s/10; w4=s%10;s=s/10; w3=s%10;s=s/10; w2=s%10;s=s/10; f[s][w2][w3][w4][w5]=false; } } bool xiao(int p,int q) //比大小，用于排序 { for (int i=1;i<=5;i++) for (int j=1;j<=5;j++) if (ans[p][i][j]<ans[q][i][j]) return true; else if (ans[p][i][j]>ans[q][i][j]) return false; } int main() { freopen("prime3.in","r",stdin); freopen("prime3.out","w",stdout); scanf("%ld%ld",&sum,&p); a[1][1]=p;up=9;if (sum<up) up=sum; first(); for (i1=1;i1<=5;i1++) { a[5][5]=mei[i1]; for (i2=1;i2<=5;i2++) { a[5][1]=mei[i2]; for (i3=1;i3<=5;i3++) { a[1][5]=mei[i3]; for (p1=0;p1<=up;p1++) { a[3][3]=p1; if (a[1][1]+a[5][5]+a[3][3]>sum||a[5][1]+a[1][5]+a[3][3]>sum) continue; for (p2=0;p2<=up;p2++) { a[4][4]=p2; if (a[5][5]==1&&a[5][1]==1&&a[1][5]==3&&a[3][3]==3&&a[4][4]==3) a[3][3]=3; xie1=a[1][1]+a[5][5]+a[3][3]+a[4][4];if (xie1>sum) continue; a[2][2]=sum-xie1; /*1-------*/if (a[2][2]<0||a[2][2]>9||!f[a[1][1]][a[2][2]][a[3][3]][a[4][4]][a[5][5]]) continue; for (p3=0;p3<=up;p3++) { a[4][2]=p3; if (a[5][5]==1&&a[5][1]==1&&a[1][5]==3&&a[3][3]==3&&a[4][4]==3&&a[4][2]==0) a[3][3]=3; xie2=a[5][1]+a[1][5]+a[3][3]+a[4][2];if (xie2>sum) continue; /*2-------*/ a[2][4]=sum-xie2;if (a[2][4]<0||a[2][4]>9||!f[a[5][1]][a[4][2]][a[3][3]][a[2][4]][a[1][5]]) continue; for (jj=1;jj<=5;jj++) { a[5][2]=mei[jj];if (a[5][1]+a[5][5]+a[5][2]>sum||a[2][2]+a[4][2]+a[5][2]>sum) continue; if (a[5][5]==1&&a[5][1]==1&&a[1][5]==3&&a[3][3]==3&&a[4][4]==3&&a[4][2]==0&&a[5][2]==3) a[3][3]=3; for (j2=1;j2<=5;j2++) { a[5][3]=mei[j2];hang5=a[5][1]+a[5][5]+a[5][2]+a[5][3];if (hang5>sum) continue; /*3-------*/ a[5][4]=sum-hang5;if (a[5][4]<0||a[5][4]>9||!f[a[5][1]][a[5][2]][a[5][3]][a[5][4]][a[5][5]]) continue; if (a[2][4]+a[4][4]+a[5][4]>sum) continue; for (j3=1;j3<=5;j3++) { a[2][5]=mei[j3]; if (a[1][5]+a[2][5]+a[5][5]>sum||a[2][2]+a[2][4]+a[2][5]>sum) continue; for (j4=1;j4<=5;j4++) { a[3][5]=mei[j4];lie5=a[1][5]+a[2][5]+a[5][5]+a[3][5];a[4][5]=sum-lie5; /*4-------*/ if (a[4][5]<0||a[4][5]>9||!f[a[1][5]][a[2][5]][a[3][5]][a[4][5]][a[5][5]]) continue; if (a[4][2]+a[4][4]+a[4][5]>sum) continue; for (p4=1;p4<=up;p4++) { a[1][2]=p4; lie2=a[2][2]+a[4][2]+a[5][2]+a[1][2];if (lie2>sum||a[1][1]+a[1][5]+a[1][2]>sum) continue; /*5-------*/ a[3][2]=sum-lie2;if (a[3][2]<0||a[3][2]>9||!f[a[1][2]][a[2][2]][a[3][2]][a[4][2]][a[5][2]]) continue; if (a[3][2]+a[3][3]+a[3][5]>sum) continue; for (p5=1;p5<=up;p5++) { a[1][3]=p5; hang1=a[1][1]+a[1][5]+a[1][2]+a[1][3];if (hang1>sum||a[1][3]+a[3][3]+a[5][3]>sum)continue; /*6-------*/ a[1][4]=sum-hang1;if (a[1][4]<1||a[1][4]>9||!f[a[1][1]][a[1][2]][a[1][3]][a[1][4]][a[1][5]]) continue; lie4=a[2][4]+a[4][4]+a[5][4]+a[1][4]; /*7-------*/ a[3][4]=sum-lie4;if (a[3][4]<0||a[3][4]>9||!f[a[1][4]][a[2][4]][a[3][4]][a[4][4]][a[5][4]]) continue; hang3=a[3][2]+a[3][3]+a[3][5]+a[3][4];if (hang3>sum) continue; /*8-------*/ a[3][1]=sum-hang3;if (a[3][1]<1||a[3][1]>9||!f[a[3][1]][a[3][2]][a[3][3]][a[3][4]][a[3][5]]) continue; if (a[1][1]+a[3][1]+a[5][1]>sum) continue; for (p6=1;p6<=up;p6++) { a[2][1]=p6; hang2=a[2][2]+a[2][4]+a[2][5]+a[2][1];lie1=a[1][1]+a[3][1]+a[5][1]+a[2][1];if (hang2>sum||lie1>sum) continue; /*9-------*/ a[2][3]=sum-hang2;if (a[2][3]<0||a[2][3]>9||!f[a[2][1]][a[2][2]][a[2][3]][a[2][4]][a[2][5]]) continue; /*10------*/ a[4][1]=sum-lie1;if (a[4][1]<1||a[4][1]>9||!f[a[1][1]][a[2][1]][a[3][1]][a[4][1]][a[5][1]]) continue; lie3=a[1][3]+a[3][3]+a[5][3]+a[2][3];hang4=a[4][2]+a[4][4]+a[4][5]+a[4][1];if (lie3>sum||hang4>sum) continue; if (lie3!=hang4||sum-hang4<0||sum-hang4>9) continue; a[4][3]=sum-hang4; /*11------*//*12------*/ if (!f[a[1][3]][a[2][3]][a[3][3]][a[4][3]][a[5][3]]||!f[a[4][1]][a[4][2]][a[4][3]][a[4][4]][a[4][5]]) continue; cnt++; for (k1=1;k1<=5;k1++) for (k2=1;k2<=5;k2++) ans[cnt][k1][k2]=a[k1][k2]; } } } } } } } } } } } } } memset(flag,0,sizeof(flag)); for (i=1;i<=cnt;i++) //用n^2的标号法排序，避免交换。 { for (j=1;j<=cnt;j++) if (!flag[j]) break; min=j; for (k=j+1;k<=cnt;k++) if (!flag[k]&&xiao(k,min)) min=k; flag[min]=true;num[min]=i; } if (cnt==0) printf("NONE"); else { for (i=1;i<=cnt;i++) { for (j=1;j<=cnt;j++) if (num[j]==i) break; for (i2=1;i2<=5;i2++) { for (i3=1;i3<=5;i3++) printf("%ld",ans[j][i2][i3]); printf("\n"); } if (i<cnt) printf("\n"); } } return 0; }usaco training 4.3.2 The Primes 题解,布布扣,bubuko.com
usaco training 4.3.2 The Primes 题解
原文：http://blog.csdn.net/jiangshibiao/article/details/20051111