http://218.5.5.242:9018/JudgeOnline/problem.php?id=1263
题目描述
在N*N的棋盘上(1<N≤10)填入1,2,...N*N共N*N个数,使得任意两个相邻的数之和为素数.例如,当N=2时,有 :
其相邻数的和为素数的有: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。
输入
输出
若有多种解,则需输出第一行之和最小,若第一行和相同,则输出第一列之和最小的排列方案;若无解,则输出"No solution"。若有解,第一行为空格分割的两个正整数,分别是该排列方案的第一行、第一列各数字之和。以下n行输出该排列方案,每个数字占4个字符,不足4位的在数字前用空格补齐。
样例输入
2
样例输出
3 5
1 2
4 3
算法分析
这题和洛谷上的不!一!样!!
P1549 棋盘问题(2)(https://www.luogu.org/problemnew/show/P1549)
输出格式:
如有多种解,则输出第一行、第一列之和为最小的排列方案;若无解,则输出“NO”。
洛谷上这题要求是:“如有多种解,则输出第一行、第一列之和为最小的排列方案”,只要搜到第一个解直接输出结束。但是这题不行,这题只能把所有解都搜过去。。。
要是爆搜肯定超时。。但是n小呀,于是开始了疯狂的预处理+剪枝。。。
因为要求输出第一行之和最小的排列方案,若第一行和相同,则输出第一列之和最小的排列方案。所以可以尝试先搜索第1行,接着再搜索第1列,最后再搜索中间那块。
初始化:
- 读入n,筛出2…2*n*n之间的所有素数表prime[i],用于表示i是否为素数。(线性筛)
- 对于每一个数i,找出2...2*n*n之内的所有能使i+j为素数的j,并储存起来。
搜索第1行:在搜索时可能判断当前已经搜索过的格子中数字之和hang是否大于先前答案中第一行的和ansh,如果是可不用继续搜索,这就是搜索剪枝。
搜索第1列,同样,搜索列也可剪枝。
搜索中间部分:只要已经出现过一个解,就不继续搜索,也可剪枝。
1 #include <iostream>
2 #include <cstdio>
3 #include <cmath>
4 #include <cstring>
5 #define reg register
6 using namespace std;
7 int n,N;//N=n*n,即最大的数,方便以后遍历所有数(也省时间)
8 int map[11][11];//储存方阵
9 bool prime[20000], v[200];//prime[i]表示i是否为素数,v[i]表示i是否用过(用于搜索)
10
11 int pprime[20000];//用于筛素数
12 inline void FindPrime() { //筛素数,这里用的是线性筛,不懂可以去百度
13 int k=0, ls=2*N+5;
14 memset(prime, 1, sizeof(prime));
15 prime[1]=false;
16 for (reg int i=1; i<= ls; ++i) {
17 if (prime[i])pprime[++k] = i;
18 for (reg int j=1; j<=k; ++j) {
19 prime[i*pprime[j]] = false;
20 if (i%pprime[j]==0)break;
21 }
22 }
23 }
24 int pre[101][101];//存放预处理结果
25 inline void predeal(){//预处理
26 int k=2; //k:储存方案数
27 for(reg int i=1;i<=N;++i){
28 k=2;
29 for(reg int j=2;j<=N;++j){
30 if(prime[j+i])
31 pre[i][k++]=j;//将使i+j为素数的所有可能的j存入pre[i][2...k];
32 }
33 pre[i][1]=k-2;//pre[i][1]存放方案数(j有几种可能),用于之后的遍历
34 }
35 }
36 int hang=1,lie=1;//hang:当前第一行所有数之和 lie:当前第一列所有数之和
37 int ansh = 1000, ansl = 1000,count=0;
38 //ansh ansl:储存最优解(最小的hang lie);count:方案数(判断是否No solution)
39 int ansmap[11][11];//储存答案方阵
40
41 inline void print() {//简单的输出结果的函数
42 printf("%d %d\n", ansh, ansl);
43 for (reg int i = 1; i <= n; i++) {
44 for (reg int j = 1; j <= n; j++) {
45 printf("%4d", ansmap[i][j]);
46 if (j == n)printf("\n");
47 }
48 }
49 }
50 inline void update() {//更新结果(判断当前结果是否比上一个结果更优)
51 ansh = hang; ansl = lie;
52 memcpy(ansmap, map, sizeof(map));
53 count++;
54 }
55 bool found;//因为当第一行与第一列已经确定了时,中间这块对答案无影响,只要搜索出一个结果即可,用于剪枝
56 inline void workmid(int dx, int dy) {
57 if(found)return;//只要中间这块已经被搜索出来了,即可停止
58 if((map[dx-1][dy]&1)^(map[dx][dy-1]&1))
59 //若上面的数与左边的数一奇一偶,肯定不符合(i+left和i+up中必定有一个为偶数,非素数)
60 return;
61 int left=map[dx-1][dy];//储存上面一格的数
62 for (reg int k = 2; k <= pre[left][1]+1; ++k) {
63 int i=pre[left][k];//遍历使left+i为素数的所有i,后面写法与此相同
64 if (prime[i+map[dx][dy-1]] && !v[i]) {
65 map[dx][dy]=i, v[i]=1;
66 if (dx<n && dy<=n)workmid(dx+1,dy), v[i]=0;//往下搜一个
67 else if (dx==n && dy<n)workmid(2,dy+1), v[i]=0;//这一列搜完了,跳到下一列
68 else if (dx==n && dy==n)update(), v[i]=0,found=1;//中间都搜完了,更新结果,标记found
69 }
70 }
71 }
72 inline void worklie(int dy) {
73 int up=map[dy-1][1];
74 for (reg int k=2; k<=pre[up][1]+1; ++k) {
75 int i=pre[up][k];
76 if (!v[i] && (hang<ansh||(hang==ansh&&(lie+i)<ansl))){
77 map[dy][1]=i, v[i]=1,lie+=i;
78 if (dy==n)workmid(2, 2), v[i]=0,lie-=i,found=0;
79 else worklie(dy + 1), v[i]=0,lie-=i;
80 }
81 }
82 }
83 inline void workhang(int dx) {
84 int left=map[1][dx-1];
85 for (reg int k=2; k<=pre[left][1]+1; ++k) {
86 int i=pre[left][k];
87 if (!v[i] && (hang+i)<=ansh){
88 map[1][dx]=i, v[i]=1,hang+=i;
89 if (dx==n)worklie(2), v[i]=0,hang-=i;
90 else workhang(dx + 1), v[i]=0,hang-=i;
91 }
92 }
93 }
94 int main() {
95 cin>>n; N=n*n;
96 FindPrime();
97 predeal();
98 map[1][1] = 1;
99 workhang(2);
100 if(count>0)print(); else printf("No solution");
101 return 0;
102 }
数字方阵2 题解
原文:https://www.cnblogs.com/1024th/p/10259260.html