AcWing 1583. PAT 计数    原题链接    简单

作者： 作者的头像   P云 ,  2020-04-06 13:27:41 ,  所有人可见 ,  阅读 1694

31


3

题目描述

对于字符串中的每一个A，它能够构成字串PA的数量是它之前的所有P的数量。
对于字符串中的每一个T，它能够构成字串PAT的数量是它之前所有字串PA的数量。

$O(n)$

C++ 代码

#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
long long p, a, b, res;
int main()
{
    string str;
    cin >> str;
    for (auto c : str)
        if (c == 'P') p ++;
        else if (c == 'A') b += p;
        else res = (res + b) % mod;
    cout << res;
}

13 评论

用户头像
Error_666   10个月前         踩      回复

学到了

用户头像
尼古拉斯小布丁   2022-11-16 16:15         踩      回复

##### 牛的，这不比状态机简单多了，还能解决问题

用户头像
liyiHuan   2022-03-28 17:27         踩      回复

？？？tqltql

用户头像
Albert_Tesla   2021-09-24 19:05         踩      回复

太强了!

用户头像
Makisekurisu_4   2021-09-19 10:12         踩      回复 
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, mod = 1e9 + 7;

LL res, p, a, t;
char str[N];

int main()
{
    scanf("%s", str);
    for (int i = 0; i < strlen(str); i++)
        if (str[i] == 'T') t++;

    for (int i = 0; i < strlen(str); i++)
    {
        if (str[i] == 'A')
        {
            res = (res + p * t) % mod;
        }
        else if (str[i] == 'P') p++;
        else if (str[i] == 'T') t--;
    }

    printf("%lld\n", res);

    return 0;
}

在Acwing上 TLE,在PTA的1093上AC了…

用户头像
AC啊   2021-06-25 15:19         踩      回复

请问为什么要取模呢？

用户头像
AC啊   2021-06-26 09:54      1    踩      回复

我懂了因为题目里让这么干

用户头像
国家特级退堂鼓演奏家   2021-06-23 17:23         踩      回复

太强了

用户头像
Sloan1028   2021-02-10 15:31         踩      回复

太牛了

用户头像
fedfan   2020-08-17 20:49         踩      回复

巧妙

用户头像
dfbdberberb   2020-05-31 15:25         踩      回复 
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e5+10;
int dp[N][4];
string a;
int mod=1000000007;
int main()
{
    cin>>a;
    a=' '+a;
 //  cout<<a.size();
    for(int i=1;i<a.size();i++)
    {
        for(int j=0; j<4 ;j++)
        dp[i][j]=dp[i-1][j];

        if(a[i]=='P')
        dp[i][1]+=dp[i-1][0]+1;
        else if(a[i]=='A'&&dp[i-1][1])
        dp[i][2]+=dp[i-1][1];
        else if(a[i]=='T'&&dp[i-1][2])
        dp[i][3]=( dp[i][3]+dp[i-1][2])%mod;

    }
  cout<<dp[a.size()-1][3];

    return 0;
}

我写出来的简直就像是一坨屎

用户头像
fedfan   2020-08-17 20:42         踩      回复

pat甲级不是不考dp的？

用户头像
dfbdberberb   2020-05-31 15:22         踩      回复

学到了大佬