PTA刷题记录

阅读原文时间：2022年04月26日阅读：1

考虑到PAT甲级考试和开学后的XCPC比赛，决定寒假把PAT (Advanced Level) Practice刷完，进度条会在这篇博客下更新。由于主要以记录为主，大体上不会像单篇题解那么详细，但是对问题的思考，代码的简洁性、可读性还是有保障的，欢迎看到的小伙伴和我讨论

2021.1.10

1001 A+B Format (20分)

很久没写题了，没想到卡了半个小时，惭愧。这里是要把结果用逗号分隔成三组，即以千为单位，不足的话则不必要填逗号，我最多只添了一个逗号，要看清题目意思再动笔

#include
#include
#include
#include
using namespace std;
int a, b, c, d;
int main(){
scanf("%d%d", &a, &b);
int num = a + b, tmp = abs(num);
c = tmp / 1000000, tmp %= 1000000;
d = tmp / 1000, tmp %= 1000;
if(num<0) printf("-"); if(abs(num)>=1000000) printf("%d,%03d,%03d", c, d, tmp);
else if(abs(num)>=1000) printf("%d,%03d", d, tmp);
else printf("%d", tmp);
}

其他做法：

https://zhuanlan.zhihu.com/p/64035132

https://www.cnblogs.com/chenchen-12/p/10084579.html

1002 A+B for Polynomials (25分)

由于多项式合并后，可能出现原本是-1和+1，相加后就成为0的情况，这不能通过在输入时计数方式判断最后的非零项有多少

#include
#include
#include
#include
using namespace std;
const int maxn = 1e3+100;
int n, cnt, id;
float a[maxn], val;
int main(){
for(int i = 1; i <= 2; i++){ scanf("%d", &n); for(int j = 1; j <= n; j++){ scanf("%d%f", &id, &val); //if(a[id]==0) cnt++; a[id] += val; } } for(int i = 0; i < maxn; i++) if(a[i]!=0) cnt++; printf("%d", cnt); for(int i = 1000; i >= 0; i--){
if(a[i]!=0) printf(" %d %.1f", i, a[i]);
}
}

2021.1.12

1005 Spell It Right (20分)

注意数字对应的英文要写对，submit的时候不要把debug的信息也显示

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 150;
map a;
string s, tmp;
int ans;
void init(){
a[0] = "zero", a[1] = "one", a[2] = "two", a[3] = "three", a[4] = "four";
a[5] = "five", a[6] = "six", a[7] = "seven", a[8] = "eight", a[9] = "nine";
}
int main(){
init();
cin >> s;
for(int i = 0; s[i]; i++)
ans += s[i]-'0';
tmp = to_string(ans);
//cout << tmp << endl;
int len = tmp.length();
for(int i = 0; i < len; i++){
cout << a[tmp[i]-'0'];
if(i!=len-1) cout << " ";
}
}

1006 Sign In and Sign Out (25分)

string比较大小即可

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e3+100;
int n;
string id, a, b, min_s = "23:59:59", max_s = "00:00:00", in, out;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){ cin >> id >> a >> b;
if(amax_s) max_s = b, out = id;
}
cout << in << " " << out;
}

1007 Maximum Subsequence Sum (25分)

基本的dp问题，最大连续区间和：

定义dp[i]为以i结尾的最大连续和，转移方程为：dp[i] = max(a[i], dp[i-1],+a[i])

坑点在于英文阅读理解：

If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

这句话等价于当最大区间和小于0时，输出整个序列的第一个元素和最后一个元素。还有个是我自己没看清楚，应该输出最小下标对应的元素，而不是下标。

#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f
using namespace std;
const int maxn = 1e4+100;
int n, id, front, tear, ans = -1;
int a[maxn], dp[maxn];
int main(){
scanf("%d", &n);
front = 1, tear = n;
for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); if(dp[i-1]>0) dp[i] = dp[i-1] + a[i];
else dp[i] = a[i], id = i;
if(ans=0 ? ans : 0, a[front], a[tear]);
}

1008 Elevator (20分)

模拟题

#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f
using namespace std;
const int maxn = 1e4+100;
int n, sum, now, tmp;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){ scanf("%d", &tmp); int num = tmp-now; sum += num > 0 ? num*6 : num*(-4);
now = tmp;
}
sum += 5*n;
printf("%d", sum);
}

1009 Product of Polynomials (25分)

模拟多项式乘法，注意细节即可

#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f
using namespace std;
const int maxn = 2e3+100;
int n, m, id, cnt;
float val, ans[maxn];
struct node{
int id;
float val;
}now[1100];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d%f", &now[i].id, &now[i].val); scanf("%d", &m); for(int i = 1; i <= m; i++){ scanf("%d%f", &id, &val); for(int j = 1; j <= n; j++){ ans[id+now[j].id] += now[j].val*val; } } for(int i = maxn-1; i >= 0; i--)
if(ans[i]!=0) cnt++;
printf("%d", cnt);
for(int i = maxn-1; i >= 0; i--){
if(ans[i]!=0)
printf(" %d %.1f", i, ans[i]);
}
}

2021.1.13

晚上看了很久的二分，不太理解其中的细节，卡了一晚上，对自己的智商感到深深的怀疑

1004 Counting Leaves (30分)

2021.1.14

感觉很久没写算法手已经很生了，主要是很多算法自己明明思考证明过，也写过，但是现在再写一遍还是会忘记。反思后觉得，还是要脚踏实地多刷题才是根本，然后就是感性理解算法是很重要的一环，一定要在脑海里有个形象的记忆，懂其中的思想。因为就算之前很严密的证明过一次，过段时间后这种严密的证明大概率会忘掉很多，再来一遍也很繁琐，但是不去细看又不太懂为什么他那样做是正确的，又会感到很疑惑。能证明这个算法的正确性和想出来这个算法那还是不太一样的。有人交流往往是幸福的，尤其是在现实中，没有的话只能在网上多看看优质的文章与讨论。（这篇博客给了我些感悟）

1003 Emergency (25分)

大意是求最短路径的条数及路径的最大点权和，可能阅读理解能力有限，看完别人博客才知道题目要求的是路径的最大点权和

复习了下邻接表存图和Dijkstra找最短路，以下可以帮助理解Dijkstra算法：

大概是这样一个场景：往源点S注水，队列代表水目前能够流到的节点，队列里面标记了水流到节点的时刻。我们用优先队列模拟水流动的过程，队头表示就是当前水流到的节点，这时与它相邻的节点也会被流到，更新节点被流到的时刻即可。显然点p第一次被水流到的时刻，就是S到p的最短路径(水的流速为1)。d[v]<p.first表示已经被水流过的节点不用进行处理了(已经处理过)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pb push_back
#define inf 0x3f3f3f
#define pii pair
using namespace std;
const int maxn = 1e4+100;
struct edge{
int to, cost;
};
vector g[maxn];
int n, m;
int u, v, val, w[maxn];
int s, t, d[maxn], num[maxn], tot[maxn];
void dijkstra(){
for(int i = 1; i <= n; i++) d[i] = inf; priority_queue, greater >que;
que.push({0, s}), d[s] = 0, num[s] = 1, tot[s] = w[s];
while(!que.empty()){
pii p = que.top(); que.pop();
int u = p.second;
if(d[u]<p.first) continue;
int cnt = g[u].size();
for(int i = 0; i < cnt; i++){
edge e = g[u][i];
int v = e.to, cost = e.cost;
if(d[u]+cost<d[v]){
d[v] = d[u] + cost;
tot[v] = tot[u] + w[v];
num[v] = num[u];
que.push({d[v], v});
}
else if(d[u]+cost==d[v]){
tot[v] = max(tot[v], tot[u]+w[v]);
num[v] += num[u];
}
}
}
}

int main(){
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i = 0; i <= n-1; i++) scanf("%d%", &w[i]);
while(m--){
scanf("%d%d%d", &u, &v, &val);
g[u].pb({v, val}), g[v].pb({u, val});
}
dijkstra();
//for(int i = 0; i <= n-1; i++) printf("%d ", d[i]);
printf("%d %d", num[t], tot[t]);
}

reference：

https://blog.csdn.net/CV_Jason/article/details/80891055

https://blog.csdn.net/u012161251/article/details/104151880

1011 World Cup Betting (20分)

水题

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pb push_back
#define inf 0x3f3f3f
#define pii pair
using namespace std;
const int maxn = 1e4+100;
float a, b, c, res = 1, ans;
char s[4];
int main(){
for(int i = 1; i <= 3; i++){
scanf("%f%f%f", &a, &b, &c);
float tmp = max(a, max(b, c));
if(tmp==a) s[i] = 'W';
else if(tmp==b) s[i] = 'T';
else s[i] = 'L';
res *= tmp;
}
ans = (res*0.65-1)*2;
printf("%c %c %c %.2f", s[1], s[2], s[3], ans);
}

1012 The Best Rank (25分)

注意不要发生复制粘贴后代码未修改的低级错误，再就是数据范围，不然会出现段错误。对数据排序，最后二分查找相应位置即可。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pb push_back
#define inf 0x3f3f3f
#define pii pair
using namespace std;
const int maxn = 2e3+100;
struct score{
int c, m, e, a;
}a[1000100];
bool cmp(int a, int b){
return a > b;
}
int n, m, id;
int x[maxn], y[maxn], z[maxn], w[maxn];
bool vis[1000100];
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){ scanf("%d", &id), vis[id] = 1; scanf("%d%d%d", &a[id].c, &a[id].m, &a[id].e); //cout << a[id].c << " "<< a[id].c << " "<< a[i].e <())-x;
int r2 = lower_bound(y+1, y+1+n, a[id].m, greater())-y;
int r3 = lower_bound(z+1, z+1+n, a[id].e, greater())-z;
int r4 = lower_bound(w+1, w+1+n, a[id].a, greater())-w;
int r = min(min(r1, r2), min(r3, r4));
printf("%d ", r);
if(r==r4) printf("A\n");
else if(r==r1) printf("C\n");
else if(r==r2) printf("M\n");
else if(r==r3) printf("E\n");
}
}

2021.1.15

1014 Waiting in Line (30分)

一道模拟题，显然的思路是开始先将客户依次排到队列中去，排满后剩下的客户选择排到业务处理的最快的队伍中去，记录时间戳即可。

难倒是不难，就是有些细节需要想清楚，我在栽在两个坑点上：

判断一个客户无法完成服务是根据他的开始服务时间应该在15:00之前，而不是以结束时间为依据
根据思路分两步处理，但是忽略了n*m可能会比k要大，造成数据输入不足

写的时候想清楚这个过程就好，重点在于细节没想到位，搜完博客后发现第一个坑点，第二个坑点苦思冥想了很久，不过最后写出来的代码相比其他人要简洁的多，并且有附加的附加调试信息

#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 2e3+100;
int n, m, k, q, w[maxn];
int que[maxn][maxn], id[maxn], p[maxn], sum[maxn][maxn], res[maxn];
int main(){
scanf("%d%d%d%d", &n, &m, &k, &q);
for(int i = 1; i <= min(n*m, k); i++) { scanf("%d", &w[i]); que[(i-1)%n][(i-1)/n+1] = i, id[(i-1)%n]++; res[i] = sum[(i-1)%n][(i-1)/n+1] = sum[(i-1)%n][(i-1)/n] + w[i]; } for(int i = 0; i <= n-1; i++) p[i] = 1; for(int i = min(n*m, k)+1; i <= k; i++){ scanf("%d", &w[i]); int tmp = inf, now; for(int j = 0; j <= n-1; j++){ if(sum[j][p[j]]=540) printf("Sorry\n");
else printf("%02d:%02d\n", 8+res[query]/60, res[query]%60);
}

}

reference：

https://www.cnblogs.com/codervivi/p/12867049.html

2021.1.17

1015 Reversible Primes (20分)

WA一发后，想了几个样例测试了一下，发现自己漏掉了一个点：1不是素数。另外这题竟然不用素数筛和快速幂，惊了，当时想着先暴力试试，不行再优化，结果就过了。不过说实话素数筛和快速幂每次套板子，自己都已经不会写了，这位杨感觉不太行的样子。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define pii pair
using namespace std;
const int maxn = 2e3+100;
bool judge(int n){
if(n==1) return false;
for(int i = 2; i <= n/i; i++) if(n%i==0) return false; return true; } int change(int n, int d){ int res = 0, a[100], t = 0; while(n){ a[++t] = n%d; n /= d; } for(int i = 1; i <= t; i++) res += a[i]*pow(d, t-i); return res; } int main(){ int n, d; while(scanf("%d", &n)&&n>0){
scanf("%d", &d);
if(judge(n)&&judge(change(n, d))) printf("Yes\n");
else printf("No\n");
}
}

1010 Radix (25分)

题目的大意是，给你两个数，N1和N2，给定其中一个数的基数，然后求另一个数的基数，使得两个数相等

这题有的地方没有给清楚，感觉有点小问题。给定标签的数不会溢出，而未给定标签的数是会溢出long long的，这点题目没有直接说明，溢出的部分需要用<0去判断。再就是二分的下限取小了，反而WA。

这里主要是对二分法的运用，我自己有个点是没有注意到的就是，求这个数的基数，如何取其上下限。如果这个数大于一位，当这个数最小为10时可以取到最大的基数即这个数的十进制，最小就是其各位的最大数字+1.但是当这个数字只有1位的时候，套用上述的方法显然就会出错，这样取得上限比下限还小，这种情况稍微处理一下就好了。

这会借着还复习了下二分法和快速幂（倍增思想(由于事先知道跳跃步数，采用二进制分解，边计算边跳跃的方式)和分治思想(将问题划分为规模更小的子问题)）

#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f
using namespace std;
string s1, s2;
ll id, radix;
ll qpow(ll a, ll n){
ll ans = 1;
while(n){
if(n&1) ans *= a; //ans乘上当前的a
a *= a; //a自乘
n >>= 1; //n往右移一位
}
return ans;
}
ll handle(string s, ll d){
ll len = s.length(), num;
ll sum = 0;
for(int i = 0; i < len; i++){ if(s[i]<='9') num = s[i]-'0'; else num = s[i]-'a'+10; sum += num*qpow(d, len-1-i); } return sum; } int main(){ cin >> s1 >> s2 >> id >> radix;
if(id==2) swap(s1, s2);
//cout << s1 << " " << s2; ll tmp = handle(s1, radix); //二分+快速幂 //char c=*max_element(str.begin(),str.end()); int cnt = -1; for(int i = 0; s2[i]; i++){ if(s2[i]<='9') cnt = max(cnt, s2[i]-'0'); else cnt = max(cnt, s2[i]-'a'+10); } ll l = cnt, r = max(l, tmp)+1; while(r-l>1){
ll mid = (l+r)/2;
ll res = handle(s2, mid);
if(res>=tmp||res<0) r = mid;
else l = mid;
}
if(handle(s2, r)==tmp) printf("%lld\n", r);
else printf("Impossible\n");
}

reference:

https://segmentfault.com/a/1190000037525090

https://blog.csdn.net/CV_Jason/article/details/80993283

https://blog.csdn.net/d891320478/article/details/8303072

https://blog.csdn.net/weixin_30782331/article/details/98610783

2021.1.17

从今天开始就要按照专题更加有效的复习了，专题会专门写几篇博客，陆续会把前几天写的题目整理进专题，希望这样写题会更加有效率

1051 Pop Sequence (25分)

1056 Mice and Rice (25分)

2021.1.19

1060 Are They Equal (25分)

1039 Course List for Student (25分)

1047. Student List for Course

2021.1.21

1054 The Dominant Color (20分)

大水题

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f
#define pii pair
#define pb push_back
using namespace std;
const int maxn = 1e8+100;
int n, m, num, ans, cnt[maxn];
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ scanf("%d%", &num); if(++cnt[num]>m*n/2) ans = num;
}
}
printf("%d", num);
}