CF-1075-E. Majority Wins? · znzryb
## 题目大意
### 题目总结：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$。
1. 选择子串 `10` 替换为 `1`，代价为 $2$。
1. 总代价 $2 + 2 = 4$。
- **样例 6 (****`00111000`****)**：
1. 选择子串 `00111`（`1` 占多数）替换为 `1`，字符串变为 `1000`，代价 $5$。
1. 选择子串 `10`（`1` 不少于 `0`）替换为 `1`，字符串变为 `100`，代价 $2$。
1. 再次对 `10` 进行操作变为 `1`，字符串变为 `1`，代价 $2$。
1. 总代价 $5 + 2 + 2 = 9$。
## 思路讲解
~~其实这道题目就是一个分类讨论，感觉放在 C 也没什么问题。~~
> 2. 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 了，为什么呢？对拍！
```cpp
1
10
0000110000
```
该样例也应该输出这个 $n+2$，但是我们输出了 $n+3$，这个是因为什么呢？
我们发现 `‘11'` 这个东西非常特殊，可以压制两边的 0，你会发现，`‘101’` 就不可以压制两边的 0 了。
因此，只要找到 `‘11'` 那么答案不会大于 $n+2$。
```cpp
if (s.find("11")!=string::npos) {
ans=min(ans,N+2);
}
```
再次忐忑地提交，你发现竟然过了？
## AC代码
AC
[https://codeforces.com/contest/2189/submission/360277668](https://codeforces.com/contest/2189/submission/360277668)
::: 源代码
```cpp
/**
* 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;
}
/*
*/
```
:::
::: 暴力程序
```cpp
/**
* 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
*/
```
:::
::: 数据生成器
```cpp
/**
* 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;
}
/*
*/
```
:::
## 心路历程（WA，TLE，MLE……）