记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 1ms 216.0 KiB
#2 Accepted 2ms 228.0 KiB
#3 Accepted 2ms 224.0 KiB
#4 Accepted 2ms 228.0 KiB
#5 Accepted 3ms 216.0 KiB
#6 Accepted 2ms 228.0 KiB
#7 Accepted 22ms 300.0 KiB
#8 Accepted 4ms 232.0 KiB
#9 Accepted 50ms 300.0 KiB
#10 Accepted 2ms 212.0 KiB

代码

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 30
int a[maxn],b[maxn],c[maxn];
int num[maxn],Next[maxn],n,cnt;
char s1[maxn],s2[maxn],s3[maxn];
bool used[maxn];
inline int id(char c)
{
	return c-'A';
}
void GetNext(int x)
{
	if(used[x]==false)
	{
		used[x]=true;
		Next[cnt++]=x;
	}
	return ;
}
bool Judge()
{
	for(int i=n-1,x=0;i>=0;i--)
	{
		int A=num[a[i]],B=num[b[i]],C=num[c[i]];
		if((A+B+x)%n!=C) return false;
		x=(A+B+x)/n;
	}
	return true;
 } 
bool CanPrune()
{
	if(num[a[0]]+num[b[0]]>=n)//最高位的和大于n 
	 return true;
	for(int i=n-1;i>=0;i--)
	{
		int A=num[a[i]],B=num[b[i]],C=num[c[i]];
		if(A==-1||B==-1||C==-1) continue;
		if((A+B)%n!=C&&(A+B+1)%n!=C)
		 return true;
	}
	return false;
}
void Print()
{
	for(int i=0;i<n;i++)
	 printf("%d ",num[i]);
	exit(0);
}
void dfs(int x)
{
	if(CanPrune()==true) return ;
	if(x==n) {
		if(Judge()==true) Print();
		return ;
	}
	for(int i=n-1;i>=0;i--)
	{
		if(used[i]==false)
		{
			num[Next[x]]=i;
			used[i]=true;
			dfs(x+1);
			num[Next[x]]=-1;
			used[i]=false;
		}
		
	}
	return ;
}
int main()
{
	scanf("%d",&n);
	scanf("%s%s%s",s1,s2,s3);
	for(int i=0;i<n;i++)
	{
		a[i]=id(s1[i]);
		b[i]=id(s2[i]);
		c[i]=id(s3[i]);
		num[i]=-1;
	}
	for(int i=n-1;i>=0;i--)
	{
		GetNext(a[i]);
		GetNext(b[i]);
		GetNext(c[i]);
	}
	for(int i=0;i<n;i++) used[i]=false;
	dfs(0);
	return 0;
 } 

信息

递交者
类型
递交
题目
P1001 虫食算
语言
C++
递交时间
2020-06-07 11:28:59
评测时间
2020-06-07 11:28:59
评测机
分数
100
总耗时
94ms
峰值内存
300.0 KiB