首页 > 代码库 > USACO 6.4 The Primes
USACO 6.4 The Primes
IOI‘94
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 | +---+---+---+---+---+
- The prime numbers‘ digits must sum to the same number.
- The digit in the top left-hand corner of the square is pre-determined (1 in the example).
- A prime number may be used more than once in the same square.
- If there are several solutions, all must be presented (sorted in numerical order as if the 25 digits were all one long number).
- A five digit prime number cannot begin with a zero (e.g., 00003 is NOT a five digit prime number).
PROGRAM NAME: prime3
INPUT FORMAT
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.
SAMPLE INPUT (file prime3.in)
11 1
OUTPUT FORMAT
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".
SAMPLE OUTPUT (file prime3.out)
The above example has 3 solutions.
11351 14033 30323 53201 13313 11351 33203 30323 14033 33311 13313 13043 32303 50231 13331
————————————————————————题解
其实这又是一道搜索顺序至关重要的搜索题
计算机比人脑强大的地方就是能做大量重复的复杂运算
我们发现主对角线其实影响最大，然后是次对角线，然后逐渐再将限制较多的行或列填上，例如最后一行或者最后一列的数必须是1,3,7,9
预处理出所有5位、各数位的和为n的素数。
按照这样的搜索顺序
1 4 6 5 2
8 1 7 2 8
10 4 1 5 10
9 2 7 1 9
2 3 3 3 1
这样我们可以就可以少打几个循环了……
在计算素数的时候同时求一些一些数位固定的数
【其中XYZ为已知数，.为未知数，_ 为1，3,7,9】
例如枚举1，X ... _
枚举2，_ . X . _
枚举3，X_ _ _ Y
枚举4,5 .X . Y Z
6可以直接计算
枚举7 X . Y . Z
枚举8，9 . X Y Z _
10可以直接计算
然后时限为2s的题就可以0.011过了
1 /* 2 LANG: C++ 3 PROG: prime3 4 */ 5 #include <iostream> 6 #include <cstdio> 7 #include <algorithm> 8 #include <cstring> 9 #define siji(i,x,y) for(int i=(x); i<=(y) ; ++i) 10 #define gongzi(j,x,y) for(int j=(x); j>=(y) ; --j) 11 #define ivorysi 12 using namespace std; 13 int n,fi; 14 int p[1005][6],sum,prime[50005],tot,all; 15 bool noprime[100005]; 16 typedef struct { 17 int l,r[200]; 18 }RECORD200; 19 /*typedef struct { 20 int l,r[50]; 21 }RECORD50;*/ 22 typedef struct { 23 int l,r[20]; 24 }RECORD20; 25 //.0-9 _ 1.3.7.9 - non-zero 26 RECORD200 pat1[10];//X..._ 4*10*10 27 RECORD200 pat2[10];//_.X._ 4*4*10 28 RECORD20 pat3[10][10];//X___Y 4*4 29 RECORD20 pat4[10][10][10];//-X.YZ 9 30 RECORD20 pat7[10][10][10];//X.Y.Z 10 31 RECORD20 pat8[10][10][10];//.XYZ_ 4 32 string sol[1005]; 33 int marks[6][6]; 34 bool check(int x) { 35 if(x%2==0 || x%5==0) return 0; 36 return 1; 37 } 38 void makeprime() { 39 siji(i,2,99999) { 40 if(!noprime[i]) { 41 prime[++tot]=i; 42 if(i>10000) { 43 int temp=0; 44 for(int k=1;k<=10000;k*=10) { 45 temp+=i/k%10; 46 } 47 if(temp==n) { 48 ++sum; 49 for(int k=1,m=5;k<=10000 && m>=1;k*=10,--m) { 50 p[sum][m]=i/k%10; 51 } 52 int t1,t2,t3,t4,t5; 53 t1=p[sum][1],t2=p[sum][2],t3=p[sum][3],t4=p[sum][4],t5=p[sum][5]; 54 pat1[t1].r[++pat1[t1].l]=sum; 55 if(check(t1)) pat2[t3].r[++pat2[t3].l]=sum; 56 if(check(t2)&&check(t3)&&check(t4)) { 57 pat3[t1][t5].r[++pat3[t1][t5].l]=sum; 58 } 59 pat4[t2][t4][t5].r[++pat4[t2][t4][t5].l]=sum; 60 pat7[t1][t3][t5].r[++pat7[t1][t3][t5].l]=sum; 61 pat8[t2][t3][t4].r[++pat8[t2][t3][t4].l]=sum; 62 } 63 } 64 } 65 for(int j=1;j<=tot && i<100000/prime[j];++j) { 66 noprime[prime[j]*i]=1; 67 if(i%prime[j]==0) break; 68 } 69 } 70 } 71 void addsolution() { 72 ++all; 73 siji(i,1,5) { 74 siji(j,1,5) { 75 sol[all].append(1,marks[i][j]+‘0‘); 76 } 77 } 78 } 79 int num(int x) { 80 int res=0; 81 siji(i,1,5) res=res*10+p[x][i]; 82 return res; 83 } 84 void solve() { 85 scanf("%d%d",&n,&fi); 86 makeprime(); 87 int us,tj,tk,tm,tw,ty,tx,tq,temp,temp1,temp2; 88 for(int i=1;i<=pat1[fi].l;++i) { 89 memset(marks,0,sizeof(marks)); 90 us=pat1[fi].r[i]; 91 siji(iv,1,5) marks[iv][iv]=p[us][iv]; 92 tj=pat2[marks[3][3]].l; 93 for(int j=1;j<=tj;++j) { 94 us=pat2[marks[3][3]].r[j]; 95 siji(iv,1,5) marks[5-iv+1][iv]=p[us][iv]; 96 tk=pat3[marks[5][1]][marks[5][5]].l; 97 for(int k=1;k<=tk;++k) { 98 us=pat3[marks[5][1]][marks[5][5]].r[k]; 99 siji(iv,2,4) marks[5][iv]=p[us][iv]; 100 tm=pat4[marks[2][2]][marks[4][2]][marks[5][2]].l; 101 for(int m=1;m<=tm;++m) { 102 us=pat4[marks[2][2]][marks[4][2]][marks[5][2]].r[m]; 103 marks[1][2]=p[us][1]; 104 marks[3][2]=p[us][3]; 105 tw=pat4[marks[2][4]][marks[4][4]][marks[5][4]].l; 106 for(int w=1;w<=tw;++w) { 107 us=pat4[marks[2][4]][marks[4][4]][marks[5][4]].r[w]; 108 marks[1][4]=p[us][1]; 109 marks[3][4]=p[us][3]; 110 marks[1][3]=0; 111 temp=0; 112 siji(iv,1,5) temp+=marks[1][iv]; 113 marks[1][3]=n-temp; 114 if(marks[1][3]<1 || marks[1][3]>9) continue; 115 temp=0; 116 siji(iv,1,5) { 117 temp=temp*10+marks[1][iv]; 118 } 119 if(noprime[temp]) continue; 120 ty=pat7[marks[1][3]][marks[3][3]][marks[5][3]].l; 121 for(int y=1;y<=ty;++y) { 122 us=pat7[marks[1][3]][marks[3][3]][marks[5][3]].r[y]; 123 marks[2][3]=p[us][2]; 124 marks[4][3]=p[us][4]; 125 tx=pat8[marks[2][2]][marks[2][3]][marks[2][4]].l; 126 for(int x=1;x<=tx;++x) { 127 us=pat8[marks[2][2]][marks[2][3]][marks[2][4]].r[x]; 128 marks[2][1]=p[us][1]; 129 marks[2][5]=p[us][5]; 130 tq=pat8[marks[4][2]][marks[4][3]][marks[4][4]].l; 131 for(int q=1;q<=tq;++q) { 132 us=pat8[marks[4][2]][marks[4][3]][marks[4][4]].r[q]; 133 marks[4][1]=p[us][1]; 134 marks[4][5]=p[us][5]; 135 marks[3][1]=marks[3][5]=0; 136 temp1=temp2=0; 137 siji(iv,1,5) temp1+=marks[iv][1],temp2+=marks[iv][5]; 138 marks[3][1]=n-temp1;marks[3][5]=n-temp2; 139 if(marks[3][1]<1 || marks[3][5]<1 ||marks[3][1]>9 || marks[3][5]>9) 140 continue; 141 temp1=temp2=0; 142 siji(iv,1,5) 143 temp1=temp1*10+marks[iv][1],temp2=temp2*10+marks[iv][5]; 144 if(noprime[temp1]||noprime[temp2]) continue; 145 temp1=temp2=0; 146 siji(iv,1,5) 147 temp1=temp1*10+marks[3][iv],temp2+=marks[3][iv]; 148 if(noprime[temp1] || temp2!=n) continue; 149 addsolution(); 150 } 151 } 152 } 153 } 154 } 155 } 156 } 157 } 158 if(all==0) puts("NONE"); 159 sort(sol+1,sol+all+1); 160 siji(i,1,all) { 161 for(int j=0;j<5;++j) { 162 cout<<sol[i].substr(j*5,5)<<endl; 163 } 164 if(i!=all) puts(""); 165 } 166 } 167 int main(int argc, char const *argv[]) 168 { 169 #ifdef ivorysi 170 freopen("prime3.in","r",stdin); 171 freopen("prime3.out","w",stdout); 172 #else 173 freopen("f1.in","r",stdin); 174 freopen("f1.out","w",stdout); 175 #endif 176 solve(); 177 return 0; 178 }
USACO 6.4 The Primes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。