https://pintia.cn/problem-sets/994805260223102976/problems/994805282389999616
主要注意超时问题
#include <iostream> using namespace std; int main(){ long long count = 0, subp = 0, subt = 0, nump = 0, numt = 0, cntT = 0, cntP = 0; string s; cin >> s; for(int i = 0; i < s.size(); i++) if(s[i] == 'T') cntT++; for(int i = 0; i < s.size(); i++){ if(s[i] == 'A'){ for(int j = i-1; j >= subp; j--) if(s[j] == 'P') cntP++; for(int j = subt; j < i; j++) if(s[j] == 'T') cntT--; count += cntT*cntP; subt = subp = i; } } cout << count00000007; return 0; }解2
#include <iostream> #include <string> using namespace std; struct A{ int P = 0; int T = 0; }; A node[100010]; int main(){ string s; cin >> s; int len = s.size(), pnum = 0, tnum = 0; for(int i = 0, w = len -1; i < len && w >= 0; i++, w--){ if(s[i] == 'A') node[i].P = pnum; else if(s[i] == 'P') pnum++; if(s[w] == 'A') node[w].T = tnum; else if(s[w] == 'T') tnum++; } long long result = 0; for(int i = 0; i < len ; ++i) result += node[i].P * node[i].T; cout << result % 1000000007 ; return 0; }