PAT 甲级 2020年春

7-1 Prime Day (20分)

#include<cstdio> #include<iostream> #include<cmath> #include<string> using namespace std; bool ifprime(int x) { if (x < 2)return false; if (x == 2)return true;//2是质数 if (x % 2 == 0)return false; bool ans = true; for (int i = 3;i <= sqrt(x);i = i + 2) { if (x % i == 0) { ans = false; break; } } return ans; } int main() { int n, i, flag = true; string str; cin >> str; for (i = 0;i < 8;i++) { n = stoi(str); bool ans = ifprime(n); if (ans) { cout << str << " Yes" << endl; } else { cout << str << " No" << endl; flag = false; } str.erase(str.begin()); } if (flag)printf("All Prime!"); return 0; }

7-2 The Judger (25分)

1.sum和 2.difference差 3.product积 4.quotient商 补充： 1.surface area 表面积，volume 体积，the length of the side 边长，lateral area 侧面积，altitude高 2.rectangle长方形,square正方形,circular cylinder圆柱体dao,cone圆锥, triangle三角形,polygon多边形,rectangular solid长方体,cube立方体,circle圆 3.add，plus加 ,subtract减 ,multiply,times乘 ,divide除 参考代码

#include<iostream> #include<set> #include<vector> using namespace std; int num[20][1005]; int f[1000005] = { 0 }; //如果数字i存在，则f[i]为1。 int fout[20] = {0}, last; vector<int>seq;//存放存在的数 int main() { int a, b,n,m; scanf("%d%d%d%d", &a, &b, &n, &m); last = n; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &num[i][j]); seq.push_back(a); seq.push_back(b); f[a] = f[b] = 1; for(int j=0;j<m;j++) for (int i = 0; i < n; i++) if(!fout[i]){ if (f[num[i][j]]) { fout[i] = 1; printf("Round #%d: %d is out.\n", j + 1, i + 1); last--; continue; } bool flag = true; for(int k=0;k<seq.size();k++) if (seq[k] - num[i][j]>0 && f[seq[k] - num[i][j]]) { //num[i][j]等于存在的某两数相减，相当于某数与num[i][j]相减存在。 flag = false; break; } if (flag) { fout[i] = 1; printf("Round #%d: %d is out.\n", j + 1, i + 1); last--; continue; } seq.push_back(num[i][j]); f[num[i][j]] = 1; } if (last > 0) { printf("Winner(s):"); for (int i = 0; i < n; i++)if (!fout[i])printf(" %d", i + 1); } else printf("No winner."); return 0; }

自己的代码（较繁琐）

#define _CRT_SECURE_NO_WARNINGS #include<cstdio> #include<iostream> #include<vector> #include<math.h> using namespace std; #define MAX 1005 int or1, or2, n, m; int G[12][MAX]; int ifout[12] = { false }; int difference[100002] = { 0 };//1为差值存在，0为不存在 bool panduan(int x, int u, int v) { if (difference[x] <= 0)return false; if (x == or1 || x == or2)return false; for (int j = 0; j < v; j++) { for (int i = 0; i < n; i++) { if (x == G[i][j])return false; } } for (int i = 0; i < u; i++) if (x == G[i][v])return false; return true; } void updatedif(int x, int u, int v) { difference[abs(or1 - x)] = 1; difference[abs(or2 - x)] = 1; for (int j = 0; j < v; j++) { for (int i = 0; i < n; i++) { if (G[i][j] > 0) difference[abs(G[i][j] - x)]++; } } for (int i = 0; i < u; i++) if (G[i][v] > 0) difference[abs(G[i][v] - x)]++; } int main() { int i, j; scanf("%d%d", &or1, &or2); difference[abs(or1 - or2)]++; scanf("%d%d", &n, &m); for (i = 0;i < n;i++) { for (j = 0;j < m;j++) scanf("%d", &G[i][j]); } for (j = 0;j < m;j++) { for (i = 0;i < n;i++) { if (ifout[i]) continue; if (panduan(G[i][j], i, j) == false) {//出局 printf("Round #%d: %d is out.\n", j + 1, i + 1); ifout[i] = j + 1; for (int k = j; k < m; k++)G[i][k] = -1; } else {//接受这一数字，更新所有差值 updatedif(G[i][j], i, j); } } } bool flag = false; for (i = 0;i < n;i++) if (ifout[i] == false) { if (flag == false) { printf("Winner(s):"); flag = true; } printf(" %d", i + 1); } if (flag == false)printf("No winner."); return 0; }

7-3 Safari Park (25分)

直接用vector保存顶点对（即边）。对于图中的每一条边，在输入序列中查看两端是否为同一种动物。 用set保存输入物种序列，达到去重计数的目的。

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<set> #include<vector> using namespace std; int n, m, k, r; struct node { int a, b; }; vector<node>reign;//保存图中的边 int main() { scanf("%d%d%d", &n, &r, &k); for (int i = 0; i < r; i++) { int a, b; scanf("%d%d", &a, &b); reign.push_back({ a,b }); } scanf("%d", &m); for (int i = 0; i < m; i++) { int num[1000];//区域i的物种编号是num[i] set<int>iset; for (int j = 1; j <= n; j++) { scanf("%d", &num[j]); iset.insert(num[j]); } if (iset.size() < k) { printf("Error: Too few species.\n"); continue; } else if (iset.size() > k) { printf("Error: Too many species.\n"); continue; } bool flag = true; for (int j = 0; j < reign.size(); j++) { //对于图中的每一条边，在输入序列中查看两端是否为同一种动物 int posa = reign[j].a; int posb = reign[j].b; if (num[posa] == num[posb]) { flag = false; break; } } if (!flag)printf("No\n"); else if (flag && iset.size() == k)printf("Yes\n"); } return 0; }

7-4 Replacement Selection (30分)

优先队列。用结构体保存待排序的数，其中包含值（v）和它处在第几run（level）。一开始level为1，如果最近出列的数比要插入的数大，则插入的数为出列的数level+1。优先级定义为如果level小的优先级高；level一样时，值小的优先级高。

#define _CRT_SECURE_NO_WARNINGS #include<cstdio> #include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; #define MAX 100005 int n, volume; struct num { int v, level; }; struct cmp { bool operator () (num a, num b) { if (a.level != b.level)return a.level > b.level; else return a.v > b.v; } }; int main() { int i, j, nowrun = 0; num input, out; priority_queue<num, vector<num>, cmp>run; scanf("%d%d", &n, &volume); out.v = 10000000; out.level = 1; for (i = 0; i < n; i++) { if (run.size() == volume) {//队列已满，则队首出列 out = run.top(); if (nowrun == 0)nowrun++; else if (nowrun != out.level) { //这一run输完了，换行输下一run，nowrun+1 printf("\n"); nowrun++; } else printf(" "); printf("%d", out.v); run.pop(); } scanf("%d", &input.v); if (out.v <= input.v)input.level = nowrun; else input.level = nowrun + 1; run.push(input); } while (run.size()) {//排空队列，即队列里剩下的也要全部输出 out = run.top(); if (nowrun == 0)nowrun++; else if (nowrun != out.level) { printf("\n"); nowrun++; } else printf(" "); printf("%d", out.v); run.pop(); } return 0; }