1093 Count PAT's (25 分)

其实核心思想就是遍历每一个‘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 }

 

上一篇:RSA算法过程及安全性


下一篇:动态多目标19Decomposition-based evolutionary dynamic multiobjective optimization using a difference model