题目：1040 有几个PAT

思路

原先思路自己也知道肯定会超时，还是写了，毕竟时间复杂度O(n³)，比较直观找到每个PA，查看后续有多少个T，求和。正确思路：看了下大佬的思路，是看每个A前的P和后的T的积，豁然开朗，修改了自己的代码。全部通过。

AC代码

#include <iostream> using namespace std; int main(){ string s; cin >> s; int P[100000] = {0},T[100000] = {0}; int no[2]={0};//记录P、T数量 for(int i=0;i<s.length();i++){ if(s[i] == 'P') ++no[0]; if(s[i] == 'A') { P[i] = no[0];//记录前方P的数量 T[i] = no[1];//前方T的数量 } if(s[i] == 'T') ++no[1]; } int sum = 0; for(int i=0;i<s.length();i++){ if(P[i] != 0){ sum += (no[1]-T[i])*P[i]; sum = sum % 1000000007; } } cout << sum << endl; return 0; }

原代码（测试点2、3、4超时）

#include <iostream> using namespace std; int main(){ string s; cin >> s; //用于标记每个位置的PAT是第几个 int P[100000] = {0},A[100000] = {0},T[100000] = {0}; int no[3]={0};//记录PAT各自的数量 for(int i=0;i<s.length();i++){ if(s[i] == 'P') P[i] = ++no[0]; if(s[i] == 'A') A[i] = ++no[1]; if(s[i] == 'T') T[i] = ++no[2]; } int sum = 0; for(int i=0;i<s.length();i++){ if(P[i]!=0){ for(int j=i+1;j<s.length();j++){ if(A[j]!=0){ for(int k=j+1;k<s.length();k++){ if(T[k]!=0){ sum += no[2]-T[k]+1; sum = sum % 1000000007; break; } } } } } } cout << sum << endl; return 0; }