P10950 太鼓达人 题解

· · 题解

这是一种欧拉回路的做法，因为我观察到题解区没有欧拉回路的题解。

题意

题意就不再赘述了，需要的可以看其他题解。

思路

如果把每个 k 位 01 串视为一个点，把“往 01 串后面加一位” 视为一条有向边，那么这是个哈密顿路径的问题，要求每个点恰好经过一次。可惜的是哈密顿路径是 NP-Complete 的。

我们还可以转换思路，把每个 k-1 位 01 串视为一个点，把“往 01 串后面加一位” 视为一条有向边，那么每个点恰好有两条入边，来源于两个第 k-1 高位不同的点，因此代表了这个点的两个不同的形态（第 k 高位分别为 0,1）。这就变成了欧拉回路问题 —— 每条边经过恰好一次。

显然第一问的答案等于边数 ——2^k。对于第二问，我们只需跑一遍 Hierholzer 算法（dfs 法求欧拉回路），每跑过一条边就把这条边输出（因为这个图一定是欧拉回路，所以无需使用栈）。

接下来是实现上的细节：我们可以采用当前弧优化来减小最坏复杂度。其次，我们必须以 2^{k-1}-1（11\dots 11） 为起点。后者是因为我们在一个环上，我们初始状态实际上是第一个位置前的一段，也就是末尾的一段，因此设置为全 1，同时这样转移到环的前面一段时都是 0。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll k;
ll cur[N];
bool ans[N];
ll tot,lim;
void dfs(ll x)
{
    for(ll i=cur[x];i<=1;i=cur[x])
    {
        cout<<i;
        cur[x]=i+1;
        dfs(((x<<1)&lim)|i);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>k;
    lim=(1ll<<(k-1))-1;
    cout<<(1ll<<k)<<" ";
    dfs(lim);
    return 0;
}

感觉比不少暴力还要简短，而且可以过 2\le k\le 21 哦。