HDU 5907-Find Q （全是q的子串）

ゝ一纸荒年。 2022-07-16 07:48 134阅读 0赞

# Find Q #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)  
Total Submission(s): 593 Accepted Submission(s): 289**

Problem Description

Byteasar is addicted to the English letter 'q'. Now he comes across a string  *S* consisting of lowercase English letters.  
  
He wants to find all the continous substrings of  *S*, which only contain the letter 'q'. But this string is really really long, so could you please write a program to help him?

Input

The first line of the input contains an integer  *T*(1≤*T*≤10), denoting the number of test cases.  
  
In each test case, there is a string  *S*, it is guaranteed that  *S* only contains lowercase letters and the length of  *S* is no more than  100000.  .

Output

For each test case, print a line with an integer, denoting the number of continous substrings of  *S*, which only contain the letter 'q'.

Sample Input

2
    qoder
    quailtyqqq

Sample Output

1
    7

Source

[BestCoder Round \#88][BestCoder Round _88]

Recommend

wange2014 | We have carefully selected several similar problems for you: [5932][] [5931][] [5930][] [5929][] [5928][]

题目意思：

求给定的S串中一共有多少个全是q的子串。

解题思路：

求出每个位置往左能延伸多少个q即可。

时间复杂度O(n)*O*(*n*)。

（亲手造出的丑陋无比的代码，1A还掉rating……诶/(ㄒoㄒ)/~~）

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    string s;//输入的字符串
    long long q[10000];//保存每个连续p数据块中p的个数
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n;
        cin>>n;
        for(int j=0; j<n; ++j)
        {
            cin>>s;
            long long len=0,Max=0,k=0,tmp=0;
            for(int i=0; i<s.size(); ++i)
            {
                if(s[i]=='q')//当前是p
                {
                    if(s[i]==s[i+1])//连续相同
                    {
                        ++len;
                        tmp=len;
                    }
                    else//特判p为首位的情况
                    {
                        if(tmp==0) len=1;
                        else
                        {
                            ++len;
                            goto A;
                        }
                    }
                }
                else//当前不是p
                {
    A:
                    Max=max(len,Max);
                    if(Max!=0)
                        q[k++]=Max;
                    len=Max=tmp=0;
                }
            }
            long long ans=0;//注意要用ll才能保证不溢出
            for(int i=0; i<k; ++i)
            {
                //cout<<q[i]<<endl;
                ans+=((1+q[i])*q[i]/2);
            }
            cout<<ans<<endl;
        }
        return 0;
    }
    /*
    3
    qoder
    quailtyqqq
    qqqq
    */

[BestCoder Round _88]: http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2388&source=1&searchmode=source
[5932]: http://acm.hdu.edu.cn/showproblem.php?pid=5932
[5931]: http://acm.hdu.edu.cn/showproblem.php?pid=5931
[5930]: http://acm.hdu.edu.cn/showproblem.php?pid=5930
[5929]: http://acm.hdu.edu.cn/showproblem.php?pid=5929
[5928]: http://acm.hdu.edu.cn/showproblem.php?pid=5928