PAT~乙级~1040 有几个PAT ~C++

男娘i 2021-12-02 00:10 339阅读 0赞

题目描述：

字符串 `APPAPT` 中包含了两个单词 `PAT`，其中第一个 `PAT` 是第 2 位(`P`)，第 4 位(`A`)，第 6 位(`T`)；第二个 `PAT` 是第 3 位(`P`)，第 4 位(`A`)，第 6 位(`T`)。

现给定字符串，问一共可以形成多少个 `PAT`？

### 输入格式： ###

输入只有一行，包含一个字符串，长度不超过105，只包含 `P`、`A`、`T` 三种字母。

### 输出格式： ###

在一行中输出给定字符串中包含多少个 `PAT`。由于结果可能比较大，只输出对 1000000007 取余数的结果。

### 输入样例： ###

APPAPT

### 输出样例： ###

\----------------------------------------------------------答题区----------------------------------------------------------

刚开始对题目的理解有些问题，正确理解是这样的，\*代表长度大于等于0的字符串，只要形如P\*A\*T，相对顺序是这样的，就可以组成。

总体思想就是统计出A前面的P，T前面的PA组合，这样就相当于用累加来实现乘积。flag\_P是P出现的次数，每次遇到A，会把他之前的P的数量加一下，每次遇到T就会把前面的PA的组合数量加起来。

#include <iostream>
    #include <stdio.h>
    using namespace std;
    int main()
    {
        char s;
        int flag_P=0;
        int num_PA=0;
        long long int result=0;
        while((s=getchar())!=EOF)
        {
            if(s=='P')
            {
                flag_P++;
            }
            if(s=='A')
            {
                num_PA+=flag_P;
            }
            if(s=='T')
            {
                result+=num_PA;
            }
        }
        result%=1000000007;
        printf("%lld",result);
        return 0;
    }

维护了一个PAT测试点问题的共享文档，欢迎大家把遇到的问题写在上面。

一起写文档：[https://yiqixie.com/d/home/fcACe6xZ2aroPxFQrQZ05Cw32][https_yiqixie.com_d_home_fcACe6xZ2aroPxFQrQZ05Cw32]  
github链接：[https://github.com/Makerdd/PAT-yiji][https_github.com_Makerdd_PAT-yiji]

[https_yiqixie.com_d_home_fcACe6xZ2aroPxFQrQZ05Cw32]: https://yiqixie.com/d/home/fcACe6xZ2aroPxFQrQZ05Cw32
[https_github.com_Makerdd_PAT-yiji]: https://github.com/Makerdd/PAT-yiji