|
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
结尾无空行
思路：
? ? ? ? 遍历暴力解会导致时间超时
? ? ? ? 问题关键在于要先有P，再有A，最后再有T；才能组成一个PAT。同时也可以注意到，
????????组合数 = 在前面的P的数量 * 在中间的A的数量 * 在后面的T的数量
? ? ? ? 这样算出每一个的数量过于复杂，所以不妨换个思路， 我们不必先求出合适P，A，T的数量，而是在遇到P，A，T时对数据先进行处理，已经知道要先有P，再有A，最后再有T，所以我们不妨先从后面来遍历字符串数组，遇到T时让T的数量t+1；遇到A时让y += 1*t,同时让 a = 0（一个A只能与同一个T组合一次）; 当遇到T时，再 sum += 1*y（一个T只能与同一组A和T组合一次）;
这样便可以得出结果
代码详细：
#include<stdio.h>
#include<string.h>
//#include<malloc.h>
#define MOD 1000000007
int main() {
char x[100000];
scanf("%s",x);
int t = strlen(x);
//int *A, *T;
//A = (int* )malloc(sizeof(int)* t);
//T = (int* )malloc(sizeof(int)* t);
int i, j, tmp1, tmp2 ;
long long int y = 0;
long long int sum = 0;
tmp1 = 0;
tmp2 = 0;
for(i= t-1; i >= 0; i--) {
if(x[i] == 'A') {
//tmp1++;
//y += (tmp1 * tmp2) % MOD;//防止PTA
//tmp1 = 0;//PTATA
y += tmp2 % MOD;
} else if( x[i] == 'T') {
tmp2++;
} else if(x[i] == 'P') {
sum = (sum + y) % MOD;
//tmp1 = 0;
//tmp2 = 0;
}
}
printf("%d",sum);
return 0;
}
|