首页 > itarticle > pat甲级1093

pat甲级1093

admin 11月 11, 2020 0

1093 Count PAT’s (25 point(s))

原地址

思路：

标记法.如果遇到字符’P ‘，累加；如果遇到字符’A’,当前pa组合的个数 = 当前’P’的个数 + 前一个’A’的得到的pa个数；
遇到’T’，当前’PAT’的个数 = 当前’PA’的个数 + 前一个’T’得到的pa个数。

代码:

来自石老板的精简代码%%%


using namespace std;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int MOD = 1000000007;
typedef long long ll;
#define pb push_back

char c,str[] = "PAT";
int a[3],b[3]; 

int () {
#ifdef ONLIGE_JUDGE
#else
    freopen("H:\in.txt","r",stdin);
#endif // ONLIGE_JUDGE
	for (int i = 0; ~scanf("%c",&c); ++i)
		for (int j = 0; j < 3; ++j)
			if (c == str[j])
				a[j]++, b[j] = j ? (b[j-1] + b[j]) % MOD : a[j];
	printf("%dn",b[2]);
    return 0;
}