题解 UVA835【Square of Primes】

2024-01-14 11:29:16

题目建议评紫，一道很难搞的搜索。我为了干这道题花了一整天的时间。

本题解包含代码。禁止抄袭，长度吓人，\(234\) 行，\(3658\) 字节。

不多说了，让我们开始吧！

首先，为了求出这个方阵，我们需要求出所有的五位质数。为了方便地存储它们，我们开一个五维布尔数组 \(vis\)。每维的取值范围都为 \(0\sim10\)。我们每发现一个五位质数为 \(\overline{abcde}\)，就要将 \(vis_{a,b,c,d,e}\) 设为 true。不过，你可能会注意到，\(vis\) 的数组每维取值范围还可以达到 \(10\)，这一个特殊的数字我会告诉你为什么要有。

在每次搜索中，我们都需要枚举当前位置的数值。当我们在矩阵中枚举出这样的数字：\(\overline{****0}\)，任何人都知道这不是个素数，因为末尾是 \(0\) 的数字一定能被 \(2,5,10\) 整除。在搜索中，这种情况就可以不用做下去了，因为不管后面怎么做，把 \(*\) 变成任何数字，这都不会是一个质数。
所以，我们就可以利用 \(10\) 来代替 \(*\)。这样就可以进行剪枝了，也便于存储。

不过这种剪枝显然是远远不够的，我们需要更厉害的剪枝方法。这道题是 USACO 4.3.2 的一道原题，当我们使用单测时，这种方法我个人 TLE 了六个点。想尝试单测的同学可以转到 LOJ。

这就是令人苦恼的时候了，我吃了顿饭，然后想到了一个重要的点：两条对角线会干涉到更多的行和列！

那么我们就要先搭建对角线了。接下来，我们尽可能让某行某列要满，这样就可以剪掉更多的分支。

我把整张表都做出来了。由于是自己个人算的所以不一定完美，大家也可以按照上面的规则进行推算。不过要注意，最后一列和最后一行的数建议先填，因为它们就像支撑整个表格的支架，这样虽然不是对角线也能进行很好的剪枝。

\(1\) \(16\) \(21\) \(17\) \(2\)
\(22\) \(11\) \(23\) \(15\) \(3\)
\(20\) \(18\) \(12\) \(19\) \(4\)
\(24\) \(14\) \(25\) \(13\) \(5\)
\(7\) \(8\) \(9\) \(10\) \(6\)

然后就要开始讲解代码了！代码有点长，将为大家剖解开来。头文件等不说了，主要看函数。后面讲解代码因为本来就字少，所以不标出哪些重点了。

在这一段，我们把很多五位质数存放在 \(vis\) 数组中。这里，全局变量初值为 \(0\)，就是 false。当枚举出质数，再进行枚举哪些位会是 \(*\)，然后存储在 \(vis\) 中。

bool isprime(int x){
	if(x==0||x==1)
		return false;
	for(int i=2;i*i<=x;++i)
		if(x%i==0)
			return false;
	return true;
}
bool vis[20][20][20][20][20];
void doprime(int x){
	int c[20];
	c[5]=x%10;
	c[4]=x/10%10;
	c[3]=x/100%10;
	c[2]=x/1000%10;
	c[1]=x/10000;
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				for(int l=0;l<2;++l)
					for(int o=0;o<2;++o){
						int a,b,cc,d,e;
						if(i)
							a=c[1];
						else
							a=10;
						if(j)
							b=c[2];
						else
							b=10;
						if(k)
							cc=c[3];
						else
							cc=10;
						if(l)
							d=c[4];
						else
							d=10;
						if(o)
							e=c[5];
						else
							e=10;
						vis[a][b][cc][d][e]=true;
					}
}
void workprime(){
	for(int i=10000;i<=99999;++i)
		if(isprime(i))
			doprime(i);
}

接下来，让我们存储这张顺序表。不建议你抄我的，建议你从头自己构造一张表。当然如果你抄了仅限这一段我也不会怪你。

int b[30][2]={
	{},
	{1,1},
	{1,5},
	{2,5},
	{3,5},
	{4,5},
	{5,5},
	{5,1},
	{5,2},
	{5,3},
	{5,4},
	{2,2},
	{3,3},
	{4,4},
	{4,2},
	{2,4},
	{1,2},
	{1,4},
	{3,2},
	{3,4},
	{3,1},
	{1,3},
	{2,1},
	{2,3},
	{4,1},
	{4,3}
};

接下来，就是最难写的 check 函数。我们需要注意以下几点：

  • 对角线是从左到右，不是从上到下。
  • 检查下标是否写对，\(x,y\) 或 \(i,j\) 有没有写反。
  • 当没填完这行、列、对角线时，不要检查数字和。不过也不能跳出循环，因为要使用 \(vis\) 数组剪枝。

在这里，没填的数我的代码使用 \(-1\) 表示。

bool check(int x,int y){
	int tot=0;
	bool flag=true;
	int c[10];
	for(int i=1;i<=5;++i){
		if(a[i][y]==-1)
			flag=false;
		if(a[i][y]==-1)
			c[i]=10;
		else
			c[i]=a[i][y];
		if(flag)
			tot+=a[i][y];
	}
	if(vis[c[1]][c[2]][c[3]][c[4]][c[5]]==false)
		return false;
	if(flag==true&&tot!=m)
		return false;
	flag=true;
	tot=0;
	for(int i=1;i<=5;++i){
		if(a[x][i]==-1)
			flag=false;
		if(a[x][i]==-1)
			c[i]=10;
		else
			c[i]=a[x][i];
		if(flag)
			tot+=a[x][i];
	}
	if(vis[c[1]][c[2]][c[3]][c[4]][c[5]]==false)
		return false;
	if(flag==true&&tot!=m)
		return false;
	if(x==y){
		flag=true;
		tot=0;
		for(int i=1;i<=5;++i){
			if(a[i][i]==-1)
				flag=false;
			if(a[i][i]==-1)
				c[i]=10;
			else
				c[i]=a[i][i];
			if(flag)
				tot+=a[i][i];
		}
		if(vis[c[1]][c[2]][c[3]][c[4]][c[5]]==false)
			return false;
		if(flag==true&&tot!=m)
			return false;
	}
	if(x==5-y+1){
		flag=true;
		tot=0;
		for(int i=5;i>=1;--i){
			int j=5-i+1;
			if(a[i][j]==-1)
				flag=false;
			if(a[i][j]==-1)
				c[j]=10;
			else
				c[j]=a[i][j];
			if(flag)
				tot+=a[i][j];
		}
		if(vis[c[1]][c[2]][c[3]][c[4]][c[5]]==false)
			return false;
		if(flag&&tot!=m)
			return false;
	}
	return true;
}

同时，因为我们不是按照顺序进行填写的，所以输出的顺序可能出现问题。我们可以定义一个专门存储答案的 class，稍后进行排序。这里的名称我使用 sol。别忘了定义一个存储答案用来排序的向量！

class sol{
	int s[10][10];
	public:
	void begin(int bb[10][10]){
		for(int i=1;i<=5;++i)
			for(int j=1;j<=5;++j)
				s[i][j]=bb[i][j];
	}
	void output(){
		for(int i=1;i<=5;++i){
			for(int j=1;j<=5;++j)
				cout<<s[i][j];
			cout<<endl;
		}
	}
	bool operator < (sol b)const{
		for(int i=1;i<=5;++i)
			for(int j=1;j<=5;++j)
				if(s[i][j]<b.s[i][j])
					return true;
				else if(s[i][j]>b.s[i][j])
					return false;
		return true;
	}
};
vector<sol>sols;

写到了这一步，其实工程基本要结束了。剩下的就是 dfs() 和主函数了。dfs 的实现大纲如下：

  1. 是否填完，如果填完就保存结果。
  2. 是否在填第一个格子。如果是就要使用题目给定的值。
  3. 否则的话进行枚举，然后深搜下降和回溯。
void dfs(int k){
	if(k==26){
		sol tmp;
		tmp.begin(a);
		sols.push_back(tmp);
		return;
	}
	int x=b[k][0];
	int y=b[k][1];
	if(k==1){
		a[x][y]=n;
		dfs(2);
		a[x][y]=-1;
		return;
	}
	for(int i=0;i<=9;++i){
		a[x][y]=i;
		if(check(x,y))
			dfs(k+1);
	}
	a[x][y]=-1;
}

最后，就是主函数了。这个也要注意不少细节。

  • 不要忘记这是多测。
  • 每次计算结束的时候要清空存储答案的向量。
  • 每组数据中间隔一个空格。UVA 并不会忽略最后的一个空行，所以当在进行最后一组数据的时候一定要特判。
void solve(){
	cin>>m>>n;
	for(int i=1;i<=5;++i)
		for(int j=1;j<=5;++j)
			a[i][j]=-1;
	dfs(1);
	if(sols.empty())
		cout<<"NONE"<<endl;
	else{
		sort(sols.begin(),sols.end());
		for(int i=0;i<sols.size();++i){
			if(i)
				cout<<endl;
			sols[i].output();
		}
	}
	sols.clear();
}
int main(){
	workprime();
	int t;
	cin>>t;
	while(t--){
		solve();
		if(t)
			cout<<endl;
	} 
}

至此，我们这道题就完美收场了。这是完整代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool isprime(int x){
	if(x==0||x==1)
		return false;
	for(int i=2;i*i<=x;++i)
		if(x%i==0)
			return false;
	return true;
}
bool vis[20][20][20][20][20];
void doprime(int x){
//	cout<<x<<endl;
	int c[20];
	c[5]=x%10;
	c[4]=x/10%10;
	c[3]=x/100%10;
	c[2]=x/1000%10;
	c[1]=x/10000;
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				for(int l=0;l<2;++l)
					for(int o=0;o<2;++o){
						int a,b,cc,d,e;
						if(i)
							a=c[1];
						else
							a=10;
						if(j)
							b=c[2];
						else
							b=10;
						if(k)
							cc=c[3];
						else
							cc=10;
						if(l)
							d=c[4];
						else
							d=10;
						if(o)
							e=c[5];
						else
							e=10;
						vis[a][b][cc][d][e]=true;
					}
}
void workprime(){
	for(int i=10000;i<=99999;++i)
		if(isprime(i))
			doprime(i);
}
int b[30][2]={
	{},
	{1,1},
	{1,5},
	{2,5},
	{3,5},
	{4,5},
	{5,5},
	{5,1},
	{5,2},
	{5,3},
	{5,4},
	{2,2},
	{3,3},
	{4,4},
	{4,2},
	{2,4},
	{1,2},
	{1,4},
	{3,2},
	{3,4},
	{3,1},
	{1,3},
	{2,1},
	{2,3},
	{4,1},
	{4,3}
};
int n,m;
int a[10][10];
bool check(int x,int y){
	int tot=0;
	bool flag=true;
	int c[10];
	for(int i=1;i<=5;++i){
		if(a[i][y]==-1)
			flag=false;
		if(a[i][y]==-1)
			c[i]=10;
		else
			c[i]=a[i][y];
		if(flag)
			tot+=a[i][y];
	}
	if(vis[c[1]][c[2]][c[3]][c[4]][c[5]]==false)
		return false;
	if(flag==true&&tot!=m)
		return false;
	flag=true;
	tot=0;
	for(int i=1;i<=5;++i){
		if(a[x][i]==-1)
			flag=false;
		if(a[x][i]==-1)
			c[i]=10;
		else
			c[i]=a[x][i];
		if(flag)
			tot+=a[x][i];
	}
	if(vis[c[1]][c[2]][c[3]][c[4]][c[5]]==false)
		return false;
	if(flag==true&&tot!=m)
		return false;
	if(x==y){
		flag=true;
		tot=0;
		for(int i=1;i<=5;++i){
			if(a[i][i]==-1)
				flag=false;
			if(a[i][i]==-1)
				c[i]=10;
			else
				c[i]=a[i][i];
			if(flag)
				tot+=a[i][i];
		}
		if(vis[c[1]][c[2]][c[3]][c[4]][c[5]]==false)
			return false;
		if(flag==true&&tot!=m)
			return false;
	}
	if(x==5-y+1){
		flag=true;
		tot=0;
		for(int i=5;i>=1;--i){
			int j=5-i+1;
			if(a[i][j]==-1)
				flag=false;
			if(a[i][j]==-1)
				c[j]=10;
			else
				c[j]=a[i][j];
			if(flag)
				tot+=a[i][j];
		}
		if(vis[c[1]][c[2]][c[3]][c[4]][c[5]]==false)
			return false;
		if(flag&&tot!=m)
			return false;
	}
	return true;
}
class sol{
	int s[10][10];
	public:
	void begin(int bb[10][10]){
		for(int i=1;i<=5;++i)
			for(int j=1;j<=5;++j)
				s[i][j]=bb[i][j];
	}
	void output(){
		for(int i=1;i<=5;++i){
			for(int j=1;j<=5;++j)
				cout<<s[i][j];
			cout<<endl;
		}
	}
	bool operator < (sol b)const{
		for(int i=1;i<=5;++i)
			for(int j=1;j<=5;++j)
				if(s[i][j]<b.s[i][j])
					return true;
				else if(s[i][j]>b.s[i][j])
					return false;
		return true;
	}
};
vector<sol>sols;
void dfs(int k){
	if(k==26){
		sol tmp;
		tmp.begin(a);
		sols.push_back(tmp);
		return;
	}
	int x=b[k][0];
	int y=b[k][1];
	if(k==1){
		a[x][y]=n;
		dfs(2);
		a[x][y]=-1;
		return;
	}
	for(int i=0;i<=9;++i){
		a[x][y]=i;
		if(check(x,y))
			dfs(k+1);
	}
	a[x][y]=-1;
}
void solve(){
	cin>>m>>n;
	for(int i=1;i<=5;++i)
		for(int j=1;j<=5;++j)
			a[i][j]=-1;
	dfs(1);
	if(sols.empty())
		cout<<"NONE"<<endl;
	else{
		sort(sols.begin(),sols.end());
		for(int i=0;i<sols.size();++i){
			if(i)
				cout<<endl;
			sols[i].output();
		}
	}
	sols.clear();
}
int main(){
	workprime();
	int t;
	cin>>t;
	while(t--){
		solve();
		if(t)
			cout<<endl;
	} 
}

说几句话：

  • 这道题很难，不过当自己写出代码 AC 时还是非常有成就感的。
  • 评紫题吧，哈哈哈这傻逼题目真有趣。
  • 不要抄袭我的代码。
  • 现在如果算上写题解的时间就真的是完整一天的刷题时间了。

感谢大家的捧场！如果觉得这对你有帮助，万水千山总是情，给一个赞行不行！如果有不明白或疏忽的地方，请在评论留言。

题解 UVA835【Square of Primes】

上一篇：qt moc 文件添加失败


下一篇：（十七）网络层--总结