2481 - E
给你一些由小写字母组成的词，每个词中的字母都是严格按照新给定的“字典序”（不是传统的a-z这样的顺序）从左到右排列的。现在我们需要把所有给定词中出现过的字母拼接起来，组成一个新词，并按新给定的“字典序”从左到右排序。对于某些无法决定次序的字母，你应用传统的字典序排序。比如"acb","bd","zwa"，那么'z'和'w'必须放在‘a’前面，‘d’必须放在‘b’后面。所以结果是‘zwacbd’。
假设题目一定有唯一解。
Input
第一行n(n<=10)，代表词的个数。接下来n行，每行代表一个词，每个词的长度不超过20。
Output
题目要求的结果
Examples
Input
3 acb bd zwa 3 klm kadl lsm 3 a b c 1 aazzss 3 dfg frt tyg
Output
zwacbd kadlsm abc azs dfrtyg
Solution C++
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <cstring> #include <set> #include <map> using namespace std; string s[11]; set<char>st; map<char,double>mp; struct node{ char c; double va; }p[27]; bool cmp(node a,node b){ return a.va<b.va; } int main(){ int n; while(scanf("%d",&n)!=EOF){ st.clear(); for(int i=0;i<n;i++){ cin>>s[i]; for(int j=0;j<s[i].size();j++) st.insert(s[i][j]); } int now=0; mp.clear(); for(set<char>::iterator it=st.begin();it!=st.end();it++){ p[++now].c=*it; p[now].va=now; mp[*it]=now; } /*for(int i=1;i<=now;i++) printf("%c %lf\n",p[i].c,p[i].va); */ while(1){ bool ok=true; bool _f=false; char x,y; for(int i=0;i<n;i++){ for(int j=0;j<s[i].size();j++){ for(int k=j+1;k<s[i].size();k++){ if(mp[s[i][j]]>mp[s[i][k]]){ x=s[i][j]; y=s[i][k]; _f=true; break; } } if(_f) break; } if(_f) break; } if(_f==false) break; int ii,jj; for(ii=1;ii<=now;ii++){ if(p[ii].c==x) break; } for(jj=1;jj<=now;jj++){ if(p[jj].c==y) break; } if(jj==1){ p[ii].va=p[jj].va-1; } else{ p[ii].va=(p[jj].va+p[jj-1].va)/2; } mp[p[ii].c]=p[ii].va; sort(p+1,p+1+now,cmp); } sort(p+1,p+1+now,cmp); for(int i=1;i<=now;i++) printf("%c",p[i].c); printf("\n"); } return 0; }