题解：P11084 [ROI 2019 Day 2] 灯串

xiezheyuan · 2024-10-02 20:14:33 · 题解

简要题意

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

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

思路

不妨先考虑 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