题目:

count PAT's
输入一串字符,其中字符集为 {P,A,T}, 求解字符中包含多少个PAT子序列。
例如:PATT 包含2个PAT 子序列, PAATT包含4个PAT子序列。

问题分析:

对于字符串s[n], 考虑某位置s[i],相对于s[i-1]增加了s[i],考虑增加s[i]对PAT子序列的影响:
如果s[i]是T字符,那么当前的PAT子序列增加的数目,就是当前PA子序列的数目,因为前面有多少个PA,增加一个T,就会增加多少个PAT;
同理,如果s[i]是A字符,那么当前的PA 的增加数目,就是当前的P的字符数目。

复杂度分析

只需要简单的遍历一遍s[n],复杂度为O(n)

通过代码

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

char s[100002];
int size;
const int mod = 1000000007;

int main() {
    int p=0,pa=0,pat=0;

    cin >> s;
    int n = strlen(s);
    for (int i=0;i<n;i++) {
        if (s[i] == 'P') {
            p++;
        }

        if (s[i] == 'A') {
            pa+=p;
            pa%=mod;
        }

        if (s[i] == 'T') {
            pat+=pa;
            pat%=mod;
        }
    }
    cout << pat<<endl;
}