CF1508A Binary Literature

原题链接：A. Binary Literature

Tag：字符串、构造

题目描述

给一个 \(n\)，以及三个长度为 \(2n\) 的 \(01\) 字符串， 问是否可以构造一个长度不超过 \(3n\) 的字符串 \(S\)， 使得三个字符串中至少有两个是 \(S\) 的子序列。

分析

首先我们先思考一下，如果把两个字符串拼一起， 就是一个 \(4n\) 的字符串， 我们想办法从上面拿下来一个 \(n\) 就可以了。

在这个地方可以用鸽巢原理证一下， 三个字符串，一定有两个字符串同时满足 \(1\) 或 \(0\) 的个数大于等于 \(n\)。 所以我们只需要先找到两个满足这个条件的字符串， 随便构造一下就可以了。

总而言之先计数， 之后构造的思路是，比如我们找到的是两个 \(1\) 的个数大于等于 \(n\) 的。 那么我们先假设放了一整排的 \(1\)，然后按照两个字符串中哪个里面两个 \(1\) 中间的 \(0\) 比较多来放入 \(0\)。

代码实现

string work(string str1,string str2,char c,int n){
    string ans;
    vector<int> tmp1, tmp2;
    tmp1.push_back(-1);
    tmp2.push_back(-1);
    for (int i = 0; i < 2 * n; i++) {
        if (str1[i] == c) {
            tmp1.push_back(i);
        }
        if (str2[i] == c) {
            tmp2.push_back(i);
        }
    }
    tmp1.push_back(2 * n);
    tmp2.push_back(2 * n);
    for (int k = 1; k < max(tmp1.size(), tmp2.size()); k++) {
        if (k > 1) {
            ans += c;
        }
        int gap = 0;
        if (k < tmp1.size()) {
            gap = max(gap, tmp1[k] - tmp1[k - 1]);
        }
        if (k < tmp2.size()) {
            gap = max(gap, tmp2[k] - tmp2[k - 1]);
        }
        gap -= 1;
        if(c == '0'){
            string tmp (gap, '1');
            ans += tmp;
        }else{
            string tmp (gap, '0');
            ans += tmp;
        }
    }
    return ans;
}
void NeverSayNever() {
    int n; cin >> n;
    vector<string> vec(3);
    for(auto &x : vec) cin >> x;
    string ans;
    vector<string> tmp1;
    vector<string> tmp0;
    for(auto &str : vec){
        int cnt0 = 0,cnt1 = 0;
        for(auto &x : str){
            if(x == '1') cnt1++;
            else cnt0++;
        }
        if(cnt0 >= n){
            tmp0.push_back(str);
        }else{
            tmp1.push_back(str);
        }
    }
    if(tmp1.size() >= 2){
        cout << work(tmp1[0],tmp1[1],'1',n) << endl;
    }else{
        cout << work(tmp0[0],tmp0[1],'0',n) << endl;
    }
}

额外思考

感觉还是一个稍微有点智慧的构造， 可以用鸽巢原理证明是对的， 一道还可以但是无法引出我什么额外思考的题。

日志

本页面创建于 2024/6/27 00:23