一道简单却又不简单的深搜题

ok，进入正题。显然这题是一题深搜的题目，but!!! 我在考试中获得了个优锈的成绩——0。至于为什么，我们稍后再讲。

首先啊，先毒一波题目。可以发现这题是有一个阴间的输入的。

要用到：while(cin>>n)啊

其次，很多人看到这题都不知所措，我先给大家看看我的数组以及每一个数组的用处。最主要的数组就是下面这仨：

bool b1[45]={false};//这个是用来标记是否为质数，因为题目最多n只有20所以其实这个数组开个20+19=39位就可以了，但是还是建议各位开大点。
bool use[20];//这个呢就是用来标记用过的数字的，所以一样用bool即可
int ans[20];//这个是用来表示符合题目要求的答案，当然也是每找出一个就会重置的

好的，现在讲完了数组，来看看最重要的部分——dfs（深搜）

但是，如果看到这里的小伙伴们并没有学过深搜是何物，可以去百度上和bilibili上找一下相关教程。学会了学懂了再回来看，毕竟如果深搜的扫地图都不会还做个毛

void dfs(int first,int last,int num,int n)//首先看到我这里用的深搜参数，各位可以按需求调整，我也觉得我的太多太麻烦了，但是这样实用。这里的各个参数的用法和用处，详见本文的P1。
{
	if(num==n)//详见P2
	{
		cout<<1;
		for(long long i=1;i<n;i++)
		{
			cout<<" "<<ans[i];
		}
		cout<<endl;
		return ;
	}
	for(long long i=1;i<=n;i++)//详见P3
	{
		if(use[i]==false && check(first,last,num,i,n))
		{
			ans[num]=i;
			use[i]=true;
			dfs(first,i,num+1,n);
			ans[num]=0;//详见P5
			use[i]=false;
		}
	}
	return ;
}

$P1$：

$first$的用法就是标记这一次搜索的第一个数字是什么。因为在搜索嘴和一个的时候是需要用到的。当然，这个变量没用，因为我们可以发现每个的第一个数字固定是$1$

$last$的用法是用来标记上一个往ans数组里面填入的是第几个，当然，我用这个变量只是为了明确点，完全可以改成$ans[num-1]$，因为这样就可以省略这个变量

$num$,这也是最重要的一个变量，不可以省略掉。$num$这个变量是用来标记你现在要开始填入第几个数，这样！你才知道你吃的是大肠！（自信） 你才知道你现在要填入第几个数，当然，这个变量还是可以省略的，只要你不怕花费一番功夫遍历一次ans数组。但是有了这个变量显然让整个dfs变得快了很多，毕竟dfs追求的不就是时间复杂度嘛。

$n$，这个就更容易理解了。就是你所输入的数字，也就是你要找这么多的数字。用处就是如果$num==n$的话，你才可以输出出答案来，否则你会受到死循环的暴击。

$P2$：

这就是上面$P1$所说的判断$num==n$的地方。首先固定肯定是要输出1的，接着再输出$ans$数组。

$P3$：

这就是深搜的点睛之笔了，也就是非常非常重要的。先全部遍历一次，但是一定要按照字典序。随后我们需要检查一下use数组有没有用过这个数字，如果用过，就跳过。没有用过的话还要检查，就是上面写的$check$函数，（$check$ 函数详见P6）

如果满足$check$函数的话，就可以准备进入深搜了。当然，还要先标记一次。为什么这里不能直接输出呢，因为你不知道后面的数字会不会影响到这里。标记就是将$use$数组的对应位置变为true表示已经用过了。然后再把答案填入$ans$数组里面。

$P5$：

至于为什么没有$P4$的话呢，那是因为我要遵从不四原则。好，回归正题，这一段呢主要就是回溯了，毕竟如果说这个在后面是不符合的条件的话，还要再把$use$数组改回来。

$P6$：

这一段就是放$check$函数了

bool check(int first,int last,int num,int now,int n)
{
	if(num+1==n)
	{
		if(b1[first+now]==true && b1[last+now]==true)
		{
			return true;
		}else
		{
			return false;
		}
	}else
	{
		if(b1[last+now]==true)
		{
			return true;
		}else
		{
			return false;
		}
	}
}

变量的意思和前面dfs的部分是一样的。

最后，就是主函数部分了

再提一句，代码仅供参考，请勿$CTJ$,$CTJ$有害自己的编程实力！！！

int main()
{
	bool b;
	for(long long i=2;i<=40;i++)
	{
		b=true;
		for(long long j=2;j*j<=i;j++)
		{
			if(i%j==0)
			{
				b=false;
				break;
			}
		}
		if(b==true)
		{
			b1[i]=true;
		}
	}
	long long n;
	int u=1;
	while(cin>>n)
	{
		cout<<"Case "<<u<<":"<<endl;
		if(n==1)//详见P7
		{
			continue;
		} 
		memset(use,false,sizeof(use));//详见P8
		use[1]=true;
		dfs(1,1,1,n);
		u++;
	}
}

$P7$：

这里就是我所说的坑点，比赛我也是因为这个0的，因为当$n$为0或者1时，不输出任何数。

$P8$：

这个就是喜闻乐见的$memset$函数，不过要注意一下，$memset$这货是按照字节来赋值的，所以只在$0$或者$-1$的时候才能赋值成功。

好的，那么这篇题解也是我写过最长的一篇了，写了我两刻半。