其实核心思想就是遍历每一个‘A’,这个A前面P的数量和后面T的数量的乘积就是一个A所能产生的PAT数,依次累加起来就是总的数量。
所以可以先找到第1个A,再找到第1个A前面所有P的数量cp,后面所有T的数量ct,相乘,并累加到结果中。
接着找第2个、第3个……第N个A,在找的过程中,如果遇到P,就将cp+1(因为这个P属于即将要找到的A的前面的P),如果遇到T就令ct-1(因为这个T是属于前一个A后面的T,但是却属于后面一个A前面的T,不应纳入计算中),找到A后,将cp*ct的值加到结果中即可。
柳婼大神的方法是十分简洁的,但个人觉得不是那么直观,所以我就再试着写一个。
1 #pragma warning(disable:4996) 2 #define _CRT_SECURE_NO_WARNINGS 3 4 #include <iostream> 5 #include <algorithm> 6 #include <cmath> 7 #include <vector> 8 #include <map> 9 #include <set> 10 #include <unordered_set> 11 #include <unordered_map> 12 #include <queue> 13 #include <cmath> 14 #include <string> 15 #define INFINITE 65535 16 #define mod 1000000007 17 using namespace std; 18 19 int main() 20 { 21 string s; 22 getline(cin, s); 23 int cnt = 0, cp=0, ca=0, ct=0; 24 int index = 0; 25 int first = 1; 26 while (index < s.size()) 27 { 28 if (first == 0) 29 { 30 if (s[index] == 'P')++cp; 31 if (s[index] == 'T')--ct; 32 } 33 if (s[index] == 'A') 34 { 35 if (first == 1) 36 { 37 first = 0; 38 for (int i = 0; i < index; ++i) 39 { 40 if ('P' == s[i])++cp; 41 } 42 for (int i = index + 1; i < s.size(); ++i) 43 { 44 if ('T' == s[i])++ct; 45 } 46 } 47 cnt = (cnt + (cp * ct) % mod) % mod; 48 } 49 ++index; 50 } 51 cout << cnt; 52 return 0; 53 }