题解：P10950 太鼓达人

· · 题解

题意：

给你一个数字 k，让你构造出字典序最小的一个字符串，这个字符串的长度 m 要最大，并且要求 任意选取两个长度为 k 的字串，要求互不相同。注意：这个字符串是一个环形，所以首尾相连。

举个例子：

当 k 等于 3 时，满足的字符串是 00010111。

他需要满足一下这些值任意两项不同：
1. 000
2. 001
3. 010
4. 101
5. 011
6. 111
7. 110
8. 100

明白了吧。

思路：

第一眼看到数据范围，这不是纯打表么？

细细一读题，不难发现，我们最多最多可以构造出 M 最大是 2^k。这应该都能看出来吧

因为题目要求字典序最小，结合样例就可以看出前 k 个数一定都是 0。

因为数据较小，所以我们考虑暴力搜索出一个 01 字符串。唯一的剪枝优化就是记录一个桶，记录一个数有没有在一个长度为 k 的子串中出现，当暴力到这个新选择的节点时，如果这个以这个节点为结尾的长度为 k 的子串有没有在前面出现过，如果有的话那就放弃，不在继续递归。

代码：

暴力代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k,a[6010],n;
bool b[6010];
ll f(ll x){//计算长度，也就是 2 的 k 次方。
    ll ans=1;
    for(int i=1;i<=x;i++) ans*=2;
    return ans;
}ll hh(string s){//把一个二进制转成一个数。
    ll base=1,ans=0;
    for(int i=s.size()-1;i>=0;i--){
        ans+=(s[i]-'0')*base;
        base*=2;
    }return ans;
}                             
void dfs(ll step){
    if(step==n+1){//如果全部选择完了，判断一下结尾的部分，因为这道题是一个环形。
        bool flag=false;        
        for(int j=n-k+2;j<=n;j++){
            string s="";
            for(int l=j;l<=j+k-1;l++) s+=(a[l]+'0');
            ll x=hh(s);
            if(b[x]==true) {flag=true;break;}
        }if(flag==false){//因为我们每次先选的是 0，所以第一个选上的一定是字典序最小的。
            for(int i=1;i<=n;i++) cout<<a[i];
            exit(0);
        }return ;
    }
    for(int i=0;i<=1;i++){//选择当前节点是 0 还是 1。
        string s="";
        a[step]=i;
        for(int j=step-k+1;j<=step;j++) s+=(a[j]+'0');
        ll x=hh(s);
        if(b[x]==true) continue;
        b[x]=true;
        dfs(step+1);
        b[x]=false;
    }
}
int main(){
    cin>>k;
    n=f(k);
    cout<<n<<" ";//输出长度
    b[0]=true;//注意我是直接跳过了前 k 个节点，所以 0 已经使用过了，以后不能再使用
    dfs(k+1);
    return 0;
}

打表代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k;
int main(){
    cin>>k;
    if(k==2) cout<<"4 0011";
    else if(k==3) cout<<"8 00010111";
    else if(k==4) cout<<"16 0000100110101111";
    else if(k==5) cout<<"32 00000100011001010011101011011111";
    else if(k==6) cout<<"64 0000001000011000101000111001001011001101001111010101110110111111";
    else if(k==7) cout<<"128 00000001000001100001010000111000100100010110001101000111100100110010101001011100110110011101001111101010110101111011011101111111";
    else if(k==8) cout<<"256 0000000010000001100000101000001110000100100001011000011010000111100010001001100010101000101110001100100011011000111010001111100100101001001110010101100101101001011110011001101010011011100111011001111010011111101010101110101101101011111011011110111011111111";
    else if(k==9) cout<<"512 00000000010000000110000001010000001110000010010000010110000011010000011110000100010000100110000101010000101110000110010000110110000111010000111110001000110001001010001001110001010010001010110001011010001011110001100110001101010001101110001110010001110110001111010001111110010010010110010011010010011110010100110010101010010101110010110110010111010010111110011001110011010110011011010011011110011101010011101110011110110011111010011111110101010110101011110101101110101110110101111110110110111110111011110111111111";
    else if(k==10) cout<<"1024 0000000000100000000110000000101000000011100000010010000001011000000110100000011110000010001000001001100000101010000010111000001100100000110110000011101000001111100001000010001100001001010000100111000010100100001010110000101101000010111100001100010000110011000011010100001101110000111001000011101100001111010000111111000100010100010001110001001001000100101100010011010001001111000101001100010101010001010111000101100100010110110001011101000101111100011000110010100011001110001101001000110101100011011010001101111000111001100011101010001110111000111100100011110110001111101000111111100100100110010010101001001011100100110110010011101001001111100101001010011100101010110010101101001010111100101100110010110101001011011100101110110010111101001011111100110011010011001111001101010100110101110011011011001101110100110111110011100111010110011101101001110111100111101010011110111001111101100111111010011111111010101010111010101101101010111110101101011011110101110111010111101101011111110110110111011011111101110111110111101111111111";
    else cout<<"2048 00000000000100000000011000000001010000000011100000001001000000010110000000110100000001111000000100010000001001100000010101000000101110000001100100000011011000000111010000001111100000100001000001000110000010010100000100111000001010010000010101100000101101000001011110000011000100000110011000001101010000011011100000111001000001110110000011110100000111111000010000110000100010100001000111000010010010000100101100001001101000010011110000101000100001010011000010101010000101011100001011001000010110110000101110100001011111000011000110000110010100001100111000011010010000110101100001101101000011011110000111000100001110011000011101010000111011100001111001000011110110000111110100001111111000100010010001000101100010001101000100011110001001001100010010101000100101110001001100100010011011000100111010001001111100010100011000101001010001010011100010101001000101010110001010110100010101111000101100110001011010100010110111000101110010001011101100010111101000101111110001100011100011001001000110010110001100110100011001111000110100110001101010100011010111000110110010001101101100011011101000110111110001110010100011100111000111010010001110101100011101101000111011110001111001100011110101000111101110001111100100011111011000111111010001111111100100100101001001001110010010101100100101101001001011110010011001100100110101001001101110010011101100100111101001001111110010100101100101001101001010011110010101001100101010101001010101110010101101100101011101001010111110010110011100101101011001011011010010110111100101110011001011101010010111011100101111011001011111010010111111100110011011001100111010011001111100110100111001101010110011010110100110101111001101101010011011011100110111011001101111010011011111100111001111001110101010011101011100111011011001110111010011101111100111101011001111011010011110111100111110101001111101110011111101100111111101001111111110101010101101010101111010101101110101011101101010111111010110101110101101101101011011111010111011110101111011101011111011010111111110110110111101101110111011011111110111011111101111011111011111111111";
    return 0;
}