题解 | #太鼓达人#

太鼓达人

https://ac.nowcoder.com/acm/problem/50424

题意

其实就是求字典序最小的长度为2^k的01串使得子串不重复出现。

思路

第一个答案很直观可以得到2^k,然后第二个答案爆搜就行了。优先选择0,如果前面以及出现过相应子串就回退填1. 这是一道欧拉回路的题,如何理解呢?就是每个状态都可以连0或者1,都有两个入边和出边。那么必然存在一条路径可以使得走过所有点并且回到原状态,于是就可以求一个欧拉回路来实现这道题。

代码

#include<bits/stdc++.h>
const int N=1e4;
 
using namespace std;
int n,bin,vis[N],ans[N];
bool dfs(int val,int step){
    if(vis[val]) return 0;
    if(step==bin)return 1;
    vis[val]=1;
    int nxt1=(val<<1)&(bin-1),nxt2=(val<<1|1)&(bin-1);
    ans[step]=val&1;
    if(dfs(nxt1,step+1)||dfs(nxt2,step+1)) return 1;
    vis[val]=0;
    return 0;
}
signed main(){
    scanf("%d",&n);
	bin=1<<n;
    printf("%d ",bin);
    dfs(0,1);
    for(int i=1;i<n;i++) putchar('0');
    for(int i=1;i<=bin-n+1;i++) printf("%d",ans[i]);
    return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
06-26 22:20
门头沟学院 Java
码农索隆:让你把简历发给她,她说一些套话,然后让你加一个人,说这个人给你改简历,然后开始卖课
我的求职精神状态
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务