首页 > 代码库 > 繁华模拟赛day8 字典序
繁华模拟赛day8 字典序
/* 这个题要我们求一个字典序,字符串给出的顺序,会对字母的字典序前后相对顺序进行限定,如何用来表示这种限定,我们注意到这种一个之后接着一个,只有先输出他前面的才能输出他,很明显就是拓扑排序,最小方案只要优先队列随便搞一搞就行了 */ #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int maxn = 115; struct edge{ int v; int nxt; }e[maxn*50]; int n,l[maxn],ans[maxn],orz; int head[maxn],cnt,du[maxn]; char sb[maxn][maxn]; priority_queue< int , vector<int> , greater<int> > q; int read(){ char ch=getchar(); int x=0,f=1; while(!(ch>=‘0‘&&ch<=‘9‘)){if(ch==‘-‘)f=-1;ch=getchar();}; while(ch>=‘0‘&&ch<=‘9‘){x=x*10+(ch-‘0‘);ch=getchar();}; return x*f; } void ins(int u,int v){ cnt++; e[cnt].v = v; e[cnt].nxt = head[u]; head[u] = cnt; } void build(){ int j; for(int i = 2;i <= n;i++){ j = 1; while(j <= l[i-1] && j <= l[i] && sb[i][j] == sb[i-1][j]) j++; if(j > l[i-1] || j > l[i] || sb[i][j] == sb[i-1][j]) continue; ins(sb[i-1][j]-‘a‘,sb[i][j]-‘a‘); du[sb[i][j]-‘a‘]++; } } bool topo(){ int u,to; for(int i = 0;i < 26;i++){ if(!du[i]) q.push(i); } while(!q.empty()){ ans[++orz] = q.top(); q.pop(); u = ans[orz]; for(int i = head[u];i;i=e[i].nxt){ to = e[i].v; du[to]--; if(!du[to]){ q.push(to); } } } return orz == 26; } int main(){ freopen("lexicographical.in","r",stdin); freopen("lexicographical.out","w",stdout); n = read(); for(int i = 1;i <= n;i++){ scanf("%s",sb[i]+1); l[i] = strlen(sb[i]+1); } build(); if(!topo()) cout<<"Impossible"; else{ for(int i = 1;i <= 26;i++){ char tmp = ans[i] + ‘a‘; cout<<tmp; } } return 0; }
繁华模拟赛day8 字典序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。