【Week12CSP模拟III-C】咕咕东学英语

算法

找规律

题目描述

对于一个只有AB两个字符组成的字符串，查找某一特定的子串

解题思路

由于最终的数据量较大，甚至所有子串都无法扫描一遍，所以，，采用找规律的方法。（求助同学得知）
不符合条件的只有两种情况，前面有单独字母后面一致如XYYYYYY，后面有单独字符前面一致如XXXXXXY。

代码

#include<iostream>
using namespace std;
const int maxn=300010;
int sum[maxn];
int main(){
    long long n;
    cin>>n;
    string s;
    cin>>s;
    int cnt=1;
    sum[cnt]=1;
    for(int i=1;i<n;i++){
        if(s[i]!=s[i-1]){
            cnt++;
        }
        sum[cnt]++;
    }
    long long ans=0;
    for(int i=2;i<cnt;i++)
        ans+=2*(sum[i]);
    if(cnt!=1)
        ans+=sum[1]+sum[cnt];
    ans=n*(n-1)/2-ans+(cnt-1);
    cout<<ans<<endl;
    //cout<<n*(n+1)/2<<endl;
    return 0;
}

题目总结

有些题目可能并没有算法，，应该打开思路，多找规律，，，。

题目原文

题目描述

咕咕东很聪明，但他最近不幸被来自宇宙的宇宙射线击中，遭到了降智打击，他的英语水平被归零了！这一切的始作俑者宇宙狗却毫不知情！
此时咕咕东碰到了一个好心人——TT，TT在吸猫之余教咕咕东学英语。今天TT打算教咕咕东字母A和字母B，TT给了咕咕东一个只有大写A、B组成的序列，让咕咕东分辨这些字母。
但是咕咕东的其他学科水平都还在，敏锐的咕咕东想出一个问题考考TT：咕咕东问TT这个字符串有多少个子串是Delicious的。
TT虽然会做这个问题，但是他吸完猫发现辉夜大小姐更新了，不想回答这个问题，并抛给了你，你能帮他解决这个问题吗？
Delicious定义：对于一个字符串，我们认为它是Delicious的当且仅当它的每一个字符都属于一个大于1的回文子串中。

输入描述

输入第一行一个正整数n，表示字符串长度
接下来一行，一个长度为n只由大写字母A、B构成的字符串。

输出描述

输出仅一行，表示符合题目要求的子串的个数。

样例输入

5
AABBB

样例输出

6

样例解释

对于该样例，符合条件的六个子串分别是：
s1-s2,s1-s4,s1-s5,s3-s5,s4-s5

数据组成