4993. FEB

2024-01-02 08:38:24

题意

给定一个字符串,可能是 B,E,FF 可以变成 B 或者 E,相邻的两个字符是 B 或者 E 表示1的价值,字符串 S 的价值为所有价值之和

输出所有价值可能的数目,并且按照升序输出所有可能价值

数据范围

1≤N≤2×105

输入

4
BEEF

输出

2
1
2

代码

#include<bits/stdc++.h>

using namespace std;

int n;
string s;

int main()
{
    cin>>n>>s;
    
    if(s==string(n,'F'))
    {
        cout<<n<<endl;
        for(int i=0;i<n;i++)    cout<<i<<endl;
    }
    else
    {
        int l=0,r=n-1;
        while(s[l]=='F')    l++;
        while(s[r]=='F')    r--;
        
        int low=0,high=0;
        auto str=s;
        for(int i=l;i<=r;i++)
        {
            if(str[i]=='F')
            {
                if(str[i-1]=='B')   str[i]='E';
                else    str[i]='B';
            }
            if(i>l&&str[i]==str[i-1])   low++;
        }
        
        str=s;
        for(int i=l;i<=r;i++)
        {
            if(str[i]=='F') str[i]=str[i-1];
            if(i>l&&str[i]==str[i-1])   high++;
        }
        
        int ends=l+n-1-r,d=2;
        if(ends)    high+=ends,d=1;
        
        cout<<(high-low)/d+1<<endl;
        for(int i=low;i<=high;i+=d)
            cout<<i<<endl;
    }
    
    return 0;
}

想法

y总视频讲解52分钟,还真是难哈哈

主要不是因为算法难,而是因为需要细致的分类讨论和一些简单的数学技巧

首先说一下代码里面的这一行

    if(s==string(n,'F'))
    {
        cout<<n<<endl;
        for(int i=0;i<n;i++)    cout<<i<<endl;
    }

string 的使用表示的是构造一个长度为 n ,内容为 F 的字符串,这里表示的是如果该字符串全部为 F 的话,就有 n 种可能的价值的取值

假设一个字符串全是 F ,可以转变成任何一种可能的价值,假设F的个数是 k ,可以最多表示 k-1 个价值,最少可以表示0个价值,最大价值和最小价值之间的所有数字都可以取到

假设一段字符串的一端是 B(或者 E 都是同样的情况,这里取一种情况来分析。在左端或者右端也是同一种情况):最多可以取到 k 个价值(还是和前面一样,假设 F 的数目是 k 个),最大的价值就是全部取 B ,最小的价值是0,这种情况表示的是字符串左端或者右端的一部分,因为只有两端才会出现这一部分字符串一端有 B/E ,另一端是空的,最大价值和最小价值之间的所有数字都可以取到

假设一段字符串的一端是 B ,另一端也是 B(表示的情况是两端的字母相同,都是 E 也是相同的)最大的价值是 k+1,最小的价值是1或者0,假设 k+1 是奇数的话,最小价值是1,假设 k+1 是偶数的话,最小价值是0,最大价值和最小价值之间的所有数字不能都取到,只能从取到从最小价值开始,每次增加2,一直增加到最大价值,也就是一个以最小价值为首项,最大价值为末项,公差为2的等差数列,表示所有可能的价值的情况

假设一段字符一端是 B ,另一端是 E(左边还是右边不影响答案),最大价值为 k ,最小价值取决于 k 的奇偶性,假设 k 是奇数,最小价值是1,假设 k 是偶数,最小价值是0,也就是说所有可能的价值的情况是以最小价值为首项,公差为2,最大价值为末项的等差数列

公差为2的两个等差数列合并,可以得到一个以两个最小值的和为首项,两个最大值的和为末项,公差为2的新的等差数列

公差为1的两个等差数列合并乐意得到一个新的公差为1 的等差数列,以两个最小值的和为首项,两个最大值的和为末项

公差为1和公差为2的两个等差数列合并,得到一个公差为1 的新的等差数列,首项是两个最小值的和,末项是两个最大值的和

代码的意思是首先特判全是 F 的情况

然后剩下的情况考虑把整个字符串分成三个部分,左边部分,中间部分,右边部分,分界线是 l ,r, l的左边全是 Fr 的右边全是 F,表示的情况是,一端有 B/E ,另一端是空的情况,这种情况的公差是1

中间的部分,我们要求一次最大价值和一次最小价值,公差是2,其实除了特判的,有一端是空的情况,其他的情况都是公差是2,另外考虑奇偶性对于编写代码其实没有影响,所以其实难度是稍微降低了一些

因为涉及对字符串的修改,所以需要对字符串进行备份

求最小价值就是把区间内所有的 F 修改,使得下一个字符和当前字符不相等,如果相邻的两个字符相等就把 low 计数器增加1,low 表示的是最小价值

求最大价值是把区间内所有的 F 修改,使得下一个字符和当前字符相等,如果相邻的两个字符相等就把 high 计数器增加1,high 表示的是最大价值

把方差设定为2,然后用 ends表示两端 F 的总个数,左端是从0到 l-1 ,右端是从 r+1n-1,总个数是 (l-1-0+1)+(n-1-(r+1)+1)=l+(n-r-1)=l+n-r-1

假设两端有 F 表示的是方差为1的等差数列和方差为2的等差数列的合并,要把方差更新为1

然后输出个数和可能情况即可

等差数列的个数是末项减去首项,除以公差,加上1

算法学习的计划是看y总的课,刷 CFdiv 2 的 ==A,B,C ==的题目,看《算法竞赛进阶指南》这本书

文章来源:https://blog.csdn.net/L3102250566/article/details/135331946
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。