题解 | #F 爱音的01串构造#

题意

构造一个由a 个 0 和 b 个 1 组成的 01 字符串，且使得这个 01 字符串所有非空连续子串的 mex 之和最大。

关键词

构造

题解

首先01同在mex=2,只有0mex=1，只有1mex=0。

所以我们要尽量使01交替排列，1连续的要少。

最简单的a==b,a==b+1,b=a+1。只需要0与1交替排列，即010101....。

如果a>b+1呢，就比如10个0，5个1。首先想到010101010100000。可这样会有五个0连续在一起，其单独0的子字符串组合是一个n=5的等差数列之和，但如果把0平均分开，就是几个n比较小的等差数列之和，应当更小,所以最优组合应当平均分开。5个1可插6个空位。10/6=1......余4，所以有四段2个0，两段1个0，组成是001001001001010。

#include<iostream>
#include<string>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        int a,b;
        cin>>a>>b;
        if(a>b){
            int ans=a/(b+1);
            int c=a%(b+1);
            for(int j=1;j<=c;j++){
                for(int k=1;k<=ans+1;k++){
                    cout<<"0";
                }
                cout<<"1";
            }
            for(int j=1;j<=b-c;j++){
                for(int k=1;k<=ans;k++){
                    cout<<"0";
                }
                cout<<"1";
            }
            for(int j=1;j<=ans;j++){
                cout<<"0";
            }
        }
        else {
            int ans=b/(a+1);
            int c=b%(a+1);
            for(int j=1;j<=c;j++){
                for(int k=1;k<=ans+1;k++){
                    cout<<"1";
                }
                cout<<"0";
            }
            for(int j=1;j<=a-c;j++){
                for(int k=1;k<=ans;k++){
                    cout<<"1";
                }
                cout<<"0";
            }
            for(int j=1;j<=ans;j++){
                cout<<"1";
            }
        }
        cout<<"\n";
    }
}