(題解 尚不完善 ,待補(bǔ)充)
題目
背景
七夕祭上洪橘，Vani牽著cl的手，在明亮的燈光和歡樂的氣氛中愉快地穿行棵帽。這時(shí)熄求，在前面忽然出現(xiàn)了一臺(tái)太鼓達(dá)人機(jī)臺(tái)，而在機(jī)臺(tái)前坐著的是剛剛被精英隊(duì)伍成員XLk逗概、Poet_shy和lydrainbowcat拯救出來的的applepi弟晚。看到兩人對(duì)太鼓達(dá)人產(chǎn)生了興趣，applepi果斷閃人卿城，于是cl拿起鼓棒準(zhǔn)備挑戰(zhàn)枚钓。然而即使是在普通難度下，cl的路人本性也充分地暴露了出來瑟押。一曲終了搀捷，不但沒有過關(guān)，就連鼓都不靈了多望。Vani十分過意不去指煎，決定幫助工作人員修鼓。
描述
鼓的主要元件是M個(gè)圍成一圈的傳感器便斥。每個(gè)傳感器都有開和關(guān)兩種工作狀態(tài)至壤，分別用1和0表示。顯然枢纠，從不同的位置出發(fā)沿順時(shí)針方向連續(xù)檢查K個(gè)傳感器可以得到M個(gè)長(zhǎng)度為K的01串像街。Vani知道這M個(gè)01串應(yīng)該是互不相同的。而且鼓的設(shè)計(jì)很精密晋渺，M會(huì)取到可能的最大值×铮現(xiàn)在Vani已經(jīng)了解到了K的值，他希望你求出M的值木西，并給出字典序最小的傳感器排布方案畴栖。
輸入格式
一個(gè)整數(shù)K。
輸出格式
一個(gè)整數(shù)M和一個(gè)二進(jìn)制串八千，由一個(gè)空格分隔吗讶。表示可能的最大的M，以及字典序最小的排布方案恋捆，字符0表示關(guān)照皆，1表示開。你輸出的串的第一個(gè)字和最后一個(gè)字是相鄰的沸停。
樣例輸入
3
樣例輸出
8 00010111
解釋
大體思路：求哈密頓環(huán)
首先膜毁，顯而易見，m=(1<<k).
對(duì)于每一個(gè)長(zhǎng)度是k的01串s愤钾，都可以對(duì)應(yīng)一個(gè)(s<<1)&(m-1)+1或(s<<1)&(m-1)+0的01串T.
例如：
s=001瘟滨，則T1=010，T2=011;
s=1101能颁，則T1=1010杂瘸，T2=1011；
...
每個(gè)01串s就可以構(gòu)成一個(gè)按照上述規(guī)則繪制的有向圖劲装，每個(gè)點(diǎn)都有2個(gè)出邊和2個(gè)入邊胧沫。
按照題目要求昌简，必定存在一種方案，能遍歷所有點(diǎn)而且回到起點(diǎn)绒怨。(為了讓字典序盡可能小纯赎，起點(diǎn)可設(shè)置成純0串)。
求哈密頓環(huán)就行了南蹂。
c++代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define LL long long
using namespace std;
const int maxn=(1<<11)+10;
int k,m,a[maxn];
bool b[maxn]={0};//b[s]表示01串s是否被訪問過
inline bool dfs(int number,int s) {
a[number]=s;
if(number>=m) {
for(int i=1; i<=m; i++)
cout<<(a[i]>>(k-1));//輸出每個(gè)01串的第一個(gè)位置的bool數(shù)
cout<<endl;
return true;
}
int T=(s<<1)&(m-1);
for(int i=0; i<=1; i++) {
if(!b[T+i]) {
b[T+i]=true;
if(dfs(number+1,T+i))
return true;
b[T+i]=false;
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin>>k;
m=(1<<k);
cout<<m<<" ";
dfs(0,0);
return 0;
}
運(yùn)行結(jié)果
