C. String Transformation 1(图的思想)

Problem - 1384C - Codeforces

题意:

考拉有两个长度相同的字符串A和B（|A|=|B|=n），由前20个小写英文字母组成（即从a到t）。

在一步棋中，Koa。

(选择A的某个位置子集p1,p2,...,pk（k≥1;1≤pi≤n;pi≠pj如果i≠j），如果Ap1=Ap2=...=Apk=x（即这个位置上的所有字母都等于某个字母x）。

从英语字母表的前20个小写字母中选择一个字母y，使y>x（即字母y在字母表上严格大于x）。

将位置p1,p2,...,pk中的每个字母设置为字母y。更正式地说：对于每个i（1≤i≤k）Koa设置Api=y。
注意，你只能修改字符串A中的字母。)

Koa想知道她为使字符串相互相等（A=B）或确定没有办法使它们相等所要做的最小的移动次数。请帮助她!

输入
每个测试包含多个测试用例。第一行包含t（1≤t≤10）--测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数n (1≤n≤105) - 字符串A和B的长度。

每个测试用例的第二行包含字符串A（|A|=n）。

每个测试用例的第三行包含字符串B(|B|=n)。

这两个字符串由前20个小写英文字母组成（即从a到t）。

保证所有测试用例的n之和不超过105。

 题解:

a只能变大,很明显,如果某个ai大于bi是一定无解的

那对于有解的情况

拿例一来说吧

aab

bcc

如果正常来想

a->b

a->c

b->c

三步

 接着我们结合上面这个图来看

a->b

a->b->c

b->c

我们可以发现可以先让a到可以到的最小的字母b

如果b和a都要到一个更大的字母c

就相当于省去了步数

#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector> 
using namespace std;
char a[100050],b[100050];
int f[30][30];
void solve()
{
	int n;
	cin >> n;
	cin >> a+1>>b+1;
	memset(f,0,sizeof f);
	for(int i = 1;i <= n; i++)
	{
		if(a[i] > b[i])
		{
			cout<<"-1\n";
			return ;
		}
		if(a[i]<b[i])
		f[a[i]-'a'][b[i]-'a'] = 1;
	} 
	int ans = 0;
	for(int i = 0;i < 20;i++)
	{
		for(int j = i+1;j < 20;j++)
		{
			if(f[i][j])
			{
				ans++;
				for(int k = j+1;k < 20;k++)
				{
					if(f[i][k])
					{
						f[j][k] = 1;
					}
				}
				break;
			}
		}
	}
	cout<<ans<<"\n";
	
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	
}