CF-1075-E. Majority Wins?

题目大意

题目总结：Majority Wins?

1. 目标

给定一个长度为 $n$ 的二进制字符串 $s$ ，通过最少总代价的操作将其最终转化为一个只包含字符 1 的字符串（即长度为 1 且内容为 1）。

2. 操作定义

在当前字符串中选择一段连续的子串 $g[l \dots r]$ ，计算其中 0 和 1 出现的次数：

如果某个字符出现的次数 不少于 另一个字符（即出现次数 $\ge$ 另一方），则可以用该字符替换掉整个子串。
操作代价：等于该子串的长度，即 $r - l + 1$ 。
你可以进行多次操作，每次操作后的字符串长度会缩短。

例如，字符串010010可以通过用成本为 $4$ 的操作将子串1001替换为1来在一次操作中转换为010；字符串1111可以通过在整个字符串上执行成本为 $4$ 的操作转换为1；字符串0100可以通过取子串100转换为00。

3. 输出要求

输出将字符串转化为 1 的最小总代价。
如果无法转化，则输出 1。

样例解释

样例 1 (0)：由于只有一个 0，无法通过任何操作产生 1。输出 1。
样例 2 (1)：已经是 1，无需操作。输出 0。
样例 4 (10)：选择子串 10（长度 2），其中 1 的数量（1个）不少于 0 的数量（1个），可替换为 1。代价为 2。
样例 5 (010)：
1. 选择子串 01 替换为 1，字符串变为 10，代价为 $2$ 。
2. 选择子串 10 替换为 1，代价为 $2$ 。
3. 总代价 $2 + 2 = 4$ 。
样例 6 (00111000)：
1. 选择子串 00111（1 占多数）替换为 1，字符串变为 1000，代价 $5$ 。
2. 选择子串 10（1 不少于 0）替换为 1，字符串变为 100，代价 $2$ 。
3. 再次对 10 进行操作变为 1，字符串变为 1，代价 $2$ 。
4. 总代价 $5 + 2 + 2 = 9$ 。

思路讲解

~~其实这道题目就是一个分类讨论，感觉放在 C 也没什么问题。~~

E was proposed as C, and C as B

不难发现，答案再大，不会超过 $n+3$ 。

然后直接输出 $n$ 的情况就是 1 的数量大于等于 0 的数量的时候。

输出 $n+1$ 是什么情况呢？首先 01 串首部或者尾部为 1 时，输出这个 $n+1$ 。

还有就是当存在一个位置，使得 $\text{suf}(1)≥\text{suf}(0)+1$ 数量的时候（这个是因为多容纳一个 0 也没事）（ $\text{suf}(x)$ 代表该位置后缀 $x$ 数量）。

同理可得 $\text{pre}(1)≥\text{pre}(0)+1$ 。

那么什么时候输出这个 $n+2$ 呢？当存在一个位置，使得 $\text{suf}(1)≥\text{suf}(0)$ 数量的时候（表示肯定有 0 嘛，那么我们不妨消掉一个，就可以回到上面一种情况）。

同理可得 $\text{pre}(1)≥\text{pre}(0)$ 。

其他情况，就输出 $n+3$ 。

然后，你忐忑地提交了，发现 WA 了，为什么呢？对拍！

1
2
3

1
10
0000110000

该样例也应该输出这个 $n+2$ ，但是我们输出了 $n+3$ ，这个是因为什么呢？

我们发现 ‘11' 这个东西非常特殊，可以压制两边的 0，你会发现，‘101’ 就不可以压制两边的 0 了。

因此，只要找到 ‘11' 那么答案不会大于 $n+2$ 。

1
2
3

if (s.find("11")!=string::npos) {
    ans=min(ans,N+2);
}

再次忐忑地提交，你发现竟然过了？

AC代码

https://codeforces.com/contest/2189/submission/360277668

源代码

/**
 * Problem: E. Majority Wins?
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/E
 * Created: 2026-01-27 23:48:36
 * Author: Gospel_rock
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    string s;
    cin>>s;
    if (s=="1") {
        cout<<0<<"\n";
        return;
    }
    ll cnt1=count(all(s),'1'),cnt0=count(all(s),'0');
    if (cnt1==0) {
        cout<<-1<<"\n";
        return;
    }
    if (cnt1>=cnt0) {
        cout<<N<<"\n";
        return;
    }
    if (s.front()=='1') {
        cout<<N+1<<"\n";
        return;
    }
    if (s.back()=='1') {
        cout<<N+1<<"\n";
        return;
    }
    s.insert(s.begin(),'#');
    vector<ll> pre_sum_1(N+2),suf_sum_1(N+2),pre_sum_0(N+2),suf_sum_0(N+2);
    for (int i=1;i<=N;++i) {
        pre_sum_1[i]=pre_sum_1[i-1]+(s[i]=='1');
        pre_sum_0[i]=pre_sum_0[i-1]+(s[i]=='0');
    }
    for (int i=N;i>=1;--i) {
        suf_sum_1[i]=suf_sum_1[i+1]+(s[i]=='1');
        suf_sum_0[i]=suf_sum_0[i+1]+(s[i]=='0');
    }
    if (suf_sum_1[2]>=suf_sum_0[2]) {
        cout<<N+1<<"\n";
        return;
    }
    if (pre_sum_1[N-1]>=pre_sum_0[N-1]) {
        cout<<N+1<<"\n";
        return;
    }
    ll ans=N+3;
    for (int i=1;i<=N;++i) {
        if (suf_sum_1[i]>=suf_sum_0[i]+1) {
            ans=min(ans,N+1);
        }
        if (pre_sum_1[i]>=pre_sum_0[i]+1) {
            ans=min(ans,N+1);
        }
        if (pre_sum_1[i]>=pre_sum_0[i]) {
            ans=min(ans,N+2);
        }
        if (suf_sum_1[i]>=suf_sum_0[i]) {
            ans=min(ans,N+2);
        }
    }
    if (s.find("11")!=string::npos) {
        ans=min(ans,N+2);
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

*/

暴力程序

/**
 * Problem: E. Majority Wins?
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/E
 * Created: 2026-01-28 14:48:13
 * Author: Gospel_rock
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    string s;
    cin>>s;
    if (count(all(s),'1')==0) {
        cout<<-1<<"\n";
        return;
    }
    ll ans=N+3;
    auto dfs=[&](auto && self,string str,ll consume,ll phase) {
        if (phase>=5) {
            return;
        }
        if (consume>=ans) {
            return;
        }
        if (str=="1") {
            ans=min(ans,consume);
            return;
        }
        if (str.size()<=1) {
            return;
        }
        for (int i=0;i<str.size();++i) {
            for (int j=i;j<str.size();++j) {
                ll cnt1=count(str.begin()+i,str.begin()+j+1,'1');
                ll cnt0=count(str.begin()+i,str.begin()+j+1,'0');
                ll len=j-i+1;
                if (cnt1>=cnt0) {
                    string to_str=string(str.begin(),str.begin()+i)+"1"+string(str.begin()+j+1,str.end());
                    self(self,to_str,consume+len,phase+1);
                }
                if (cnt0>=cnt1) {
                    string to_str=string(str.begin(),str.begin()+i)+"0"+string(str.begin()+j+1,str.end());
                    self(self,to_str,consume+len,phase+1);
                }
            }
        }
    };
    dfs(dfs,s,0,1);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
1
2
10

*/

数据生成器

/**
 * Problem: E. Majority Wins?
 * Contest: Codeforces Round 1075 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2189/problem/E
 * Created: 2026-01-28 15:06:38
 * Author: Gospel_rock
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void Solve() {
    // ll N;
    // cin >> N;
    ll N=uniform_int_distribution<ll>(3,10)(rng);
    cout<<1<<"\n";
    cout<<N<<"\n";
    for (int i=1;i<=N;++i) {
        if (bernoulli_distribution(0.7)(rng)) {
            cout<<0;
        }else {
            cout<<1;
        }
        // cout<<uniform_int_distribution<ll>(0,1)(rng);
    }
    cout<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    // cin >> lT;
    // while(lT--)
        Solve();
    return 0;
}

/*

*/

Znzryb's Blog