2019牛客暑期多校训练营（第五场）H-subsequence 2 (拓扑排序+思维)

系统管理员 2021-10-23 17:14 184阅读 0赞

[>传送门<][Link 1]

**题意：**

给你几组样例，给你两个字符**a**，**b**，一个长度**len**，一个长度为**len**的字符串**str**，**str**是字符串**s**的子串

**str**是**s**删掉除过**a**，**b**两字符剩下的子串，现在求**s**，多种情况输出一种。构造不出来输出-1

**思路：**

想都想不到的[拓扑排序][Link 2]。

因为这个**str**肯定是满足**s**顺序关系的**s**的子串，所以依次对**str**建图，又因为给了好几个子串所以全部建图，如果最后跑完拓扑，得到的字符串长度等于**s**长度即 可。

**所以今后遇到求顺序一定的问题或图，哪怕是字符串都往拓扑排序靠**

**细节：**对于这道题最重要的就是对每一个字符编号

1.     **pos = (s\[i\]-'a')\*10000+sum; sum**为该字符出现的次数；
2.     **ans += (u-1)/10000+'a'; u**为编号； 即时出现**cc**这种情况，编号为20001,20002，但**(u-1)/10000+'a**结果都是等于**c**的
3.     强的一批的编号方式

** Code**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn = 1e6 + 5;
    
    int n, m, len;
    char a, b;
    int in[maxn], num[30]; //in表示入度， num表示各字母在原序列中出现的次数 
    vector<int> e[maxn]; //记录边 
    string s, ans;
    //拓扑排序 
    bool topsort()
    {
        queue<int> q;
        for(int i = 0; i < 26; i++){
            //之所以只取相同字母的第一个，是因为在第一个后面出现的肯定会有入度 
            if(in[i*10000+1]==0&&num[i]!=0) 
                q.push(i*10000+1);
        }
        while(!q.empty()) {
            int u=q.front(); q.pop();
            ans += (u-1)/10000+'a';
            for(int v = 0; v < e[u].size(); v++){
                if(--in[e[u][v]]==0)
                    q.push(e[u][v]);
            }
        }
        if(ans.size()==n) return true;
        else return false;    
    }
    int main()
    {
        cin >> n >> m;
        for(int i = 0; i < (m-1)*m/2; i++) { 
            cin >> a >> b >> len;
            if(len==0) continue;
            cin >> s;
            int pos, pre = -1, na = 0, nb = 0;
            for(int i = 0; i < len; i++) {
                if(s[i]==a) pos = (s[i]-'a')*10000 + (++na); //对相应的点进行编号 
                else pos = (s[i]-'a')*10000 + (++nb);
                if(pre==-1) pre = pos;
                else {
                    e[pre].push_back(pos); //添加边（即使是重边也没有关系） 
                    in[pos]++;
                    pre=pos;
                }
            }
            num[a-'a'] = na, num[b-'a'] = nb; //用来记录a, b是否原在序列中出现过 
        }
        
        if(topsort()) cout<<ans<<endl;
        else cout<<-1<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/wizarderror/p/11311196.html

[Link 1]: https://ac.nowcoder.com/acm/contest/885/H
[Link 2]: https://www.cnblogs.com/wizarderror/p/11311082.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/6ee04220c9bc4c069f9225621c7a977e.png