PAT-1040 有几个PAT (25 分)

痛定思痛。 2022-02-04 03:41 238阅读 0赞

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

### 输入格式： ###

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

### 输出格式： ###

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

### 输入样例： ###

APPAPT

### 输出样例： ###

2

暴力求解存在超时问题，看了很多大佬写的代码，学到一种思路，只需一遍循环便能解决问题  
1.首先，从左往右遍历，计数P出现的个数  
2.如果P的个数不为0，并且当前字符是A，那么对于这个A来说，目前能构成PA的个数就是之前的PA个数加上当前P的个数  
3.如果PA的个数不为0，并且当前字符是T，那么对于这个T来说，目前能构成PAT的个数就是之前的PAT个数加上当前PA的个数  
4.注意每次运算完PAT个数，整除一下1000000007，如果放在最后再整除的话很可能数据太大，又变成一个大数问题了

### 代码 ###

#include<iostream>
    #include<cstring>
    using namespace std;
    int main()
    { 
        string s;
        long long p=0,pa=0,pat=0;//记录当前p,pa,pat的个数
        cin>>s;
        for(int i=0;i<s.length();i++)
        { 
            if(s[i]=='P')p++;
            else if(p&&s[i]=='A')
            { 
                pa+=p;
            }
            else if(pa&&s[i]=='T')
            { 
                pat+=pa;
                pat%=1000000007;
            }
        }
        cout<<pat<<endl;
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，238人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python实现Pat 1040. Longest Symmetric String (25)

[题目][Link 1] Given a string, you are supposed to output the length of the longest sym

你的名字/ 2022年06月04日 08:39/ 0 赞/ 165 阅读

相关 1040. 有几个PAT（25）

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

野性酷女/ 2022年05月26日 06:41/ 0 赞/ 182 阅读

相关 1040 有几个PAT （25 分）

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

旧城等待，/ 2022年05月15日 16:24/ 0 赞/ 169 阅读

相关 PAT排名汇总（25 分）

计算机程序设计能力考试（Programming Ability Test，简称PAT）旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力，科学的

￡神魔★判官ぃ/ 2022年05月09日 06:10/ 0 赞/ 199 阅读

相关 PAT乙级1040

1040 有几个PAT （25 分）字符串 `APPAPT` 中包含了两个单词 `PAT`，其中第一个 `PAT` 是第 2 位(`P`)，第 4 位(`A`)，第 6 位

ゝ一纸荒年。/ 2022年05月08日 06:52/ 0 赞/ 205 阅读

相关 PAT-B 1040. 有几个PAT（25）

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

短命女/ 2022年03月11日 07:27/ 0 赞/ 196 阅读

相关 PAT-1040 有几个PAT (25 分)

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

痛定思痛。/ 2022年02月04日 03:41/ 0 赞/ 238 阅读

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

题目描述：字符串 `APPAPT` 中包含了两个单词 `PAT`，其中第一个 `PAT` 是第 2 位(`P`)，第 4 位(`A`)，第 6 位(`T`)；第二个 `PA

男娘i/ 2021年12月02日 00:10/ 0 赞/ 318 阅读

相关 1040. 有几个PAT

输入格式：输入只有一行，包含一个字符串，长度不超过1，只包含 `P`、`A`、`T` 三种字母。输出格式：在一行中输出给定字符串中包含多少个 `PAT`。由

本是古典何须时尚/ 2021年11月02日 05:24/ 0 赞/ 238 阅读

相关 PAT 1040 有几个PAT (25分)（Java）

题目描述字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位§，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位§，第

- 日理万妓/ 2021年09月24日 03:20/ 0 赞/ 266 阅读