写个标题吧
CFGym 103409G Occupy the Cities
题意：有一个长为n < 1e6的01字符串，初始时保证至少有一个1。对于每一轮，每个1都可以向左或向右扩展1个，将其变成1。
问最少多少个回合，可以使所有0变为1。
思路：
首先清楚一个点，从第二轮开始后，这个1串的扩展就都是向左向右各扩展一个了。
那么最开始我们将0串分类，最左边的0串记为l1,中间被两个1夹着的0串记为l2,最右边的0串记为l3。
那么ans=max(l1,l2/2,l3).我们这样求出来的ans并不一定满足，因为这种做法是假设从第二轮开始的。
那么我们最多再加上1s，就可以符合。所以答案只可能为ans或ans+1。
都到了这一步了，我当时比赛脑子怎么就瓦特了？这个时候直接检验答案是否满足就行了啊！！！我还在想什么怎么决定
每个初始1是往左还是往右扩展，晕晕。
检验答案的话，很简单，从最左边开始模拟就行了。
代码优化：因为最左边和最右边的0串是没有被两个1夹着的，所以我么可以在最左边和最右边再加个1，使数据的结构统一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e6+11;
char a[maxn];
ll n;
ll check(ll t){
ll l=0;
for(ll r=1;r<=n+1;r++){
if(r==n+1){
if(l>=n) return 1;
else return 0;
}
if(a[r]=='1'){
ll l1=r-l-1;
if(t>l1){
l=r+t;
}
if(t==l1){
if(t>=1) l=r+t-1;
else l=r;
}
if(t<l1){
return 0;
}
}
}
}
void solve(){
ll l=0;
ll ans=0;
a[n+1]='1';
for(ll r=1;r<=n+1;r++){
if(a[r]=='1'){
if(l==0){
ans=max(ans,r-l-1);
l=r;
continue;
}
if(r==n+1){
ans=max(ans,r-l-1);
continue;
}
ans=max(ans,(r-l)/2);
l=r;
}
}
if(check(ans)){
cout<<ans<<endl;return ;
}
cout<<ans+1<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll ca;cin>>ca;
while(ca--){
cin>>n;
for(ll i=1;i<=n;i++){
cin>>a[i];
}
solve();
}
return 0;
}
|