acwing 4993 FEB | vegeone

vegeone
0%

acwing 4993 FEB

发表于 更新于 分类于 Valine：

题意

给定一个只含‘E’、’B’、’F’的字符串，F可以被修改为E或B，求最终转化为没有‘F’的字符串中含有“EE”、“BB”的子串个数和的各种情况

思路

通过找规律可以发现最终的结果是一段等差数列，然后列举F的情况：

  1. 首尾的F转变为E或B可以给答案增加0或1的贡献

  2. 对于中间的F，若两边相同，转变为E或B可以给答案增加0或2的贡献；若两边不同，可以给答案增加1的贡献，这种F可以直接当作E或者B来看
    所以可以得出结论，如果首尾有F，那公差为1，否则公差为2，因此我们只需贪心的求最小值和最大值即可。然后，对于一连串的F，最小值尽可能间隔着以EBEBEB的形式放，最大值尽可能以EEE或BBB的形式放：

  3. 对于情况1，最小值只要和最近的非F字符不同即可，可以做到贡献为0，最大值和最近的非F字符相同即可

  4. 对于情况2，最小值由于需要间隔放，考虑到F串的左右两边相同或否，需要根据奇偶判断贡献为1/0；最大值无论和左边相同还是和右边相同结果一样

    代码

    我先进行了预处理，将FFFEEBBBBEEE变成了3F2E4B3E这种形式，便于后续更好计算判断，然后对于非F串都设定贡献为 ，对于F变为E或B所产生的相邻处的新贡献都从F处所算得。
    代码如下：

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
#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>>n>>str;
    str=' '+str;
    bool f=true;
    for(int i=1;i<=n;++i){
        if(str[i]!='F')f=false;
    }
    if(f){
        cout<<n<<endl;
        for(int i=0;i<n;++i)cout<<i<<endl;
        return;
    }
    bool flag=true;
    if(str[1]=='F'||str[n]=='F')flag=false;
    int maxv=0,minv=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(t[0]=='F'){
        maxv=num[0];
    }else maxv=minv=num[0]-1;
    if(t[m-1]=='F'){
        maxv+=num[m-1];
    }else maxv+=num[m-1]-1,minv+=num[m-1]-1;
    for(int i=1;i<m-1;++i){
        if(t[i]=='F'){
            if(t[i-1]!=t[i+1]){
                maxv+=num[i];
                minv+=num[i]%2;
            }else {
                maxv+=num[i]+1;
                minv+=1-num[i]%2;
            }
        }else maxv+=num[i]-1,minv+=num[i]-1; 
    }
    // cerr<<maxv<<" "<<minv<<endl;
    if(flag){
        cout<<(maxv-minv+2)/2<<endl;
        for(int i=minv;i<=maxv;i+=2){
            cout<<i<<endl;
        }
    }else {
        cout<<maxv-minv+1<<endl;
        for(int i=minv;i<=maxv;++i){
            cout<<i<<endl;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)	solve();
    return 0;
}