题解：P12651 [KOI 2024 Round 2] 最大异或

· · 题解

在写这题的时候突然意识到下划线都比我的代码来的可读（

容易发现 S 的任意子串都不会超过 S，所以其中一个参与异或的数字必然是 S。

然后容易发现最大化异或出来的值等价于使前面的位尽可能大，所以可以不管后面的令前面的 0 变成 1，并保持住前面原有的 1。

我们找到第一个 0，从前面连续的 1 中选一个下来开始异或即可。

此时容易做到 O(n^2)，过不了。

但是我们发现大量的 1 放下来可能会对后面造成冲突，于是从前面剪一段与当前连续 0 长度相同的放过来异或即可。

这样就可以 O(n) 了。

于是我们瞬秒了这一题？？？

实现上有些细节和特判，具体看代码。

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    string s;
    cin>>n>>s;
    string flc;
    s=" "+s;
    bool flag=0;
    bool galf=0;
    for(int i=1;i<=n;i++){
        if(!(s[i]=='0'&&flc.size()==0))
        flc+=s[i],galf|=s[i]=='0';
        flag|=s[i]=='0';
    }
    if(!flag){
        for(int i=1;i<n;i++)putchar('1');
        puts("0");
        return;
    }
    if(!galf){
        if(!flc.size())flc="0";
        cout<<flc<<'\n';
        return;
    }
    flc=" "+flc;
    swap(flc,s);
    n=s.size()-1;
    int x=-1;
    for(int i=1;i<=n&&x==-1;i++)
    if(s[i]=='0')x=i-1;
    else cout<<"1";
    int qwq=x+1;
    int y=-1;
    for(int i=qwq;i<=n&&s[i]!='1';i++)y=i;
    if(x<=y-x)y=x+x;
    y-=x;x-=y;x++;
    for(int i=0;i+qwq<=n;i++)
    cout<<((s[i+qwq]+s[i+x])&1);
    cout<<"\n";
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 「为什么……为什么啊……」

// 激动的情绪立刻就干涸了。
// 吼声中断，变成轻微的呜咽。
// 大粒泪珠从眼角盈出，滴滴答答地落在腿上，裙摆留下湿痕。

// Nygglatho Astartus