P9687 题解

· · 题解

题意：构造一个长度为 n 的 01 字符串 S，此字符串有以下两点要求：

  1. 对于字符串中所有的 p 个不在字符串两端的 0，它们左边和右边的一个字符为 1。
  2. 使构造出的字符串的字典序最小。

先设 S 完全由 0 构成。
对于点 1，设一变量 j，为 S 中的字符序号。j 赋初始值为 1（因为“不在字符串两端”）。将 S 中的字符 S_j 左边和右边的元素改为 1，（即 S_{j-1}\leftarrow 1,S_{j+1}\leftarrow 1），然后将 j 的值加上 2，继续修改 S_{j+2} 左右两个元素，如此循环 p 次，此时所构造的 S 中，每两个 1 之间都由一个 0 隔开。

对于点 2，仅需倒序输出所构造的 S 即可。因为 S 是从开头开始构造的，所以 S_{0} 一定为 1，若 p 远小于 n，则 S 的后半段大部分都是 0，此时倒序字符串的字典序是小于原字符串的，而且符合以上两点要求。也就是说，倒序字符串的字典序小于等于原字符串，且符合要求，所以倒序输出即可。

那如何判断输出 -1 呢？若 2p\ge n，则输出 -1，否则输出所构造的 S。因为每两个 1 之间都由一个 0 隔开，所以从第一个 1 到最后一个 1 的长度就为 2p+1，如果 2p\ge n，则 2p+1 是一定大于 n 的，构造出的 S 长度须小于等于 n 才合法，所以此时就输出 -1。

#include <bits/stdc++.h>

using namespace std;

const int N = 114514;

int t, n, p, s[N];

int main() {
    cin >> t;
    while (t--) {
        int j = 1;
        cin >> n >> p;
        if (2 * p >= n) {
            cout << -1 << '\n';
            continue;
        }
        else {
            for (int i = 0; i < n; ++i) s[i] = 0;
            for (int i = 0; i < p; ++i) {
                    s[j + 1] = 1;
                    s[j - 1] = 1;
                    j += 2;
            }
            for (int i = n - 1; ~i; --i) {
                cout << s[i];
            }
            cout << '\n';
        }
    }
    return 0;
}