时间限制: 1 Sec 内存限制: 128 MB

题目描述

　　七夕祭上，Vani牵着cl的手，在明亮的灯光和欢乐的气氛中愉快地穿行。这时，在前面忽然出现了一台太鼓达人机台，而在机台前坐着的是刚刚被精英队伍成员XLk、Poet_shy和lydrainbowcat拯救出来的的applepi。看到两人对太鼓达人产生了兴趣，applepi果断闪人，于是cl拿起鼓棒准备挑战。然而即使是在普通难度下，cl的路人本性也充分地暴露了出来。一曲终了，不但没有过关，就连鼓都不灵了。Vani十分过意不去，决定帮助工作人员修鼓。

　　鼓的主要元件是M个围成一圈的传感器。每个传感器都有开和关两种工作状态，分别用1和0表示。显然，从不同的位置出发沿顺时针方向连续检查K个传感器可以得到M个长度为K的01串。Vani知道这M个01串应该是互不相同的。而且鼓的设计很精密，M会取到可能的最大值。现在Vani已经了解到了K的值，他希望你求出M的值，并给出字典序最小的传感器排布方案。

输入

　　一个整数K。

输出

　一个整数M和一个二进制串，由一个空格分隔。表示可能的最大的M，以及字典序最小的排布方案，字符0表示关，1表示开。你输出的串的第一个字和最后一个字是相邻的。

样例输入

样例输出

8 00010111

提示

　得到的8个01串分别是000、001、010、101、011、111、110和100。注意前后是相邻的。长度为3的二进制串总共只有8种，所以M = 8一定是可能的最大值。

　对于全部测试点，2≤K≤11。

题解

刚开始看的时候一点思路都没有，dalao们都说是个欧拉回路的题。回去捡欧拉回路的知识，get到了一些很有用的提示：

一笔画：

⒈凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。

⒉凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。

⒊其他情况的图都不能一笔画出。（奇点数除以二便可算出此图需几笔画成。）

基本概念：

欧拉通路 (欧拉迹)—通过图中每条边一次且仅一次，并且过每一顶点的通路。

欧拉回路 (欧拉闭迹)—通过图中每条边一次且仅一次，并且过每一顶点的回路。

欧拉图—存在欧拉回路的图。欧拉图就是从一顶出发每条边恰通过一次又能回到出发顶点的那种图，即不重复的行遍所有的边再回到出发点。

通路和回路－称vie1e2…envj为一条从 vi到 vj且长度为n的通路，其中长度是指通路中边的条数．称起点和终点相同的通路为一条回路。

简单图－不含平行边和自回路的图。

混合图－既有有向边，也有无向边的图

平凡图－仅有一个结点的图

完全图－有n个结点的且每对结点都有边相连的无向简单图，称为无向完全图；有n个结点的且每对结点之间都有两条方向相反的边相连的有向简单图为有向完全图。

欧拉图的特征：

无向图

a）G有欧拉通路的充分必要条件为：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。

b）G有欧拉回路(G为欧拉图)：G连通，G中均为偶度顶点。

有向图

a）D有欧拉通路：D连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点（终点）的入度比出度大1，另一个顶点（起点）的入度比出度小1。

b）D有欧拉回路(D为欧拉图)：D连通，D中所有顶点的入度等于出度。一个有向图是欧拉图，当且仅当该图所有顶点度数都是0。

对照着种种概念来想这道题，二进制数前后相连对应图的联通，每个二进制数只能用一遍对应点只能经过一次，前后相接对应图走到原点……原来是这样一个欧拉回路啊。然而本蒟蒻就开始傻傻地枚举二进制数，看他们之间是否能建边，再在建好的边里跑欧拉回路QAQ，果然T得厉害。刚开始觉得是邻接矩阵太慢了，又换了邻接表。还是很慢，决定只要搜到最大值就结束，11居然也能秒出答案，交了第二遍发现WA了，才想起来自己把首尾相接这个事给忘了。那要怎么判断？暴力对比明显不可行，然后就没有办法了。看了一眼老白的博客，说这个题的时间复杂度是O(n)的，极其诧异，默默地看了看我那个暴力一样的枚举，不T就怪。

所以说到底应该怎么做呢？从我暴力建边这个事中其实可以总结出规律：每一个数一定是两个入边两个出边(只有首尾那两位不一样)，所以根本就不用想它一定是个欧拉回路，第一问的答案实际上用不着求。知道了第一问的答案，第二问只要深搜找最小的字典序就可以，对于每一位先看它能否是0再看它能否是1，前k位是0000肯定没问题，毕竟是个欧拉路，只要搜到最后一个点一定是可以回到起点的。

感觉自己现在简直是处于夏洛克·福尔摩斯所说的那种：真相就摆在你眼前，你却一味地去看而不懂得观察。观察能力是一种重要的生存能力，也是一个人真正聪慧敏锐与否的判断标准吧。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int sj=(1<<11)+5;
int k,temp,jg[sj<<1],qy;
bool r[sj];
bool dfs(int x,int st)
{if(r[x]) return 0;if(st==temp) return 1;jg[k+st-1]=x&1;r[x]=1;if(dfs((x<<1)&qy,st+1)) return 1;if(dfs(((x<<1)|1)&qy,st+1)) return 1;r[x]=0;return 0;
}
int main()
{scanf("%d",&k);temp=(1<<k);qy=temp-1;for(int i=1;i<k;i++) jg[i]=0;dfs(0,1);printf("%d ",temp);for(int i=1;i<=temp;i++) printf("%d",jg[i]);return 0;
}