P9013 [USACO23JAN] Find and Replace S 题解

P9013 [USACO23JAN] Find and Replace S题目描述Bessie 正在使用世界上最先进最伟大的文本编辑器miV她想将一个仅由大写和小写英文字母组成的字符串转换为一个新的字符串。每一次操作miV 可以将字符串中所有的字母c 1 c_1c1​替换成另一种字母c 2 c_2c2​。例对于字符串aAbBa如果将其中的a替换成B那么字符串会变为BAbBB。Bessie 非常地忙碌所以对于给出的T ( 1 ≤ T ≤ 10 ) T (1 \le T \le 10)T(1≤T≤10)组测试数据请输出她至少需要多少次操作才能把原字符串转换为新字符串。输入格式第一行是一个整数T TT表示测试数据的数量。接下来有T TT对长度相等的字符串。字符串中所有的字符都是大写或小写的字母。字符串的长度不会超过10 5 10^5105。输出格式对于每组测试数据输出转换字符串需要的最小操作数。如果这不可能做到输出− 1 -1−1。样例 1 解释第一组数据两个字符串相等所以不需要任何操作。第二组数据你不可能在把其中一个B转换为A的同时保持剩下一个B不变。第三组数据你可以把字符串中所有的a转换为b。第四组数据你可以按ABCD → EBCD → EACD → BACD \texttt{ABCD} \rightarrow \texttt{EBCD} \rightarrow \texttt{EACD} \rightarrow \texttt{BACD}ABCD→EBCD→EACD→BACD的方式转换。输入输出样例 #1输入 #14 abc abc BBC ABC abc bbc ABCD BACD输出 #10 -1 1 3说明/提示对于 $ 40 % $ 的数据字符串的长度不超过50 5050。对于另外 $ 20% $ 的数据所有的字符串仅包含从a到e的小写字母。对于 $ 100% $ 的数据字符串的长度不超过10 5 10^51051 ≤ T ≤ 10 1 \le T \le 101≤T≤10。思路直接写即可。代码#includebits/stdc.husingnamespacestd;longlongt,a[505],u0,b[505],ud1,c[505],se[505],ce[505],op0,oc0,d[505],od0,que0,qve0,qqe0;string s,cc;vectorlonglongv[505],vv[505];queuelonglongq;mapchar,longlongmp;intmain(){cint;for(inti1;i26;i){mp[(char)(Ai-1)]i;// cout(char)(Ai-1)endl;}for(inti33;i58;i){mp[(char)(Ai-1)]i-6;// cout(char)(Ai-1)endl;}while(t--){cinscc;u0;op0;for(inti0;i53;i){a[i]0;v[i].clear();vv[i].clear();b[i]0;c[i]0;d[i]0;se[i]0;ce[i]0;}for(inti0;is.size();i){se[mp[s[i]]]1;if(a[mp[s[i]]]0){a[mp[s[i]]]mp[cc[i]];b[mp[s[i]]]1;v[mp[cc[i]]].push_back(mp[s[i]]);vv[mp[cc[i]]].push_back(mp[s[i]]);vv[mp[s[i]]].push_back(mp[cc[i]]);c[mp[cc[i]]]1;d[mp[s[i]]]1;d[mp[cc[i]]]1;}elseif(a[mp[s[i]]]!mp[cc[i]]){u1;break;}}for(inti0;icc.size();i){ce[mp[cc[i]]]1;}if(u1){cout-1endl;continue;}// for(int i1;i52;i){// couta[i] iendl;// }ud1;while(ud!0){ud0;for(inti1;i52;i){if(c[i]1(b[i]0||a[i]i)){c[i]0;b[i]0;for(intj0;jv[i].size();j){longlongttv[i][j];if(tt!i){op;}b[tt]0;}ud1;}}}oc0;for(inti1;i52;i){if(se[i]0ce[i]0){oc1;}}for(inti1;i52;i){if(se[i]0ce[i]1){oc1;}}for(inti1;i52;i){if(se[i]1ce[i]0b[i]0){oc1;}}od0;qve0;qqe0;for(inti1;i52;i){if(b[i]1||c[i]1){que0;q.push(i);b[i]c[i]0;// couti a[i]endl;while(q.size()!0){longlonga1q.front();q.pop();od;for(intj0;jvv[a1].size();j){longlongttvv[a1][j];if(b[tt]1||c[tt]1){q.push(tt);b[tt]0;c[tt]0;}}if(v[a1].size()2){que1;}}if(que0){od;qve1;}else{qqe1;}}}if(qqe0qve1oc0){cout-1endl;continue;}coutopodendl;}return0;}