SRX_Test_2_key

╰+攻爆jí腚メ 2021-10-25 14:56 154阅读 0赞

转载自 Livedream

YBT1396

#include<iostream>
    #include<map>
    #include<queue>
    #include<vector>
    using namespace std;
    /*
    无解的情况：
    1. 能确定的字母种类少于目标单词的字母种类，比如能确定abc，但目标单词中含有e
    2. 拓扑排序的结果不唯一，也就是每次发现的入度为0的结点不唯一 
    3. 拓扑排序有环 
    */ 
    string s[5005], t, std_s;
    map<char, char> Map;
    vector<char> v[125];
    int in[125], tot;
    bool vis[125];
    char ans[27];
    
    string get_dict() //获取图中的字符的字典序 字符串 
    {
        string tmp = ""; //标准字典序串 
        for(char c = 'a'; c <= 'z'; c++)
        {
            if(vis[c] == true)
            {
                tmp += c;
            }
        }
        return tmp; //标准字符串 
    }
    
    bool is_enough() //判断结点是否足够 
    {
        for(int i = 0; i < t.size(); i++)
        {
            if(vis[t[i]] == false) //目标单词t中存在字符t[i]，而建的图中没有 
                return false;
        }
        return true; 
    } 
    
    bool topo_sort()
    {
        queue<char> q;
        int cnt = 0;
        for(char c = 'a'; c <= 'z'; c++)
        {
            if(vis[c] == true && in[c] == 0)
            {
                q.push(c);
                cnt++;
                if(cnt > 1)
                    return false;
            }
        }
        while(q.empty() == false)
        {
            char cur = q.front();
            q.pop();
            ans[++tot] = cur; //存拓扑排序结果 
            int cnt = 0; //记录拆掉cur结点后有多少结点的入度减为0 
            for(int i = 0; i < v[cur].size(); i++)
            {
                char next = v[cur][i];
                in[next]--;
                if(in[next] == 0)
                {
                    cnt++; //统计入度为0的点 
                    q.push(next);
                } 
            }
            if(cnt > 1) //入度为0的点多于1个，无解 
                return false;
        }
        std_s = get_dict(); //获取图中的节点数 
        if(tot < std_s.size()) //有环 
            return false;
        return true;
    } 
    void print()
    {
        for(int i = 1; i <= tot; i++)
        {
            Map[ans[i]] = std_s[i-1]; //ans和std_s建立对应关系 
        }
        for(int i = 0; i < t.size(); i++)
        {
            cout << Map[t[i]];
        }
        return ;
    } 
    int main()
    {
        int k;
        cin >> k;
        for(int i = 1; i <= k; i++)
        {
            cin >> s[i];
            if(i == 1)
                continue;
            for(int j = 0; j < min(s[i].size(), s[i-1].size()); j++)
            {
                char c1 = s[i-1][j], c2 = s[i][j];
                if(c1 != c2)
                {
                    v[c1].push_back(c2);
                    in[c2]++; //入度 
                    vis[c1] = vis[c2] = true;
                    break; //只找第一对不相同的字符 
                }
            }
        }
        cin >> t; //目标字符串 
        if(is_enough() == false || topo_sort() == false)
        {
            cout << 0;
            return 0;
        }
        print();
        return 0;
    }

转载于:https://www.cnblogs.com/yangxuejian/p/10963090.html