Kevin and Binary Strings 题解

题目大意

给你一个以 $1$ 开头的二进制字符串 $s$。 你要选出两个非空子串，使得它们对应的二进制数的 异或（XOR）最大。 输出任意一组最优子串的左右下标（从 $1$ 开始）。

核心结论（贪心）

想要异或最大，只需要记住一句话： 一个子串必须取整个串，另一个子串从第一个 0 开始取到末尾。

详细规则

1. 整个串一定是其中一个子串：$[1, n]$（位数最长，保证异或最大）。
2. 在字符串中找到第一个出现的 $0$，位置为 $pos$。
3. 第二个子串就是：$[pos+1, n]$。
4. 特殊情况：如果串里全是 $1$，第二个子串取 $[1,1]$。

为什么这样是对的？

1. 位数越长，异或值越大：所以必须选整个串作为一个子串。
2. 异或最高位为 1 时最大：找到第一个 $0$，和整个串异或，最高位直接变成 $1$。
3. 这是能得到的最大可能值，没有更优方案。

AC 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.size();
        int pos = -1;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                pos = i;
                break;
            }
        }
        if (pos == -1) {
            cout << 1 << " " << n << " " << 1 << " " << 1 << "\n";
        } else {
            cout << 1 << " " << n << " " << pos + 1 << " " << n << "\n";
        }
    }
    return 0;
}

代码解释

1. 多组测试用例：while(t--) 处理每组数据。
2. 找第一个 0：遍历字符串，记录第一个 0 的下标。
3. 全 1 特判：没有 0，输出 [1,n] 和 [1,1]。
4. 正常情况：输出 [1,n] 和 [第一个0位置+1, n]。

复杂度分析

• 时间复杂度：$O(\sum |s|)$，线性遍历，符合题目 $5000$ 限制。
• 空间复杂度：$O(|s|)$，仅存字符串。
• 最优性：满足题目时间限制，是最优解法。

样例演示

输入：1000

• 第一个 0 在下标 $1$
• 输出：1 4 2 4
• 对应子串：1000 和 000，异或结果最大。

输入：111

• 无 0
• 输出：1 3 1 1