[PAT解题报告] Count PAT's
我出的题——也是简单题。数PAT的个数。
如果我们知道这个A之前有多少个P，则那些P和这个A一起可以构成这么多个PA。
如果我们知道这个T之前有多少个PA，则那些PA和这个T一起就可以构成这么多个PAT。
所以就是动态统计P, PA, PAT的个数。
遇到P, 则P的个数加1。
遇到A，则PA的个数加P的个数。
遇到T，则PAT的个数加PA的个数。
注意别忘记每次加法后取余数。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
using namespace std;
char s[100005];
const int M = 1000000007;
int main() {
int p = 0, pa = 0, pat = 0;
scanf("%s",s);
for (int i = 0; s[i]; ++i) {
if (s[i] == 'P') {
if (++p >= M) {
p -= M;
}
}
else if (s[i] == 'A') {
if ((pa += p) >= M) {
pa -= M;
}
}
else if ((pat += pa) >= M) {
pat -= M;
}
}
printf("%d\n", pat);
return 0;
}
原体链接： http://www.patest.cn/contests/pat-a-practise/1093
投递华为HUAWEI等公司10个岗位
