传送门：P10330 [UESTCPC 2024] 黑白珠串

更佳的阅读体验：洛谷 P10330 题解

简要题意：构造一个存在长度为 $x_i$ 且包含 $y_i$ 个 $\texttt{1}$ 的最短的 $\texttt{01}$ 串，并给出每个子串开始的位置。

可以想到，我们只需要构造一个前半段全是 $\texttt{1}$，后半段全是 $\texttt{0}$ 的字符串即可。这样，每个子串都在这个 $\texttt{01}$ 串中间，包含几个 $\texttt{1}$ 和几个 $\texttt{0}$，就可以使得这个 $\texttt{01}$ 串最短。

我们设 $\texttt{1}$ 的个数为 $m_1$，$\texttt{0}$ 的个数为 $m_0$，则有 $m_1 = \max \limits_{i = 1}^{k} y_i$，$m_0 = \max \limits_{i = 1}^{k} (x_i - y_i)$，满足第 $i$ 个条件的子串从 $m_1 - y_i$ 开始。

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int k, x[N], y[N], m0, m1;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> k;
    for (int i = 1; i <= k; ++i) {
        cin >> x[i] >> y[i];
        m0 = max(m0, x[i] - y[i]), m1 = max(m1, y[i]);
    } cout << m0 + m1 << '\n';
    for (int i = 1; i <= m1; ++i) cout << 1;
    for (int i = 1; i <= m0; ++i) cout << 0;
    cout << '\n';
    for (int i = 1; i <= k; ++i) cout << m1 - y[i] << '\n';
    return 0;
}