HDOJ2894-DeBruijin构图..求欧拉回路径(经过边的顺序)

来源：恒创科技编辑：恒创科技编辑部

2024-02-02 08:30:59

题意:

中文题说实话我看了好久才看懂...着急...就是给一个数k..要做的是找出一个循环节..使得每次平移一位得到不同的数..平移完整个循环节得到所有0~2^k-1..并且每个数只出现一次...问一个循环节的长度是多少...并且输出字典序最小的一个循环节...

题解:

话说我对欧拉回路的理解还是相当的naive...

总结:

这类问题的模式都是题目要求哈密顿回路..并且一类首尾相接的问题...要转化成欧拉回路..用边代表原图的点..而新图的点是原图的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;
}