http://codeforces.com/contest/510/problem/C
题意:给定n个字符串。问是否存在一种字母顺序,使得这n个字符串的顺序满足字典序(自定义的)。如果有多种顺序,输出字典序(标准的)最小的。
思路:将字符串的关系处理成边的关系。每次对于第i个和第i+1个字符串,从前往后扫,直到不相等的那一位,设为k,然后连边,指向i+1。表明第i个字符串的第k位大于第i+1个字符串的第k位。如果没有不想等的。说明其中一个是另一个的字串。如果前者是后者的字串,那么不影响。如果后者是前者的字串,则不存在满足条件的字典序。然后做拓扑排序。由于有多种输出字典序(标准的)最小的方案。所以存点的时候用优先队列存。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
/* *********************************************** Author :111qqz Created Time :2015年12月06日 星期日 15时16分50秒 File Name :code/cf/problem/510C.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=105; int n; char st[N][N]; int p[30]; int offset[30]; bool conc[30][30]; int in[N]; int ans[N]; struct node { int x; node(int xx) { x=xx; } bool operator <(const node a)const{ return x>a.x; } }; bool getconc( int x,int y) { int lx = strlen(st[x]); int ly = strlen(st[y]); int len = min(lx,ly); for ( int i = 0; i < len ; i++) { if (st[x][i]!=st[y][i]) { conc[st[x][i]-'a'][st[y][i]-'a'] = true; return true; } } // if (lx>ly) return false; return true; } bool pre() { ms(conc,false); ms(in,0); scanf("%d",&n); for ( int i = 0 ;i < n ; i++) scanf("%s",st[i]); bool ok = true; for ( int i = 0 ; i < n-1 ; i++) { ok = getconc(i,i+1); if (!ok) break; } if (ok) return true; return false; } bool topo() { priority_queue<node>q; for ( int i = 0 ; i < 26 ; i++) if (in[i]==0) q.push(i); int cnt = 0 ; while (!q.empty()) { node v = q.top();q.pop(); cnt++; ans[cnt]=v.x; for ( int i = 0 ; i < 26 ; i++) { if (!conc[v.x][i]) continue; in[i]--; if (in[i]==0) q.push(i); } } if (cnt<26) return false; return true; } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif if (pre()) { for ( int i = 0 ; i < 26 ; i++) for ( int j = 0 ; j < 26 ; j++) if (conc[i][j]) in[j]++; if (topo()) { for (int i = 1 ; i <= 26 ; i++) printf("%c",char(ans[i]+'a')); puts(""); } else { puts("Impossible"); } } else { puts("Impossible"); } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人!