DeBruijin
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 319 Accepted Submission(s): 203
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
Source
Recommend
gaojie
由题意分析欧拉回路是存在的。所以直接搜索出欧拉回路。
还是经典的欧拉回路算法。
任取一个起点,开始下面的步骤
(1)、如果该点没有相连的点,就将该点加进路径中然后返回。
(2)、如果该点有相连的点,就列一张相连点的表然后遍历它们直到该点没有相连的点。(遍历一个点,删除一个点)
(3)、处理当前的点,删除和这个点相连的边, 在它相邻的点上重复上面的步骤,把当前这个点加入路径中.
(1)、如果该点没有相连的点,就将该点加进路径中然后返回。
(2)、如果该点有相连的点,就列一张相连点的表然后遍历它们直到该点没有相连的点。(遍历一个点,删除一个点)
(3)、处理当前的点,删除和这个点相连的边, 在它相邻的点上重复上面的步骤,把当前这个点加入路径中.
#include <stdio.h> #include<string.h> int v[1<<11|1],ma,mi,ans[1<<11|1],cnt; //v记录数字是否被用过。ma和mi分别记录k字节可构成数的上界和高位。 void dfs(int u) { int i,t; for(i=0;i<2;i++)//为满足字典序 { t=((u%mi)<<1)+i;//取出后k-1数位。在进一位加i构成下一位数 if(!v[t]&&t<ma)//如该数没出现过继续搜索 { v[t]=1; dfs(t); ans[cnt++]=i; } } } int main() { int k,i; while(~scanf("%d",&k)) { memset(v,0,sizeof v); cnt=0; mi=1<<(k-1); ma=mi<<1; printf("%d ",ma); dfs(0);//从0开始搜索所以前面默认先加k-1个0 for(i=1;i<=k-1;i++) printf("0"); for(i=cnt-1;i>=k-1;i--)//应为是滚轮。所以最后几位不用要会与前面加的0重复 printf("%d",ans[i]); printf("\n"); } return 0; } /*感谢小吉吉的注释和支持,爱死你了。又麻烦你把大脑当CPU了。 k=3时的运行过程 t的顺序为 0 1 2 4 5 3 6 7 ans[] 记录的0,1 顺序: 0 0 1 1 1 0 1 0 出栈顺序: 0 1 0 1 1 1 0 0 */