7
16
2015
1

【深搜剪枝】NOIP2004 T4虫食算

codevs传送门

NOIP的深搜果然不是吃素的QAQ。

一开始按照小学奥数的姿势,从末尾数字向前枚举,写了个【真暴力·渣剪枝】。

结果TLE了最大的一个点(见最后):

Miserable Code :

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#define maxn 30
int n,M[100],K[maxn],ans,vim=0;;
int A[maxn],B[maxn],C[maxn];//A+B=C
int init()
{
	scanf("%d\n",&n);
	int c;
	for (int i=1;i<=n;i++)
		scanf("%c",&A[i]);
	scanf("\n");
	for (int i=1;i<=n;i++)
		scanf("%c",&B[i]);
	scanf("\n");
	for (int i=1;i<=n;i++)
		scanf("%c",&C[i]);
	for (int i=65;i<=maxn+65;i++)
		M[i]=-1;
}
int MM[maxn];
void dfs(int x,int JW)
{
	if (vim) return;
	if (x==0&&JW==0)
	{
		for (int i='A';i<='A'+n-1;i++)
			printf("%d ",M[i]);
		vim=1;
		return;
	}
	if (x==0) return;
	if (M[A[1]]+M[B[1]]>=n) return;
	int a1=0,a2=n-1,b1=0,b2=n-1,c1=0,c2=n-1;
	int AA=M[A[x]],BB=M[B[x]],CC=M[C[x]];
	if (M[A[x]]>=0)a1=a2=M[A[x]];
	if (M[B[x]]>=0)b1=b2=M[B[x]];
	if (M[C[x]]>=0)c1=c2=M[C[x]];
	if (a1==a2&&b1==b2&&c1==c2);
	else
	{
		if (b1==b2&&c1==c2) 
			a1=a2=(c1-b1-JW+n)%n;
		if (a1==a2&&c1==c2) 
			b1=b2=(c1-a1-JW+n)%n;
	}
	for (int a=a1;a<=a2;a++)
	{
		if (K[a]&&(K[a]!=A[x])) continue; 
		for (int b=b1;b<=b2;b++)
		{
			int c=(a+b+JW)%n;
			if (c1<=c&&c<=c2) 
			if ((a==b)^(A[x]==B[x])) continue;
			if ((c==b)^(C[x]==B[x])) continue;
			if ((c==a)^(C[x]==A[x])) continue;
			
			if (K[b]&&(K[b]!=B[x])) continue;
			if (K[c]&&(K[c]!=C[x])) continue;
			else
			{
				int KA=K[a],KB=K[b],KC=K[c];
				M[A[x]]=a;M[B[x]]=b;M[C[x]]=c;K[a]=A[x];K[b]=B[x];K[c]=C[x];
				dfs(x-1,(a+b+JW)/n);
				K[a]=KA;K[b]=KB;K[c]=KC;M[A[x]]=AA;M[B[x]]=BB;M[C[x]]=CC;
			}
			if (vim) return;
		}
	}
		
}
int main()
{
	init();
	dfs(n,0);
	return 0;
}

然后改了个姿势,枚举每个字母对应的数字,深搜到下一层之前判断已有的情况。

结果手测仍然TLE QAQ。

最后把上面两个姿势结合,(实际上就是第一个程序+每次判断),注意应该先把数字放得比较大(剪枝效率高),就秒了←_←

Final Code (略压缩):

#include<cstdio>略压缩
#define maxn 30
int n,M[maxn],K[maxn],X[maxn],vim=0,now;
char S[3][maxn];
int Judge()
{
	int JW=0,t;
	for (int i=n;i>=1;i--)
	{
		t=M[S[0][i]-'A']+M[S[1][i]-'A']+JW;
		if (t%n!=M[S[2][i]-'A']) return 0;
		JW=t/n;
	}
	if (JW) return 0;
	for (int i=0;i<=n-1;i++)printf("%d ",M[i]);
	return 1;
}
int Hehe()
{
	int ma,mb,mc,t;
	for (int i=n;i>=1;i--)
	{
		ma=M[S[0][i]-'A'];mb=M[S[1][i]-'A'];mc=M[S[2][i]-'A'];
		int  t1=(ma+mb)%n,t2=(ma+mb+1)%n;
		if (ma!=-1&&mb!=-1&&mc!=-1) if (t1==mc||t2==mc) continue;else return 0;
		if (ma!=-1&&mb!=-1) if (K[t1]&&K[t2]) return 0;else continue;
		if (mc!=-1&&mb!=-1) if (K[(mc-mb+2*n)%n]&&K[(mc-mb-1+2*n)%n]) return 0;else continue;
		if (mc!=-1&&ma!=-1) if (K[(mc-ma+2*n)%n]&&K[(mc-ma-1+2*n)%n]) return 0;else continue;
	}
	return 1;
}
void dfs(int x)
{
	if (x>n) {if (Judge()) vim=1;return;}
	for (int i=n-1;i>=0;i--)
		if (!K[i]) 
		{	
			M[X[x]]=i;K[i]=1;
			if (Hehe()) 
				dfs(x+1);
			if (vim) return;
			K[i]=0;M[X[x]]=-1;
		}
}
int main()
{
	scanf("%d",&n);
	int c;
	for (int i=0;i<3;i++)
	{
		scanf("\n");
		for (int j=1;j<=n;j++)
			scanf("%c",&S[i][j]);
	}
	for (int i=n;i>=1;i--)
		for (int j=0;j<3;j++)
		{
			if (!M[S[j][i]-'A'])
			{
				M[S[j][i]-'A']=-1;
				X[++now]=S[j][i]-'A';
			}
		}
	dfs(1);
	return 0;
}
【附】TLE某点:
 
IN:
20
NLHFIEASBRQJOGKMDPCT
NQGPSIIGKDMFDCBFMQSO
PNKNTOLHEIJHFGJKHJGG
 
OUT:
18 14 0 9 15 17 7 13 12 16 1 10 4 2 8 5 11 3 6 19

CCF/NOIP不得好死

自制黑幕,装完逼就跑真TM刺激。

Category: NOIP | Tags: NOIP 枚举 | Read Count: 839
AP 2nd Inter Economi 说:
2022年9月08日 21:55

The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student, and the economics subject paper-1 AP 2nd Inter Economics Model Paper and paper-2 important questions with suggestions are available through AP Jr and Sr inter Economics Model Paper 2023 Pdf with guess paper. The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com