1040 有几个PATpython3无超时

这道题思路来自于PAT 1040 有几个PAT python （无超时）

1、最初代码

#!/usr/bin/env python
# -*-coding:utf-8 -*-
''' @File : 1040.py @Time : 2020/04/21 09:40:16 @Author : Schiller Xu @Version : 1.0 @License : (C)Copyright 2020-2021, SchillerXu @Desc : None '''s=input()
n=0for i in range(len(s)-1):if s[i]=='A':n=n+s[0:i].count('P')*s[i+1:].count('T')n=n%1000000007print(n)

思路是以A为基准，如果A前面有a个“P”，A后面有b个“T”，那就可以组成 $a*b$个PAT，但是在多个A的情况下，count有很多计算是多余的。

2、改进代码

这道题比较有意思的是解题的思路，先算P的个数，再算PA的个数，再算PAT的个数。

代码如下：

#!/usr/bin/env python
# -*-coding:utf-8 -*-
''' @File : 1040-1.py @Time : 2020/07/20 09:40:34 @Author : Schiller Xu @Version : 1.0 @License : (C)Copyright 2020-2021, SchillerXu @Desc : None '''n = input()
count_P = count_PA = count_PAT = 0
for i in n:if i=='P':count_P += 1elif i=='A':count_PA += count_Pelse:count_PAT += count_PA
print(count_PAT % 1000000007)

思路很清奇，可以用来解决很多类似的问题。

3、参考资料

PAT 1040 有几个PAT python （无超时）