七夕祭上,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的值,并给出字典序最小的传感器排布方案。

链接🔗
「BZOJ 3033」 太鼓达人

题解

n-1 位的二进制串看成 2n12^{n-1} 个点,然后连向与它二进制位第一位和最后一位不同的两个点,然后可以发现是个欧拉图,字符串长度为 2n2^n ,然后可以用 dfs 暴力求出来

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 1<<12;
int n,k,ans[maxd];
bool vis[maxd];
void dfs(int x,int y)
{
    if(vis[x]) return;
    vis[x] = 1;ans[y] = x >> (n-1);
    if(y==k)
    {
        for(int i=1;i<=k;i++) printf("%d",ans[i]);
        exit(0);
    }
    dfs((x<<1)&(k-1),y+1);
    dfs((x<<1|1)&(k-1),y+1);
    vis[x] = 0;
}
int main()
{
    scanf("%d",&n); k = 1 << n; printf("%d ",k);
    dfs(0,1);
    return 0;
}