欢迎光临散文网 会员登陆 & 注册

USACO2023JanuarySilverProblem1FindandReplace

2023-07-26 10:39 作者:信奥赛USACO郑老师  | 我要投稿

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {

    int T;

    cin>>T;

    while(T>0){

        vector<int> g(128),inDegree(128);

        T--;

        string s,t;

        cin>>s>>t;

        bool miss=false;

        set<int> allc,outchar;

        set<pair<int,int>> inpair;

        bool notAlleq=false;

        for(int i=0;i<s.size();i++){

            int a=(int)s[i], b=(int)t[i];

            if(inpair.count(make_pair(a,b))>0){//ignore duplicated pairs

                continue;

            }else{

                inpair.insert(make_pair(a,b));

            }

            if(g[a]>0&&g[a]!=b){

                miss=true;

                break;

            }

            outchar.insert(b);

            allc.insert(a), allc.insert(b);

            if(a!=b){

                notAlleq=true;

            }

            g[a]=b;

            inDegree[b]++;

        }

        if(miss){

            cout<<-1<<endl;

            continue;

        }

        if(outchar.size()==52&&!(s==t)){

            cout<<-1<<endl;

            continue;

        }        

        int ans=0;

        int count=0;

        for(int c:allc){

            if(g[c]>0){

                if(g[c]!=c){

                    ans++;                        

                }else{

                    g[c]=0;

                }

            }

        }

        //find all pure cycle to add ans

        vector<int> pathRec(128);

        for(int c:allc){

            if(pathRec[c]>0){

                continue;

            }

            int a=c;

            bool endFound=false;

            bool hasInDegreeMoreThanOne=false;

            while(pathRec[a]==0){

                pathRec[a]=c;

                if(inDegree[a]>1){

                    hasInDegreeMoreThanOne=true;

                }

                if(g[a]>0){

                    a=g[a];

                }else{

                    endFound=true;

                    break;

                }                

            }

            if(!endFound&&pathRec[a]==c&&!hasInDegreeMoreThanOne){

                ans++;

            }

        }

        cout<<ans<<endl;

    }

    return 0;

}


USACO2023JanuarySilverProblem1FindandReplace的评论 (共 条)

分享到微博请遵守国家法律