PAT-乙级题目汇总及回顾

发表于 | 更新于: | 分类于

PAT乙级真题思路（前八十题）：

1001 - 害死人不偿命的(3n+1)猜想(15)

对应”(3n+1) - first”

1002 - 写出这个数（20）

对应”write-the-world”（大概是起名字的时候脑子Bug了…

1003 - 我要通过！（20）

在柳婼给出的题解中，寻找到题目生成的规律来简化问题。我的第一个反应就是根据表达式生成，在字符串长度100以内存在哪些式子，然后再进行匹配。

对应”want-to-pass”

1004 - 成绩排名（20）

简单的比一下最大最小值，对应”grades-rank”

1005 - 继续(3n+1)猜想（25）

柳婼的题解中，是利用一个arr作为标记，将验证过的数字标记为1，最后把arr=0的数字输出出来。

我这里是用两个set，取一个差集得到没有验证过的数字。

###1006 - 换个格式输出整数 （15）

对应”change-print-format”

1007 - 素数对猜想（20）

对应”prime-pair”

1008 - 数组元素循环右移问题 （20）

对于这种问题，没必要完全模拟。这里利用三次反转进行。

1
2
3
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+m);
reverse(nums.begin() + m, nums.end());

1009 - 说反话（20）

可以使用reverse函数，也可以用栈。

1
2
3
4
stack<string> v;
v.push(s);
cout << v.top();
v.pop();

1010 - 一元多项式求导

这里要注意，当没有输出的时候，要输出”0 0”才可以。

另外，这种问题中，可以即时输入/输出的。

1011 - A+B和C（15）

1012 - 数字分类（20）

根据不同要求对数字进行分类。

1013 - 数素数（20）

1014 - 福尔摩斯的约会（20）

找到对应字符以后进行判断即可。注意最后输出的时候要前面加0补位。

1015 - 德才论（25）

这里没有AC，主要问题是超时。

因为对不同人的分类是在一个结构体中用state变量表示，在排序的时候采取的是所有人的排序，就会超时。

应该对不同state的人分别排序，然后再按照state进行输出，比如可以用vector<node> v[4]这样的vector数组。

1016 - 部分A+B

遍历一下字符串，再乘十计算就可以了。

1017 - A除以B（20）

手动模拟除法，难度不大。

1018 - 锤子剪刀布 （20）

问题不大，这里用了map来记录，没有发现map可以直接比较大小的，只封装了一个函数来做。

1019 - 数字黑洞（20）

这道题我是对每一位进行处理，但是看柳婼的题解可以输入string然后利用sort调整位置。在对于位数较多的时候，sort是个比较好的方法。

1020 - 月饼（25）

一个规划的问题，但题目内容很简单，只要注意到浮点数和位数问题就不大了。

1021 - 个位数统计（15）

从开始遍历一遍即可。

1022 - D进制的A+B（20）

和后面的比，这个就太容易了

1023 - 组个最小数（20）

先找到最小的不为零的数作为第一个数字，其余数字升序排列即可。这里有一个可以加速的地方，当已知位置t之前没有合适的数字了，可以直接跳过这些进行输出。

1024 - 科学计数法（20）

我这里是用字符串进行处理的，把几个部分分开，然后再合并在一起。更多的是纯字符串的处理，没有过多用数学的办法。

1025 - 反转链表（25）

【感觉是目前，乙级真题中最复杂的一个了】

关键是要知道<algorithm>中有一个reverse函数。

这里借鉴柳婼小姐姐的思路：

注意，不是所有的元素都有用

所以输入以后，需要sum统计一下有多少在链表中的元素。

接下来把链表按照顺序存入一个list中，但是实际上，对于这道题而言并不需要修改链表的next指针，只需要在输出的时候，输出list[i+1]就可以了。

利用reverse就可以反转链表，判断条件sum上需要去掉不能整除的部分：

1
2
for (int i = 0; i < (sum - sum % k); i += k)
        reverse(begin(list) + i, begin(list) + i + k);

1026 - 程序运行时间（15）

类比clock()函数进行计算，主要就是进位的问题。

1027 - 打印沙漏（20）

注意，这个沙漏！右面不能有空格。

这里使用了string的一种定义方法产生相同的字符串：

1
string stars(num, symbol);

1028 - 人口普查（20）

只要判断好时间界限，问题就比较容易啦~

1029 - 旧键盘（20）

【参考柳婼小姐姐的题解比较好~

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <cctype>
using namespace std;
int main() {
    string s1, s2, ans;
    cin >> s1 >> s2;
    for (int i = 0; i < s1.length(); i++)
        if (s2.find(s1[i]) == string::npos && ans.find(toupper(s1[i])) == string::npos)
            ans += toupper(s1[i]);
    cout << ans;
    return 0;
}

后面有一道题目比这个还要复杂一些。

1030 - 完美数列（25）

排个序，问题就很容易解决啦~

1031 - 查验身份证（15）

其实还挺有用的:)

字符串处理一下，记得最后的对应关系就可以啦~

1032 - 挖掘机技术哪家强（20）

用个vector存一下就好啦

1033 - 旧键盘打字（20）

承接1029题目，多加了一些错误的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <cctype>
using namespace std;
int main() {
  string bad, should;
  getline(cin, bad);  //为了防止第一行是空的，不能用cin >> ,用getline(cin, ...)
  getline(cin, should);
  for (int i = 0, length = should.length(); i < length; i++) {
    if (bad.find(toupper(should[i])) != string::npos) continue;//如果字母有错误的话
    if (isupper(should[i]) && bad.find('+') != string::npos) continue;//如果输出应该是大写字母，但是上档坏掉了
    cout << should[i];
  }
  return 0;
}

1034 - 有理数四则运算（20）

【这道题有一些麻烦，因为涉及到分数的四则运算，四种运算都需要写出来。

我的思路是建一个结构体用来存储，同时有化简分数、带分数化成假分数的函数。在结构体外重构了加减乘除的运算，同时实现了通分的操作。

这样是先化简再进行通分，最后再根据结果要求调整格式。

1035 - 插入与归并（25） important

判断当前的序列是处于插入排序还是归并排序，二者的主要区别是在经过前面的一段有序队列后，剩余的队列是否有序。

先用一个指针i找到从头开始最后一个排好序的位置，注意这里的限定条件要到n-1，因为判断的时候会用到i+1。

接下来用指针j从i+1的位置开始寻找第一个不满足a[j]==b[j]，如果j能够到结尾，就说明是插入排序。j的判断是寻找后面有没有变动，如果都没变动，就判断是插入排序。

模拟递归排序的过程：

1
2
3
4
5
6
7
8
9
10
11
12
cout << "Merge Sort" << endl;
int k = 1, flag = 1;
while(flag) {
    flag = 0;
    for (i = 0; i < n; i++) {
        if (a[i] != b[i])
            flag = 1;
    }
    k = k * 2;
    for (i = 0; i < n / k; i++)
        sort(a + i * k, a + (i + 1) * k);
    sort(a + n / k * k, a + n);

注意，最后一句的sort是为了处理剩余的内容，由于是正整数，所以$n/k\times k \neq n $

1036 - 跟奥巴马一起编程（15）

那就编呗-。-期待以后还有川普的

1037 - 在霍格沃茨找零钱（20）

就是一个进制的问题，盘算一下就好啦

1038 - 统计同成绩学生（20）

可以用一个数组，也可以用一个map来记录数字。

1039 - 到底买不买（20）

第一直觉是用map来解决，然后每一项进行对比。

也可以用两个数组来搞定，遇到相同的就“消消乐”变成’#’，然后再统计其他的数量。

1040 - 有几个PAT（25）

首先来一段柳婼同学活泼的分析：

要想知道构成多少个PAT，那么遍历字符串后对于每一A，它前面的P的个数和它后面的T的个数的乘积就是能构成的PAT的个数。然后把对于每一个A的结果相加即可~~辣么就简单啦，只需要先遍历字符串数一数有多少个T~~然后每遇到一个T呢~countt–;每遇到一个P呢，countp++;然后一遇到字母A呢就countt * countp~~~把这个结果累加到result中~~~~最后输出结果就好啦~~对了别忘记要对10000000007取余哦~~~~

这种问题最好抽象出数学规律~这样会极大降低计算的难度的。本来想用三层循环来模拟，暴力的求解，结果超时了…

1041 - 考试座位号（15）

一个搜索的问题，后面用试机位置号，那前面的标记也是用试机来做。

1042 - 字符统计（20）

注意包含空格，所以不能用cin >>

统计的内容只包括英文字母，所以只需要一个长度为26的数组来保存。

1043 - 输出PATest（20）

整理现有的字母然后输出。

1044 - 火星数字（20）

进制转换问题的基础上又加了一些新的内容，将火星人的两位用不同的表示。

就是处理的时候，稍微麻烦了一些，难度还好。

1045 - 快速排序（25）

如果重复遍历，很容易超时。就用空间来换取时间，定义一个max和一个min的数组，分别存储由前到后和由后到前的最大最小值。最后再遍历一遍和前后的最大最小值比较一下就可以啦~

而柳婼小姐姐的思路是先整体排序，如果当前元素没有变化而且它左边的所有值的最大值都比它小的时候，它就可能是主元。

1046 - 划拳（15）

简单算一下就好啦~

（不过划拳这么麻烦呀…感觉会懵的hh

1047 - 编程团体赛（20）

记录一下参赛的队伍就可以啦~

1048 - 数字加密（20）

这里需要注意两个数字位数不一样的情况，如果A比B长，就把B前面补零补齐。

1049 - 数列的片段和（20）

注意是double就可以啦~

1050 - 螺旋矩阵（25)

这个似乎是一次期末考试的题目，思路也比较清晰，但是要注意各种边界情况。在计算范围的时候，也要格外小心，是谁减一的问题。

1051 - 复数乘法（15）

一个很重要的点：当A或者B小于0但是大于-0.005(比如-0.00001)时候，如果按照A>=0的判断，会输出“-0.00”这样的结果,事实上应该输出“0.00”【B同理，应该输出“+0.00i”】

1052 - 卖个萌（20）

转义字符、注意，有空格的要用getline。

1053 - 住房空置率 （20）

输出百分号要用%%，另外，要认真读题！！！

1054 - 求平均值（20）

这题目也可以抛出异常来写。

1
2
3
4
5
6
7
8
//sscanf() – 从一个字符串中读进与指定格式相符的数据
sscanf(a, "%lf", &temp);
//sprintf() – 字符串格式化命令，主要功能是把格式化的数据写入某个字符串中
sprintf(b, "%.2lf", temp);
int flag = 0;
for(int j = 0; j < strlen(a); j++) {
    if(a[j] != b[j]) flag = 1;
}

1055 - 集体照（25）这个再做一做hh

1056 - 组合数的和（15）

给出N个不同的非零个位数字，难度已经降低非常非常多了。如果是包括重复的，丢进set里就可以。然后两层遍历就可以啦~但是要注意到相同数字的问题。

1057 - 数零壹（20）

统计、转化进制，注意不分大小写，所以要把字母统一一下。

1058 - 选择题（20）*

这道题目要求输出的内容偏多，我的第一直觉是用一个题目的结构体数组来存储题目，单独一个数组存储成绩，最后再遍历一遍数组。

柳婼在实现的时候，使用了几个数组来分别存储。虽然竞赛可以这样写，但是工程这样写可能要被打洗了hhh

1059 - C语言竞赛（20）

这道题目的输出也涉及到几个部分，首先要有一个存储id与排名对应的数组或者map。至于重复查询的问题，我的第一反应是用一个数组来表示，但是实际上用set更方便一些。

这类问题的关键点是寻找，用哪个变量寻找哪个变量，决定index和value的值。

1060 - 爱丁顿数（25）

这类逻辑题要注意寻找数学规律，看起来很苛刻的条件其实并没有很难实现。

我的思路是对应的寻找，发现对应的数字够大，剩下的数字不那么大。就是找到了爱丁顿数，但实际思考的过程中，还是出现了一些问题，包括何时break的问题。另外，要弄清楚是index和序号的问题。可以考虑从1开始存储~

1061 - 判断题（15）

比上面的判选择题简单了很多hhh

1062 - 最简分数（20）

这道题，我的第一个思路是把两个端点的值算出来，变成double类型，再在中间一个一个一个算，不断和端点值进行匹配。

要注意：输入的大小关系！

在比较的时候，如果用两个整数相乘，会更省时间而且准确度更高。

1063 - 计算谱半径（20）

就是一个最大值的题目，像是15分的题

1064 - 朋友数（20）

我们默认一个整数自己是自己的朋友。

这一句话就把这道题的难度拉到最低点了…只需要把所有数各位的和丢进一个set里就解决了。

1065 - 单身狗（25）

这里柳婼给出了一个简洁的思路，在一个数组中，couple之间相互存对方的id来进行匹配。

1066 - 图像过滤（15）

看起来很复杂，是一个像素一个像素处理，其实只是对每一个数值进行更改。这种问题不用存储到数组中，可以边输入边处理输出这样~

1067 - 试密码（20）

字符串匹配的问题，很简单。

1068 - 万绿丛中一点红（20）*

  1. 读题的时候要仔细！必须是唯一的！
  2. 这道题目的难点在寻找周围八个像素点，类似扫雷一样。可以用一些简便的形式来写，不然就要copy代码了…

1069 - 微博抽奖（20）

仔细读题就好啦~主要要怎么抽，抽到曾经抽过的人应该怎么办~

1070 - 结绳（25）

只要让最短的绳子不断不断的折叠就可以啦~最长的绳子尽量少的折叠~还蛮简单的~

1071 - 小赌怡情（15）

简单的IO…

1072 - 开学寄语（20）

四位数的标号，就可以用forbid[10000]来存储，但是对于实际中不定长的问题，还是用set可能比较好。这类问题都可以即时输入/输出。

1073 - 多选题常见计分法（20）

之前就有一道多选的题目，但要求略有变化。这里考虑了部分选项正确的情况，计算分数更复杂；同时要求输出统计成绩的情况。

这题写了一个下午…最后还有一个测试点没有通过，整理一下坑点啦~

  1. 错误计数就是错选
  2. 在选项计数中，选错的、漏选的，都要计算
  3. 最终判断最多的不是题目错的人数最多，是选项错误次数最多（迷醉…

1074 - 宇宙无敌加法器（20）

综合性进制转换的题目，但是思路是类似的啦~

1075 - 链表元素分类（25）

看到这个题目就想起来之前反转链表的噩梦…

1076 - Wifi密码（15）

只要不断while( cin >> s)并且判断s[2] == 'T'，将对应数字加入密码字符串即可。

1077 - 互评成绩计算（20）

可以存储maxn和minn，计算sum再删掉即可，难度不大。

1078 - 字符串压缩与解压（20）

压缩：一次遍历，一个计数，一个临时存储判断，遇到不同的就压缩进去。

解压：判断数字or字母，字母则输出，数字则取下一个然后加倍输出。

1079 - 延迟的回文数（20）

利用algorithm中的reverse可以把字符串快速反转过来，然后转换成数字相加得到下一个值。

可以像柳婼的思路，写一个类似全加器的算法~考虑到进位的问题。

也可以每次把两个数都读出来，再进行计算。

1080 - Mooc期终成绩（25）

关键在于定义好数据结构和map，看清题目以后，按照需求进行处理就可以了~

将练习中出现的问题进行整理。

int to string 的转换

1
2
#include <string>
string num = to_string(sum);

string to int 的转换

  • 对于每一个char类型a,只需要a - '0'即可。
  • 利用stoi()函数进行转换。

使用greater<int>

#include <functional> //greater<int>

set_difference()

对比两个set之间的区别，最后是插入到一个新的set中。

1
std::set_difference(nums.begin(), nums.end(), result.begin(), result.end(), inserter(v, v.begin()));

迭代器

迭代器的定义：set<int>::iterator it

初始值：v.begin()

循环条件：it != v.end()

注意，迭代器不能往回走，只能前进。

1
2
3
4
for (set<int>::iterator it = v.begin(); it != v.end(); ++it)
	{
		printRes = printRes + to_string(*it) + " ";
	}

去掉字符串结尾空格的办法

寻找到最后一个不是空格的元素，再+1，erase掉。

1
printRes.erase(printRes.find_last_not_of(" ")+1);

erase的用法

erase的原型有三个：
（1）string& erase ( size_t pos = 0, size_t n = npos );
（2）iterator erase ( iterator position );
（3）iterator erase ( iterator first, iterator last );
也就是说有三种用法：
（1）erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
（2）erase(position);删除position处的一个字符(position是个string类型的迭代器)
（3）erase(first,last);删除从first到last之间的字符（first和last都是迭代器）

C++中利用find_first_of等进行匹配

1
int find_first_of(char c, int start = 0):

查找字符串中第1个出现的c,由位置start开始。
如果有匹配，则返回匹配位置；否则，返回-1.默认情况下，start为0，函数搜索整个字符串。

1
int find_last_of(char c):

查找字符串中最后一个出现的c。有匹配，则返回匹配位置；否则返回-1.

类似的还有find_last_not_of

判断是否为素数

1
2
3
4
5
bool isprime(int a) {
    for (int i = 2; i * i <= a; i++)
        if (a % i == 0) return false;
    return true;
}

求最大公约数

辗转相除法：

1
2
3
long long int gcd(long long int t1, long long int t2) {
    return t2 == 0 ? t1 : gcd(t2, t1 % t2);
}

结构体！一定要想起来！

重构小于比较

在结构体外，比较的时候，参数就需要两个元素。

1
2
3
4
bool operator < (mooncake a, mooncake b)
{
	return a.unit > b.unit;
}

while (cin >> temp_num && cin >> temp_index)

在条件这里直接cin输入，如果没有足够的数据，就不会继续循环了。

字符串的substr()

返回一个子串拷贝的对象，分别是pos和len。

substr (size_t pos = 0, size_t len = npos) const;```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
### 关于String的find()函数
`find()`函数在找不到指定值的情况下会返回`string::npos`
其中`string::npos`也可以表示`直到字符串结束`
### 留心输入为空的情况
这个时候要使用`getline`而不能用`cin` >>
### 对1000000007取模的原因
1000000007有八个零，一共十位。
1. 1000000007是个质数
2. int_32位的最大值为2147483647，所以对于int32位来说1000000007足够大
3. int_64位的最大值为2^63-1，对于1000000007来说它的平方不会在int64中溢出
4. 所以在大数相乘的时候，因为(a∗b)%c=((a%c)∗(b%c))%c，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出
### `set`的查找
如果没有找到就会遍历到结尾。
```C++
if(ss.find(id) == ss.end()) {
    ss.insert(id);
}

最后-。-，第一次考PAT乙级，因为超时只有94分…