题目大意是给你一串单词,判断能否连接成一条长串,两个单词能够连接的条件是后一个单词的首字母与前一个单词的尾字母相同(单词至少有2个字母)。单词仅由小写字母组成。
这个题目对于我们新手来说还是有难度的。首先这是一个图论问题,我们把单词看作是点,单词之间的连接关系看作是边。题目所给的数据规模:单词的个数到达10万,所以我们不能把每一个单词看作一个点,而是把相同的单词看左是一个点。实际上,对于每一个单词,我们只需要知道它的首字母和尾字母就可以了,中间并不管,那么首字母和尾字母相同就是相同的单词,那么这样不同的单词最多只有26*26=676个了。
把单词连成一条长串,实际上是有向图的欧拉道路的打印结果。那么根据有向图里面欧拉道路的结论,除了起点和终点以外,其它的点的入度等于出度,起点的入度比出度少1,终点的出度比入度少1。对于这道题来说,我们只需要统计以某个字母为开头和结尾单词的个数,比方说,我们统计以m结尾的单词的个数(记为end)以及以m开头的单词的个数(记为front),对于a~z都要统计。我们仅仅允许出现1次end>front和1次front>end,其余情况end==front(所有的end都等于front也是可以的)。满足上述条件的就可以连成长串,否则不可以。当然,存在欧拉道路首先要连通,我们可以先搜索一次判断是否连通,这里的连通是指把相同的单词看成一个点,把有向图的方向忽略,当做无向图,判断是否连通。
#include<iostream> #include<string> #include<cstring> #define MAXN 676 using namespace std; int word[MAXN],vis[MAXN];//word数组保存不同的单词的数目,首字母*26+尾字母作为下标 void dfs(int cur) { for(int i=0;i<MAXN;i++) if(word[i]&&!vis[i]&&(cur%26==i/26||cur/26==i%26)) { vis[i]=1; dfs(i); } } int main() { //freopen("in.txt","r",stdin); int i,N,T; string tmp; cin>>T; while(T--) { int first; cin>>N; memset(word,0,sizeof(word)); for(i=0;i<N;i++) { int num,last; cin>>tmp;//输入单词 last=tmp.length()-1; num=(tmp[0]-'a')*26+(tmp[last]-'a');//提取首尾字母,计算对应的下标 word[num]++; if(i==0) first=num;//记下第一个单词,用于搜索 } //先搜索,判断是否连通 memset(vis,0,sizeof(vis)); vis[first]=1; dfs(first); int ok=1; for(i=0;i<MAXN;i++) if(word[i]&&!vis[i]) {ok=0;break;} if(ok==0)//如果不连通则一定不可以连成长串 { cout<<"The door cannot be opened."<<endl; continue; } //再判断是否存在欧拉道路 int front[26]={0},end[26]={0}; for(i=0;i<MAXN;i++) { front[i/26]+=word[i]; end[i%26]+=word[i]; } int flag1=0,flag2=0; ok=1; for(i=0;i<26;i++) { if(front[i]==end[i]) continue; else if(front[i]-end[i]==1) flag1++; else if(end[i]-front[i]==1) flag2++; else {ok=0;break;} if(flag1>1||flag2>1) {ok=0;break;} } if(ok&&(flag1==0&&flag2==0||flag1==1&&flag2==1)) cout<<"Ordering is possible."<<endl; else cout<<"The door cannot be opened."<<endl; } return 0; }
发表评论
-
UVa 10422 Knights in FEN
2012-09-07 08:40 903题目:http://uva.onlinejudge.org/i ... -
UVa 539 The Settlers of Catan
2012-08-31 22:22 28题目:http://uva.onlinejudge.org/i ... -
UVa 301 Transportation
2012-08-31 22:10 34题目:http://uva.onlinejudge.org/i ... -
UVa 639 Don't Get Rooked
2012-08-30 23:01 816题目:http://uva.onlinejudge.org/i ... -
UVa 216 Getting in Line
2012-08-29 20:48 725题目:http://uva.onlinejudge.org/i ... -
UVa 10474 Where is the Marble?
2012-08-28 13:45 852题目:http://uva.onlinejudge.org/i ... -
UVa 592 Island of Logic
2012-08-27 11:05 1647题目:http://uva.onlinejudge ... -
UVa 11205 The broken pedometer
2012-08-25 17:28 1052题目:http://uva.onlinejudge.org/i ... -
UVa 131 The Psychic Poker Player
2012-08-24 22:28 876题目:http://uva.onlinejudge.org/i ... -
UVa 729 The Hamming Distance Problem
2012-08-24 12:18 698题目:http://uva.onlinejudge.org/i ... -
Uva 10098 Generating Fast
2012-08-23 15:28 660题目:http://uva.onlinejudge.org/i ... -
UVa 146 ID Codes
2012-08-20 18:46 766题目:http://uva.onlinejudge.org/i ... -
UVa 10167 Birthday Cake
2012-08-16 20:57 606题目:http://uva.onlinejudge.org/i ... -
UVa 10596 Morning Walk
2012-08-14 22:05 882题目:http://uva.onlinejudge.org/i ... -
Uva 10305 Ordering Tasks
2012-08-13 23:40 660题目:http://uva.onlinejudge.org/i ... -
Uva 10004 Bicoloring
2012-08-13 23:34 879题目:http://uva.onlinejudge.org/i ... -
Uva 532 Dungeon Master
2012-08-13 23:29 791题目:http://uva.onlinejudge ... -
Uva 439 Knight Moves
2012-08-11 22:24 657题目:http://uva.onlinejudge.org/i ... -
UVa 784 Maze Exploration
2012-08-11 14:09 828题目:http://uva.onlinejudge.org/i ... -
Uva 572 Oil Deposits
2012-08-11 11:43 746题目:http://uva.onlinejudge.org/i ...
相关推荐
UVa Online Judge 10944 Accepted Code
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
UVA109的题解,经测试完全正确,还附有题解。
uva272
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。