学步园

开始的时候自己写的代码最多只能过7组数据。我一直想不把输出存起来，直接找到一个就输出，这样的话就只能一行一行枚举，这样的话填的时候限制条件就很少了。搞到最后所有可以想到的剪枝都用了，还是只能过7组数据。没办法只好搜一下解题报告，原来别人都是把输出存起来的。这样的话限制条件就多了。

填表顺序：

第一行，第一列；

左下到右上；

左上到右下；

第二行，第二列，第四行，第四列；

第三行，第三列；

这样的顺序就是为了使限制条件尽可能的多。

自己完全没有想到。

代码：

/*<br /> ID: mnlm1991<br /> PROG: prime3<br /> LANG: C++<br /> */</p> <p>#include<cstdio><br /> #include<cstdlib><br /> #include<cmath><br /> #include<cstring><br /> #include<vector><br /> #include<algorithm><br /> #include<string><br /> #include<map><br /> #include<set><br /> #include<bitset><br /> #include<queue><br /> #include<iostream></p> <p>using namespace std;</p> <p>const int MaxN = 100002;<br /> const int M = 10000;<br /> const int mod[] = {10000, 1000, 100, 10, 1};<br /> int prm[M];<br /> bool is[MaxN];<br /> int sum;<br /> int start;<br /> int N;<br /> int pos[MaxN + 1];<br /> bool flag;<br /> struct ANS<br /> {<br /> int tt[5][5];<br /> bool operator < (const ANS & other) const<br /> {<br /> int i;<br /> int j;<br /> for (i = 0; i < 5; i++)<br /> {<br /> for (j = 0; j < 5; j++)<br /> {<br /> if (tt[i][j] != other.tt[i][j])<br /> {<br /> return tt[i][j] < other.tt[i][j];<br /> }<br /> }<br /> }<br /> return false;<br /> }<br /> };<br /> ANS ans[10000];<br /> ANS tmp;<br /> int cnt;<br /> int DigitSum(int x)<br /> {<br /> int ret = 0;<br /> while (x)<br /> {<br /> ret += x % 10;<br /> x /= 10;<br /> }<br /> return ret;<br /> }<br /> bool Digit(int x)<br /> {<br /> while (x)<br /> {<br /> if (x % 10 == 0)<br /> {<br /> return false;<br /> }<br /> x /= 10;<br /> }<br /> return true;<br /> }<br /> int d[5];<br /> void getpos(int x, int k)<br /> {<br /> if (x < M)<br /> {<br /> return;<br /> }<br /> pos[x] = k;<br /> return;<br /> }<br /> int getprm(int n)<br /> {<br /> int i, j, k = 0;<br /> int s;<br /> int e = (int)(sqrt(0.0 + n) + 1);<br /> memset(is, 1, sizeof(is));<br /> memset(pos, -1, sizeof(pos));<br /> for (i = 4; i < n; i += 2)<br /> {<br /> is[i] = 0;<br /> }<br /> int x;<br /> for (i = 3; i < e; i += 2)<br /> {<br /> getpos(i, k);<br /> if (is[i])<br /> {<br /> if (i >= M && DigitSum(i) == sum)<br /> {<br /> prm[k++] = i;<br /> }<br /> else<br /> {<br /> is[i] = false;<br /> }<br /> for (s = i * 2, j = i * i; j < n; j += s)<br /> {<br /> is[j] = 0;<br /> }<br /> }<br /> }<br /> for (i = max(i, M + 1); i < n; i += 2 )<br /> {<br /> getpos(i, k);<br /> getpos(i - 1, k);<br /> if (is[i] && DigitSum(i) == sum)<br /> {<br /> prm[k++] = i;<br /> }<br /> else<br /> {<br /> is[i] = false;<br /> }<br /> }<br /> return k;<br /> }<br /> int table[5][5];<br /> int p1[100000];<br /> int p15[10][10][1000];<br /> int p13[10][10][1000];<br /> int p124[10][10][10][100];<br /> void Init()<br /> {<br /> memset(p1, -1, sizeof(p1));<br /> int i;<br /> int j = 0;<br /> for (i = pos[start * mod[0]]; i < pos[(start + 1)* mod[0]]; i++)<br /> {<br /> if (Digit(prm[i]))<br /> {<br /> p1[j++] = prm[i];<br /> }<br /> }<br /> int k;<br /> int l;<br /> int w;<br /> memset(p15, -1, sizeof(p15));<br /> for (i = 1; i < 10; i++)<br /> {<br /> for (j = 0; j < 10; j++)<br /> {<br /> l = 0;<br /> for (k = pos[i * mod[0]]; k < pos[(i + 1)* mod[0]]; k++)<br /> {<br /> if (prm[k] % 10 == j)<br /> {<br /> p15[i][j][l++] = prm[k];<br /> }<br /> }<br /> }<br /> }<br /> memset(p13, -1, sizeof(p13));<br /> for (i = 1; i < 10; i++)<br /> {<br /> for (j = 0; j < 10; j++)<br /> {<br /> l = 0;<br /> for (k = pos[i * mod[0]]; k < pos[(i + 1)* mod[0]]; k++)<br /> {<br /> if (prm[k] / mod[2] % 10 == j)<br /> {<br /> p13[i][j][l++] = prm[k];<br /> }<br /> }<br /> }<br /> }<br /> memset(p124, -1, sizeof(p124));<br /> for (i = 1; i < 10; i++)<br /> {<br /> for (j = 0; j < 10; j++)<br /> {<br /> for (k = 0; k < 10; k++)<br /> {<br /> l = 0;<br /> for (w = pos[(i * 10 + j)* 1000]; w < pos[(i * 10 + j + 1)* 1000]; w++)<br /> {<br /> if (prm[w] / mod[3] % 10 == k)<br /> {<br /> p124[i][j][k][l++] = prm[w];<br /> }<br /> }<br /> }<br /> }<br /> }<br /> return;<br /> }<br /> void DFS(int kk)<br /> {<br /> int i;<br /> int j;<br /> int k;<br /> int t;<br /> int l;<br /> switch (kk)<br /> {<br /> case 0 :<br /> for (i = 0; p1[i] != -1; i++)<br /> {<br /> t = p1[i];<br /> for (k = 4; k >= 0; k--)<br /> {<br /> table[0][k] = t % 10;<br /> t /= 10;<br /> }<br /> for (j = 0; p1[j] != -1; j++)<br /> {<br /> t = p1[j];<br /> for (k = 4; k > 0; k--)<br /> {<br /> table[k][0] = t % 10;<br /> t /= 10;<br /> }<br /> DFS(kk + 1);<br /> }<br /> }<br /> break;<br /> case 1 :<br /> for (i = 0; p15[table[4][0]][table[0][4]][i] != -1; i++)<br /> {<br /> t = p15[table[4][0]][table[0][4]][i];<br /> for (j = 1; j < 4; j++)<br /> {<br /> table[4 - j][j] = t / mod[j] % 10;<br /> }<br /> DFS(kk + 1);<br /> }<br /> break;<br /> case 2 :<br /> for (i = 0; p13[table[0][0]][table[2][2]][i] != -1; i++)<br /> {<br /> t = p13[table[0][0]][table[2][2]][i];<br /> for (j = 1; j < 5; j++)<br /> {<br /> table[j][j] = t / mod[j] % 10;<br /> }<br /> DFS(kk + 1);<br /> }<br /> break;<br /> case 3 :<br /> for (i = 0; p124[table[1][0]][table[1][1]][table[1][3]][i] != -1; i++)<br /> {<br /> t = p124[table[1][0]][table[1][1]][table[1][3]][i];<br /> table[1][2] = t / mod[2] % 10;<br /> table[1][4] = t / mod[4] % 10;<br /> for (j = 0; p124[table[0][1]][table[1][1]][table[3][1]][j] != -1; j++)<br /> {<br /> t = p124[table[0][1]][table[1][1]][table[3][1]][j];<br /> table[2][1] = t / mod[2] % 10;<br /> table[4][1] = t / mod[4] % 10;<br /> DFS(kk + 1);<br /> }<br /> }<br /> break;<br /> case 4 :<br /> for (i = 0; p124[table[3][0]][table[3][1]][table[3][3]][i] != -1; i++)<br /> {<br /> t = p124[table[3][0]][table[3][1]][table[3][3]][i];<br /> table[3][2] = t / mod[2] % 10;<br /> table[3][4] = t / mod[4] % 10;<br /> for (j = 0; p124[table[0][3]][table[1][3]][table[3][3]][j] != -1; j++)<br /> {<br /> t = p124[table[0][3]][table[1][3]][table[3][3]][j];<br /> table[2][3] = t / mod[2] % 10;<br /> table[4][3] = t / mod[4] % 10;<br /> DFS(kk + 1);<br /> }<br /> }<br /> break;<br /> case 5 :<br /> t = 0;<br /> for (i = 0; i < 4; i++)<br /> {<br /> t = t * 10 + table[2][i];<br /> }<br /> t *= 10;<br /> l = 0;<br /> for (i = 0; i < 4; i++)<br /> {<br /> l = l * 10 + table[i][2];<br /> }<br /> l *= 10;<br /> for (i = pos[t]; i < pos[t + 10]; i++)<br /> {<br /> table[2][4] = prm[i] % 10;<br /> for (j = pos[l]; j < pos[l + 10]; j++)<br /> {<br /> table[4][2] = prm[j] % 10;<br /> DFS(kk + 1);<br /> }<br /> }<br /> break;<br /> case 6 :<br /> t = 0;<br /> l = 0;<br /> for (i = 0; i < 5; i++)<br /> {<br /> t = t * 10 + table[4][i];<br /> l = l * 10 + table[i][4];<br /> }<br /> if (is[t] && is[l])<br /> {<br /> memcpy(ans[cnt].tt, table, sizeof(table));<br /> cnt++;<br /> }<br /> break;<br /> default : ;<br /> }<br /> return;<br /> }<br /> int main()<br /> {<br /> freopen("prime3.in", "r", stdin);<br /> freopen("prime3.out", "w", stdout);<br /> while (scanf("%d%d", &sum, &start) != EOF)<br /> {<br /> int N = getprm(MaxN);<br /> Init();<br /> cnt = 0;<br /> DFS(0);<br /> if (!cnt)<br /> {<br /> printf("NONE/n");<br /> }<br /> else<br /> {<br /> int i;<br /> int j;<br /> int k;<br /> sort(ans, ans + cnt);<br /> for (i = 0; i < cnt; i++)<br /> {<br /> if (i)<br /> {<br /> printf("/n");<br /> }<br /> for (j = 0; j < 5; j++)<br /> {<br /> for (k = 0; k < 5; k++)<br /> {<br /> printf("%d", ans[i].tt[j][k]);<br /> }<br /> printf("/n");<br /> }<br /> }<br /> }<br /> }<br /> return 0;<br /> }<br />