内存:128  时间:1

题目描述

小千名字的首字母是 ‘q’,他一直很喜欢这个字母。

某天,小艾说:“既然你这么喜欢 ‘q’ 这个字母,那就在我给出的一个由小写字母组成的字符串中找出所有仅包含字母 ‘q’ 的连续子串的个数吧!”

小千:“这当然难不倒我,不过这么好的机会当然要留给其他人咯!”

这道题能难倒你么?写一个程序试试吧!

输入

输入的第一行包含一个正整数

T(1T10)

,表示测试数据的组数。

对于每组数据,包含一行一个小写字母组成字符串,保证

SS

的长度不超过

10000

输出

对于每组数据,输出一行一个整数,即仅包含字母’q’的连续子串的个数。

样例输入

2
qoder
quailtyqqq

样例输出

1
7

提示

假如字符串为qqq时,我们给每一个字母分一个下标0、1、2。

那么由 ‘q’ 组成的字串便是0、1、2、01、012、12,总共六种情况。

代码如下

#include <iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
typedef long long LL;
char c[110000];
LL getsum(LL n)
{
    if(n%2==0)return n/2*(1+n);
    else return (1+n)/2*n;
}
int main()
{
    int n;
    scanf("%d%*c",&n);
    while(n--)
    {
        LL sum=0,s=0;
        gets(c);
        for(LL i=0; i<(LL)strlen(c); i++)
        {
            if(c[i]=='q')s++;
            else
            {
                if(s)sum+=getsum(s);
                s=0;
            }
        }
        printf("%lld\n",sum+getsum(s));
    }
    return 0;
}

代码来源于互联网,仅供参考!