Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)

问题描述

Byteasar迷恋上了’q’这个字母。

在他眼前有一个小写字母组成的字符串SS，他想找出SS的所有仅包含字母’q’的连续子串。但是这个字符串实在是太长了，你能写个程序帮助他吗？

输入描述

输入的第一行包含一个正整数T(1\leq T\leq10)T(1≤T≤10)，表示测试数据的组数。

对于每组数据，包含一行一个小写字母组成字符串SS，保证SS的长度不超过100000100000。

输出描述

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

输入样例

2

qoder

quailtyqqq

输出样例

1

7

【题解】



连续的子串是指a[x],a[x+1]..a[y];这样的东西。

x不同，或y不同都是不同的子串。

可以证明。一个长度为l的连续q，可以累加答案1+2+…+l;

注意用long long；

一堆学长看到答案为int类型就疯狂hack…

#include <cstdio>

#include <cstring>

int T,len;

char s[101000];

long long f(long long n)

{

    return (1 + n)*n / 2;

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    scanf("%d", &T);

    while (T--)

    {

        long long temp = 0;

        scanf("%s", s);

        len = strlen(s);

        int i = 0;

        while (i <= len - 1)

        {

            int j = i;

            if (s[i] == 'q')

            {

                while (j+1 <= len-1 && s[j + 1] == 'q')

                    j++;

                long long k = j - i + 1;

                temp += f(k);

            }

            i = j + 1;

        }

        printf("%I64d\n", temp);

    }

    return 0;

}