Flandre Scarlet's Blog

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;
}

CCF/NOIP不得好死

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