题目链接：https://ac.nowcoder.com/acm/contest/885/H
3个人一起卡B卡一年，各种水题都没看，难顶。
由于前m个小写在字母地无序对恰好全部出现，我们可以直接算出每个字母的第几个应该在哪个位置。
比如我要确定字母a的第一个在第几个位置，那么就看所有有a的条件中，在第一个a之前的字母总和是多少，再加上a在他自己本身的次序1，就是它所在的位置。
无解的情况要小心，WA了几发。
1、每个字母所在的位置不能超过n
2、一个位置只能放一个字母
3、每个字母的个数在不同的条件中必须一样
4、1-n的位置必须放满
否则无解输出-1
#include<bits/stdc++.h> #define maxl 100010 using namespace std; int n,m; int pos[26][maxl]; int len,mlen[26]; char ch[10]; char s[maxl]; char ans[maxl]; bool in[maxl]; bool flag; inline void prework() { scanf("%d%d",&n,&m); int cnt0,cnt1; memset(mlen,-1,sizeof(mlen)); flag=true; for(int i=1;i<=m*(m-1)/2;i++) { scanf("%s%d",ch,&len); cnt0=cnt1=0; if(len>0) { scanf("%s",s+1); for(int j=1;j<=len;j++) { if(s[j]==ch[0]) { cnt0++; pos[ch[0]-'a'][cnt0]+=cnt1; } else { cnt1++; pos[ch[1]-'a'][cnt1]+=cnt0; } } } if(mlen[ch[0]-'a']==-1) mlen[ch[0]-'a']=cnt0; else if(mlen[ch[0]-'a']!=cnt0) flag=false; if(mlen[ch[1]-'a']==-1) mlen[ch[1]-'a']=cnt1; else if(mlen[ch[1]-'a']!=cnt1) flag=false; } } inline void mainwork() { if(!flag) return; for(int i=0;i<m;i++) for(int j=1;j<=mlen[i];j++) if(pos[i][j]+j<=n) { if(!in[pos[i][j]+j]) { ans[pos[i][j]+j]='a'+i; in[pos[i][j]+j]=true; } else { flag=false; return; } } else { flag=false; return; } for(int i=1;i<=n;i++) if(!in[i]) { flag=false; return; } } inline void print() { if(flag) for(int i=1;i<=n;i++) printf("%c",ans[i]); else puts("-1"); } int main() { prework(); mainwork(); print(); return 0; }
