USACO silver T1求调/hack
查看原帖
USACO silver T1求调/hack
396994
Winston12321_楼主2023/1/31 22:55

rt,比赛结束了,终于可以请教大佬了!

思路:一个字母对应多个字母是不合法的,然后统计转换数类似建成图,此外每一棵基环树都会多耗费一次转换,这时如果52个字母都需要转换那么也是不合法的

#include <iostream>
#include <cstring>
using namespace std;
int T;
string a,b;
int len;
int mp[140];
int vis[140];
int vn[140];
int ans;
int use;
bool huan;
int main()
{
	cin>>T;
	while(T--)
	{
		memset(mp,0,sizeof(mp));
		memset(vis,0,sizeof(vis));
		ans=0;
		use=0;
		huan=0;
		cin>>a>>b;
		len=a.length();
		a=' '+a;
		b=' '+b;
		for(int i=1;i<=len;++i)
			if(!mp[a[i]])
			{
				++use;
				mp[a[i]]=b[i];
				if(a[i]!=b[i]) ++ans;
			}
			else if(mp[a[i]]!=b[i])
			{
				ans=-1;
				break;
			}
		if(ans==-1)
		{
			cout<<-1<<endl;
			continue;
		}
		for(int i='a';i<='z';++i)
		{
			int tmp=i;
			while(true)
			{
				if(tmp==0 || vis[tmp]) break;
				vn[tmp]=1;
				if(tmp==mp[tmp]) break;
				tmp=mp[tmp];
				if(vn[tmp])
				{
					huan=1;
					++ans;
					break;
				}
			}
			for(int j=50;j<=130;++j) if(vn[j]) vis[j]=1,vn[j]=0;
		}
		for(int i='A';i<='Z';++i)
		{
			int tmp=i;
			while(true)
			{
				if(tmp==0 || vis[tmp]) break;
				vn[tmp]=1;
				if(tmp==mp[tmp]) break;
				tmp=mp[tmp];
				if(vn[tmp])
				{
					huan=1;
					++ans;
					break;
				}
			}
			for(int j=50;j<=130;++j) if(vn[j]) vis[j]=1,vn[j]=0;
		}
		if(huan && use==52) ans=-1;
		cout<<ans<<endl;
	}
	return 0;
}
2023/1/31 22:55
加载中...