题解 | #太鼓达人#

太鼓达人

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;
}
全部评论

相关推荐

争当牛马还争不上
码农索隆:1.把简历改哈 2.猛投,狠投 3.把基础打牢 这样你在有机会的时候,才能抓住
点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
07-03 16:02
门头沟学院 Java
今天面试,非常紧张,面试官问我springboot有哪些核心模块都答不上来了,真的对自己无语了!
程序员小白条:28届我勒个去,很多人面试都没机会
查看1道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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