太鼓达人

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1419 字
de Bruijn 序列 Frederickson
一本通
练习
正文

/*
原题：T1532（3.7 欧拉回路）太鼓达人 / de Bruijn 序列
题意：给定 K（2≤K≤11），构造环形 01 串，使从各处连续取出 K 位得到的 2^K 个子串互不相同，
输出 M=2^K 与字典序最小的排布方案（首尾相邻）。
思路：这正是 de Bruijn 序列。字典序最小的 de Bruijn 序列由 FKM 算法给出：
把所有"长度整除 K"的 Lyndon 词按字典序拼接，总长恰为 2^K。
Lyndon 词即严格小于自身所有非平凡循环移位的串，直接枚举长度 L|K 的所有二进制串判定即可。
复杂度：时间 O(2^K·K)，空间 O(2^K)
易错点：1) 在图上跑 Hierholzer 并"优先走 0"并不保证字典序最小，必须用 FKM；
2) 只对长度能整除 K 的 Lyndon 词拼接，长度不整除的不能要；
3) 拼接后总长应恰为 2^K，若不等说明判定有误。
*/
#include <bits/stdc++.h>
using namespace std;
// 判断 s 是否为 Lyndon 词：严格小于自身所有非平凡循环移位
bool isLyndon(const string& s){
    int L=s.size();
    for(int r=1;r<L;r++){
        string t=s.substr(r)+s.substr(0,r);
        // Lyndon 词要求严格小于每个非平凡循环移位，相等说明是周期串，也要排除
        if(t<=s){
            return false;
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int K;
    if(!(cin>>K)){
        return 0;
    }
    vector<string> words;
    for(int L=1;L<=K;L++){
        if(K%L!=0){
            continue;
        }
        int total=1<<L;
        for(int mask=0;mask<total;mask++){
            string s;
            for(int i=L-1;i>=0;i--){
                s.push_back(((mask>>i)&1)?'1':'0');
            }
            if(isLyndon(s)){
                words.push_back(s);
            }
        }
    }
    sort(words.begin(),words.end());
    string seq;
    for(size_t i=0;i<words.size();i++){
        seq+=words[i];
    }
    cout<<(1<<K)<<" "<<seq<<"\n";
    return 0;
}
太鼓达人

正文

一本通·提高篇的其它内容
