这个题暴搜10分钟写出来了，也AC了。但听XLK和LYD神牛讲的欧拉回路的方法，真心跪了！
XLK题解（有改动）：
很显然，第一问的答案就是2^n。
第二问，构造一个有2^(n-1)个节点的图，对应2^(n-1)个n-1位二进制数。从代表数k的节点(0<=k<2^(n-1))向代表数(k<<1)&(1<<n-1)的节点，和代表数(k<<1)&(1<<n-1)+1的节点分别连一条边。可以发现这样的图中，所有点的入度和出度都是2，因此这是一个欧拉图。因此我们从0号点开始dfs寻找一个欧拉回路，回溯的时候记录到栈中，最后倒序输出即可。因为要求字典序最小，dfs的时候要注意搜索顺序，先走0边，再走1边。这个算法寻找欧拉回路，每个点、每条边只访问一次，是O(V+E)级别的。
时间复杂度O(2^n)，预计得分100分。
暴搜代码：
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 bool fg,d[1<<15],vis[1<<15]; 7 int tot,k; 8 void read() 9 { 10 memset(vis,0,sizeof vis); 11 fg=false; 12 tot=1<<k; 13 } 14 bool check() 15 { 16 int i=1,j=tot+1; 17 for(;i<=k-1;i++,j++) 18 { 19 if(d[i]!=d[j]) return false; 20 } 21 fg=true; 22 for(i=1;i<=tot;i++) printf("%d",d[i]); 23 } 24 void dfs(int step,int num) 25 { 26 if(fg) return; 27 if(step==tot) 28 { 29 check(); 30 return; 31 } 32 for(int i=0;i<tot;i++) 33 { 34 if(!vis[i]) 35 { 36 int sk; 37 if((num>>(k-1))==1) sk=num-(1<<(k-1)); 38 else sk=num; 39 if(sk==(i>>1)) 40 { 41 d[step+k]=i&1; 42 vis[i]=true; 43 dfs(step+1,i); 44 vis[i]=false; 45 } 46 } 47 } 48 } 49 void go() 50 { 51 printf("%d ",tot); 52 for(int i=1;i<=k;i++) d[i]=0; 53 vis[0]=true; 54 dfs(1,0); 55 printf("\n"); 56 } 57 int main() 58 { 59 while(scanf("%d",&k)!=EOF) 60 { 61 read(); 62 go(); 63 } 64 return 0; 65 }
欧拉回路代码：
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 using namespace std; 5 int p,d[1<<15],n; 6 bool vis[1<<15]; 7 void prev() 8 { 9 memset(vis,0,sizeof vis); 10 p=0; 11 } 12 void dfs(int u) 13 { 14 int to1=(u<<1)&((1<<n)-1); 15 int to2=to1+1; 16 if(!vis[to1]) 17 { 18 vis[to1]=true; 19 dfs(to1); 20 d[++p]=0; 21 } 22 if(!vis[to2]) 23 { 24 vis[to2]=true; 25 dfs(to2); 26 d[++p]=1; 27 } 28 } 29 void go() 30 { 31 dfs(0); 32 printf("%d ",1<<n); 33 for(int i=1;i<n;i++) printf("0"); 34 for(int i=p;i>=n;i--) printf("%d",d[i]); 35 printf("\n"); 36 } 37 int main() 38 { 39 while(scanf("%d",&n)!=EOF) 40 { 41 prev(); 42 go(); 43 } 44 return 0; 45 }
后记：
由于紧张备战NOIP考试，所以，难题和新算法就都暂时不学了，把基础巩固好，发现基础太弱了，难题也不会。。