通过从给定的二进制字符串中选择相等长度的子字符串，最大化给定函数

介绍

二进制字符串是计算机中最基本的存储方式之一。在计算机科学中，我们经常需要对二进制字符串进行操作。本文将介绍一个关于二进制字符串的新问题：如何通过从给定的二进制串中选择相等长度的子字符串，最大化给定函数。

问题描述

给定一个由0和1组成的二进制字符串s，函数f(x)表示字符串x中所有字符的异或和（即x的所有字符的值相异或的结果）。现在，你需要从字符串s中选择若干个等长度的子串，并将它们拼接成一个新字符串t。你需要找到一个方案使得f(t)的值最大。

输入格式

输入数据为两行，第一行为s，第二行为每个要选择子串的长度l。

输出格式

输出应为一个整数，表示f(t)的最大值。

数据范围

输入字符串的长度不超过1,000,000 。

解法

对于这个问题，我们需要找到一个独特的解决方案。这里我们建议用一个基于哈希表的算法。首先，我们可以将每个长度为l的子串的异或和存储在哈希表中，这样我们就可以在O(1)的时间内查找任何给定子串的异或和。接下来，我们可以用一些启发式的算法来搜索所有可能的方案。

最朴素的方法是枚举所有n/l个长度为l的子串，并对它们的异或和进行加和。这种方法的时间复杂度为O(n^2)，对于大型数据集来说是不可行的。

为了改进算法，我们可以利用哈希表解决下面的问题：给定一个长度为l的子串，如何在O(1)时间内找到它的异或和？有一个简单的方法是，首先将每个字符的值都取模为2（即0或1），然后将这些值视为二进制数并将它们相加。这就是该子串的异或和。例如，对于子串1011，我们可以将它转换为二进制数1011=1*2^3+0*2^2+1*2^1+1*2^0=8+0+2+1=11，所以它的异或和为11。我们可以将哈希表的键值设置为异或和，值设置为相应子串的数量。这样，我们就可以在O(1)时间内查询任何子串的异或和。

有了哈希表，我们现在可以尝试一些基于贪心的启发式算法来搜索所有可能的方案。例如，我们可以尝试从子串中选择出现次数最多的子串，然后在剩余的子串中选择出现次数第二多的子串，并将这两个子串拼接起来，重复此过程直到所有子串都被拼接为止。这样做的原因是，从哈希表中选择出现次数最多的子串可以最大化拼接后的字符串的异或和。这种方法的时间复杂度是O(nlogn)，其中n是二进制字符串的长度。在本问题中，这个算法已经足够快了，但是它的时间复杂度依然比较高。

有一种更快的方法是使用分治算法。我们可以将二进制字符串s划分成两个长度为n/2的子字符串s1和s2。然后，我们可以通过递归地求解子问题来构造字符串t。对于每个子问题，我们可以使用哈希表找到s1和s2中所有长度为l的子串的异或和，并将它们排序。接下来，我们可以使用哈希表找到长度为2l的拼接子串，并将它们排序。然后，我们可以使用标准的分治技术将两个排序的列表合并为一个排序的列表。最后，我们可以通过比较拼接子串的异或和的大小来选择两个列表中的元素。

C++实现

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Dow(i,b,a) for(int (i)=(b);(i)>=(a);(i)--)
#define Debug(c) cout << #c << " = " << c << endl;
const int Maxn = 1e6+5;
const int Mod = 998244353;
inline int read() {int x=0,f=1;char ch=' ';while(ch>'9'||ch<'0') {if(ch=='-')f=-f;ch=getchar();}while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;}
int s[Maxn],n,st,dr,mid,num[Maxn],flag[Maxn];  //st, dr表示枚举的子串的左右端，mid表示当前子串的中点
inline int Qm(int num) {  //求二进制数的异或和
    int ans = 0;
    while(num) {
        ans ^= (num%2);
        num /= 2;
    }
    return ans;
}
unordered_map  M;
inline bool CK(int l,int mid,int r) {  //比较在左区间和在右区间选择的子串的异或和，返回1表示左优先级高，返回0表示右优先级高
    int num1 = M[num[mid]];
    int num2 = M[num[mid]^num[r]];
    if(num1==num2 && flag[mid]
    if(num1>num2) return 1;
    return 0;
}
inline int Find(int l,int r,int gl,int gr) {  //返回在[l,r]区间中长度为gr的子串的与历史数据异或和的最大值
    int ans = -1;
    int l1 = max(l,gl-gr);
    int r1 = min(r,gr-1);
    if(l1>r1) return -1;
    For(i,l1,r1) {
        if(M.count(num[i]) && i+gr-1<=r && (!flag[i]/*未被使用*/)) ans = i;
    }
    if(ans==-1) return -1;
    st = max(ans-gr+1,gl);
    dr = min(ans+gr-1,r);
    while(st
        mid = (st+dr+1)/2;
        if(CK(l,mid,ans)) dr = mid-1;
        else st = mid;
    }
    flag[ans] = 1;  //标记这个选择，防止重复选择
    return ans;
}
int Q[Maxn],head = 1,tail;  //双端队列，用于动态规划
signed main() {
    char c=getchar();
    while(c=='0'||c=='1') {
        s[++n] = c-'0';
        c = getchar();
    }
    if(n<=20000) {  //较短的字符串可以使用纯随机算法，更快
        int k = read();
        int Maxn = n/k;
        int ans = -1;
        For(i,1,20) {
            int sum = 0;
            For(j,1,Maxn) {
                int res = 0;
                For(p,(j-1)*k+1,j*k) {
                    res ^= s[p];
                }
                M[res]++;
                sum += res;
            }
            ans = max(ans,sum);
        }
        printf("%lld\n",ans);
        exit(0);
    }
    int k = read();
    int slen = 0;
    tail = 1;
    For(i,1,k) {
        int sum = 0;
        M.clear();
        For(j,(i-1)*n/k+1,i*n/k) {
            Q[++tail] = j;
            if(!((tail-head+1)%k)) {
                For(o,head+1,tail) {
                    sum ^= s[Q[o]];
                }
                num[++slen] = sum;
                M[sum]++;
                head++;
            }
        }
    }
    int l = 1,r = slen;
    int gl,gr;
    int ans = -1;
    For(i,1,k/2) {
        if(l>r) break;
        int sum = 0;
        int ll = Find(l,r,1e9,-1);  //在[1,r]中选择一个长度为k/2的子串，并找到在[l-1,lm1](l-1<=lm1<=r-k/2)中使选择的子串异或和最大的子串lm1
        if(ll==-1) break;
        gl = max(ll-k/2,0ll);  //左区间为选择子串左侧k/2长度子串的左侧
        gr = max(k/2,ll-gl);  //右区间为选择子串左侧k/2长度子串与从当前选定子串往后选择k/2长度子串两个数组成的区间
        Dow(i,gl,1) {  //从左向右扩展左区间，用于之后的选择
            if(flag[i]) break;
            if(Qm(num[i]^num[ll])>Qm(num[ll])) break;
            gl = i;
        }
        For(i,ll,r) {  //从右向左扩展右区间，用于之后的选择
            if(flag[i]) break;
            if(i>=ll && Qm(num[i]^num[ll])>Qm(num[ll])) break;
            gr = i-ll+1;
        }
        int now = ll-gr;
        int len = 1;
        int flg = 0;
        while(1) {
            if(now<1) break;
            if(flag[now]) {
                now = now-k/2;  //如果选择区间与之前的选择有交集，则向左移动
                if(flg==0) len--;
                else flg--;
                continue;
            }
            if(ll+k/2-1>=now) {  //如果选择区间插入了当前扩张的区间，则向右移动
                now = ll+k/2;
                if(flg==len-1) flg--;
                else len--;
                continue;
            }
            M[num[ll]^num[now]]--;
            sum += num[ll]^num[now];
            ll = now;
            flg = min(flg,len-1);  //检查当前选择是否改变之前选择的右区间
            while(flg+10) {
                flg++;
                sum += num[ll]^num[ll+flg*k/2];
            }
            num[++slen] = num[ll];
            flag[now] = 1;
            now += k/2;
            len++;
            if(ll+k/2-1<=now) {  //如果当前选择区间插入了之前扩张的区间，则向右移动
                now = ll+k/2;
                if(flg==len-1) flg--;
                else len--;
            }
        }
        ans = max(ans,sum);
        l = ll+k/2;
    }
    cout << ans << endl;
    return 0;
}