题解 | #小红的大小判断#(官方题解详细版)

alt

思路如下

对于本题翻转的情况

  • 情况1:连通块数量多1 左边界与左边界左边的一样 000111 翻转的时候就会多一个 001000
  • 情况2:连通块数量少1 左边界与左边界的不一样 0011100 翻转的时候就会少一个 0000011
  • 情况3:连通块数量不变 仅有整个字符串两侧的翻转不变 所以要想通过情况3不变 只有两个边缘的情况 所以需要通过枚举边界寻找范围 alt
  • 如图
  • 在枚举右边界的过程中
  • 计算出此时的右边界左侧相同的数量left_qk1
  • 左侧一共有i个 (i的范围是1开始不是0 所以忽略了最左侧)(最右侧也是一样忽略掉)
  • 那么不相同的就是i-left_qk1个
  • 两侧一个加一个减 就是不变
#define int long long //最好还是开一下long long 数据很大
using namespace std;
signed main(){
    string s;
    cin>>s;
    int count1=1;
    int left_qk1=0;
    for(int i=1;i<s.size()-1;i++){
        //以i为右边界 顺便遍历左边界
        if(s[i]!=s[i-1]) left_qk1++;//左边界不相同的情况 遍历范围1-i
        if(s[i]!=s[i+1]){
            //右侧边界不相同的情况 那么此时的总数应该取决于左侧边界相同的情况有多少
            count1+=i-left_qk1;
        }
        else{
            //右侧边界相同的情况 对应左侧边界不相同的情况
            count1+=left_qk1;
        }
    }
    cout<<count1;
    return 0;
}
//考试未发现的关键性质 
//区间内翻转并不会影响区间内相邻连通块数量,仅会影响区间边缘的连通块数量

//对于本题翻转的情况 
//情况1:连通块数量多1 左边界与左边界左边的一样 000111 翻转的时候就会多一个 001000
//情况2:连通块数量少1 左边界与左边界的不一样 0011100 翻转的时候就会少一个 0000011
//情况3:连通块数量不变 仅有整个字符串两侧的翻转不变 所以要想通过情况3不变 只有两个边缘的情况

//考试时思路:
//0011000   1 2 3     0011000
//分析 先求一共多少个颜色块 根据颜色块遍历 
//所有个颜色块全覆盖 1  颜色块 不能两两之间全选   相邻的颜色块之间 每个颜色块可以变色 4 反向 最边缘的不行
//要留一个
//遍历只有一个的 只要是颜色块长度大于1的 都有n个行  最边上的是n-1 所以是5

本解学习的kendieer的题解

如有问题 感谢指正

全部评论

相关推荐

评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务