太鼓達人 搜索

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

　　鼓的主要元件是M個圍成一圈的傳感器。每一個傳感器都有開和關兩種工做狀態，分別用1和0表示。顯然，從不一樣的位置出發沿順時針方向連續檢查K個傳感器能夠獲得M個長度爲K的01串。Vani知道這M個01串應該是互不相同的。並且鼓的設計很精密，M會取到可能的最大值。如今Vani已經瞭解到了K的值，他但願你求出M的值，並給出字典序最小的傳感器排布方案。app

給了一個子串長K，每一個字串由01組成，因此最大狀態量是2^k spa

而後dfs生成字串用map判重設計

#include<map>
#include<cstdio>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;

map<string,bool> ma;

string s,s1;

int sum=0,k;

void dfs(string s1,int ans)
{
	if(ans==sum&&ma[s1]==0)
	{
		string s2=s1.substr(0,sum);
		cout<<s2;
		exit(0);
	}
	string s2=s1.substr(ans,sum-1);
	if (!ma[s2+'0'])
	{
		ma[s2+'0']=1;
		dfs(s1+'0',ans+1);
		ma[s2+'0']=0;
	}
	if (!ma[s2+'1'])
	{
		ma[s2+'1']=1;
		dfs(s1+'1',ans+1);
		ma[s2+'1']=0;
	}
	
}

int main()
{
	int k;
	scanf("%d",&k);
	sum=(1<<k);
	printf("%d ",sum);
	for (int i=1;i<=k;i++) s1+='0';
	ma[s1]=1;
	
	dfs(s1,1);
	
}