TLE一半,求助
查看原帖
TLE一半,求助
881019
lihuanran楼主2023/7/12 14:58
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>

using namespace std;

inline int read()
{
	int p=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+(c^48),c=getchar();}
	return p*f;
}

char a[30],b[30],c[30];

map<char,int>mp;

int tmp[30],n;

inline bool check()
{
	memset(tmp,0,sizeof(tmp));
	for(register int i=n;i>=1;i--)
	{
		int x=mp[a[i]]+mp[b[i]];
		tmp[i]+=x%n;
		tmp[i-1]+=x/n;
		tmp[i-1]+=tmp[i]/n;
		tmp[i]%=n;
	}
	for(register int i=n;i>=1;i--)
		if(mp[c[i]]!=tmp[i]) return 0;
	return 1;
}

bool vis[30],flag;

inline bool judge()
{
	if(mp[a[1]]+mp[b[1]]>=n) return 0;
	for(register int i=n;i>=1;i--)
	{
		if(mp[a[i]]==-1||mp[b[i]]==-1||mp[c[i]]==-1) continue;
		if(((mp[a[i]]+mp[b[i]])%n!=mp[c[i]])&&((mp[a[i]]+mp[b[i]]+1)%n!=mp[c[i]])) return 0;
	}
	return 1;
}

char num[30];

void dfs(char ch)
{
	if(!judge()) return ;
	if(ch=='A'+n)
	{
		if(check()) 
		{
			for(register int i=0;i<n;i++)
				cout<<mp[i+'A']<<" ";
			exit(0);
		}
		return ;
	}
	for(register int i=n-1;i>=0;i--)
	{
		if(vis[i]) continue;
		mp[ch]=i;
		vis[i]=1;
		dfs((char)ch+1);
		mp[ch]=-1;
		vis[i]=0;
	}
}

bool v[250];

int main()
{
	scanf("%d",&n);
	scanf("%s %s %s",a+1,b+1,c+1);
	for(register int i=0;i<n;i++) mp['A'+i]=-1;
	dfs('A');
	return 0;
}
2023/7/12 14:58
加载中...