PAT甲级真题刷题笔记

持续更新，记得点赞收藏关注！

英文专题

polynomials 多项式即形如a x^b + c x^d
exponents and coefficients 指数和系数
tie 平局
radix基数

题目按分类

//省心万能头文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;
int main()
{/*code*/return 0;
}

简单

1006

#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
struct person{string name;string time1;string time2;
};
bool cmp1(person a,person b){return a.time1<b.time1;
}
bool cmp2(person a,person b){return a.time2>b.time2;
}
int main(){int n;cin>>n;person p[n];for(int i=0;i<n;i++)cin>>p[i].name>>p[i].time1>>p[i].time2;sort(p,p+n,cmp1);cout<<p[0].name<<' ';sort(p,p+n,cmp2);cout<<p[0].name;return 0;
}

1011
坑：题意理解上是取每行最大的数

def change(num):if(num==0):return 'W'if(num==1):return 'T'if(num==2):return 'L'max_index=[]
profit=1
for i in range(0,3):in_str=[float(i) for i in input().split()]max_=max(in_str)#print(max_)profit*=max_for i in range(len(in_str)):if(in_str[i]==max_):max_index.append(i)profit*=0.65
profit-=1for i in max_index:print(change(i),end=' ')
print('{:.2f}'.format(profit*2))

数字数学问题

gcd +prime number素数+conversion of number systems进制转换+高精度加减乘除

1002 A+B for Polynomials

注意坑：

Please be accurate to 1 decimal place.
系数为0时不输出即可，没必要非得删掉
有可能输入的同一行中有许多相同指数
这道题用python麻烦，不一定能拿全分

list.sort( key=None, reverse=False)
# 创建一个包含元组的列表
my_list= [(3, 5), (1, 2), (2, 6), (4, 1), (5, 5)]

# 使用lambda表达式按元组的第二个元素对列表进行排序（升序）
my_list.sort(key=lambdax: x[1])

# 输出排序后的列表
print(my_list)
# Output: [(4, 1), (1, 2), (3, 5), (5, 5), (2, 6)]list = sorted(iterable, key=None, reverse=False)  
其中，iterable 表示指定的序列，key 参数可以自定义排序规则，可以接受一个函数，该函数的功能是指定 sorted() 函数按照什么标准进行排序；#自定义按照字符串长度排序
print(sorted(chars,key=lambda x:len(x)))print(a,end='')#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
bool cmp(pair<int,double> a,pair<int,double> b){return a.first>b.first;
}
int main(){map<int,double>poly;int n,a;double b;for(int j=0;j<2;j++){cin>>n;for(int i=0;i<n;i++){cin>>a;cin>>b;poly[a]+=b;}}vector<pair<int,double>> ans(poly.begin(),poly.end());//构造函数 没有等号sort(ans.begin(),ans.end(),cmp);int cnt=0;for(auto it=ans.begin();it!=ans.end();it++){if((*it).second)cnt++;}cout<<cnt;for(auto it=ans.begin();it!=ans.end();it++){if((*it).second)printf(" %d %.1lf",(*it).first,(*it).second);}return 0;
}

1009 多项式乘法

#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,double> a,pair<int,double> b){return a.first>b.first;
}
int main(){map<int,double> poly;map<int,double> ans_poly;int m,n,ex;double co;cin>>n;for(int i=0;i<n;i++){cin>>ex>>co;poly[ex]=co;}cin>>m;for(int i=0;i<m;i++){cin>>ex>>co;for(auto p=poly.begin();p!=poly.end();p++ ){int new_ex=(*p).first+ex;ans_poly[new_ex]+=((*p).second*co);//cout<<(*p).second<<" "<<co<<" "<<(*p).second*co<<endl;}}vector<pair<int,double>> ans(ans_poly.begin(),ans_poly.end());sort(ans.begin(),ans.end(),cmp);int cnt=0;for(auto it=ans.begin();it!=ans.end();it++){if((*it).second)cnt++;}cout<<cnt;for(auto it=ans.begin();it!=ans.end();it++){if((*it).second)printf(" %d %.1lf",(*it).first,(*it).second);}return 0;
}

1010 进制转换
不知道为啥没拿满分

dic={'a':10,'b':11,'c':12,'d':13,'e':14,'f':15,'g':16,'h':17,'i':18,'j':19,'k':20,'l':21,'m':22,'n':23,'o':24,'p':25,'q':26,'r':27,'s':28,'t':29,'u':30,'v':31,'w':32,'x':33,'y':34,'z':35}
list_=[i for i in range(10,36)]
def change(a,from_):
#from_进制的a转换成10进制num=0cnt=0for i in range(len(a)-1,-1,-1):if(a[i].isdigit()):num+=int(a[i])*(int(from_)**cnt)else:'''for key,value in dic.items():if(a[i]==key):num+=value*(int(from_)**cnt)break'''value=list_[ord(a[i])-ord('a')]#print('value',a[i],value)num+=value*(int(from_)**cnt)cnt+=1return numin_str=input().split()
n1,n2,tag,radix=in_strif(tag==2):n1,n2=n2,n1 #始终使n1是radix进制的数
#最终均转换成10进制比对
n1=change(n1,radix)
for i in range(1,n1+1):if(change(n2,i)==n1):print(i)exit()
#print(change(n2,16))
print("Impossible")

模拟

1012
题意比较难理解
实现有技巧，不然代码会很长

技巧之处：
bool cmp(student a,student b){//按单个科目分数进行降序排序return a.score[flag]>b.score[flag];
}
for(flag=0;flag<4;flag++){sort(stu,stu+n,cmp);for(int j=0;j<n;j++){//判断如果该学生该成绩与上一名次的学生该成绩一样，则名次也应一样if(j>=1&&stu[j].score[flag]==stu[j-1].score[flag])stu[j].rank[flag]=stu[j-1].rank[flag];//否则就记录正常名次else stu[j].rank[flag]=j;//判断学生名次最佳的是哪门课目 记录最佳科目的下标if(stu[j].rank[flag]<stu[j].rank[stu[j].best])stu[j].best=flag;}}/
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int flag;
struct student{int best;int id;int score[4];int rank[4];
};bool cmp(student a,student b){//按单个科目分数进行降序排序return a.score[flag]>b.score[flag];
}int main()
{int n,m;const char z[4]={'A','C','M','E'};scanf("%d %d",&n,&m);student stu[2005];for(int i=0;i<n;i++){cin>>stu[i].id>>stu[i].score[1]>>stu[i].score[2]>>stu[i].score[3];//计算平均数stu[i].score[0]=(stu[i].score[1]+stu[i].score[2]+stu[i].score[3])/3;stu[i].best=0;}for(flag=0;flag<4;flag++){sort(stu,stu+n,cmp);for(int j=0;j<n;j++){//判断如果该学生该成绩与上一名次的学生该成绩一样，则名次也应一样if(j>=1&&stu[j].score[flag]==stu[j-1].score[flag])stu[j].rank[flag]=stu[j-1].rank[flag];//否则就记录正常名次else stu[j].rank[flag]=j;//判断学生名次最佳的是哪门课目 记录最佳科目的下标if(stu[j].rank[flag]<stu[j].rank[stu[j].best])stu[j].best=flag;}}for(int i=0;i<m;i++){int num;cin>>num;for(int j=0;j<n;j++){if(stu[j].id==num){//因为记录名次是从0开始记录，所以输出应该+1printf("%d %c\n",stu[j].rank[stu[j].best]+1,z[stu[j].best]);break;}if(j==n-1){printf("N/A\n");}}}return 0;
}

排序、查找、二分

贪心

动态规划

方法：1. 枚举 o(n^3)
2. 记录前缀和的预处理o(n^2)
3. 动态规划法o(n)
设置数组dp[]，dp[i]表示以a[i]结尾的连续序列最大和
单个元素时dp[i]=a[i]
多个元素时dp[i]=dp[i-1]+a[i]
则状态转移方程dp[i]=max{a[i],dp[i-1]+a[i]} (i:1~n枚举)

//无需输出最大子序列头尾版本
#include <iostream>
using namespace std;
int main()
{int n, m, sum = 0, max_sum = 0;cin >> n;for (int i = 0; i < n; ++i){cin >> m;sum = ((sum += m) > 0 ? sum : 0);max_sum = (sum > max_sum ? sum : max_sum);}cout << max_sum;
}

1007 Maximum Subsequence Sum
老题新出

坑：1. 不是传统的只是求出最大和还要输出组成最大和的第一个元素和最后一个元素
要求i,j都尽可能小，则组成最大和的第一个元素一定是序列左边第一个正数

#include <iostream>
#include <vector>using namespace std;int main()
{int n, sum = 0, max_sum = -1, former = 0, latter, former_tmp = 0; //former,latter记录最大子序列的首位index，//max_sum=-1考虑0的存在，former_tmp必须赋初值(考虑第一个数是0的情况)cin >> n;latter = n - 1; //全为负数时输出序列的首位两个数vector<int> seq(n);for (int i = 0; i < n; ++i){scanf("%d", &seq[i]);sum += seq[i];if (sum < 0)//同理dp的思想，已经<0了则前面整段扔掉，将下一位作为头开始{sum = 0;former_tmp = i + 1; //former_tmp定位可能的最大子序列头index}else if (sum > max_sum){max_sum = sum;former = former_tmp;latter = i;}}max_sum = (max_sum < 0 ? 0 : max_sum);//考虑全为负数的情况cout << max_sum << " " << seq[former] << " " << seq[latter];
}//基于传统模版上的做法
#include <cstdio>
#include <cstring>
const int maxn=10010;struct node
{int start,end;int sum;int value;
}dp[maxn];
int main()
{int k;scanf("%d",&k);for(int i=0;i<k;++i){scanf("%d",&dp[i].value);}int maxsum=dp[0].value;dp[0].sum=dp[0].value;dp[0].start=0;dp[0].end=0;for(int i=1;i<k;++i){if(dp[i].value+dp[i-1].sum>=dp[i].value){dp[i].sum=dp[i].value+dp[i-1].sum;dp[i].start=dp[i-1].start;dp[i].end=i;}else{dp[i].sum=dp[i].value;dp[i].start=i;dp[i].end=i;}maxsum=maxsum>dp[i].sum?maxsum:dp[i].sum;}if(maxsum<0){printf("0 %d %d\n",dp[0].value,dp[k-1].value);}else{printf("%d ",maxsum);for(int i=0;i<k;++i){if(maxsum==dp[i].sum){printf("%d %d\n",dp[dp[i].start].value,dp[dp[i].end].value);break;}}}return 0;
}

栈、队列、链表

堆

树、图、并查集

1003 最短路径问题

思路：图最好还是用c/c++写
朴素dijkstra(有向图改一改可以解决无向图)
book数组分成两个集合 y已确定最短距离的点 or u未确定的点
1.dist[1]=0,其他均为max
2.for 依次遍历所有点，将u中选择最短的点加入y，将该点挨个更新其他点的距离

坑：1. 输出的是到目的城市的最短路径的不同路线的数量
这个也要设一个数组num，存放到各城市的不同路线的数量，更新的时候进行操作：
如果满足更新条件即旧路线比新的长，目的城市不同路线的数量要变更，之前这个num对应的记录作废
如果只是新旧一样长，目的城市不同路线的数量直接加上“引发新路线“的该中间节点的不同路线数量

输出经过最短路径得到的最多的rescue teams
这个就是最短路径中最大的结点权值和，这个也是设一个数组w，初始化以及起始城市本来就有teams，
更新的时候进行操作：
如果满足更新条件即旧路线比新的长，之前的路线以及w记录全部作废，挨个变更为到该城市后总共的teams+=该城市自带的teams+中间节点带的teams
如果只是新旧一样长，对比一下原来的w和[该城市自带的teams+中间节点带的teams]的新w，哪个大则选哪个

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int n=501;
int num_city,num_r,c_now,c_dis;
bool book[n]={0};
int teams[n];//the number of rescue teams 
int dist[n];
int graph[n][n];
int w[n] = {0};
int num[n] = {0};
int dijkstra(int c_now,int c_dis){memset(dist,0x3f,sizeof dist);dist[c_now]=0;w[c_now]=teams[c_now];//自己自带的num[c_now]=1;for(int i=0;i<num_city;i++){ //n-1次才能遍历全int min_index=-1;for(int j=0;j<num_city;j++){ //找出当前有最短路线的节点if(!book[j]&&(min_index==-1||dist[min_index]>dist[j]))min_index=j;}book[min_index]=true;//当作中间点for(int j=1;j<num_city;j++)//利用中间点更新其他节点的最短路径数值if(dist[min_index]+graph[min_index][j]<dist[j]){w[j]=teams[j]+w[min_index];dist[j]=dist[min_index]+graph[min_index][j];num[j]=num[min_index];}else if(dist[min_index]+graph[min_index][j]==dist[j]){if(teams[j]+w[min_index]>w[j])w[j]=teams[j]+w[min_index];num[j]+=num[min_index];}if(min_index==c_dis)break;//优化，提前结束}if(dist[c_dis]==0x3f)return -1;//没有一条路径能到dis城市return num[c_dis];
}
int main(){memset(graph,0x3f,sizeof graph);cin>>num_city>>num_r>>c_now>>c_dis;int c1,c2,r_len;for(int i=0;i<num_city;i++){cin>>teams[i];}for(int j=0;j<num_r;j++){cin>>c1>>c2>>r_len;graph[c1][c2]=min(graph[c1][c2],r_len);graph[c2][c1]=min(graph[c2][c1],r_len);}// for(int i=0;i<num_city;i++){//     for (int j=0;j<num_city;j++)//         cout<<graph[i][j]<<" ";//     cout<<endl;// }int cnt=dijkstra(c_now,c_dis);cout<<cnt<<" "<<w[c_dis]<<endl;return 0;
}复习：
memset(graph,0x3f,sizeof graph);
赋值的时候注意graph[c1][c2]=min(graph[c1][c2],r_len);
dijsktra基本思想

1004

坑：1. cin >> N >> M;适合于输入几个数之间只间隔空格的
cin>>x;
cin>>y; 这种是换行的
2.层序遍历事先设rear=1，当队列元素==rear时这是一层完成+出队，并同时更新rear等于现在的队尾元素

#基于层序遍历
tree = []  # id numofchild childid
q = []
in_str1 = input().split()
num = int(in_str1[0])
non_leaf = int(in_str1[1])
for i in range(non_leaf):in_str2 = [int(i) for i in input().split()]tree.append(in_str2)
temp_leaf = 0
all_leaf = num - non_leaf
rear = 1
q.append(1)
while (len(q)):p_id = q[0]find_it = 0for item in tree:if (item[0] == p_id):q+=(item[2:])find_it = 1if (find_it == 0):temp_leaf += 1if (p_id == rear):#最重要的部分在这里，什么时候知道是这一层的最后一个节点if (all_leaf > temp_leaf):print(str(temp_leaf)+' ', end='')all_leaf -= temp_leaftemp_leaf = 0rear = q[-1]else:print(temp_leaf, end='')all_leaf -= temp_leaftemp_leaf = 0del q[0]

#include<iostream>
#include<vector>
#include<queue>
using namespace std;int main(){int num,non_leaf,leaf;cin>>num>>non_leaf;int leaf_node=num-non_leaf;vector<int> tree[non_leaf];//第一个放父节点名字for(int i=0;i<non_leaf;i++){int id;int k;cin>>id>>k;//cout<<id<<endl;tree[i].push_back(id);while(k){int new_node;cin>>new_node;tree[i].push_back(new_node);k--;}}queue<int> q;q.push(01);int i,temp=0,sum=0,rear=1;printf("%d",sum);while(!q.empty()){sum+=temp;temp=0;int front=q.front();for(i=0;i<non_leaf;i++){if(tree[i].front()==front)break;}if(i==num or tree[i].size()==1  )temp+=1;else{vector<int>::iterator it=tree[i].begin();it++;for(; it!=tree[i].end();it++){q.push(*it);}}if(q.front()==rear){if(leaf_node>sum){cout<<sum<<" ";leaf_node-=sum;}else cout<<sum;sum=0;temp=0;rear=q.back();}q.pop();}return 0;
}