题意:
中文题说实话我看了好久才看懂...着急...就是给一个数k..要做的是找出一个循环节..使得每次平移一位得到不同的数..平移完整个循环节得到所有0~2^k-1..并且每个数只出现一次...问一个循环节的长度是多少...并且输出字典序最小的一个循环节...
题解:
话说我对欧拉回路的理解还是相当的naive...参考了这个博文http://www.cnblogs.com/proverbs/archive/2012/08/21/2649984.html
总结:
这类问题的模式都是题目要求哈密顿回路..并且一类首尾相接的问题...要转化成欧拉回路..用边代表原图的点..而新图的点是原图的n-1位...
Program:
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<queue> #include<stack> #include<set> #include<time.h> #include<map> #include<algorithm> #define ll long long #define eps 1e-5 #define oo 1000000007 #define pi acos(-1.0) #define MAXN 1<<12 #define MAXM 500005 using namespace std; bool used[MAXN]; int k,num,ans[MAXN]; void dfs(int x) { int p1=(x<<1)&((1<<k)-1),p2=p1|1; //p1,p2就代表了平移后可能变成的数 if (!used[p1]) { used[p1]=true; dfs(p1); ans[++num]=0; } if (!used[p2]) { used[p2]=true; dfs(p2); ans[++num]=1; } } int main() { int i; while (~scanf("%d",&k)) { memset(used,false,sizeof(used)),num=0; printf("%d ",1<<k); for (i=1;i<k;i++) printf("0"); dfs(0); for (i=num;i>=k;i--) printf("%d",ans[i]); printf("\n"); } return 0; }