HDOJ 2894 DeBruijin(dfs構造オイラーリターン)

DeBruijin
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 681    Accepted Submission(s): 396
Problem Description
回転ドラムの表面は、図に示すようにmブロック扇形に分かれている(m=8).図中の陰影領域は導電材料で作られ、空白領域は絶縁材料で作られ、終端a、b、cは3(k=3)で接地されているか、接地されていないかはそれぞれバイナリ信号0または1で表されている.したがって、ドラムの位置はバイナリ信号で表すことができる.この8つのセクタの材料をどのように選択して、1つのセクタを回転するたびに異なるバイナリ信号、すなわち1週間回転するごとに、000から111の8つの数を得ることができるかを聞いてみましょう.
回転ドラムの表面をmブロック扇形に分割し,各部を0または1と表記し,連続するk個数の秩序群(同一方向)が異なり,固定されたkに対してmが最大でどれだけ達成できるか,条件に合致する1つのこのような秩序群を任意に出力する.
 
Input
各caseは、図に示すabcのような接地線の数を表すk(2<=k<=11)の数を入力する.
 
Output
各caseはmが達成できる最大値を出力し、辞書順が最も小さい条件に合致する秩序化グループを出力し、中間はスペースで区切られる.Case間は空行がありません.順序付きグループ出力のフォーマットは、00010111(k=3であり、1サイクルのみ(0001011100010111...)を出力し、先頭と末尾がちょうど接続されている)である.
 
Sample Input

   
   
   
   

    
    
    
    3
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    8 00010111
   
   
   
   

 
题意:中国语の问题も理解していないで、安利は1発の题意::あなたに1つの环形の列を构筑させて、2進数0、1から构成して、それからそれぞれ异なるk个を切り取って、构成の数はすべて异なって、今あなたに1つのkをあげて、それから字典の序の最小の列を构筑して、切り取ったxの长さの値を満たすようにすべて异なっています.
 
問題解:mが達成できる最大値は2^kに違いない.  数の範囲は0~(2^k)-1である.  数Xが表すノードから,2つのエッジを接続し,(X<<1)&((1< 
コードは次のとおりです.
 

#include<cstdio>
#include<cstring>
int num[1<<11+10],n,cnt;
int visit[1<<11+10];

void dfs(int x)
{
	int temp;
	temp=(x<<1)&((1<<n)-1);// x         ，       
	if(!visit[temp])
	{
		visit[temp]=1;
		dfs(temp);
		num[++cnt]=0; 
	}
	if(!visit[temp+1])//x         ，     1 
	{
		visit[temp+1]=1;
		dfs(temp+1);
		num[++cnt]=1;
	}
}

int main()
{
	int i,j;
	while(scanf("%d",&n)!=EOF)
	{
		memset(num,0,sizeof(num));
		memset(visit,0,sizeof(visit));
		printf("%d ",1<<n);
		for(i=1;i<n;++i)
			printf("0");
		cnt=0;
		dfs(0);
		for(i=cnt;i>n;--i)
			printf("%d",num[i]);
		printf("%d
",num[i]);
	}
	return 0;
}