寒假训练4

F题

解题思路

为了让所有子串的mex之和最大，核心策略是：尽可能让0和1交替出现，避免长段连续相同字符。 原因分析：

1.子串的mex值取决于子串中是否包含0和1。

2.如果子串同时包含0和1，则mex=2，贡献最大。

3.如果子串只包含0，则mex=1，贡献中等。

4.如果子串只包含1，则mex=0，贡献最小。

因此，构造时应尽可能让0和1分散排列，使得更多子串同时包含两种字符。当某一字符数量远多于另一字符时，应将较少的字符作为"分隔符"，均匀插入到较多的字符之间。

构造方法：

1.如果a > b（0比1多）：

将b个1作为分隔符，插入到a个0之间，形成b+1段0。

为了让0的分布尽量均匀，每段0的个数应为a/(b+1)，多余的0放在最后一段。

2.如果b ≥ a（1比0多）：

将a个0作为分隔符，插入到b个1之间，形成a+1段1。

每段1的个数应为b/(a+1)，多余的1放在最后一段。

这种均匀分配的构造方式能够最大程度减少连续相同字符的长度，从而最大化mex之和。

示例代码：

void solve() {
    int a, b;
    cin >> a >> b;
    
    if (a == 0) {
        cout << string(b, '1') << "\n";
        return;
    }
    if (b == 0) {
        cout << string(a, '0') << "\n";
        return;
    }
    
    if (a > b) {
        int groups = b + 1;
        int base = a / groups;
        int extra = a % groups;
        
        for (int i = 0; i < groups; i++) {
            int cnt = base + (i < extra ? 1 : 0);
            cout << string(cnt, '0');
            if (i < b) cout << '1';
        }
    } else {
        int groups = a + 1;
        int base = b / groups;
        int extra = b % groups;
        
        for (int i = 0; i < groups; i++) {
            int cnt = base + (i < extra ? 1 : 0);
            cout << string(cnt, '1');
            if (i < a) cout << '0';
        }
    }
    cout << "\n";
}

H题

解题思路

直接输出277777788888899和27777789999999999

示例代码：

void solve(){
    cout<<277777788888899<<" "<<27777789999999999;
}