BZOJ3033: 太鼓达人【欧拉回路+DFS】

3033: 太鼓达人

【题目描述】

传送门

【题解】

这题就是一个欧拉回路,K很小DFS就可以了。

代码如下

#include<cstdio>
using namespace std;
int n,t,Ans[1<<12];
bool vis[1<<12];
bool DFS(int x,int P){
    if(vis[x]) return 0;
    if(P==t) return 1;
    vis[x]=1;Ans[P]=x&1;
    if(DFS((x<<1)&(t-1),P+1)) return 1;
    if(DFS((x<<1|1)&(t-1),P+1)) return 1;
    vis[x]=0;return 0;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    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]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部