1002. Anti-prime Sequences

TAG 搜索 回溯 深度优先

之前看了这题目，毫无头绪，所以搁置了很久，到最近才ac掉。

这种题目，应该是没办法用数学方法推算的，就算有，我想我也推不出。不过1000个数的全排列太大了，用搜索好像又会超时。但仔细分析又发现，条件比较苛刻，all consecutive subsequences of length 2,3,...,d sum to a composite number，也就是说，从2到d的子序列都要满足，不单单d长度的。 /*我一开始理解错了*/ 这样的话，能大量剪枝，保证不会超时。而且只需找到一个字典序最小的解，也提示我们应该是按字典序进行深搜。

所以仔细分析后，大胆深搜就可以ac了。这也启示我今后看到问题不要轻言放弃，要仔细分析，不要被题目表象迷惑，说不定只是水题一道。

(^ω^)

#include <stdio.h>
#include <memory.h>
const int N=10000;
bool isprime[N];
int  n,m,d;
bool used[1001];
int  seq[1001];
bool found;
void makeprime()
{
	memset( isprime, true, sizeof(isprime) );
	for (int i=2; i<=100; ++i)
	{
		if ( isprime[i] )
		{
			for (int j=2; j*i<N; ++j)
			{
				isprime[j*i]=false;
			}
		}
	}
}
bool  check_pre(int pt,int num)
{
	int sum=num;
	for (int i=2; i<=d && pt-i+1>0; ++i)
	{
		sum+=seq[pt-i+1];
		if ( isprime[sum] )
		{
			return false;
		}
	}
	return true;
}
void search_seq(int depth)
{
	if ( depth > (m-n)+1 )
	{
		found=true;
			printf("%d",seq[1]);
		    for (int i=n+1; i<=m; ++i )
		    {
				printf(",%d", seq[i-n+1] );
		    }
			printf("/n");
		return;
	}
	for (int i=n; i<=m && !found; ++i)
	{
		if ( !used[i] )
		{
			if ( check_pre(depth,i) )
			{
				seq[depth]=i;
				used[i]=true;
				search_seq(depth+1);
				used[i]=false;
			}
		}
	}
}

int main(int argc, char *argv[])
{
	makeprime();
	while ( scanf("%d%d%d", &n, &m, &d) && (n+m+d)!=0 )
	{
		memset(used, false, sizeof(used) );
		found=false;
		for (int i=n; i<=m && !found; ++i)
		{
			used[i]=true;
			seq[1]=i;
			search_seq(2);
			used[i]=false;
		}
		if ( !found )
		{
			printf("No anti-prime sequence exists./n");
		}
	}
	return 0;
}