首页 > 搜索 > DFS搜索 > HDU 2894-DeBruijin-栈-[解题报告]HOJ
2014
02-17

HDU 2894-DeBruijin-栈-[解题报告]HOJ

DeBruijin

问题描述 :

旋转鼓的表面分成m块扇形,如图所示(m=8)。图中阴影区表示用导电材料制成,空白区用绝缘材料制成,终端a、b和c是3(k=3)处接地或不是接地分别用二进制信号0或1表示。因此,鼓的位置可用二进制信号表示。试问应如何选取这8个扇形的材料使每转过一个扇形都得到一个不同的二进制信号,即每转一周,能得到000到111的8个数。


那我们现在把旋转鼓的表面分成m块扇形,每一份记为0或1,使得任何相继的k个数的有序组(按同一方向)都不同,对固定的k,m最大可达到多少,并任意输出符合条件的一个这样的有序组。

输入:

每个case输入一个数k (2<=k<=11),表示图中所示的abc这样的接地线的数量。

输出:

每个case输入一个数k (2<=k<=11),表示图中所示的abc这样的接地线的数量。

样例输入:

3

样例输出:

8 00010111

这个题暴搜10分钟写出来了,也AC了。但听XLK和LYD神牛讲的欧拉回路的方法,真心跪了!

XLK题解(有改动):

很显然,第一问的答案就是2^n

第二问,构造一个有2^(n-1)个节点的图,对应2^(n-1)n-1位二进制数。从代表数k的节点(0<=k<2^(n-1))向代表数(k<<1)&(1<<n-1)的节点,和代表数(k<<1)&(1<<n-1)+1的节点分别连一条边。可以发现这样的图中,所有点的入度和出度都是2,因此这是一个欧拉图。因此我们从0号点开始dfs寻找一个欧拉回路,回溯的时候记录到栈中,最后倒序输出即可。因为要求字典序最小,dfs的时候要注意搜索顺序,先走0边,再走1边。这个算法寻找欧拉回路,每个点、每条边只访问一次,是O(V+E)级别的。

时间复杂度O(2^n),预计得分100分。

 

暴搜代码:

 

#include <cstdio>
 #include <cstdlib>
 #include <iostream>
 #include <cstring>
 using namespace std;
 bool fg,d[1<<15],vis[1<<15];
 int tot,k;
 void read()
 {
     memset(vis,0,sizeof vis);
     fg=false;
     tot=1<<k;
 }
 bool check()
 {
     int i=1,j=tot+1;
     for(;i<=k-1;i++,j++)
     {
         if(d[i]!=d[j]) return false;
     }
     fg=true;
     for(i=1;i<=tot;i++) printf("%d",d[i]);
 }
 void dfs(int step,int num)
 {
     if(fg) return;
     if(step==tot)
     {
         check();
         return;
     }
     for(int i=0;i<tot;i++)
     {
         if(!vis[i])
         {
             int sk;
             if((num>>(k-1))==1) sk=num-(1<<(k-1));
             else sk=num;
             if(sk==(i>>1))
             {
                 d[step+k]=i&1;
                 vis[i]=true;
                 dfs(step+1,i);
                 vis[i]=false;
             }
         }
     }
 }
 void go()
 {
     printf("%d ",tot);
     for(int i=1;i<=k;i++) d[i]=0;
     vis[0]=true;
     dfs(1,0);
     printf("\n");
 }
 int main()
 {
     while(scanf("%d",&k)!=EOF)
     {
         read();
         go();
     }
     return 0;
 }

 

 

欧拉回路代码:

#include <cstdio>
 #include <cstdlib>
 #include <cstring>
 using namespace std;
 int p,d[1<<15],n;
 bool vis[1<<15];
 void prev()
 {
     memset(vis,0,sizeof vis);
     p=0;
 }
 void dfs(int u)
 {
     int to1=(u<<1)&((1<<n)-1);
     int to2=to1+1;
     if(!vis[to1])
     {
         vis[to1]=true;
         dfs(to1);
         d[++p]=0;
     }
     if(!vis[to2])
     {
         vis[to2]=true;
         dfs(to2);
         d[++p]=1;
     }
 }
 void go()
 {
     dfs(0);
     printf("%d ",1<<n);
     for(int i=1;i<n;i++) printf("0");
     for(int i=p;i>=n;i--) printf("%d",d[i]);
     printf("\n");
 }
 int main()
 {
     while(scanf("%d",&n)!=EOF)
     {
         prev();
         go();
     }
     return 0;
 }

 

 

后记:

由于紧张备战NOIP考试,所以,难题和新算法就都暂时不学了,把基础巩固好,发现基础太弱了,难题也不会。。

 

解题参考:http://www.cnblogs.com/proverbs/archive/2012/08/21/2649984.html


, ,
  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.