自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:04:06，当前版本为作者最后更新于2024-10-02 20:14:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简要题意

对于一个 $01$ 串 $A$，我们称它是美丽的，当且仅当我们用 $A$ 中的 $1$ 分割这个字符串（这个字符串必须存在至少一个 $1$），假如 $1$ 的数量为 $x$，则分隔而成的 $x+1$ 个全 $0$ 串长度相等。

给定一个长度为 $n$ 的 $01$ 串，你需要删除最少的字符，使得剩下的字符串是美丽的，你需要输出这个字符串。

$1\leq n\leq 5\times 10^5$

思路

不妨先考虑 $76$ 分做法。我们可以枚举分割后每一个字符串的长度，然后考虑暴力构造这样的字符串取最长的，注意字符串的后缀必须要是一个合法的全 $0$ 串，实现。时间复杂度 $O(n^2)$。

考虑优化，首先一个重要的结论是虽然遍历每种长度的字符串无法做到的，但是遍历每种长度的字符串分割成了多少个字符串是可以做到的（调和级数求和，$O(n\log n)$ 级别）。

考虑对于每一个长度，维护一个指针，先维护前缀 $0$ 的数量，每次在上面二分，然后让指针跳到这个数的下一个 $1$ 的位置，以此类推。

时间复杂度上界 $O(n\log^2 n)$，不过实际表现不错。

代码

#include <bits/stdc++.h>
//#define int long long
using namespace std;

const int N = 5e5 + 5;
int n, a[N], nxt[N][2];
string s;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> s;
    s = " " + s;
    for(int i=1;i<=n;i++) a[i] = a[i - 1] + (s[i] == '0');
    nxt[n][0] = nxt[n][1] = n + 1;
    for(int i=n;i>=1;i--){
        nxt[i - 1][0] = nxt[i][0], nxt[i - 1][1] = nxt[i][1];
        nxt[i - 1][s[i] - '0'] = i;
    }
    int ans = 0, ansx = 0, anstt = 0;
    for(int i=1;i<=n;i++){
        int tot = 0, cur = 0;
        while(cur <= n){
            int pos = lower_bound(a + cur + 1, a + n + 1, a[cur] + i) - a;
            if(pos == n + 1) break;
            tot++; cur = nxt[pos][1];
        }
        if(tot <= 1) continue;
        int res = (tot - 1) * (i + 1) + i;
        if(res > ans) ans = res, ansx = i, anstt = tot;
    }
    if(ans < count(s.begin(), s.end(), '1')){
        cout << (ans = count(s.begin(), s.end(), '1')) << '\n';
        for(int i=1;i<=ans;i++) cout << 1;
        cout << '\n';
        return 0;
    }
    cout << ans << '\n';
    for(int i=1;i<=anstt;i++){
        for(int j=1;j<=ansx;j++) cout << 0;
        if(i != anstt) cout << 1;
    }
    cout << '\n';
    return 0;
}

// Written by xiezheyuan