第二次pta认证P测试C++

测试C++"/>

第二次pta认证P测试C++

#include <iostream>
using namespace std;
int f(int n){if (n==0){return 1;}if (n==1){return 3;}return 4*f(n-1)-f(n-2);
}
int n;
int main()
{cin>>n;cout<<f(n);return 0;
}

第二题

试题编号：2022-13-0302
试题名称：长正整数相加
时间限制： 1.0s
内存限制： 128.0MB
【问题描述】
输入两个十进制正整数 M 和 N，求它们的和，结果用十进制表示。注意，M
和 N 可能非常大。
【输入描述】
第一行包含一个正整数 M（1≤M<10100）；
第二行包含一个正整数 N（1≤N<10100）。
【输出描述】
输出一个正整数，表示计算结果。
【输入样例】
769584695655486596597654685486745
452537865655768856564568658
【输出样例】
769585148193352252366511250055403
【题目解析】
本题考察数组与字符串处理，及其与循环、分支的综合运用。以字符串输
入，按照列竖式方式求解即可。需要注意进位情况的处理。如果使用
std::string 和 std::reverse 则可简化代码。

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;const int MAXN=10005;
int a[MAXN],b[MAXN],c[MAXN],ans[MAXN],len_a,len_b,len_ans;void read(int *a,int &len){string s;cin >> s;len=s.length();for (int i = 0; i < len; ++i){a[i]=s[i]-48;}reverse(a,a+len);
}
int main(){//高精度加法//读入两个加数,存入数组中read(a,len_a);read(b,len_b);len_ans=max(len_a,len_b);//进行相加操作for (int i = 0; i <= len_ans; ++i){ans[i] = a[i]+b[i]+c[i];if (ans[i]>9){//大于9，需要进位c[i+1]=ans[i]/10;ans[i]-=10;}}if (ans[len_ans]>0){//最高位进位了，整体长度+1len_ans+=1;}//输出结果for (int i = len_ans-1; i >= 0; --i){cout << ans[i];}cout << endl;return 0;
}

第三题

试题编号：2022-13-0203
试题名称：研究生入学考试
时间限制： 1.0s
内存限制： 128.0MB
【问题描述】
一年一度的研究生入学考试结束了，招生办的老师打算对所有的考生进行
成绩排名，从而确定复试的名单。排名的规则如下：(1)以入学考试的平均成绩
作为排名的依据（分数均为整数）；(2)对于考生 A，如果总共有 K 个考生的平
均成绩比 A 要高，那么 A 的排名为 K+1；(3)如果考生 A 和考生 B 的平均成绩相
同，则他们的排名也相同。招生办的老师希望你能编写一个程序，来帮助他们
解决这个问题。
【输入描述】
第一行为一个整数 N（1≤N≤1000），表示考生的人数。随后有 N 行，每
一行有两个非负整数描述了一位考生的信息，依次为准考证号和平均成绩。其
中，准考证号不超过 8 位，平均成绩不超过 200。
【输出描述】
输出共有 N 行，按照名次从高到低每行输出一位考生的信息，包括名次、
准考证号和平均成绩。如果两位考生的名次相同，则以准考证号为序，考号小
的在前，大的在后。
【输入样例】
5
1000 95
1001 100
1002 94
1006 95
1007 100
【输出样例】
1 1001 100
1 1007 100
3 1000 95
3 1006 95
5 1002 94

#include <iostream>
#include <algorithm>
using namespace std;
int n,num=1;
struct student{int id;int score;
};
student s[1001];
bool compare(student s1,student s2){if (s1.score>s2.score){return true;} else if (s1.score==s2.score){if (s1.id<s2.id){return true;}}return false;
}
int main()
{cin>>n;for (int i = 0; i < n; ++i){cin>>s[i].id>>s[i].score;}sort(s,s+n,compare);for (int i = 0; i < n; ++i){if (s[i].score!=s[i-1].score){//与前一个成绩相同，排名不变num=i+1;}cout << num << " " << s[i].id << " " << s[i].score << endl;}return 0;
}

第四题

试题编号：2022-13-0203
试题名称：跷跷板
时间限制： 1.0s
内存限制： 128.0MB
【题目描述】
游乐场的跷跷板以力矩相等原则判断是否平衡。即如果 wldl = wrdr，则认
为跷跷板是平衡的。此处，wl、wr分别表示跷跷板左右两侧的物体体重，dl、dr
分别表示左右两侧物体到跷跷板中央支点的距离。扩展跷跷板为多层结构，即
wl与 wr均可以用子跷跷板代替。此时当且仅当所有子跷跷板都是平衡的，才称
跷跷板为平衡的。
【输入描述】
采用递归方式输入数据。每行数据描述一个跷跷板。每行数据为用空格分
隔的 4 个非负整数，分别表示 wl、dl、wr、dr。当 wl或 wr为 0 时，表示该物体实
际上为一个子跷跷板，而接下来的数据将对该子跷跷板进行描述。而当 wl和 wr
均为 0 时，先描述左子跷跷板，后描述右子跷跷板。因此，多层跷跷板的数据
表示可总结为：先左后右，深度优先。
【输出描述】
如果该多层跷跷板为平衡的，输出 1，否则输出 0。
【输入样例】
0 1 0 3
0 3 0 2
4 1 2 2
6 1 3 2
3 4 2 6
【输出样例】
1

第五题

试题编号：2022-13-0305
试题名称：最萌身高差
时间限制： 1.0s
内存限制： 128.0MB
【问题描述】
有 N 位同学获得了奖学金，现要从中选出两位代表上台领奖。出于“审
美”要求，希望选出的两位代表 A 和 B 满足：A 的身高比 B 高，A 获得的奖学金
比 B 多，且奖学金的差额大于 M。请计算选取上台同学的方案数。
【输入描述】
第一行包含两个正整数 N 和 M；
第二行包含 N 个正整数 Si，分别代表第 i 位同学获得的奖学金。输入顺序
在前的同学身高较高。
【输出描述】
输出一个正整数，表示方案数。
【输入样例】
6 2
6 5 4 3 2 1
【输出样例】
6
【数据范围】
30%的数据满足：1<= N<= 100；
100%的数据满足：
1<= N<= 100000，1<= M<= 100000，1<= Si<= 100000。
【题目解析】
对 30%的数据，可以考虑逐次使用冒泡排序+二分查找完成。
对 100%的数据，可以考虑采用归并排序的思路通过分治递归求解，也可以考虑
使用线段树优化查找。