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++; } } PRintf("%d/n",ans); } return 0;}新闻热点
疑难解答
