PAT乙级1040

2017-01-14 19:45:40来源:CSDN作者:qq_22194315人点击

1040. 有几个PAT(25)

时间限制120 ms
内存限制65536 kB
代码长度限制8000 B
判题程序Standard作者CAO, Peng

字符串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

#include<iostream>#include<vector>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;const int MAXN = 100010;const int MOD = 1000000007;char str[MAXN];int leftNumP[MAXN] = { 0 };int main(){	/*int count = 0;	string s;	cin >> s;	for (int pos1 = s.find('P'); pos1>= 0 && pos1 <= s.size() - 3; pos1 = s.find('P', pos1+1))	{		for (int pos2 = s.find('A',pos1+1); pos2  >= 0 && pos2 <= s.size() - 2; pos2 = s.find('A', pos2+1))		{			for (int pos3 = s.find('T', pos2 + 1); pos3 >= 0 && pos3 <= s.size() - 1;pos3 = s.find('T', pos3+1))			{				count++;			}		}	}	cout << count% 1000000007;	暴力法超时*/	gets_s(str);//读入字符串	int len = strlen(str);//长度	for (int i = 0; i < len; i++)	{//从左到右遍历字符串		if (i > 0)		{//如果不是0号位			leftNumP[i] = leftNumP[i - 1];//继承上一位的结果		}		if (str[i] == 'P')		{//当前位是P			leftNumP[i]++;//令leftNumP[i]+1		}	}	int ans = 0, rightNumT = 0;//ans为答案,rightNumT记录右边T的个数	for (int i = len - 1; i >= 0; i--)//从右到左遍历字符串	{		if (str[i] == 'T')//当前位是T			rightNumT++;//右边T的个数加1		else if (str[i] == 'A')//当前位是A			ans = (ans + leftNumP[i] * rightNumT) % MOD;//累积乘积	}	printf("%d", ans);	return 0;}
//提交时gets_s改成gets,编译器的问题

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台