H - subsequence 2
题意
要你使用前(m)个小写字母构造一个长度为(n)的字符串
有(m*(m-1)/2)个限制条件:
- (c_{1} 、c_{2}、 len)：表示除去其他非(c_{1}、c_{2})之外的字母剩下的串长度为(len)
- (s)：除去其他非(c_{1}、c_{2})之外的字母剩下的字符串，长度为(len)
需要我们根据这个限制条件构造出原串，如果不存在输出(-1)
思路
我们可以发现题目给了两个字母之间的相对位置。比如(aab)，第二个(a)前面一定得接了个(a)，(b)一定要第二个(a)的条件符合之后，然后第二个(a)放进去之后才能到(b)
那么对于每个字母都要先把前面的都输出完了，才能到自己，那么我们可以想到拓扑（其实是队友想的），一定要入度为零才能到本身，然后我们就可以和拓扑结合起来。
- 定义字母：我们可以令(a)为(0000)~(9999)之间的数来定义（因为最多可能有(1e^4)个）， 然后(b)用(10000)~(19999)这样接下去定义每个字母。
- 建图：根据题目给的串建图， 前后建一条边。
- 然后去跑拓扑就(OK)了
- 如果你构造出来的串长度不为(n)就输出(-1)（出现循环节之类乱七八糟的情况）
一些坑点
- 建图的时候要判断会不会出现前面出现的(a)有(3)个，这次出现的(a)有(4)个这样的情况，这样不符合条件，可以加一个数组特判一下。
- 输入要注意(len = 0)的时候会输入空行，这边要处理好。（没处理好的我，(WA)了好多发）
一些数据
这些数据都是输出(-1)，其实我第一组数据之前只是输入出锅了，然后导致我一直(WA)，其实我没有输出(-1)也过了
3 3
ab 3
aab
ac 2
aa
bc 0
3 3
ab 3
aab
ac 1
a
bc 1
b
AC 代码
（本人太菜，代码很乱，请多见谅）
#include<bits/stdc++.h>
#define mes(a, b) memset(a, b, sizeof a)
using namespace std;
const int maxn = 1e4+10;
int n, m;
int head[maxn*50], f[30], cnt, in[maxn*50], sum[30];
char ch[maxn];
vector<int> ans;
struct Edge{
int v, next;
}e[maxn*50];
void init(){ //初始化
mes(head, -1);
mes(in, 0);
mes(sum, 0);
for(int i = 0; i <= 26; i++){
f[i] = i*10000;
}
ans.clear();
cnt = 0;
}
void add(int u, int v){
e[++cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
int change(int u){ //根据字母的ID转换为字母
for(int i = 0; i < 26; i++){
if(u - f[i] < 10000)
return i;
}
}
int topu(){
queue<int> q;
int tot = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < sum[i]; j++){
if(!in[j+f[i]]){
q.push(j+f[i]);
}
}
}
while(!q.empty()){
int u = q.front(); q.pop();
if(change(u) >= m)
return -1;
ans.push_back(change(u));
tot++;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
in[v]--;
if(!in[v])
q.push(v);
}
}
return tot;
}
int main(){
scanf("%d%d", &n, &m);
init();
int q = m*(m-1)/2;
char c1, c2;
int len;
int flag = 0;
while(q--){
char s[10];
scanf("%s%d", s, &len);
c1 = s[0];c2 = s[1];
getchar();
gets(ch);
int cnt1 = 0, cnt2 = 0, u, v; //cnt1:c1字母出现的次数
if(len > 0){ //cnt2:c2字母出现的次数
if(ch[0] == c1){
u = cnt1+f[c1-'a'];
cnt1++;
}
else{
u = cnt2+f[c2-'a'];
cnt2++;
}
for(int i = 1; i < len; i++){
if(ch[i] == c1){
v = cnt1+f[c1-'a'];
cnt1++;
}
else{
v = cnt2+f[c2-'a'];
cnt2++;
}
add(u, v);
u = v;
in[v]++;
}
}
if(!sum[c1-'a']|| sum[c1-'a'] == cnt1) //如果这次出现的次数和之前不一样，不符合条件
sum[c1-'a'] = cnt1;
else
flag = 1;
if(!sum[c2-'a']|| sum[c2-'a'] == cnt2)
sum[c2-'a'] = cnt2;
else
flag = 1;
}
int num = topu();
if(num != n || flag){
printf("-1
");
return 0;
}
for(int i = 0; i < ans.size(); i++){
printf("%c", ans[i]+'a');
}
printf("
");
return 0;
}