【洛谷5890】小欧与回文串构造 | Mrsrz's blog

构造。

题目大意：

给定 $n,k$，要求构造长度恰好为 $n$ 的 01 串，使得其中本质不同的回文子串个数恰好为 $k$。

题解：

当 $n$ 较小的时候，可以暴力枚举。

当 $n$ 较大时，有以下构造方法：

我们构造的串为 001011001011001011...，即 001011 不断循环。

发现其前缀 001011001 恰好包含 $8$ 个不同回文子串，且之后继续循环仍然为 $8$ 个。

那我们可以先将 $8$ 个分配给这里，然后 $k-8$ 个的构造，可以在串前面加上 $k-8$ 个 0。

这样就可以构造任意长度的 $8\leq k <n$ 的串了。

当 $n$ 较大时，$k<8$ 没有方法，而 $k=n$ 时这种方法会少一个（前缀长度不到 $9$），这时只要 $k$ 个 0 就可以了。

Code：

#include<iostream>
#include<cstring>
#include<string>
#include<set>
using namespace std;
int T,n,k;
std::set<string>st;
bool check(const string&s){
    for(int i=0;i<s.length();++i)
    if(s[i]!=s[s.length()-i-1])return 0;
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(cin>>T;T--;){
        cin>>n>>k;
        if(n<=16){
            const int C=1<<n;
            bool o=0;
            for(int S=0;S<C;++S){
                int x=0;
                string s="";
                st.clear();
                for(int i=0;i<n;++i)
                s+=(char)((S>>i&1)^'0');
                for(int l=0;l<n;++l){
                    string nw="";
                    for(int r=l;r<n;++r){
                        nw+=s[r];
                        if(check(nw)&&!st.count(nw))
                        st.insert(nw),++x;
                    }
                }
                if(x==k){
                    cout<<"Yes\n"<<s<<'\n';
                    o=1;
                    break;
                }
            }
            if(!o)cout<<"No\n";
        }else
        if(n==k){
            cout<<"Yes\n";
            for(int i=0;i<k;++i)cout.put('1');
            cout<<'\n';
        }else{
            if(k<8)cout<<"No\n";else{
                cout<<"Yes\n";
                k-=8;
                string ans="";
                while(ans.length()+6<=n-k)ans+="001011";
                if(ans.length()<n-k)ans+="0";
                if(ans.length()<n-k)ans+="0";
                if(ans.length()<n-k)ans+="1";
                if(ans.length()<n-k)ans+="0";
                if(ans.length()<n-k)ans+="1";
                for(int i=0;i<k;++i)cout.put('0');
                cout<<ans<<'\n';
            }
        }
    }
    return 0;
}