PAT B1040 有几个PAT (25分)

PAT B1040 有几个PAT (25分)

#include <cstdio>
#include <cstring>

int main(){
	char c[100010];
	scanf("%s", c);
	
	int P[100010], T[100010];
	int temp = 0;
	for(int i=0; i<strlen(c); i++){
		if(c[i] == 'P'){
			temp++;
		}else if(c[i] == 'A'){
			P[i] = temp;
		}
	}
	
	temp = 0;
	int sum = 0;
	for(int i=strlen(c)-1; i>=0; i--){
		if(c[i] == 'T'){
			temp++;
		}else if(c[i] == 'A'){
			T[i] = temp;
			sum += T[i]*P[i];
			sum %=  1000000007;
		}
	}
	
	printf("%d", sum);
	
	return 0;
}

看了五分钟没什么太好的思路,只能想到暴力解。
看了书上的解法,这题最关键的还是要能看出“确定一个A的位置,拼出PAT的个数为它左边P的个数乘它右边T的个数”。

上一篇:拿糖果


下一篇:Ogre光源查找与设置