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

>传送门<

题意：

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

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

思路：

想都想不到的拓扑排序。

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

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

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

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

Code

#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;

}

巴特西

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

最新文章

热门文章