acwing 4966 填充 | vegeone

vegeone
0%

acwing 4966 填充

发表于 更新于 分类于 Valine：

题意

给定一个只含‘0’、’1’、’?’的字符串，？可以被修改为0或1，求最终转化为没有‘？’的字符串中含有“00”、“1”的最多不重叠子串个数

思路

和前一题FEBacwing 4993 FEB很像，甚至都不需要找规律，就是纯粹的分类讨论。

？尽可能去把相邻的奇数连续串弥补即可

代码

我先进行了预处理，将000????11100变成了304?3120这种形式(3个0四个?三个1两个0)，便于后续更好计算判断，然后对于每个?串，先满足前面的连续穿个数为偶数，再满足后续的连续串个数为偶数。
代码如下：

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
void solve()
{
    int n;
    string str;
    cin>>str;
    n=str.size();
    str=' '+str;
    int sum=0;
    vector<int>num;
    string t="";
    int befloc=1;
    for(int i=1;i<=n;++i){
        if(str[i]!=str[befloc]){
            num.push_back(i-befloc);
            t+=str[befloc];
            befloc=i;
        }
    }
    num.push_back(n+1-befloc);
    t+=str[befloc];
    int m=num.size();
    if(m==1){
        cout<<num[0]/2<<endl;
        return;
    }
    vector<int>f(m);
    if(t[0]=='?'){
        if(num[0]%2!=num[1]%2){
            if(num[0]%2){
                sum+=(num[0]-1)/2;
                num[1]++;
            }else {
                sum+=num[0]/2;
            }
        }else {
            sum+=(num[0]+num[0]%2)/2;
            num[1]-=num[0]%2;
        }
    }else sum=num[0]/2;
    if(t[m-1]=='?'){
        sum+=num[m-1]/2+(num[m-1]%2?num[m-2]%2:0);
        
    }else sum+=num[m-1]/2;
    
    for(int i=1;i<m-1;++i){
        // cerr<<i<<" "<<sum<<endl;
        if(t[i]=='?'){
            if(num[i-1]%2){
                num[i]--;
                sum++;
            }
            if(num[i]%2!=num[i+1]%2){
                if(num[i]%2){
                    sum+=(num[i]-1)/2;
                    num[i+1]++;
                }else {
                    sum+=num[i]/2;
                }
            }else {
                sum+=(num[i]+num[i]%2)/2;
                num[i+1]-=num[i]%2;
            }
        }else sum+=num[i]/2; 
    }
    cout<<sum<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)	solve();
    return 0;
}