1040 有几个PAT (25 分)
- 2019 年 10 月 8 日
- 筆記
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
【我的代码】
// 1040 有几个PAT (25 分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> #include <string> using namespace std; int main() { //输入 string a; cin >> a; int i = 0; long num_T = 0, num_AT = 0, num_PAT = 0; //计算 for (i = a.size() - 1; i >= 0; i--) { if (a[i] == 'T') { num_T++; } else if (a[i] == 'A') {//找到一个A后，就能和前面所有数过的数进行组合，组成PAT num_AT = (num_AT + num_T) % 1000000007; } else {//对P而言，只能结合前面所有AT的数量，并不能与T直接挂钩 num_PAT = (num_PAT + num_AT) % 1000000007; } } cout << num_PAT % 1000000007; return 0; }
【思路】
通过读题，我们发现对于由同一个T结尾PAT可以允许存在多个。也就是说，PAT的个数取决于P的个数和后面AT的个数（同一个AT可以对应多个P从而形成PAT），而AT的个数又取决于T的个数（同一个T可以跟多个A组合成AT）。因此我们仅需从后往前计数即可。
