自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 23:17:07，当前版本为作者最后更新于2025-08-16 18:26:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

容易发现 $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