【PAT (Basic Level) Practice】——【其他高效技巧与算法】1040 有几个PAT

【PAT (Basic Level) Practice】——【其他高效技巧与算法】1040 有几个PAT

文章目录

一【题目难度】二【题目编号】三【题目描述】四【题目示例】五【解题思路】六【最终得分】七【代码实现】八【提交结果】

一【题目难度】

乙级 二【题目编号】

1040 有几个PAT (25 分) 三【题目描述】

字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位( P )，第 4 位( A )，第 6 位( T )；第二个 PAT 是第 3 位( P )，第 4 位( A )，第 6 位( T )。现给定字符串，问一共可以形成多少个 PAT？ 四【题目示例】

输入格式：
输入只有一行，包含一个字符串，长度不超过 1 0 5 10^5 105 ，只包含 P、A、T 三种字母。

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

输入样例：
APPAPT

输出样例：
2

五【解题思路】

不用想，暴力肯定有一些用例超时（因为我试过了hh~），没办法实在没思路了，看的答案，不得不说真的妙：对于一个确定位置的A来说，以它形成的PAT的个数等于它左边P的个数乘以它右边T的个数。例如对字符串APPAPT的中间那个A来说，它左边有两个P，右边有一个T，因此这个A能形成的PAT的个数就是2*1=2。于是问题就转换为：对字符串中的每个A，计算它左边P的个数与它右边T的个数的乘积，然后把所有A的这个乘积相加就是答案。统计左边P的个数的时候扫描一遍字符串，从左到右如果是P当前位置的个数加1，如果不是P那么就是A（计算这个需要一个数组存储对应位置的个数），继承左边P的个数，统计右边T的个数的时候就可以直接算出结果，如果是T，那么个数加1，如果不是T那么就是A（计算这个不需要数组，因为右边的T肯定可以和左边的P和A配对），此时已经知道了当前这个A左边P的个数和右边T的个数，直接计算即可，注意最后输出的时候要按照题目要求对结果取模 六【最终得分】

25分 七【代码实现】

#include
#include
int main()
{
    char str[100001];
    scanf("%s",str);
    int len = strlen(str),res = 0,leftCountP[100001],rightCountT = 0;
    for(int i = 0;i 0)
        {
            leftCountP[i] = leftCountP[i-1];
        }
        if(str[i] == 'P')
        {
            leftCountP[i]++;
        }
    }
    for(int i = len-1;i>=0;i--)
    {
        if(str[i] == 'T')
        {
            rightCountT++;
        }
        else if(str[i] == 'A')
        {
            res = (res + (rightCountT * leftCountP[i])) % 1000000007;
        }
    }
    printf("%d",res);
    return 0;
}

八【提交结果】