nowcoder多校5-subsequence 2(拓扑排序)

题目链接:nowcoder多校5-subsequence 2

题意:

有一个长度为n字符串,然后有m个询问,每次询问两个字母,然后给出原字符串中仅保留这两个字母的形式,问最终是否能准确得到那个长度为n的字符串。

题解:

对于每次询问的回答,只需要把第i个和第i+1个连有向边,然后拓扑排序即可,没必要连出所有的边(会MLE)。

参考代码:

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 1e4 + 4;
const int MAXM = 26 * 1e4 + 5;
const int inf = 1e4 + 4;
const int mod = 1e4 + 4;
int n, m;
struct EDGE
{
    int v, nxt;
} edge[MAXM << 6];
int fir[MAXM], ecnt = 0;
void addedge(int u, int v)
{
    edge[ecnt].v = v;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
char cc[MAXN];
int flag = 0;
int num[MAXN], tot[30], deg[MAXM];
vector<int> vec;
void topo()
{
    queue<int> q;
    while (!q.empty())
        q.pop();
    vec.clear();
    flag = 0;
    for (int i = 0; i < MAXM; i++)
        if (deg[i] == 0)
            q.push(i), flag++;
    if (flag != 1)
        return;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vec.push_back(u);
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            deg[v]--;
            if (!deg[v])
                q.push(v);
        }
    }
}
int main()
{
    cin >> n >> m;
    memset(deg, -1, sizeof(deg));
    memset(fir, -1, sizeof(fir));
    for (int i = 1; i <= m * (m - 1) / 2; i++)
    {
        char c1, c2;
        cin >> c1 >> c2;
        int len;
        cin >> len;
        memset(tot, 0, sizeof(tot));
        memset(num, 0, sizeof(num));
        for (int j = 1; j <= len; j++)
            cin >> cc[j], tot[cc[j] - 'a']++;
        for (int j = 1; j <= len; j++)
        {
            num[j] = (tot[cc[j] - 'a'] - 1) * 26 + (cc[j] - 'a');
            tot[cc[j] - 'a']--;
        }
        for (int j = 1; j < len; j++)
        {
            int k = j + 1;
            if (deg[num[j]] == -1)
                deg[num[j]] = 0;
            if (deg[num[k]] == -1)
                deg[num[k]] = 0;
            addedge(num[j], num[k]);
            deg[num[k]]++;
        }
    }
    topo();
    if (flag != 1)
        return puts("-1"), 0;
    if ((int)vec.size() == n)
    {
        for (auto v : vec)
            printf("%c", v % 26 + 'a');
    }
    else
        puts("-1");
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。