2021年PAT--春

Arithmetic Progression of Primes

In mathematics, an arithmetic progression (AP，等差数列) is a sequence of numbers such that the difference between the consecutive terms is constant. In 2004, Terence Tao (陶哲轩) and Ben Green proved that for any positive n, there exists at least one arithmetic progression consists of n consecutive prime numbers. For example, { 7，37，67，97，127，157 } is one solution for n=6. Now it is your job to find a maximum solution for a given n within a given range.

Input Specification:

Each input file contains one test case, which gives two positive integers in a line: n (≤10), the number of consecutive prime terms in an arithmetic progression, and MAXP (2≤MAXP<105), the upper bound of the largest prime in the solution.

Output Specification:

For each test case, if there exists a solution, print in ascending order the prime numbers in a line. If the solution is not unique, output the one with the maximum common difference. If there is still a tie, print the one with the maximum first number. If there is no solution bounded by MAXP, output the largest prime in the given range instead.

All the numbers in a line must be separated by a space, and there must be no extra space at the beginning or the end of the line.

Sample Input 1:

5 1000

Sample Output 1:

23 263 503 743 983

Sample Input 2:

10 200

Sample Output 2:

题意:给定n和m，要求你输出一个长度为n的素数且值不超过m的等差数列，如果多个，优先输出差值最大的，仍有多个，输出第一个数最大的序列。

解析:小暴力，直接跑一边求出m中所有素数，然后从大往小枚举差值和第一个素数，满足条件的话就是答案，直接退出即可，枚举差值时候如果从m开始就会超时，因此我们考虑第一个数是最小是2，差值是j，那么必须满足2+(n-1)*j<=m，因此m最大值就是(m-2)/(n-1)，因此可以减少一些复杂度，就不会超时了。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int> primes;
bool st[N];//判断一个数是否是素数
bool is_primes(int x)//判断素数
{if(x<=1) return false;for(int i=2;i<=x/i;i++) if(x%i==0) return false;return true;
}
void solve()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) if(is_primes(i)) primes.push_back(i),st[i]=true;if(n==1)//特判1,防止下面除0{printf("%d\n",primes.back());return;}for(int j=(m-2)/(n-1);j>=1;j--)//差值{for(int i=primes.size()-1;i>=0;i--){int x=primes[i],last=x;//第一个数vector<int> ans;ans.push_back(x);for(int p=2;p<=n;p++)//依次计算每个数{if(st[last+j]) ans.push_back(last+j),last+=j;else if(last+j>m||!st[last+j]) break;//不合法}if(ans.size()==n)//找到答案{for(int i=0;i<n;i++){if(i!=0) printf(" ");printf("%d",ans[i]);}printf("\n");return;}}}printf("%d\n",primes.back());//输出最后一个素数即可
}
int main()
{int t=1;//scanf("%d",&t);while(t--) solve();return 0;
}

Lab Access Scheduling

Nowadays, we have to keep a safe social distance to stop the spread of virus due to the COVID-19 outbreak. Consequently, the access to a national lab is highly restricted. Everyone has to submit a request for lab use in advance and is only allowed to enter after the request has been approved. Now given all the personal requests for the next day, you are supposed to make a feasible plan with the maximum possible number of requests approved. It is required that at most one person can stay in the lab at any particular time.

Input Specification:

Each input file contains one test case. Each case starts with a positive integer N (≤2×103), the number of lab access requests. Then N lines follow, each gives a request in the format:

hh:mm:ss hh:mm:ss

where hh:mm:ss represents the time point in a day by hour:minute:second, with the earliest time being 00:00:00 and the latest 23:59:59. For each request, the two time points are the requested entrance and exit time, respectively. It is guaranteed that the exit time is after the entrance time.

Note that all times will be within a single day. Times are recorded using a 24-hour clock.

Output Specification:

The output is supposed to give the total number of requests approved in your plan.

Sample Input:

7
18:00:01 23:07:01
04:09:59 11:30:08
11:35:50 13:00:00
23:45:00 23:55:50
13:00:00 17:11:22
06:30:50 11:42:01
17:30:00 23:50:00

Sample Output:

Hint:

All the requests can be approved except the last two.

题意:因为疫情，实验室同一时间只能呆一个人，现在有n个人的申请表，问你最多能批准几个。

解析: 贪心，根据结束时间和所占时间从小到大排序即可，因为结束时间早也就意味着剩下的时间越多，越有可能安排更多的人。

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
struct node
{int sx,sy,t;//开始,结束时间以及所占时间bool operator<(const node&s)const{if(sy!=s.sy) return sy<s.sy;//优先批准结束时间早的return t<s.t;}
}tr[N];
void solve()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++){int a,b,c,d,e,f,sx,sy,t;scanf("%d:%d:%d %d:%d:%d",&a,&b,&c,&d,&e,&f);sx=a*3600+b*60+c;sy=d*3600+e*60+f;t=sy-sx;tr[i]={sx,sy};}sort(tr+1,tr+n+1);int ans=1,time=tr[1].sy;for(int i=2;i<=n;i++){if(tr[i].sx>=time)//如果可行{ans++;time=tr[i].sy;//更新当前时间}}printf("%d\n",ans);
}
int main()
{int t=1;//scanf("%d",&t);while(t--) solve();return 0;
}

Structure of Max-Heap

In computer science, a max-heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree.

Your job is to first insert a given sequence of integers into an initially empty max-heap, then to judge if a given description of the resulting heap structure is correct or not. There are 5 different kinds of description statements:

x is the root
x and y are siblings
x is the parent of y
x is the left child of y
x is the right child of y

Input Specification:

Each input file contains one test case. For each case, the first line gives 2 positive integers: N (≤1,000), the number of keys to be inserted, and M (≤20), the number of statements to be judged. Then the next line contains N distinct integer keys in [−104,104] which are supposed to be inserted into an initially empty max-heap. Finally there are M lines of statements, each occupies a line.

Output Specification:

For each statement, print 1 if it is true, or 0 if not. All the answers must be print in one line, without any space.

Sample Input:

5 6
23 46 26 35 88
35 is the root
46 and 26 are siblings
88 is the parent of 46
35 is the left child of 26
35 is the right child of 46
-1 is the root

Sample Output:

题意:给定n和q表示序列长度和询问个数，n个元素依次插入大根堆，然后q次询问，如果是真输出1，否则输出0.

解析: 模拟大根堆插入，记录每个值的ID位置，父子，兄弟关系即马上可以确定，注意，值会是负，因此我们可以加上1e4偏移值，这样就不会下标越界了。

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5;
int a[N],id[N];
void push(int x)//大根堆压入操作
{while(x!=1&&a[x]>a[x/2]) swap(a[x],a[x/2]),x/=2;
}
void solve()
{int n,q;scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]+=1e4;//防止下标为负push(i);}for(int i=1;i<=n;i++) id[a[i]]=i;//记录某个值的下标while(q--){int x,y,op;//两个数值以及操作命令编号string s;cin>>x>>s;if(s=="is"){cin>>s>>s;if(s=="root") op=1;else if(s=="parent") op=3,cin>>s>>y;else if(s=="left") op=4,cin>>s>>s>>y;else op=5,cin>>s>>s>>y;}else{cin>>y>>s>>s;op=2;}x+=1e4,y+=1e4;//防止下标为负if(op==1)//x是根{if(id[x]==1) printf("1");else printf("0");}else if(op==2)//x和y是兄弟节点{if(id[x]/2==id[y]/2) printf("1");else printf("0");}else if(op==3)//x是y的父亲节点{if(id[x]==id[y]/2) printf("1");else printf("0");}else if(op==4)//x是y的左儿子{if(id[x]==id[y]*2) printf("1");else printf("0");}else//x是y的右儿子{if(id[x]==id[y]*2+1) printf("1");else printf("0");}}printf("\n"); 
}
int main()
{int t=1;//scanf("%d",&t);while(t--) solve();return 0;
}

Recycling of Shared Bicycles

There are many spots for parking the shared bicycles in Hangzhou. When some of the bicycles are broken, the management center will receive a message for sending a truck to collect them. Now given the map of city, you are supposed to program the collecting route for the truck. The strategy is a simple greedy method: the truck will always move to the nearest spot to collect the broken bicycles. If there are more than one nearest spot, take the one with the smallest index.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers: N (≤ 200), the number of spots (hence the spots are numbered from 1 to N, and the management center is always numbered 0), and M, the number of streets connecting those spots. Then M lines follow, describing the streets in the format:

S1 S2 Dist

where S1 and S2 are the spots at the two ends of a street, and Dist is the distance between them, which is a positive integer no more than 1000. It is guaranteed that each street is given once and S1 is never the same as S2.

Output Specification:

For each case, first print in a line the sequence of spots in the visiting order, starting from 0. If it is impossible to collect all the broken bicycles, output in the second line those spots that cannot be visited, in ascending order of their indices. Or if the job can be done perfectly, print in the second line the total moving distance of the truck.

All the numbers in a line must be separated by 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input 1 (shown by the figure below):

Sample Output 1:

0 2 1 7 6 3 4 5
33

Sample Input 2:

Sample Output 2:

0 2 1 7 3 4
5 6

题意:无向图，n个车站点，m条边，工作人员要收集所有车，从0点开始，每次走到离自己最近的一个点，如果有多个满足，会走下标小的，第一行要求你输出工作人员的路径，如果能走遍所有点，第二行输出走过的距离，否则输出哪些点走不到。

解析: 最短路+暴力，因为n的范围不超过200，因此直接跑弗洛伊德得到两两之间最短路，设立一个set保存还有哪些点没访问，然后每次删除当前点，寻找下个点，如此反复即可。

#include <bits/stdc++.h>
using namespace std;
const int N=205;
int n,m,dist[N][N];//保存两点之间最短路值
void Floyd()
{//因题,下标从0开始for(int k=0;k<=n;k++)for(int i=0;i<=n;i++)for(int j=0;j<=n;j++){if(i==j) dist[i][j]=0;else dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);}
}
void solve()
{scanf("%d%d",&n,&m);memset(dist,0x3f,sizeof dist);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);dist[a][b]=dist[b][a]=min(dist[a][b],c);}Floyd();vector<int> ans;set<int> st;//保存当前还有哪些点没走for(int i=0;i<=n;i++) st.insert(i);int pos=0,cnt=0,sum=0;//分别记录当前位置,已经访问数,走过的距离while(1){ans.push_back(pos);cnt++;st.erase(st.find(pos));//把当前点删掉int mi=1e9,nx=-1;for(auto id:st){if(dist[pos][id]<mi) mi=dist[pos][id],nx=id;}if(nx==-1) break;//不能再走了pos=nx;//更新当前位置sum+=mi;}for(int i=0;i<ans.size();i++){if(i!=0) printf(" ");printf("%d",ans[i]);}printf("\n");if(cnt==n+1) printf("%d\n",sum);//都能遍历else{bool ok=false;for(auto i:st){if(!ok) ok=true;else printf(" ");printf("%d",i);}printf("\n");}
}
int main()
{int t=1;//scanf("%d",&t);while(t--) solve();return 0;
}