链接:http://acm./showproblem.php?pid=5944
题意:给定一个字符串s,求有多少个三元组(i,j,k)满足i,j,k是等比数列且s[i]=='y'&&s[j]=='r'&&s[k]=='x'。
分析:暴力枚举公比,然后枚举起点位置,注意逆序。
代码:
#include<map>#include<set>#include<stack>#include<cmath>#include<queue>#include<bitset>#include<math.h>#include<vector>#include<string>#include<stdio.h>#include<cstring>#include<iostream>#include<algorithm>#pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef double db;typedef long long ll;typedef unsigned int uint;typedef unsigned long long ull;const db eps=1e-5;const int N=1e4+10;const int M=1e5+10;const ll MOD=1000000007;const int mod=1000000007;const int MAX=1000000010;const double pi=acos(-1.0);char s[N];int main(){int i,j,T,len,ans;scanf("%d", &T);while (T--) {scanf("%s", s);ans=0;len=strlen(s);for (i=2;i*i<=len;i++)for (j=1;j*i*i<=len;j++)if (s[j-1]=='y'&&s[j*i-1]=='r'&&s[j*i*i-1]=='x') ans++;for (i=2;i*i<=len;i++)for (j=1;j<=len;j++)if (j%(i*i)==0&&s[j-1]=='y'&&s[j/i-1]=='r'&&s[j/i/i-1]=='x') ans++;printf("%d\n", ans);}return 0;}