PAT乙级真题（2014·冬）

大纲

1031、查验身份证-（解析）-简单题

1032、挖掘机技术哪家强-（解析）-细节题(┬┬﹏┬┬)，太抠细节了

1033、旧键盘打字-（解析）-输入格式！这才是重点(┬┬﹏┬┬)，让我多瞧了20分钟

1034、有理数四则运算-（解析）-该死的，long long，坏我青春(┬┬﹏┬┬)

1035、插入与归并-（解析）-插入排序与归并排序方法

题目

1031、查验身份证

一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：

首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；然后将计算的和对11取模得到值Z；最后按照以下关系对应Z值与校验码M的值：

Z：0 1 2 3 4 5 6 7 8 9 10
M：1 0 X 9 8 7 6 5 4 3 2

现在给定一些身份证号码，请你验证校验码的有效性，并输出有问题的号码。

输入格式：

输入第一行给出正整数N（≤100）是输入的身份证号码的个数。随后N行，每行给出1个18位身份证号码。

输出格式：

按照输入的顺序每行输出1个有问题的身份证号码。这里并不检验前17位是否合理，只检查前17位是否全为数字且最后1位校验码计算准确。如果所有号码都正常，则输出All passed。

输入样例1：

4
320124198808240056
12010X198901011234
110108196711301866
37070419881216001X

输出样例1：

12010X198901011234
110108196711301866
37070419881216001X

输入样例2：

2
320124198808240056
110108196711301862

输出样例2：

All passed

#include <iostream>
using namespace std;
// 简单题
int main(){int n;cin>>n;char arr[11]{'1','0','X','9','8','7','6','5','4','3','2'};int num[]{7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};string str;bool flag = false;while(n--){cin>>str;int sum=0;for(int i=0; i<str.size()-1; ++i){sum += (int)(str[i]-'0')*num[i];}if(str[str.size()-1] != arr[sum%11]){// cout<<str[str.size()-1]<<" "<<arr[sum%11]<<endl;cout<<str<<endl;flag = true;}}if(!flag) cout<<"All passed"<<endl;return 0;
}

1032、挖掘机技术哪家强

为了用事实说明挖掘机技术到底哪家强，PAT 组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入格式：

输入在第 1 行给出不超过 105 的正整数 N，即参赛人数。随后 N 行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从 1 开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。

输出格式：

在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

输入样例：

6
3 65
2 80
1 100
2 70
3 40
3 0

输出样例：

2 150

#include <iostream>
using namespace std;
// 又是一道细节题(┬┬﹏┬┬)，num_max不能为0极其以上，太抠细节了
int main(){long long data[100005]={0}; // 总得分,全局会自动初始化long long n;cin>>n;long long id,f;for(int i=0; i<n; ++i){cin>>id>>f;data[id]+=f;}long long id_max=0,num_max=-1;for(int i=1; i<=n; ++i){if(data[i]>num_max){id_max = i;num_max = data[i];}}cout<<id_max<<" "<<num_max<<endl;return 0;
}

1033、旧键盘打字

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及坏掉的那些键，打出的结果文字会是怎样？

输入格式：

输入在 2 行中分别给出坏掉的那些键、以及应该输入的文字。其中对应英文字母的坏键以大写给出；每段文字是不超过 105 个字符的串。可用的字符包括字母 [a-z, A-Z]、数字 0-9、以及下划线 _（代表空格）、,、.、-、+（代表上档键）。题目保证第 2 行输入的文字串非空。

注意：如果上档键坏掉了，那么大写的英文字母无法被打出。

输出格式：

在一行中输出能够被打出的结果文字。如果没有一个字符能被打出，则输出空行。

输入样例：

7+IE.
7_This_is_a_test.

输出样例：

_hs_s_a_tst

#include <iostream>
#include <cctype>
using namespace std;
// !!!!在两行中，这种输入格式！这才是重点(┬┬﹏┬┬)，让我多瞧了20分钟
int main(){// 大写在内，小写一定打不出string str,in_str;getline(cin,str);getline(cin,in_str);bool flag = false;if(str.find('+')!=string::npos) flag = true;for(char c : in_str){if(flag&&isupper(c)) continue;if(str.find(toupper(c))!=string::npos) continue; // 不能被打印cout<<c;}return 0;
}

1034、有理数四则运算

本题要求编写程序，计算 2 个有理数的和、差、积、商。

输入格式：

输入在一行中按照 a1/b1 a2/b2 的格式给出两个分数形式的有理数，其中分子和分母全是整型范围内的整数，负号只可能出现在分子前，分母不为 0。

输出格式：

分别在 4 行中按照 有理数1 运算符 有理数2 = 结果 的格式顺序输出 2 个有理数的和、差、积、商。注意输出的每个有理数必须是该有理数的最简形式 k a/b，其中 k 是整数部分，a/b 是最简分数部分；若为负数，则须加括号；若除法分母为 0，则输出 Inf。题目保证正确的输出中没有超过整型范围的整数。

输入样例 1：

2/3 -4/2

输出样例 1：

2/3 + (-2) = (-1 1/3)
2/3 - (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)

输入样例 2：

5/3 0/6

输出样例 2：

1 2/3 + 0 = 1 2/3
1 2/3 - 0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf

#include <iostream>
#include <cmath>
using namespace std;
// 该死的，long long，坏我青春(┬┬﹏┬┬)
// 修改后的gcd函数，始终返回正数
long long gcd(long long a, long long b) {a = abs(a);b = abs(b);return b != 0 ? gcd(b, a % b) : a;
}void get_str(long long a, long long b) {// 处理分母为0的情况if (b == 0) {cout << "Inf";return;}// 处理分子为0的情况if (a == 0) {cout << 0;return;}// 计算最大公约数并约分long long n = gcd(a, b);a /= n;b /= n;// 确保分母为正if (b < 0) {a = -a;b = -b;}// 判断是否需要负号bool is_negative = (a < 0);if (is_negative) {cout << "(-";a = -a; // 将分子转为正数处理}// 输出带分数或真分数if (b == 1) {cout << a;} else {if (a >= b) {cout << a / b << " ";a %= b;}cout << a << "/" << b;}if (is_negative) {cout << ")";}
}int main() {long long a1, b1, a2, b2;scanf("%lld/%lld %lld/%lld", &a1, &b1, &a2, &b2);// 加法get_str(a1, b1);cout << " + ";get_str(a2, b2);cout << " = ";get_str(a1 * b2 + a2 * b1, b1 * b2);cout << endl;// 减法get_str(a1, b1);cout << " - ";get_str(a2, b2);cout << " = ";get_str(a1 * b2 - a2 * b1, b1 * b2);cout << endl;// 乘法get_str(a1, b1);cout << " * ";get_str(a2, b2);cout << " = ";get_str(a1 * a2, b1 * b2);cout << endl;// 除法get_str(a1, b1);cout << " / ";get_str(a2, b2);cout << " = ";if (a2 == 0) {cout << "Inf"; // 处理除数为0的情况} else {get_str(a1 * b2, a2 * b1);}cout << endl;return 0;
}

1035、插入与归并

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例 1：

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例 2：

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例 2：

Merge Sort
1 2 3 8 4 5 7 9 0 6

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 虽然核心是快速排序，与归并排序
// 当时也有许多小核心，输入格式，严格-ACM// 归并排序
void merge(vector<int>& vec, int st, int mid, int en){int i=st,j=mid+1,k=0;vector<int> temp(en-st+1,0);while(i<=mid&&j<=en){if(vec[i]<=vec[j]){temp[k++] = vec[i++];}else{temp[k++] = vec[j++];}}while(i<=mid) temp[k++] = vec[i++];while(j<=en) temp[k++] = vec[j++];for(int z=st; z<=en; ++z){vec[z] = temp[z-st];}
}int main(){int n;cin>>n;vector<int> source(n,0);vector<int> temp(n,0);for(int i=0; i<n; ++i) cin>>source[i];for(int i=0; i<n; ++i) cin>>temp[i];// 判断是否是插入排序vector<int> copy_num = source;for(int i=1; i<n; ++i){ // 开始判断int key = copy_num[i];int j = i - 1;while(j>=0&&copy_num[j]>key){copy_num[j+1]=copy_num[j];j--;}copy_num[j+1] = key;if(equal(copy_num.begin(),copy_num.end(),temp.begin())){ // 如果相同i++; // 下一步if(i != n){int key = copy_num[i];int j = i-1;while(j>=0&&copy_num[j]>key){copy_num[j+1]=copy_num[j];j--;}copy_num[j+1] = key;}cout<<"Insertion Sort"<<endl;for(int i=0; i<copy_num.size(); ++i){if(i!=copy_num.size()-1) cout<<copy_num[i]<<" ";else cout<<copy_num[i];}return 0;}}// 判断是否为合并vector<int> Merge_sort = source;int step = 1;int len = Merge_sort.size();bool flag = false;while(step<len){int st,mid,en;for(int i=0; i<len; i+=2*step){st = i;mid = min(i+step-1,len-1); // 刚好就是边界的位置en = min(i+2*step-1,len-1);merge(Merge_sort,st,mid,en);}if(flag){cout<<"Merge Sort"<<endl;for(int i = 0; i<Merge_sort.size(); ++i){if(i!=Merge_sort.size()-1) cout<<Merge_sort[i]<<" ";else cout<<Merge_sort[i];}return 0;}if(equal(Merge_sort.begin(),Merge_sort.end(),temp.begin())){flag = true;}step = 2*step;}return 0;
}

知识点

一、加权求和 :: 数学知识 ::

加权求和是一种数学运算方法，通过对不同数据赋予不同权重，以综合考虑各数据的重要程度或影响比例，从而得到一个总体的评估值或结果。以下是其详细解释：

基本原理

• 权重的定义 ：权重是一个大于等于 0 的数值，表示某个数据在整体中的相对重要性或所占的比例。权重越大的数据，在加权求和中的影响力也越大。

• 计算方法 ：将每个数据分别乘以对应的数据，然后将所有的乘积相加，得到的结果即为加权求和的结果。假设有一组数据为 x1​,x2​,…,xn​，对应的权重为 w1​,w2​,…,wn​，则加权求和的结果 S 可以表示为：S=w1​x1​+w2​x2​+⋯+wn​xn​。

与简单求和的区别

• 简单求和 ：简单求和是将所有的数据直接相加，不考虑各个数据之间的差异和重要性，认为每个数据对总和的贡献是相等的。

• 加权求和 ：加权求和则充分考虑到了不同数据的重要程度不同，通过对数据进行加权处理，使得重要的数据在总和中占据更大的比重，从而更准确地反映数据的实际情况和整体特征。

二、排序 :: 基础学习 ::

• 插入排序：是一种简单直观的比较式排序算法。它的原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。（稳定排序）
• 归并排序：归并排序的核心思想是分治，我需要先把它拆分成小问题，然后递归地解决这些小问题，最后合并结果。（稳定排序）

插入排序：

插入排序：是一种简单直观的比较式排序算法。它的原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。（稳定）

#include <iostream>
using namespace std;
int arr[5]{1,29,31,4,5};
void insertSort(){ // 插入排序for(int i=1; i<5; i++){int j = i-1;int key = arr[i];while(j>=0&&key<arr[j]){arr[j+1] = arr[j];j--;}arr[j+1] = key;}for(int c:arr) cout<<c<<" ";
}
int main(){insertSort();return 0;
}

归并排序：

归并排序：归并排序的核心思想是分治，我需要先把它拆分成小问题，然后递归地解决这些小问题，最后合并结果。（稳定）

递归：

#include <iostream>
using namespace std;void merge(int arr[], int res[], int st, int mid, int en){ // 合并int i = st, j=mid+1, k = st;while(i<=mid && j<=en){if(arr[i]<=arr[j]){res[k++] = arr[i];i++;}else{res[k++] = arr[j];j++;}}while(i<=mid){res[k++] = arr[i++];}while(j<=en){res[k++] = arr[j++];}
}void mergeSort(int arr[], int res[], int st, int en){ // 数组传入本来就是引用if(st<en){ // 可以合格int mid = st+(en-st)/2;mergeSort(arr,res,st,mid); // 分治mergeSort(arr,res,mid+1,en); // 分治// 进行合并merge(arr,res,st,mid,en);}
}
int main(){int arr[5]{1,29,31,4,5};int res[5]; // 结果集合mergeSort(arr,res,0,4); // for(int i:res) cout<<i<<" ";return 0;
}

非递归方式：

#include <iostream>
using namespace std;void merge(int arr[], int st, int mid, int en){ // 合并出来的嘟int i = st,j = mid+1,k = 0;int temp[en-st+1]; // 临时数组while(i<=mid&&j<=en){if(arr[i]<=arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}while(i<=mid) temp[k++] = arr[i++];while(j<=en) temp[k++] = arr[j++];for(int z = st; z<=en; ++z) arr[z] = temp[z-st];
}// 主打一个事情的两面性
int main(){int arr[6]{1,2,6,2,8,1};int step = 1;int len = sizeof(arr)/sizeof(int); // 计算的长度while(step<len){ // 是计算字节的int st,mid,en;for(int i=0; i<len; i+=2*step){// 计算出来两个数组st = i;mid = min(st+step-1,len-1);en = min(st+2*step-1,len-1);// 合并merge(arr,st,mid,en); // 传入的刚好都是边界}step = 2*step;}for(int i:arr) cout<<i<<" ";return 0;
}

三、取模

最开始的灵魂3问：

• 负数与负数之间 (-7/-3)
• 负数与正数之间 (-7/3)
• 正数与负数之间 (7/-3) 

都是如何取模的？

在C++中，取模运算（%）和除法运算（/）的行为遵循以下规则：

1. 除法运算的符号规则：
   商的值总是向上取整。例如：

   • 7 / -3 的计算结果是 -2（因为 7 ÷ (-3) ≈ -2.33，向零取整后为 -2）。

   • -7 / 3 的结果是 -2，而 -7 / -3 的结果是 2。

2. 取模运算的符号规则：
   余数的符号的始终与被除数保持一致。例如：

   • 7 % -3 的余数是 1（因为 7 = (-3) * (-2) + 1，余数符号与被除数 7 一致）。

   • -7 % 3 的余数是 -1（因为 -7 = 3 * (-2) + (-1)，余数符号与被除数 -7 一致）。

3. 数学恒等式：
   对于所有整数 a 和 b（b ≠ 0），始终满足：
   a = （a/b）*b + a%b;

---

借鉴博客、视频：

1、排序——归并排序（Merge sort）

2、插入排序（动画）

3、归并排序（动画）

3、归并排序（视频 C版） 

---