D. AB-string——CF1238D

小灰灰 2023-06-06 10:35 24阅读 0赞

https://codeforces.com/problemset/problem/1238/D  
思路：  
1、每个字符存在回文串的最地条件是： AA ， BB， ABA ， BAB 这几个。  
对于某个子串的 是 good 串，那么这个子串的构成就是上述这些串“拼接”起来（ 这里的拼接 是可以重合的那种 ， 举个例子 AA 和ABA ——> AABA, 是这样）。

2、good串分为 三类：  
第一类：AA…（或BB…）；  
第二类： AABB；  
第三类：AABBABB… 这一类就是剩下的

第一类： 这一类的特点就是组成字符都相同 。  
第二类：这类特点是 分两段不同的  
第三类：这一类就是剩下的

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 3e5;
    #define ll long long
    string str;
    ll a[maxn];// 转换数组
    ll sum[maxn];//前缀和
    int main()
    { 
        ios_base::sync_with_stdio(false);
        ll n;
        cin>>n;
        cin>>str;
        
        int len = 0;//a 数组的大小
        // 转换 为int数组 过程
        int cnt = 1;
        for(int i = 1;i <(int)str.size();i++)
        { 
            if(str[i] == str[i-1]) cnt++;
            else
            { 
                a[len++] = cnt;
                cnt = 1;
            }
        }
        a[len++] = cnt;
       
        // 求前缀和过程
        sum[0] = a[0];
        for(int i = 1;i < n;i++)
        { 
            sum[i] = sum[i-1]+a[i];
        }
    
        // 求答案过程
        ll ans = 0;
        for(int l = 0;l < len;l++)// 以l类型开口的 good子串
        { 
    
            ans+= (a[l]-1 +1)*(a[l]-1)/2;// ①AAA形式 的求法 ：等差数列
            if(l+1 < len)ans+= (a[l]-1)*(a[l+1]-1);// AABB形式 的求法： 组合
            if(l +2 <len)ans+=a[l]*( sum[len-1]- sum[l+1]);// AABBAAB。。 形式 求法：组合
    
        }
    
        cout<<ans;
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，24人围观）

还没有评论，来说两句吧...

相关阅读

相关格式化之 %d，%2d， %02d

在Java中，`%d`，`%2d` 和 `%02d` 都用于格式化整数： 1. `%d`： `%d` 是格式化整数的基本占位符。当使用 `%d` 格式化整数

矫情吗；*/ 2024年02月21日 10:13/ 0 赞/ 60 阅读

相关 d954(D9546)

恩施到汉口的D954途经站时刻列表有吗？恩施到汉口的D954这趟动车的开车时间12:19，预计到达时间15:49，总预计用时03:30。 ![d954(D9546)\

矫情吗；*/ 2023年09月26日 12:36/ 0 赞/ 52 阅读

相关 d313(d3131)

动车D313从苏州哪里？动车D313从苏州哪里坐苏州火车南站就是苏州新建的动车站 ![d313(d3131)\_d313(d3131)][d313_d3131_d3

快来打我*/ 2023年09月26日 12:36/ 0 赞/ 107 阅读

相关 d1833(d1833时刻表)

D一二聚体正常值是多少血浆D一二聚体正常值是血浆D-二聚体含量小于0.5mg/L。血浆D-二聚体是纤维蛋白降解后的特异性产物，测定血浆D-二聚体可以判断纤维蛋白是否已经

Bertha 。/ 2023年09月26日 12:35/ 0 赞/ 136 阅读

相关 D. AB-string——CF1238D

https://codeforces.com/problemset/problem/1238/D 思路： 1、每个字符存在回文串的最地条件是： AA ， BB， ABA

小灰灰/ 2023年06月06日 10:35/ 0 赞/ 25 阅读

相关 D2D项目开发

总结-模块-页面效率除了 undefined 其他均可!! 案1 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGV

忘是亡心i/ 2022年12月23日 07:03/ 0 赞/ 214 阅读

相关 D2D

D2D: Device-to-Device即是设备到设备的通信。 1.认识D2D 基于蜂窝网络的D2D通信，或称为邻近服务（Proximity Service,ProS

不念不忘少年蓝@/ 2022年06月13日 13:42/ 0 赞/ 218 阅读

相关 d3d 矩阵记录

//单位矩阵:任何矩阵与它相乘都等于自己 void CMatrix4_4::Identity() { memset(this,0,sizeof

ゝ一纸荒年。/ 2022年06月02日 10:35/ 0 赞/ 211 阅读

相关 c++ %d-%d-%d %d:%d:%d 转unix时间戳

最近的业务，需要用到string转UNIX时间戳，记录一下实现过程 c++代码如下： \include <stdio.h> \include <memory.h

淩亂°似流年/ 2022年04月10日 01:23/ 0 赞/ 210 阅读

相关 3D-3D:ICP

3D-3D:ICP 1. ICP算法 2. SVD方法 3.非线性优化方法 1. ICP算法 2D-2D问题是通过已知的2D图像坐标点对来求解图

素颜马尾好姑娘i/ 2022年03月12日 02:52/ 0 赞/ 382 阅读