题意及思路

  • 题意：给定一个只含有‘P’、‘A’、‘T’的字符串。求PTA出现的次数（不要求三个字母连续出现，只需要保持相对位置即可）🙂。
  • 思路：🙄直接暴力搜索PTA出现位置，统计次数会超时。不超时的做法是，对于每一个A，统计其前面的P个数leftP及后面的T个数rightT。则对于当前A来说，😐出现PAT的次数为leftP * rightT；给出分析图。

  • 总结：这题采用的是递推的思路加上前缀后缀之类的概念，😏还需要多多体会。

代码 

#include<bits/stdc++.h>

using namespace std;

const int mod = 1000000007, N = 1e5+5;
int leftP[N], rightT = 0, ans = 0;

int main()
{
	std::ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    for(int i=0;i<n;i++){
    	if(i>0) leftP[i] = leftP[i-1];
    	if(s[i]=='P') leftP[i]++;
	}
	for(int i=n-1;i>=0;i--){
		if(s[i]=='T') rightT++;
		else if(s[i]=='A'){
			ans = (ans + leftP[i]*rightT)%mod;
		}
	}
	cout << ans << endl;
    
	return 0;
}