题目链接: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;
}