1003 我要通过 (20 分)

题目

题目链接

题解

实现题。

理解题目表达的意思：

1. 字符串中必须仅有 P、 A、 T 这三种字符，不可以包含其它字符；

2. 可以在 PAT 左右两侧加任意个相同数量的 A，比如 PAT、APATA、AAPATAA 均是正确的，但 APAT、PATA、AAPATA 均是不正确的。

3. 开始递归定义了！

   “如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。”

   找一下规律：

   由条件2可知，PAT、APAT、AAPATAA 是正确的，那么我们看看这三个能推出哪些是正确的。

   • PAT 中 a=空，b=A，c=空，所以 aPbATca 为 PAAT，所以 PAAT 是正确的；由 PAAT 中 a=空，b=AA，c=空，所以 aPbATca 为 PAAAT，所以 PAAAT 是正确的；……
   2. APATA 中 a=A，b=A，c=A，所以 aPbATca 为 APAATAA，所以 APAATAA 是正确的；由 APAATAA 中 a=A，b=AA，c=AA，所以 aPbATca 为 APAAATAAA，所以 APAAATAAA 是正确的；……
   3. AAPATAA 中 a=AA，b=A，c=AA，所以 aPbATca 为 AAPAATAAAA，所以 AAPAATAAAA 是正确的；由 AAPAATAAAA 中 a=AA，b=AA，c=AAAA，所以 aPbATca 为 AAPAAATAAAAAA，所以 AAPAAATAAAAAA 是正确的；……   \space  

   直观上来看，发现 a 的 A 数量只与开始给定的数字符串有关，再怎么递推下去数量都不变； b 的 A 数量只会随着递推次数增加；c 的 A 数量很显然是与 a 的 A 数量有关的，每次递推都要拼接个 a 构成新的 c。这不规律就来了嘛，c 的 A 数量在每次递推时都会拼接上个 a，（简记 a、b、c 分别表示其中 A 的数量），那么 c = a * 递推次数，其中递推次数不正是 b 嘛，所以条件3表达是就是满足 a * b = c 的字符串，当然也必须满足前两条条件才算真正符合条件。

理解完了就会写了！

代码

#include
using namespace std;
int n;
int main()
{
	cin >> n;
	while (n --) {
		string s;
		cin >> s;
		// 保证只能存在 P A T 
		int flag = 0;
		for (int i = 0;i