LOJ P10024 质数方阵 题解
每日一题 day64 打卡
Analysis
这道题一看应该是搜索，因为方阵是5 \(\times\) 5固定的。
显然，枚举方阵每一位比直接枚举每一行要好很多，但还是要剪枝。
剪枝一：
因为我们知道(1,1)且每一位上数的和，所以我们可以确定出一个不必枚举25次之多的枚举方案。
下面是我枚举的顺序，只需枚举13位就能推出整个方阵。
剪枝二：
如果搜完一行中的4个而推出的第5个，那个数要满足\(0 \leq x \leq 9\)。
如果第5个是行头，应该满足\(x \neq 0\)。
剪枝三：
搜完一行后如果这5个数组成的五位数不是质数，则直接continue。
注意：
1.每一行的顺序是题目给定的，比如(1,1),(1,2),(1,3),(1,4),(1,5)。
2.要提前用素数筛把五位素数筛好。
3.因为最后输出答案有顺序，所以要全储存起来，最后再排序。
#include
#include
#include
#include
#define int long long
#define maxn 100000+10
#define rep(i,s,e) for(register int i=s;i<=e;++i)
#define dwn(i,s,e) for(register int i=s;i>=e;--i)
using namespace std;
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
return f*x;
}
void write(int x)
{
if(x<0) {putchar('-'); x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int sum,_11,cnt,tot;
int map[6][6];
struct node
{
int ans_map[6][6];
}ans[10010];
int book[maxn],prime[maxn];
void init()//-1 sign prime
{
memset(book,-1,sizeof(book));
rep(i,2,99999)
{
if(book[i]==-1) prime[++cnt]=i;
for(int j=1;j<=cnt&&1ll*i*prime[j]<=99999;++j)
{
book[i*prime[j]]=0;
if(i%prime[j]==0) break;
}
}
}
bool cmp(node x,node y)
{
rep(i,1,5)
rep(j,1,5)
{
if(x.ans_map[i][j]==y.ans_map[i][j]) continue;
return x.ans_map[i][j]sum) continue;
map[2][2]=_22;
rep(_33,0,9)
{
if(_11+_22+_33>sum) continue;
map[3][3]=_33;
rep(_44,0,9)
{
if(_11+_22+_33+_44>sum) continue;
if(book[calc(_11,_22,_33,_44,sum-(_11+_22+_33+_44))]==0) continue;
if(sum-(_11+_22+_33+_44)>=10) continue;
map[4][4]=_44;
int _55=map[5][5]=sum-(_11+_22+_33+_44);
rep(_34,0,9)
{
if(_44+_34>sum) continue;
map[3][4]=_34;
rep(_24,0,9)
{
if(_44+_34+_24>sum) continue;
map[2][4]=_24;
rep(_14,1,9)
{
if(_44+_34+_24+_14>sum) continue;
if(book[calc(_14,_24,_34,_44,sum-(_44+_34+_24+_14))]==0) continue;
if(sum-(_44+_34+_24+_14)>=10) continue;
map[1][4]=_14;
int _54=map[5][4]=sum-(_44+_34+_24+_14);
rep(_21,1,9)
{
if(_21+_22+_24>sum) continue;
map[2][1]=_21;
rep(_23,0,9)
{
if(_21+_22+_24+_23>sum) continue;
if(book[calc(_21,_22,_23,_24,sum-(_21+_22+_24+_23))]==0) continue;
if(sum-(_21+_22+_24+_23)>=10) continue;
map[2][3]=_23;
int _25=map[2][5]=sum-(_21+_22+_24+_23);
rep(_13,1,9)
{
if(_13+_23+_33>sum) continue;
map[1][3]=_13;
rep(_43,0,9)
{
if(_13+_23+_33+_43>sum) continue;
if(book[calc(_13,_23,_33,_43,sum-(_13+_23+_33+_43))]==0) continue;
if(sum-(_13+_23+_33+_43)>=10) continue;
map[4][3]=_43;
int _53=map[5][3]=sum-(_13+_23+_33+_43);
rep(_12,1,9)
{
if(_11+_12+_13+_14>sum) continue;
if(book[calc(_11,_12,_13,_14,sum-(_11+_12+_13+_14))]==0) continue;
if(sum-(_11+_12+_13+_14)==0) continue;
if(sum-(_11+_12+_13+_14)>=10) continue;
map[1][2]=_12;
int _15=map[1][5]=sum-(_11+_12+_13+_14);
rep(_42,0,9)
{
if(_42+_33+_24+_15>sum) continue;
if(book[calc(sum-(_42+_33+_24+_15),_42,_33,_24,_15)]==0) continue;
if(sum-(_42+_33+_24+_15)+_53+_54+_55>sum) continue;
if(book[calc(sum-(_42+_33+_24+_15),sum-(sum-(_42+_33+_24+_15)+_53+_54+_55),_53,_54,_55)]==0) continue;
if(_12+_22+_42+sum-(sum-(_42+_33+_24+_15)+_53+_54+_55)>sum) continue;
if(book[calc(_12,_22,sum-(_12+_22+_42+sum-(sum-(_42+_33+_24+_15)+_53+_54+_55)),_42,sum-(sum-(_42+_33+_24+_15)+_53+_54+_55))]==0) continue;
if(sum-(_42+_33+_24+_15)==0) continue;
if(sum-(_42+_33+_24+_15)>=10) continue;
if(sum-(sum-(_42+_33+_24+_15)+_53+_54+_55)>=10) continue;
if(sum-(_12+_22+_42+sum-(sum-(_42+_33+_24+_15)+_53+_54+_55))>=10) continue;
map[4][2]=_42;
int _51=map[5][1]=sum-(_42+_33+_24+_15);
int _52=map[5][2]=sum-(sum-(_42+_33+_24+_15)+_53+_54+_55);
int _32=map[3][2]=sum-(_12+_22+_42+sum-(sum-(_42+_33+_24+_15)+_53+_54+_55));
rep(_31,1,9)
{
if(_11+_21+_31+_51>sum) continue;
if(book[calc(_11,_21,_31,sum-(_11+_21+_31+_51),_51)]==0) continue;
if(_31+_32+_33+_34>sum) continue;
if(book[calc(_31,_32,_33,_34,sum-(_31+_32+_33+_34))]==0) continue;
if(sum-(_11+_21+_31+_51)+_42+_43+_44>sum) continue;
if(book[calc(sum-(_11+_21+_31+_51),_42,_43,_44,sum-(sum-(_11+_21+_31+_51)+_42+_43+_44))]==0) continue;
if(sum-(_31+_32+_33+_34)+_15+_25+_55>sum) continue;
if(book[calc(_15,_25,sum-(_31+_32+_33+_34),sum-(sum-(_31+_32+_33+_34)+_15+_25+_55),_55)]==0) continue;
if(sum-(sum-(_11+_21+_31+_51)+_42+_43+_44)!=sum-(sum-(_31+_32+_33+_34)+_15+_25+_55)) continue;
if(sum-(_11+_21+_31+_51)==0) continue;
if(sum-(_11+_21+_31+_51)>=10) continue;
if(sum-(_31+_32+_33+_34)>=10) continue;
if(sum-(sum-(_11+_21+_31+_51)+_42+_43+_44)>=10) continue;
map[3][1]=_31;
int _41=map[4][1]=sum-(_11+_21+_31+_51);
int _35=map[3][5]=sum-(_31+_32+_33+_34);
int _45=map[4][5]=sum-(sum-(_11+_21+_31+_51)+_42+_43+_44);
++tot;
rep(i,1,5)
{
rep(j,1,5)
{
ans[tot].ans_map[i][j]=map[i][j];
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
sort(ans+1,ans+tot+1,cmp);
rep(i,1,tot)
{
rep(h,1,5)
{
rep(l,1,5)
{
write(ans[i].ans_map[h][l]);
}
putchar('\n');
}
if(i!=tot) putchar('\n');
}
return 0;
}
如有失误请各位大佬斧正（反正我不认识斧正是什么意思）