P10330 黑白珠串

lucky_Mrzhao · 2024-04-10 07:33:00 · 题解

题目分析：

这一道题其实就是一道构造题。

问一条珠串，要满足有至少一个子串满足题目要求，并输出相应子串的位置。其实就是在构造一条 01 序列。

那该如何构造呢?

分析一下其实可以发现，我们可以将所有的 1 放在前面，所有的 0 放在后面，这样到达一定数量的时候，一定能满足所有条件。

比如以下样例

3
3 1
3 2
2 0

当珠串为 1100 时，就一定会满足所有要求。

那我们又要如何保证珠子数量最少时，又能满足所有条件呢？

再次看到上面的这个样例，当 b_i=0 的时候，说明这一段中一定不会有黑珠。那么 这一串中一定要有 a_i 个白珠，就直接让

如果这一段中有黑珠，那么一定要保证有b数组中的最大值，就是

但是也要保证白珠数量要足够为黑珠补位，就是

其实这个珠串已经构造好了，珠串长度就是 need_0+need_1 个。

那我们该如何输出方案呢？我们以珠串1的结尾为断点，那么其实要满足条件，就只须用从断点处向左移 b_i 格，又因为珠串从 0 开始，减掉任意一个 b_i 时一定是保证会向右错位，刚好能跟序列节点对上。

AC code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[100005],b[100005];
signed main(){
    cin >> n;
    int need1 = -1,need0 = -1;
    for(int i = 1;i <= n;i++){
        cin >> a[i] >> b[i];
        if(b[i]==0) need0 = max(need0,a[i]);
        else{
            need1 = max(need1,b[i]);
            need0 = max(need0,a[i]-b[i]);
        }
    }
    cout << need0 + need1 << endl;
    for(int i = 1;i <= need1;i++) cout << 1;
    for(int i = 1;i <= need0;i++) cout << 0;
    cout << endl;
    for(int i = 1;i <= n;i++){
        cout << need1 - b[i] << endl;
    }
}