题目描述
难度分:1200
输入T(≤103)表示T组数据。所有数据的字符串长度之和≤5000。
每组数据输入长度≤5000的01
字符串s。保证s的第一个字符是1
。
你需要在s中选择两个非空子串(可以重叠,可以有前导零),将其视作两个二进制数,计算XOR。
目标是最大化XOR。输出你选择的两个子串的左右端点l1 r1 l2 r2,下标从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
,所以比较容易发现两段中一定有一段是整个串,不妨设l1=1,r1=n。因为只要另一段[l2,r2]和[l1,r1]不相同,就一定可以保住s[1],从而有一个n位的异或结果。
因此我们只要求l2和r2就可以了。遍历i∈[2,n]找到s[i]=0
的第一个位置,如果不存在这个位置,说明整个串是全1
的,只需要令l2=r2,让[l1,r1]的最后一个1
(最低位的1
)变成0
即可。假设j是第一个满足s[j]=0
的位置,那么要想两段的异或结果最大,一定要找到一个l2<j,且满足s[l2]=1
的位置。之所以要求l2<j是因为如果l2≥j的情况下,无论r2取在哪里,[l2,r2]和[l1,r1]异或的时候都不可能让j和l2对齐。除此之外,为了让l2和j对齐,还必须满足len=r2−l2+1=n−j+1。
接下来只需要比较所有符合s[l2]≠s[j]的l2哪个最好就可以了。假设len=r2−l2+1,对每个l2预处理出一个pos数组,这个数组就是以下两个序列中满足s[i1]≠s[i2]的i1位置
i1∈[j,j+1,j+2,…,j+len−2,j+len−1]
i2∈[l2,l2+1,l2+2,…,r2−1,r2]
为了高位尽可能在异或后变成1
,显然pos的字典序越小越好,如果某两个序列v1和v2满足v1是v2的前缀,那么更长的v2是更好的,因为不同的位置更多,异或完能得到更多的1
。得到最好的pos序列,它对应的l2,r2就是我们要求的。
复杂度分析
时间复杂度
获得l2候选需要先遍历i∈[2,n]找到第一个s[i]=0
的位置,对这个位置还需要遍历j<i,找到所有满足s[j]≠s[i]的位置作为l2的候选。由于只会有一个i会触发j∈[1,i)的遍历,所以这一步的时间复杂度为O(n)。
接下来遍历l2的候选,时间复杂度为O(n)。维护最优的pos数组,求出某个l2的时间复杂度为O(n),比较两个pos数组谁更优的时间复杂度为O(n),所以这一步的时间复杂度为O(n2)。
综上,整个算法的时间复杂度为O(n2)。
空间复杂度
空间消耗的瓶颈主要在于每个l2候选的pos数组,l2候选以及pos数组都是O(n)规模的。所以,整个算法的额外空间复杂度为O(n2)。
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;
}