PAT 甲级冬考 || 我的最后一篇甲级题解
2019-12-08 本文已影响0人
zilla
记我的第三次PAT。12月7日，羽生结弦的25岁生日，考研初试倒计时13天。
暑假期间花了一个多月扎扎实实看晴神笔记、写博客，除了个别dp之类的远古题目，基本独立完成了甲级题库里的所有题目，甚至为此两个月几乎没做数学，专业课一刷也是学着忘着。秋考的时候几乎是抱着2.5h以内必满分的心去的（甚至开开心心穿了华晨宇的9.8应援服）。事实上是，上来被第一题搞崩。第一题就DFS跟我的预期节奏完全不一样，前1.5h还一分没得，就在脑子一片空白敲键盘。当场就想放弃浙大，想过放弃之后70min内AC掉了后三题（中间手抖的厉害把考试客户端关掉叫老师来重开了），但后半程大家交的太猛服务器炸了，最后20min只有几分钟是可以看到题面、可以提交的。考场老师说可能会延时。就带着一点小小的期望，凭着大概印象就开始一阵深搜，写完已经过了提交时间，跑了一下样例，有点慢，但结果正确，但并没能等到延时。80分结束了我准备了两个月的秋考。当晚决定报名今天这场，赌赢了。
这两天是yuzu的比赛日，前天想熬夜看比赛但是太困= =，到了SP比完那会儿突然就醒了，刷了一眼看见yuzuSP落后NC十几分，就丧到无心睡眠➕无心学习😢。想到1207就是羽生生日➕FS比赛日，想着要稳住AK开开心心回来看yuzu比赛。yuzu辛苦了。もっと もっと 強く思ってやる。ありがとう！
正文⬇️
手抖着强行冷静码了两个多钟头，最后十分钟AK了。自秋考过去三个月了，这段时间总共写了不超过15题。机考这个结果满意。
这次代码写的算不上简洁，但是过去就让它放在那吧。
最后一次PAT甲级 大概也是最后一次写甲级题解了
我可以❤️！！！
7-1 Good in C (20分)
第一题明显在修修补补，大概0》13》15》17》20。最后一道AC的。
开始的时候，没有明显错误，交了好几次还0真的怕。
getline忘了怎么用，scanf遇到空格就gg，只能一个一个读字符。。
char数组好久没用过 ，生疏。
- char数组开大一点，否则倒数第二个点段错误
- 第一个词和最后一个词要注意。
- 换行和空格要小心。
#include <bits/stdc++.h>
using namespace std;
int main() {
char mat[26][7][5];
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 7; j++) {
scanf("%s", mat[i][j]);
}
}
char words[20001];
int wc = 0;
getchar();
while (1) {
scanf("%c", &words[wc]);
if (words[wc] == '\n') break;
wc++;
}
words[wc] = '\0';
int ii = 0, cnt_word = 0;
while (words[ii]) {
char curr[12];
int jj = 0;
while (words[ii] && words[ii] >= 'A' && words[ii] <= 'Z') {
curr[jj++] = words[ii++];
}
curr[jj] = '\0';
while (words[ii] && (words[ii] < 'A' || words[ii] > 'Z')) ii++;
if (jj > 0) {
cnt_word++;
if (cnt_word > 1) printf("\n\n");
for (int cc = 0; cc < 7; cc++) {
for (int k = 0; k < jj; k++) {
for (int p = 0; p < 5; p++) {
printf("%c", mat[curr[k] - 'A'][cc][p]);
}
if (k < jj - 1) printf(" ");
}
if (cc < 6) printf("\n");
}
}
}
return 0;
}
7-2 Block Reversing (25分)
在PAT里，“链表”就是如此友好～～～
串起来，整体reverse，再分组局部reverse即可。
#include <bits/stdc++.h>
#define INF 0x3fffffff
using namespace std;
struct Node{
int val, addr, order = INF;
int nxt = -1;
bool operator<(const Node &n2) const {
return order < n2.order;
}
};
int main()
{
vector<Node> ml(100000);
int nn, hh, bl;
scanf("%d%d%d", &hh, &nn, &bl);
for(int i = 0; i < nn; i++) {
int addr, val, nxt;
scanf("%d%d%d", &addr, &val, &nxt);
ml[addr].addr = addr, ml[addr].val = val, ml[addr].nxt = nxt;
}
int curr = hh, len = 0;
while(curr!= -1) {
ml[curr].order = len;
curr = ml[curr].nxt;
len++;
}
sort(ml.begin(), ml.end());
reverse(ml.begin(), ml.begin()+len);
int gn = len/bl;
if(len % bl > 1) reverse(ml.begin(), ml.begin()+ len%bl);
for(int i = 0; i < gn; i++) {
reverse(ml.begin() + len%bl + i * bl, ml.begin() + len%bl + i * bl + bl);
}
for(int k = 0; k< len-1;k++) {
printf("%05d %d %05d\n", ml[k].addr, ml[k].val, ml[k+1].addr);
}
printf("%05d %d -1\n", ml[len-1].addr, ml[len-1].val);
return 0;
}
7-3 Summit (25分)
第一反应就是这个呀。1142 Maximal Clique (25分)
#include <bits/stdc++.h>
#define INF 0x3fffffff
using namespace std;
bool gra[201][201] = {false};
int nn, mm;
int main() {
scanf("%d%d", &nn, &mm);
for (int i = 0; i < mm; i++) {
int v1, v2;
scanf("%d%d", &v1, &v2);
gra[v1][v2] = gra[v2][v1] = true;
}
int nt;
scanf("%d", &nt);
for (int i = 0; i < nt; i++) {
int cnt, temp;
set<int> mem;
bool isOK = true;
scanf("%d", &cnt);
for (int j = 0; j < cnt; j++) {
scanf("%d", &temp);
if (isOK) {
for (auto item:mem) {
if (!gra[item][temp]) {
isOK = false;
break;
}
}
if (isOK) mem.insert(temp);
}
}
if (isOK) {
bool mor = false;
int ii = 1;
for (; !mor && ii <= nn; ii++) {
bool _in = true;
if (mem.find(ii) == mem.end()) {
for (auto item:mem) {
if (!gra[ii][item]) {
_in = false;
break;
}
}
if (_in) {
mor = true;
break;
}
}
}
if (mor) printf("Area %d may invite more people, such as %d.\n", i + 1, ii);
else printf("Area %d is OK.\n", i + 1);
} else printf("Area %d needs help.\n", i + 1);
}
}
7-4 Cartesian Tree (30分)
本来以为是堆。后来反应过来这连完全二叉树都不是。
噗……刚发现有变量重名了。还好一个是局部。。。太慌了最后剩40min还是13 25 25 0，这题真的手速起飞。。。竟然还有时间回去再看第一题（交这题之前又严重手抖关了考试客户端= =）
- 还是递归建树。思路比较接近已知层序、中序，建树
只要知道根结点，用中序就能把左右子树分出来。 - 题中Cartesian Tree父结点大于子结点。那么最大的结点就是当前子树的根，找到它的位置就可以了。
#include <bits/stdc++.h>
#define INF 0x3fffffff
using namespace std;
struct Node {
int data;
Node *lc = NULL, *rc = NULL;
};
int nn, in_seq[32];
int min_pos(int le, int rt) {
int idx = -1, mm = INF;
for (int i = le; i <= rt; i++) {
if (in_seq[i] < mm) {
idx = i, mm = in_seq[i];
}
}
//printf("%d %d\n",mm,idx);
return idx;
}
Node *createT(int st, int ed) {
if (st > ed) return NULL;
if (st == ed) {
Node *nn = new Node;
nn->data = in_seq[st];
return nn;
}
Node *nn = new Node;
int div = min_pos(st, ed);
nn->data = in_seq[div];
nn->lc = createT(st, div - 1);
nn->rc = createT(div + 1, ed);
return nn;
}
void level_tra(Node *root) {
queue < Node * > mq;
mq.push(root);
while (!mq.empty()) {
Node *curr = mq.front();
mq.pop();
nn--;
printf("%d", curr->data);
if (nn > 0) printf(" ");
if (curr->lc) mq.push(curr->lc);
if (curr->rc) mq.push(curr->rc);
}
}
int main() {
scanf("%d", &nn);
for (int i = 0; i < nn; i++) {
scanf("%d", &in_seq[i]);
}
Node *rt = createT(0, nn - 1);
level_tra(rt);
return 0;
}
