Codeforces Round #659 (Div. 1) A.String Transformation 1
题目链接
Koa the Koala has two strings A and B of the same length n (|A|=|B|=n) consisting of the first 20 lowercase English alphabet letters (ie. from a to t).
In one move Koa:
selects some subset of positions p1,p2,…,pk (k≥1;1≤pi≤n;pi≠pj if i≠j) of A such that Ap1=Ap2=…=Apk=x (ie. all letters on this positions are equal to some letter x).
selects a letter y (from the first 20 lowercase letters in English alphabet) such that y>x (ie. letter y is strictly greater alphabetically than x).
sets each letter in positions p1,p2,…,pk to letter y. More formally: for each i (1≤i≤k) Koa sets Api=y.
Note that you can only modify letters in string A.
Koa wants to know the smallest number of moves she has to do to make strings equal to each other (A=B) or to determine that there is no way to make them equal. Help her!
Input
Each test contains multiple test cases. The first line contains t (1≤t≤10) — the number of test cases. Description of the test cases follows.
The first line of each test case contains one integer n (1≤n≤1e5) — the length of strings A and B.
The second line of each test case contains string A (|A|=n).
The third line of each test case contains string B (|B|=n).
Both strings consists of the first 20 lowercase English alphabet letters (ie. from a to t).
It is guaranteed that the sum of n over all test cases does not exceed 105.
Output
For each test case:
Print on a single line the smallest number of moves she has to do to make strings equal to each other (A=B) or ?1 if there is no way to make them equal.
Example
input
5
3
aab
bcc
4
cabc
abcb
3
abc
tsr
4
aabd
cccd
5
abcbd
bcdda
output
2
-1
3
2
-1
这题比较考验思维~
我们发现从 A-Z 这样变化就能涵盖所有操作，那么可以进行建图，将
初始化为
，把所有
和
建边，每次 DFS 都减
即可，AC代码如下:
#include<bits/stdc++.h>
using namespace std;
vector<int>g[20];
int vis[20];
void dfs(int u){vis[u]=1;for(int v:g[u]){if(!vis[v]) dfs(v);}
}void init(){for(int i=0;i<20;i++) vis[i]=0,g[i].clear();
}int main(){int t,n;string a,b;cin>>t;while(t--){init();cin>>n>>a>>b;int flag=0;for(int i=0;i<n;i++){if(a[i]!=b[i]){if(a[i]>b[i]){flag=1;break;}}g[a[i]-'a'].push_back(b[i]-'a');g[b[i]-'a'].push_back(a[i]-'a');}if(flag){printf("-1\n");continue;}int ans=20;for(int i=0;i<20;i++){if(!vis[i]) dfs(i),ans--;}cout<<ans<<endl;}
}