【算法笔记】B1040 有几个PAT
2024-09-03 00:23:14
1040 有几个PAT (25 分)
字符串 APPAPT
中包含了两个单词 PAT
,其中第一个 PAT
是第 2 位(P
),第 4 位(A
),第 6 位(T
);第二个 PAT
是第 3 位(P
),第 4 位(A
),第 6 位(T
)。
现给定字符串,问一共可以形成多少个 PAT
?
输入格式:
输入只有一行,包含一个字符串,长度不超过105,只包含 P
、A
、T
三种字母。
输出格式:
在一行中输出给定字符串中包含多少个 PAT
。由于结果可能比较大,只输出对 1000000007 取余数的结果。
输入样例:
APPAPT
输出样例:
2
思路:
对于每个A,能组成PAT的个数是左边P的个数和右边T的个数的乘积,因此只统计每个字母左边P的个数即可,时间复杂度为O(len)。
然后从后往前统计T的个数,每遇到一个A就计算一次并加到结果中。
codes:
#include<iostream>
using namespace std;
const int maxn = ;
const int mod = ;
string str;
int leftNumP[maxn]={};
int main(){
getline(cin, str);
int len = str.size();
int cnt = ;
for(int i = ; i < len; i++){
if(i > )
leftNumP[i] = leftNumP[i - ];
if(str[i] == 'P')
leftNumP[i]++;
}
int rightNumT = ;
for(int i = len - ; i >= ; i--){
if(str[i] == 'T')
rightNumT ++;
else if(str[i] == 'A'){
cnt = (cnt + leftNumP[i] * rightNumT) % mod;
}
}
cout<<cnt;
return ;
}
最新文章
- Silverlight 后台设置 button 纯色背景
- 如何在Visual Studio 2012中发布Web应用程序时自动混淆Javascript
- [BZOJ2654]tree(二分+MST)
- hdu 5294 最短路+最大流 ***
- [ActionScript 3.0] NetConnection建立客户端与服务器的双向连接
- Android --通知栏Notification
- 从零开始攻略PHP(5)——字符串操作与POSIX正则
- PHP自定义函数格式化json数据怎么调用?
- 做什么都要坚持,写blog也一样,
- 控制CPU占用率曲线
- Python爬虫学习:三、爬虫的基本操作流程
- c#中queue的用法
- Javascript中Array(数组)对象常用的几个方法
- mysql一库多表查询主键
- ServletListener对象学习笔记
- DAY25、面向对象总复习
- BZOJ.1812.[IOI2005]Riv 河流(树形背包)
- (2):Mysql 查看、创建、更改 数据库和表
- 尝试IRC &; freenode
- COGS.1689.[HNOI2010]Bounce 弹飞绵羊(分块)