本文主要是介绍hdu 2894 DeBruijin，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
DeBruijin
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 561 Accepted Submission(s): 322
Problem Description
旋转鼓的表面分成m块扇形,如图所示(m=8)。图中阴影区表示用导电材料制成,空白区用绝缘材料制成,终端a、b和c是3（k=3）处接地或不是接地分别用二进制信号0或1表示。因此,鼓的位置可用二进制信号表示。试问应如何选取这8个扇形的材料使每转过一个扇形都得到一个不同的二进制信号,即每转一周,能得到000到111的8个数。
那我们现在把旋转鼓的表面分成m块扇形，每一份记为0或1，使得任何相继的k个数的有序组（按同一方向）都不同，对固定的k，m最大可达到多少，并任意输出符合条件的一个这样的有序组。
那我们现在把旋转鼓的表面分成m块扇形，每一份记为0或1，使得任何相继的k个数的有序组（按同一方向）都不同，对固定的k，m最大可达到多少，并任意输出符合条件的一个这样的有序组。
Input
每个case输入一个数k （2<=k<=11）,表示图中所示的abc这样的接地线的数量。
Output
每个case输出m所能达到的最大值 ，并且输出字典序最小的一个符合条件的有序组，中间用空格隔开。Case间没有空行。有序组输出的格式为：00010111（k=3，只输出一个周期（0001011100010111……），并且首尾刚好是相接的）。
Sample Input
3
Sample Output
8 00010111
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD 10009
#define MAXN 100100
#define INF 0x7fffffff
#define MEM(a,x) memset(a,x,sizeof a)
#define ll __int64const int M=(int)(1<<12);using namespace std;int list[M];
int ans[M];
int cnt;
int m;void dfs(int v)
{int x=(v<<1)&m;if(!list[x]){list[x]=1;dfs(x);ans[cnt++]=0;}if(!list[x+1]){list[x+1]=1;dfs(x+1);ans[cnt++]=1;}
}int main()
{
//freopen("ceshi.txt","r",stdin);int n;while(scanf("%d",&n)!=EOF){MEM(list,0);cnt=0;m=(1<<n)-1;printf("%d ",(1<<n));dfs(0);for(int i=1;i<n;i++)printf("0");
// cout<<"cnt "<<cnt<<endl;for(int i=cnt-1;i>n-2;i--)printf("%d",ans[i]);puts("");}return 0;
}
这篇关于hdu 2894 DeBruijin的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
