#include <bits/stdc++.h> using namespace std; using gg=long long; int main() { ios::sync_with_stdio(false); cin.tie(0); string a; getline(cin,a); int cnt=0; for(int i=0;i<a.size();i++) { if(a[i]=='P') { for(int j=i+1;j<a.size();j++) { if(a[j]=='A') { for(int k=j+1;k<a.size();k++) { if(a[k]=='T') cnt++; } } } } } cout<<cnt%1000000007; return 0; }
暴力枚举显然会超时。
我们可以观察到,每一个单词A能组成的pat的数量是其左边的p数量乘以其右边的t数量。
这样我们就统计每一个位置左边p数量及右边t数量即可。
#include <bits/stdc++.h> using namespace std; using gg=long long; int main() { ios::sync_with_stdio(false); cin.tie(0); string a; getline(cin,a); gg cnt=0; vector<gg>p(a.size()),t(a.size()); for(int i=1;i<a.size();i++) { p[i]=p[i-1]+(a[i-1]=='P'); } for(int i=a.size()-2;i>=0;i--) { t[i]=t[i+1]+(a[i+1]=='T'); } for(int i=0;i<a.size();i++) { if(a[i]=='A') { cnt=(cnt+p[i]*t[i])%1000000007; } } cout<<cnt; return 0; }