Description

　　七夕祭上，Vani牽著cl的手，在明亮的燈光和歡樂的氣氛中愉快地穿行。這時，在前面忽然出現(xiàn)了一臺太鼓達人機臺，而在機臺前坐著的是剛剛被精英隊伍成員XLk、Poet_shy和lydrainbowcat拯救出來的的applepi。看到兩人對太鼓達人產(chǎn)生了興趣，applepi果斷閃人，于是cl拿起鼓棒準備挑戰(zhàn)。然而即使是在普通難度下，cl的路人本性也充分地暴露了出來。一曲終了，不但沒有過關(guān)，就連鼓都不靈了。Vani十分過意不去，決定幫助工作人員修鼓。

　　鼓的主要元件是M個圍成一圈的傳感器。每個傳感器都有開和關(guān)兩種工作狀態(tài)，分別用1和0表示。顯然，從不同的位置出發(fā)沿順時針方向連續(xù)檢查K個傳感器可以得到M個長度為K的01串。Vani知道這M個01串應(yīng)該是互不相同的。而且鼓的設(shè)計很精密，M會取到可能的最大值。現(xiàn)在Vani已經(jīng)了解到了K的值，他希望你求出M的值，并給出字典序最小的傳感器排布方案。

Input

　　一個整數(shù)K。

Output

　一個整數(shù)M和一個二進制串，由一個空格分隔。表示可能的最大的M，以及字典序最小的排布方案，字符0表示關(guān)，1表示開。你輸出的串的第一個字和最后一個字是相鄰的。

Sample Input

Sample Output

HINT

　得到的8個01串分別是000、001、010、101、011、111、110和100。注意前后是相鄰的。長度為3的二進制串總共只有8種，所以M = 8一定是可能的最大值。

　　對于全部測試點，2≤K≤11。

Source

Poetize2

題解：歐拉圖+dfs 

之前就知道歐拉圖，但是一直沒有仔細的學(xué)過，也基本上沒有應(yīng)用過。

先引出歐拉圖的一些基本概念

1.歐拉通路：通過圖中的每條邊一次且僅一次，并且過每個頂點的通路

2.歐拉回路：通過圖中的每條邊一次且僅一次，并且過每個頂點的回路

3.歐拉圖：存在歐拉回路的圖。歐拉圖就是從一個頂點出發(fā)每條邊恰經(jīng)過一次又回到出發(fā)頂點的那種圖，即不重復(fù)的行遍所有的邊再回到出發(fā)點。

4.簡單圖：不含平行邊和自由路的圖

5.混合圖：既有有向邊，也有無向邊的圖

6.平凡圖：僅一個節(jié)點的圖

7.完全圖：有n個結(jié)點且每對結(jié)點都有邊相連的無向簡單圖，稱為無向完全圖。有n個結(jié)點的且每對結(jié)點之間都有兩條方向相反的邊相連的有向簡單圖，稱為有向完全圖。

無向圖

（1）G有歐拉通路的充分必要條件為：G聯(lián)通，G中只有兩個奇數(shù)頂點（分別是歐拉通路的兩個端點）

（2）G有歐拉回路（G為歐拉圖）：G聯(lián)通，G中均為偶度頂點

有向圖

（1）D有歐拉通路：D聯(lián)通，除兩個頂點外，其余頂點的入度出度相等，這兩個特殊的頂點中，一個頂點的入度比出度大1，另一個頂點的入度比出度小1

（2）D有歐拉回路（D為歐拉圖）：D聯(lián)通，D中所有頂點的入度等于出度。一個有向圖是歐拉圖，當且僅當該圖所有頂點的度數(shù)都是0

對于這道題來說，01串的所有組合有2^k種，但是直接分析的話并不能確定所有的組合一定都能出現(xiàn)。

但是我們將所有的組合都看成一個點，那么每個點在最后加上0或1，使01串的長度為k，有兩種選擇，同樣再前面添加0或1也是一樣。那么對于每個點來說出度和入度是相同的，也就是說我們可以得到一種有向的歐拉圖。

對于歐拉圖來說，一定存在歐拉回路，也就是說一定存在方案使2^k中組合都出現(xiàn)。

同時因為是歐拉圖，那么這道題基本上就變成了一筆畫問題，對于一筆畫問題的話我們可以放心的dfs,會在非常高的效率內(nèi)出解。

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#define N 3000using namespace std;int vis[N],ans[N];int n,t;int dfs(int x,int k){	if (vis[x]) return 0;	if (k==t) return 1;	vis[x]=1; ans[k]=x&1;	if (dfs((x<<1)&(t-1),k+1)) return 1;	if (dfs((x<<1|1)&(t-1),k+1)) return 1;	vis[x]=0;	return 0;}int main(){	freopen("a.in","r",stdin);	scanf("%d",&n);	PRintf("%d ",(t=1<<n));	dfs(0,1);	for (int i=1;i<n;i++) printf("0");	for (int i=1;i<=t-n+1;i++)	 printf("%d",ans[i]);	printf("/n");}