HDU 5907：Find

HDU 5907：Find

Find Q

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/131072 K (Java/Others) Total Submission(s): 263    Accepted Submission(s): 148

Problem Description

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

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

S, which only contain the letter 'q'.

Sample Input

2 qoder quailtyqqq

Sample Output

1 7

题意：有一个小写字母组成的字符串S，输出S的所有仅包含字母'q'的连续子串的个数。

思路：只S中所有的仅包含q的段的长度，每一段能组成这种字串的个数都是一个等差数列的前n项和。

比如qqqaqq 长度3 2 子串个数 = 1+2+3 + 1+2 = 6 + 3 = 9

AC代码：

#include #include#include#includeusing namespace std;char c[110000];__int64 getsum(__int64 n) //等差数列前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--) { __int64 sum=0,s=0; gets(c); for(__int64 i=0; i<(__int64)strlen(c); i++) { if(c[i]=='q')s++; else { if(s)sum+=getsum(s); s=0; } } printf("%I64d\n",sum+getsum(s)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。