当前位置： 移动技术网 > IT编程>开发语言>C/C++ > BZOJ3033: 太鼓达人(欧拉回路)

BZOJ3033: 太鼓达人(欧拉回路)

2018年10月15日  | 移动技术网IT编程  | 我要评论

版税,最优美的文章,基因身份证

题意

题目链接

sol

第一问的答案是\(2^m\)，因为每个位置只有\(0 / 1\)两种情况，最优情况下一定是每个位置代表着一个长度为\(k\)的字符串

考虑相邻两个字符串之间的转化，第二个字符串可以由第一个字符串在后面加\(0 / 1\)转移而来，因为转移关系会形成环，所以我们只需要找一条欧拉回路即可，每次走的时候优先走编号小的边

代码好神啊。看不懂的话可以手玩一下\(n = 2\)的数据

#include<bits/stdc++.h>
using namespace std;
int k, lim, vis[1 << 12], ans[1 << 12];
int dfs(int sta, int dep) {

    if(vis[sta]) return 0;
    if(dep == lim + 1) return 1;
    vis[sta] = 1; ans[dep] = sta & 1;//得到该字符的最后一个元素 
    if(dfs((sta << 1) & lim, dep + 1)) return 1;
    if(dfs((sta << 1 | 1) & lim, dep + 1)) return 1;
    vis[sta] = 0;
    return 0;
}
int main() {
    cin >> k;
    cout << (lim = ((1 << k) - 1)) + 1 << endl;
    dfs(0, 1);
    for(int i = 1; i < k; i++) putchar('0');
    for(int i = 1; i <= lim - k + 2; i++) printf("%d", ans[i]); 
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网