当前位置：首页 > article >正文

Codeforces Round 979 (Div. 2) B. Minimise Oneness

article 2024/10/20 20:50:38

题目链接：题目

大意：

构造长度为 $n$ 的01字符串，使得全为零的子序列和至少有一个1的子序列的数量之差的绝对值最小。

思路：

很明显，所有子序列中不是全为0就是至少有一个1，所以算出子序列总数，再让全为0的子序列数量接近它的一半。子序列不要求相邻，只要求相对位置不变，而在这个题目中又只需要考虑0，那么只用看0的个数。
由杨辉三角发现，长度为 $n$ 的子序列总数就是第 $n$ 层杨辉三角之和减一，而长度加一，子序列总数至少翻倍，所以0的个数为n-1就行了。

代码：

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pair<int, int>
#define vec vector

void solve(){   
    int n;
    cin >> n;
    string ans;
    for(int i = 0; i < n - 1; i++){
        ans.push_back('0');
    }
    ans.push_back('1');
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}