P1341 无序字母对
2018-06-17 22:21:22来源:未知 阅读 ()
题目描述
给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
输入输出格式
输入格式:第一行输入一个正整数n。
以下n行每行两个字母,表示这两个字母需要相邻。
输出格式:输出满足要求的字符串。
如果没有满足要求的字符串,请输出“No Solution”。
如果有多种方案,请输出前面的字母的ASCII编码尽可能小的(字典序最小)的方案
输入输出样例
4 aZ tZ Xt aX
XaZtX
说明
【数据规模与约定】
不同的无序字母对个数有限,n的规模可以通过计算得到。
这题是欧拉回路的裸题
但是有两个地方需要注意
1.在函数中输出不能使用传值变量为循环变量
2.ios::sync容易引起RE!、
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 using namespace std; 7 const int MAXN=4001; 8 void read(int & n) 9 { 10 char c='+';int x=0;int flag=0; 11 while(c<'0'||c>'9') 12 { c=getchar(); if(c=='-') flag=1; } 13 while(c>='0'&&c<='9') 14 {x=x*10+(c-48);c=getchar();} 15 flag==1?n=-x:n=x; 16 } 17 int n; 18 int map[MAXN][MAXN]; 19 int indegree[MAXN]; 20 int ans[MAXN]; 21 int flag=0; 22 void dfs(int num,int now) 23 { 24 ans[now]=num; 25 if(now==n+1) 26 { 27 for(int i=1;i<=n+1;i++) 28 printf("%c",(char)ans[i]); 29 exit(0); 30 } 31 for(int i=65;i<=127;i++) 32 { 33 if(map[num][i]) 34 { 35 map[num][i]=0; 36 map[i][num]=0; 37 dfs(i,now+1); 38 map[num][i]=1; 39 map[i][num]=1; 40 } 41 } 42 ans[now]=0; 43 } 44 int main() 45 { 46 cin>>n; 47 ios::sync_with_stdio(false); 48 for(int i=1;i<=n;i++) 49 { 50 char a,b; 51 cin>>a>>b; 52 if(!map[a][b]) 53 { 54 map[a][b]=1; 55 map[b][a]=1; 56 indegree[a]++; 57 indegree[b]++; 58 } 59 } 60 int tot=0; 61 int bgji=0x7fff,bgou=0x7ffff; 62 for(int i=65;i<=127;i++) 63 { 64 if(indegree[i]%2==1) 65 { 66 tot++; 67 bgji=min(bgji,i); 68 } 69 else if(indegree[i]) 70 bgou=min(i,bgou); 71 } 72 if(tot!=0&&tot!=2) 73 { 74 printf("No Solution"); 75 exit(0); 76 } 77 tot==0? 78 dfs(bgou,1): 79 dfs(bgji,1); 80 return 0; 81 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:P1168 中位数
- 单链表的选择排序 2019-09-17
- 递归(七):递归程序填空 2019-08-16
- #leetcode刷题之路17-电话号码的字母组合 2019-03-13
- c++数据 2018-12-20
- 洛谷P3796 【模板】AC自动机(加强版) 2018-07-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash