题目描述

难度分:$1200$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的字符串长度之和$\leq 5000$。

每组数据输入长度$\leq 5000$的01字符串$s$。保证$s$的第一个字符是1。

你需要在$s$中选择两个非空子串（可以重叠，可以有前导零），将其视作两个二进制数，计算$XOR$。

目标是最大化$XOR$。输出你选择的两个子串的左右端点$l_1$ $r_1$ $l_2$ $r_2$，下标从$1$开始。

如果答案不止一种，输出其中任意一个。

输入样例

5
111
1000
10111
11101
1100010001101

输出样例

2 2 1 3
1 3 1 4
1 5 1 4
3 4 1 5
1 13 1 11

算法

贪心

由于$s$的第一个字符一定是1，所以比较容易发现两段中一定有一段是整个串，不妨设$l_1=1,r_1=n$。因为只要另一段$[l_2,r_2]$和$[l_1,r_1]$不相同，就一定可以保住$s[1]$，从而有一个$n$位的异或结果。

因此我们只要求$l_2$和$r_2$就可以了。遍历$i \in [2,n]$找到$s[i]=$0的第一个位置，如果不存在这个位置，说明整个串是全1的，只需要令$l_2=r_2$，让$[l_1,r_1]$的最后一个1（最低位的1）变成0即可。假设$j$是第一个满足$s[j]=$0的位置，那么要想两段的异或结果最大，一定要找到一个$l_2 \lt j$，且满足$s[l_2]=$1的位置。之所以要求$l_2 \lt j$是因为如果$l_2 \geq j$的情况下，无论$r_2$取在哪里，$[l2_,r_2]$和$[l_1,r_1]$异或的时候都不可能让$j$和$l_2$对齐。除此之外，为了让$l_2$和$j$对齐，还必须满足$len=r_2-l_2+1=n-j+1$。

接下来只需要比较所有符合$s[l_2] \neq s[j]$的$l_2$哪个最好就可以了。假设$len=r_2-l_2+1$，对每个$l_2$预处理出一个$pos$数组，这个数组就是以下两个序列中满足$s[i_1] \neq s[i_2]$的$i_1$位置

$i_1 \in [j,j+1,j+2,…,j+len-2,j+len-1]$
$i_2 \in [l_2,l_2+1,l_2+2,…,r_2-1,r_2]$

为了高位尽可能在异或后变成1，显然$pos$的字典序越小越好，如果某两个序列$v_1$和$v_2$满足$v_1$是$v_2$的前缀，那么更长的$v_2$是更好的，因为不同的位置更多，异或完能得到更多的1。得到最好的$pos$序列，它对应的$l_2,r_2$就是我们要求的。

复杂度分析

时间复杂度

获得$l_2$候选需要先遍历$i \in [2,n]$找到第一个$s[i]=$0的位置，对这个位置还需要遍历$j \lt i$，找到所有满足$s[j] \neq s[i]$的位置作为$l_2$的候选。由于只会有一个$i$会触发$j \in [1,i)$的遍历，所以这一步的时间复杂度为$O(n)$。

接下来遍历$l_2$的候选，时间复杂度为$O(n)$。维护最优的$pos$数组，求出某个$l_2$的时间复杂度为$O(n)$，比较两个$pos$数组谁更优的时间复杂度为$O(n)$，所以这一步的时间复杂度为$O(n^2)$。

综上，整个算法的时间复杂度为$O(n^2)$。

空间复杂度

空间消耗的瓶颈主要在于每个$l_2$候选的$pos$数组，$l_2$候选以及$pos$数组都是$O(n)$规模的。所以，整个算法的额外空间复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 5010;
char s[N];
int T, n;

bool cmp(vector<int>& v1, vector<int>& v2) {
    int i = 0, j = 0;
    while(i < v1.size() && j < v2.size()) {
        if(v1[i] < v2[j]) return true;
        if(v1[i] > v2[j]) return false;
        i++, j++;
    }
    if(i == v1.size()) return false;
    return true;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        int l1 = 1, r1 = n;
        vector<array<int, 3>> cands;
        for(int i = 2; i <= n; i++) {
            int len = n - i + 1;
            if(s[i] == '0') {
                for(int j = 1; j < i; j++) {
                    if(s[j] == '1') {
                        cands.push_back({j, i, len});
                    }
                }
                if(cands.size()) break;
            }
        }
        if(cands.empty()) {
            printf("%d %d %d %d\n", l1, r1, 1, 1);
        }else {
            int start = cands[0][1];
            vector<int> seq;
            int index = 0, target = index;
            for(auto&cand: cands) {
                int left = cand[0], right = left + cand[2] - 1;
                vector<int> v;
                for(int i = 0; left + i <= right; i++) {
                    if(s[start + i] != s[left + i]) {
                        v.push_back(start + i);
                    }
                }
                if(seq.empty() || cmp(v, seq)) {
                    seq = v;
                    target = index;
                }
                index++;
            }
            int l2 = cands[target][0], r2 = l2 + cands[target][2] - 1;
            printf("%d %d %d %d\n", l1, r1, l2, r2);
        }
    }
    return 0;
}