题解：CF2030B Minimise Oneness

Nottingham_Forest · 2024-10-21 19:36:58 · 题解

题目大意

有 t 组数据，每组数据输入一个整数 n，求出一个长度为 n 的01串 s，使得 | f(s)-g(s) | 最小，其中 f(s) 表示 s 的非空子序列中只包含 0 的序列的个数，g(s) 表示 s 的非空子序列中包含至少 1 个 1 的序列的个数，如有多解输出any。

思路

因为由于我们需要 | f(s)-g(s) | 最小，也就是说，要 f(s) 与 g(s) 尽量接近，所以前面一个 1，后面全是 0 的是最优的。因为这样的话，要想有至少一个 1，就必须要选择第一个 1，那么其它的 0 就选不选均可了，这样就变成了 n-1 个 0 组成的字符串有多少个子序列，这就是 g(s)。那么如果要全是 0，就是 n-1 个 0 组成的字符串有多少个非空子序列，这就是 f(s)。注意到 f(s) 与 g(s) 只差 1，因为 f(s) 不可选 1，但 g(s) 可以，就只差这一个，这样就是最优的。

CODE

#include<bits/stdc++.h>
using namespace std;
int t, n;
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        cout << 1;
        for (int i = 1; i < n; i++) {
            cout << 0;
        }
        cout << endl;//直接输出1个1，n-1个0，注意多测，换行
    }
    return 0;
}