NYOJ 99 单词拼接
单词拼接 时间限制： 3000 ms|内存限制： 65535 KB 难度： 5
- 描述
- 给你一些单词，请你判断能否把它们首尾串起来串成一串。
前一个单词的结尾应该与下一个单词的道字母相同。
如
aloha
dog
arachnid
gopher
tiger
rat
可以拼接成：aloha.arachnid.dog.gopher.rat.tiger
【NYOJ 99 单词拼接】
- 输入
-
第一行是一个整数N(0
- 输出
- 如果存在拼接方案，请输出所有拼接方案中字典序最小的方案。(两个单词之间输出一个英文句号".")
如果不存在拼接方案，则输出
***- 样例输入
2 6 aloha arachnid dog gopher rat tiger 3 oak maple elm
- 样例输出
aloha.arachnid.dog.gopher.rat.tiger ***
欧拉图+深度优先搜索！
刚接触图论，毕竟水平有限，参照了网上的代码！
AC码：
#include #include #include char str[1006][35]; int out[30],in[30],visit[1006],len[1006]; int n,stack[1006]; int Euler() { int i,start=-1,end=-1; for(i=0; i<26; i++) { if(out[i]!=in[i]) { if(out[i]-in[i]==1&&start==-1) start=i; else if(out[i]-in[i]==-1&&end==-1) end=i; else return -1; } } if(start>-1&&end>-1) return start; else if(start==-1&&end==-1) { for(i=0; i<26; i++) { if(out[i]!=0) return i; } } else return -1; } int DFS(char start,int index) { if(index==n) return 1; int i,begin=0,end=n-1,mid; while(begin<=end) { mid=(begin+end)/2; if(str[mid][0]==start) break; else if(str[mid][0]>start) end=mid-1; else begin=mid+1; } if(begin>end) return 0; while(str[mid][0]==start&&mid>=0) --mid; for(i=mid+1; str[i][0]==start; i++) { if(!visit[i]) { stack[index]=i; visit[i]=1; if(DFS(str[i][len[i]-1],index+1)) return 1; visit[i]=0; } } return 0; } int cmp(const void *a,const void *b) { return (strcmp((char *)a,(char *)b)); } int main() { int T,i,count; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(out,0,sizeof(out)); memset(in,0,sizeof(in)); memset(visit,0,sizeof(visit)); for(i=0; i
推荐阅读
- 字符串拼接成段落，换行符（\n）如何只执行n-1次
- css|我用css精灵图拼接了自己的英文名字，不会还有人不知道精灵图技术吧（）
- 背单词是噩梦（不着急，比“红宝书”更好的记忆单词的方法来了！——从词源的角度记单词(二））
- 墨墨单词/2018.3.6/
- SCI论文写作怎样巧用英语单词--Editideas(辑思编译)
- 汤世声（学好英语，从提高记忆力开始）
- 语音篇?重读位置（七）
- 2018.05.08
- Android命名规范
- 72.编辑距离