BZOJ3033: 太鼓达人(欧拉回路)
程序员文章站
2022-08-17 17:30:23
题意 "题目链接" Sol 第一问的答案是$2^M$,因为每个位置只有$0 / 1$两种情况,最优情况下一定是每个位置代表着一个长度为$K$的字符串 考虑相邻两个字符串之间的转化,第二个字符串可以由第一个字符串在后面加$0 / 1$转移而来,因为转移关系会形成环,所以我们只需要找一条欧拉回路即可,每 ......
题意
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; }