PAT (Basic Level) Practise 1040 有几个PAT（25）通过全部测试点

时间：2022-12-29 23:03:15

这是PAT的一道Basic级25分的真题（PAT-B-101-125-1-2015-03-14/E），也放进了Basic Level的Practise里，对应链接如下

http://www.patest.cn/contests/pat-b-101-125-1-2015-03-14/E

http://www.patest.cn/contests/pat-b-practise/1040 （截至目前，此处可以提交自己的代码看测试结果）

 

对于新手来说，想拿满分是略有难度的（因为部分测试用例规模很大，又对时间有要求），身为彩笔的我撸出了满分后，打算写篇日志庆祝记录一下...

运行结果：

测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 180 14/14
1 答案正确 1 308 1/1
2 答案正确 25 10548 2/2
3 答案正确 25 10600 4/4
4 答案正确 24 10548 4/4

 

 

 

 

 

 

题目要求：

1040. 有几个PAT（25）

时间限制 120 ms
内存限制 65536 kB
代码长度限制 8000 B
判题程序  Standard
作者 CAO, Peng

字符串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

思路：

第一次做只通过了第一、第二个测试(15/25)，总之失败的就不说了...

题目也提示了，输入非常大，因此尽可能做到对输入只进行尽可能少的遍历

因为“PAT”只有三个字母，那么如下条件成立：

　　如果选定一个A，那么含这个A的"PAT"个数，为这个A左边的P的个数，乘以这个数右边的T的个数

因此，需要统计每个A左边几个P，右边几个T。

从头到尾遍历一边输入的字符串，对于每个位置用hashmap记录截止到该位置的P的个数，大概就是<position,count>这样，同时在遍历过程中，用数组或者vector记录下每个A的位置。

再反向进行一次遍历，记录T的个数，道理同P。

至此，我们得到了每个A的位置，以及每个A左边有几个P，右边有几个T，对每个A一乘，再都加起来，就有结果了。

 

 1 #include <iostream>
 2 #include <string>
 3 #include <hash_map>
 4 
 5 using namespace std;
 6 using namespace __gnu_cxx;
 7 
 8 int main()
 9 {
10 
11     hash_map<int,int> p_left;   // 位置key的左边有多少个P
12     hash_map<int,int> t_right;  // 位置key的右边有多少个T
13     vector<int> a_pos;          // 字符串中出现A的位置
14 
15     string s;
16     while(cin>>s){
17 
18         int str_size = s.size();
19         int p_count=0, t_count=0;
20         int result=0;
21 
22         // 正序遍历一遍，记录P和A的信息
23         for(int i=0;i<str_size;++i){
24             if(s[i]=='A')
25                 a_pos.push_back(i);
26             else if(s[i]=='P')
27                 p_count++;
28             p_left[i] = p_count;
29         }
30 
31         // 逆序遍历一边，记录T的信息
32         for(int i=str_size-1;i>-1;--i){
33             if(s[i]=='T')
34                 t_count++;
35             t_right[i] = t_count;
36         }
37 
38         int vec_size = a_pos.size();
39         for(int i=0;i<vec_size;++i){
40             int a = a_pos[i];
41             result += p_left[a]*t_right[a];
42             result %= 1000000007;
43         }
44 
45         cout << result << endl;
46     }
47 
48     return 0;
49 }

贴上来发现还可以再稍微优化一点，22-29行的位置，只有满足 s[i] == 'A' 的时候，才执行 p_left[i] = p_count，对于T可同理，

因为只有A的位置才需要这些信息。（好在用C++写一般不用担心内存限制...）

 

总之呢，hashmap大法好，O(1)保平安。

 

标签：

相关文章