Young theoretical computer scientist Fxx get a string which contains lowercase letters only.
The string S contains n lowercase letters S1S2…Sn.Now Fxx wants to know how many three tuple (i,j,k) there are which can meet the following conditions:
1、i,j,k are adjacent into a geometric sequence.
2、Si=’y’,Sj=’r’,Sk=’x’.
3.Either j|i or j|k
Input In the first line, there is an integer T(1≤T≤100) indicating the number of test cases.
T lines follow, each line contains a string, which contains only lowercase letters.(The length of string will not exceed 10000).
Output For each case, output the answer.
Sample Input 2 xyyrxx yyrrxxxxx
Sample Output 0 2
Source BestCoder Round #89
題意：給你一個字符串，問你有多少個三元組i，j，k，滿足以下條件 1.i,j,k構成等比數列 2.Si=’y’,Sj=’r’,Sk=’x’. 3.i,j,k都是整數 解題思路：我剛開始是想枚舉i的位置，然后直接暴力做。但是這樣做會超時，我們知道，等比數列的增長很快，所以我們可以枚舉公比和i的位置。
#include<bits/stdc++.h>using namespace std;const int maxn = 1e4 + 10;char s[maxn];int main(){ int T; scanf("%d",&T); while(T--) { scanf("%s",s); int len = strlen(s); int ans = 0; for(int i = 0; i < len; i++) { for(int q = 2;;q++) { int a = i + 1; int b = a*q; int c = b*q; if(c > len) break; if(s[a - 1] == 'y'&&s[b - 1] == 'r'&&s[c - 1] == 'x') ans++; if(s[a - 1] == 'x'&&s[b - 1] == 'r'&&s[c - 1] == 'y') ans++; } }新聞熱點
疑難解答
