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

题目解析

给定两个非负整数 a（表示字符 '0' 的数量）和 b（表示字符 '1' 的数量），要求构造一个由 a 个 '0' 和 b 个 '1' 组成的字符串使所有非空连续子串的 mex⁡ 之和最大。 那我们要让相同字符连续长度最小，关键是把数量多的字符，均匀分配到数量少的字符

代码演示

void solve(){
    int a,b;
    cin>>a>>b;  // 输入0的数量a，1的数量b
    string s;   // 存储最终构造的字符串
    
    // 特殊情况1：没有0（a=0），直接输出b个1
    if(a==0){
        for(int i=1;i<=b;i++){
            cout<<"1";
        }
        cout<<endl;
        return;  // 结束函数
    }
    // 特殊情况2：没有1（b=0），直接输出a个0
    else if(b==0){
        for(int i=1;i<=a;i++){
            cout<<"0";
        }
        cout<<endl;
        return;  // 结束函数
    }

    // 核心逻辑：分两种情况（0多 或 1多）
    if(a>=b){  // 0的数量 ≥ 1的数量
        // 计算：把a个0分到(b+1)个"间隔"里（1作为分隔符，b个1能分出b+1个间隔）
        int cns = a/(b+1);  // 每个间隔至少放cns个0
        int tmp = a%(b+1);  // 有tmp个间隔需要多放1个0
        
        // 先构造第一个间隔的0
        for(int i=1;i<=cns;i++){
            s += "0";  // 加基础数量的0
        }
        if(tmp>0){     // 如果有剩余的0，第一个间隔多放1个
            s += "0";
            tmp--;     // 剩余数量减1
        }
        
        // 遍历每个1，后面跟着对应数量的0
        for(int i=1;i<=b;i++){
            s += "1";  // 加一个1作为分隔
            // 加基础数量的0
            for(int j=1;j<=cns;j++){
                s += "0";
            }
            // 如果还有剩余的0，当前间隔多放1个
            if(tmp>0){
                s += "0";
                tmp--;
            }
        }
    }else{  // 1的数量 > 0的数量（逻辑和上面对称）
        // 把b个1分到(a+1)个"间隔"里（0作为分隔符，a个0能分出a+1个间隔）
        int cns = b/(a+1);  // 每个间隔至少放cns个1
        int tmp = b%(a+1);  // 有tmp个间隔需要多放1个1
        
        // 先构造第一个间隔的1
        for(int i=1;i<=cns;i++){
            s += "1";
        }
        if(tmp>0){
            s += "1";
            tmp--;
        }
        
        // 遍历每个0，后面跟着对应数量的1
        for(int i=1;i<=a;i++){
            s += "0";
            for(int j=1;j<=cns;j++){
                s += "1";
            }
            if(tmp>0){
                s += "1";
                tmp--;
            }
        }
    }
    cout<<s<<endl;  // 输出最终构造的字符串
}