首页 > 其他 > 详细

1040 有几个PAT (25分)

时间:2020-03-08 17:35:36      阅读:64      评论:0      收藏:0      [点我收藏+]

在这个题目上卡了很久,被骗进循环的陷阱里,怎么修改代码都超时,凎!

其实可以很容易分析出来,以‘A’为准,求左边有多少个‘P’,右边有多少个‘T’,把他们相乘就可以确定该‘A’可以组成多少个pat;

《算法笔记》上给了一段代码,思路就是这样,但照着敲这么也ac不过,凎!

看了柳婼的博客才惊叹居然这么简单,复杂度只有O(n),简直是奇女子!

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int len = s.length(), result = 0, countp = 0, countt = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == T)
            countt++;
    }
    for (int i = 0; i < len; i++) {
        if (s[i] == P) countp++;
        if (s[i] == T) countt--;
        if (s[i] == A) result = (result + (countp * countt) % 1000000007) % 1000000007;
    }
    cout << result;
    return 0;
}

 

1040 有几个PAT (25分)

原文:https://www.cnblogs.com/kalicener/p/12443664.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!