PAT – 第17页

1058. 选择题(20)-PAT乙级真题

批改多选题是比较麻烦的事情，本题就请你写个程序帮助老师批改多选题，并且指出哪道题错的人最多。

输入格式：

输入在第一行给出两个正整数N（<=1000）和M（<=100），分别是学生人数和多选题的个数。随后M行，每行顺次给出一道题的满分值（不超过5的正整数）、选项个数（不少于2且不超过5的正整数）、正确选项个数（不超过选项个数的正整数）、所有正确选项。注意每题的选项从小写英文字母a开始顺次排列。各项间以1个空格分隔。最后N行，每行给出一个学生的答题情况，其每题答案格式为“(选中的选项个数选项1 ……)”，按题目顺序给出。注意：题目保证学生的答题情况是合法的，即不存在选中的选项数超过实际选项数的情况。

输出格式：

按照输入的顺序给出每个学生的得分，每个分数占一行。注意判题时只有选择全部正确才能得到该题的分数。最后一行输出错得最多的题目的错误次数和编号（题目按照输入的顺序从1开始编号）。如果有并列，则按编号递增顺序输出。数字间用空格分隔，行首尾不得有多余空格。如果所有题目都没有人错，则在最后一行输出“Too simple”。

输入样例：
3 4
3 4 2 a c
2 5 1 b
5 3 2 b c
1 5 4 a b d e
(2 a c) (2 b d) (2 a c) (3 a b e)
(2 a c) (1 b) (2 a b) (4 a b d e)
(2 b d) (1 e) (2 b c) (4 a b c d)
输出样例：
3
6
5
2 2 3 4

分析：n个学生，m道题目。对于每一道题目，将题目的总分存储在total[i]数组里面，将题目的选项插入存储在right[i]（为集合类型）里面。wrongCnt[i]存储第i道题错误的人数，对于n个学生，每一个学生的答案插入一个集合st里面，比较st与right[i]是否相等，如果相等说明该生答对了，他的score += total[i]（加上当前题目的总分），如果该生答错了，wrongCnt[i]++，表示第i道题新增一个错误的人。输出每一个学生的得分；遍历wrongCnt数组，求wrongCnt的最大值maxWrongCnt。如果maxWrongCnt == 0说明没有一个人做错题目，则输出“Too simple”，否则输出maxWrongCnt的值，和wrongCnt数组中wrongCnt[i] == maxWrongCnt的那些题号～
注意：scanf中的%d和%c之间一定要有分隔符的主动scanf输入，否则可能接收成空格或者空值～

#include <cstdio>
#include <vector>
#include <set>
using namespace std;
int main() {
    int n, m, temp, k;
    scanf("%d%d", &n, &m);
    vector<set<char>> right(m);
    vector<int> total(m), wrongCnt(m);
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &total[i], &temp, &k);
        for(int j = 0; j < k; j++) {
            char c;
            scanf(" %c", &c);
            right[i].insert(c);
        }
    }
    for(int i = 0; i < n; i++) {
        int score = 0;
        scanf("\n");
        for(int j = 0; j < m; j++) {
            if(j != 0) scanf(" ");
            scanf("(%d", &k);
            set<char> st;
            char c;
            for(int l = 0; l < k; l++) {
                scanf(" %c", &c);
                st.insert(c);
            }
            scanf(")");
            if(st == right[j]) {
                score += total[j];
            } else {
                wrongCnt[j]++;
            }
        }
        printf("%d\n", score);
    }
    int maxWrongCnt = 0;
    for(int i = 0; i < m; i++) {
        if(wrongCnt[i] > maxWrongCnt) {
            maxWrongCnt = wrongCnt[i];
        }
    }
    if(maxWrongCnt == 0)
        printf("Too simple");
    else {
        printf("%d", maxWrongCnt);
        for(int i = 0; i < m; i++) {
            if(wrongCnt[i] == maxWrongCnt) {
                printf(" %d", i + 1);
            }
        }
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <set>

using namespace std;

int main() {

int n, m, temp, k;

scanf("%d%d", &n, &m);

vector<set<char>> right(m);

vector<int> total(m), wrongCnt(m);

for(int i = 0; i < m; i++) {

scanf("%d%d%d", &total[i], &temp, &k);

for(int j = 0; j < k; j++) {

char c;

scanf(" %c", &c);

right[i].insert(c);

}

for(int i = 0; i < n; i++) {

int score = 0;

scanf("\n");

for(int j = 0; j < m; j++) {

if(j != 0) scanf(" ");

scanf("(%d", &k);

set<char> st;

char c;

for(int l = 0; l < k; l++) {

scanf(" %c", &c);

st.insert(c);

}

scanf(")");

if(st == right[j]) {

score += total[j];

} else {

wrongCnt[j]++;

}

printf("%d\n", score);

}

int maxWrongCnt = 0;

for(int i = 0; i < m; i++) {

if(wrongCnt[i] > maxWrongCnt) {

maxWrongCnt = wrongCnt[i];

}

if(maxWrongCnt == 0)

printf("Too simple");

else {

printf("%d", maxWrongCnt);

for(int i = 0; i < m; i++) {

if(wrongCnt[i] == maxWrongCnt) {

printf(" %d", i + 1);

}

return 0;

}

1057. 数零壹(20)-PAT乙级真题

给定一串长度不超过10^5的字符串，本题要求你将其中所有英文字母的序号（字母a-z对应序号1-26，不分大小写）相加，得到整数N，然后再分析一下N的二进制表示中有多少0、多少1。例如给定字符串“PAT (Basic)”，其字母序号之和为：16+1+20+2+1+19+9+3=71，而71的二进制是1000111，即有3个0、4个1。

输入格式：

输入在一行中给出长度不超过105、以回车结束的字符串。

输出格式：

在一行中先后输出0的个数和1的个数，其间以空格分隔。

输入样例：
PAT (Basic)
输出样例：
3 4

分析：用getline接收一行字符串，对于字符串的每一位，如果是字母(isalpha)，则将字母转化为大写，并累加(s[i] – ‘A’ + 1)算出n，然后将n转化为二进制，对每一位处理，如果是0则cnt0++，如果是1则cnt1++，最后输出cnt0和cnt1的值～～

#include <iostream>
#include <cctype>
#include <string>
using namespace std;
int main() {
    string s;
    getline(cin, s);
    int n = 0;
    for(int i = 0; i < s.length(); i++) {
        if(isalpha(s[i])) {
            s[i] = toupper(s[i]);
            n += (s[i] - 'A' + 1);
        }
    }
    int cnt0 = 0, cnt1 = 0;
    while(n != 0) {
        if(n % 2 == 0) {
            cnt0++;
        } else {
            cnt1++;
        }
        n = n / 2;
    }
    printf("%d %d", cnt0, cnt1);
    return 0;
}

#include <iostream>

#include <cctype>

#include <string>

using namespace std;

int main() {

string s;

getline(cin, s);

int n = 0;

for(int i = 0; i < s.length(); i++) {

if(isalpha(s[i])) {

s[i] = toupper(s[i]);

n += (s[i] - 'A' + 1);

}

int cnt0 = 0, cnt1 = 0;

while(n != 0) {

if(n % 2 == 0) {

cnt0++;

} else {

cnt1++;

}

n = n / 2;

}

printf("%d %d", cnt0, cnt1);

return 0;

}

1056. 组合数的和(15)-PAT乙级真题

给定N个非0的个位数字，用其中任意2个数字都可以组合成1个2位的数字。要求所有可能组合出来的2位数字的和。例如给定2、5、8，则可以组合出：25、28、52、58、82、85，它们的和为330。

输入格式：

输入在一行中先给出N（1<N<10），随后是N个不同的非0个位数字。数字间以空格分隔。

输出格式：

输出所有可能组合出来的2位数字的和。

输入样例：
3 2 8 5
输出样例：
330

分析：用sum统计所有可能组合出来的两位数字之和，在sum累加的过程中，对于每一个输入的数字temp，都能和其他N-1个数字组合出新的数字，temp能够放在个位也能够放在十位，所以每个数字temp都能在个位出现(N-1)次，十位出现(N-1)次，在个位产生的累加效果为temp * (N-1)，而在十位产生的累加效果为temp * (N-1) * 10，所以所有数字的累加结果sum即是所有可能组合出来的2位数字的和～

#include <cstdio>
int main() {
    int N, sum = 0, temp;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &temp);
        sum += temp * 10 * (N - 1) + temp * (N - 1);
    }
    printf("%d", sum);
    return 0;
}

#include <cstdio>

int main() {

int N, sum = 0, temp;

scanf("%d", &N);

for (int i = 0; i < N; i++) {

scanf("%d", &temp);

sum += temp * 10 * (N - 1) + temp * (N - 1);

}

printf("%d", sum);

return 0;

}

【note】PAT甲级题目中的单词整理

randomize 使…随机化

collaborate 合作

gamblers 赌徒

inadequate 不充分的

shuffles 洗牌

casino 赌场

simulate 假装，模拟，模仿

a deck of playing cards 一副牌

Joker 鬼牌

红桃（Heart）、黑桃（Spade）、方片（Diamond）、梅花（Club）

trophy 奖牌，奖杯

Lottery 彩票

distinct 清晰的，明显的，不同的

top-down 自顶向下

decimal 小数

general 通用的，普遍的，普通的

decimal system 十进制 == decimal number

any numeral system 任何进制

notorious 臭名昭著的，声名狼藉的，众人皆知的

suffix 后缀

stuck 动不了的，被卡住的

Deduplication 链表去重

absolute value 绝对值

separate 分开的，独有的，另外的

adjacent 毗连的，邻近的

be supposed to 应该，被期望

exactly 确切地

course 课程

Course List for Student 学生选课情况

alphabetical 按字母顺序

fundamental 基本的，重要的

even 偶数

odd 奇怪的，奇数

hence 因此

recursively 递归

specify 具体说明

potential 潜在的

cluster 集群

property 房产，财产

estate 房产

unit price 单价

two-digit number 两位数

For the sake of simplicity 为了简单起见

for every seniority level 对于每一个高层，对于每一层

bonus 奖金，红利，好处

coupon 优惠券

Forbes 福布斯（美国著名财经杂志）

be supposed to 应该，被期望

tie 平局

sequence {A[1], A[2], …} is said to be “smaller” than sequence {B[1], B[2], …} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k]

如果序列{A[1], A[2], …}与 {B[1], B[2], …}，如果存在k>=1，使得对任意的i < k都有A[i] == B[i]，而A[k] < B[k]成立，那么就称为方案A比方案B小

ascend 上升 increasing 上升

descend 下降 decreasing 下降

Stripe 条纹，链

distinguish 区分，区别

key words 关键词

Each input file contains one test case. 每一个输入文件包含一个测试用例。

Note: Simple chopping is assumed without rounding. 不用四舍五入

number 数量

It is assumed that 我们假定…

followers 追随者，支持者

Hence 因此

forward 转发

indirect 间接的，拐弯抹角的，迂回的

with positive increments only 只是正向增加

Quadratic probing 二次方探查法

Graduate Admission 研究生入学

respectively 各自地

disjoint 不相交的，脱节，解体

partition 分割，分隔

denote 代表，指示，表示

permutation 一组排列

erase erase erase！！

false FALSE false！！！

volume 容积，量，体积

threshold 起征点，下限，开端

MRI 核磁共振像

M by N matrix m行n列矩阵

quota 限额

for the sake of 为了

scattered cities 分散的城市

recommendation 推荐，建议

candidate 候选的

residential 住宅区

client 委托人，客户，当事人

one-way is 1 if the street is one-way from V1 to V2, or 0 if not

如果该道路是从V1到V2的单行线，则one-way为1，否则为0

fewest intersections 最少结点的

radix 基数，进制，根

intersection 交点，交集

1059. C语言竞赛(20)-PAT乙级真题

C语言竞赛是浙江大学计算机学院主持的一个欢乐的竞赛。既然竞赛主旨是为了好玩，颁奖规则也就制定得很滑稽：

0. 冠军将赢得一份“神秘大奖”（比如很巨大的一本学生研究论文集……）。
1. 排名为素数的学生将赢得最好的奖品 —— 小黄人玩偶！
2. 其他人将得到巧克力。

给定比赛的最终排名以及一系列参赛者的ID，你要给出这些参赛者应该获得的奖品。

输入格式：

输入第一行给出一个正整数N（<=10000），是参赛者人数。随后N行给出最终排名，每行按排名顺序给出一位参赛者的ID（4位数字组成）。接下来给出一个正整数K以及K个需要查询的ID。

输出格式：

对每个要查询的ID，在一行中输出“ID: 奖品”，其中奖品或者是“Mystery Award”（神秘大奖）、或者是“Minion”（小黄人）、或者是“Chocolate”（巧克力）。如果所查ID根本不在排名里，打印“Are you kidding?”（耍我呢？）。如果该ID已经查过了（即奖品已经领过了），打印“ID: Checked”（不能多吃多占）。

输入样例：
6
1111
6666
8888
1234
5555
0001
6
8888
0001
1111
2222
8888
2222
输出样例：
8888: Minion
0001: Chocolate
1111: Mystery Award
2222: Are you kidding?
8888: Checked
2222: Are you kidding?

分析：ran数组标记每个id对应的排名，集合ss存储所有已经询问过的id，如果发现当前id已经出现在ss中，则输出“Checked”，如果ran[id] == 0说明当前id不在排名列表中，所以输出“Are you kidding?”，如果ran[id]为1则输出“Minion”，如果ran[id]为素数则输出“Mystery Award”，否则输出“Chocolate”

#include <iostream>
#include <set>
#include <cmath>
using namespace std;
int ran[10000];
bool isprime(int a) {
    if(a <= 1) return false;
    int Sqrt = sqrt((double)a);
    for(int i = 2; i <= Sqrt; i++) {
        if(a % i == 0)
            return false;
    }
    return true;
}
int main() {
    int n, k;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int id;
        scanf("%d", &id);
        ran[id] = i + 1;
    }
    scanf("%d", &k);
    set<int> ss;
    for(int i = 0; i < k; i++) {
        int id;
        scanf("%d", &id);
        printf("%04d: ", id);
        if(ran[id] == 0) {
            printf("Are you kidding?\n");
            continue;
        }
        if(ss.find(id) == ss.end()) {
            ss.insert(id);
        } else {
            printf("Checked\n");
            continue;
        }
        if(ran[id] == 1) {
            printf("Mystery Award\n");
        }else if(isprime(ran[id])) {
            printf("Minion\n");
        }else {
            printf("Chocolate\n");
        }
    }
    return 0;
}

#include <iostream>

#include <set>

#include <cmath>

using namespace std;

int ran[10000];

bool isprime(int a) {

if(a <= 1) return false;

int Sqrt = sqrt((double)a);

for(int i = 2; i <= Sqrt; i++) {

if(a % i == 0)

return false;

}

return true;

}

int main() {

int n, k;

scanf("%d", &n);

for(int i = 0; i < n; i++) {

int id;

scanf("%d", &id);

ran[id] = i + 1;

}

scanf("%d", &k);

set<int> ss;

for(int i = 0; i < k; i++) {

int id;

scanf("%d", &id);

printf("%04d: ", id);

if(ran[id] == 0) {

printf("Are you kidding?\n");

continue;

}

if(ss.find(id) == ss.end()) {

ss.insert(id);

} else {

printf("Checked\n");

continue;

}

if(ran[id] == 1) {

printf("Mystery Award\n");

}else if(isprime(ran[id])) {

printf("Minion\n");

}else {

printf("Chocolate\n");

}

return 0;

}

1119. Pre- and Post-order Traversals (30)-PAT甲级真题（前序后序转中序）

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences, or preorder and inorder traversal sequences. However, if only the postorder and preorder traversal sequences are given, the corresponding tree may no longer be unique.

Now given a pair of postorder and preorder traversal sequences, you are supposed to output the corresponding inorder traversal sequence of the tree. If the tree is not unique, simply output any one of them.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first printf in a line “Yes” if the tree is unique, or “No” if not. Then print in the next line the inorder traversal sequence of the corresponding binary tree. If the solution is not unique, any answer would do. It is guaranteed that at least one solution exists. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input 1:
7
1 2 3 4 6 7 5
2 6 7 4 5 3 1
Sample Output 1:
Yes
2 1 6 4 7 3 5
Sample Input 2:
4
1 2 3 4
2 4 3 1
Sample Output 2:
No
2 1 3 4

题目大意：给出一棵树的结点个数n，以及它的前序遍历和后序遍历，输出它的中序遍历，如果中序遍历不唯一就输出No，且输出其中一个中序即可，如果中序遍历唯一就输出Yes，并输出它的中序
分析：用unique标记是否唯一，如果为true就表示中序是唯一的～
已知二叉树的前序和后序是无法唯一确定一颗二叉树的，因为可能会存在多种情况，这种情况就是一个结点可能是根的左孩子也有可能是根的右孩子，如果发现了一个无法确定的状态，置unique = false，又因为题目只需要输出一个方案，可以假定这个不可确定的孩子的状态是右孩子，接下来的问题是如何求根结点和左右孩子划分的问题了，首先我们需要知道树的表示范围，需要四个变量，分别是前序的开始的地方prel，前序结束的地方prer，后序开始的地方postl，后序结束的地方postr，前序的开始的第一个应该是后序的最后一个是相等的，这个结点就是根结点，以后序的根结点的前面一个结点作为参考，寻找这个结点在前序的位置，就可以根据这个位置来划分左右孩子，递归处理～

#include <iostream>
#include <vector>
using namespace std;
vector<int> in, pre, post;
bool unique = true;
void getIn(int preLeft, int preRight, int postLeft, int postRight) {
    if(preLeft == preRight) {
        in.push_back(pre[preLeft]);
        return;
    }
    if (pre[preLeft] == post[postRight]) {
        int i = preLeft + 1;
        while (i <= preRight && pre[i] != post[postRight-1]) i++;
        if (i - preLeft > 1)
            getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1);
        else
            unique = false;
        in.push_back(post[postRight]);
        getIn(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);
    }
}
int main() {
    int n;
    scanf("%d", &n);
    pre.resize(n), post.resize(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &pre[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &post[i]);
    getIn(0, n-1, 0, n-1);
    printf("%s\n%d", unique == true ? "Yes" : "No", in[0]);
    for (int i = 1; i < in.size(); i++)
        printf(" %d", in[i]);
    printf("\n");
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector<int> in, pre, post;

bool unique = true;

void getIn(int preLeft, int preRight, int postLeft, int postRight) {

if(preLeft == preRight) {

in.push_back(pre[preLeft]);

return;

}

if (pre[preLeft] == post[postRight]) {

int i = preLeft + 1;

while (i <= preRight && pre[i] != post[postRight-1]) i++;

if (i - preLeft > 1)

getIn(preLeft + 1, i - 1, postLeft, postLeft + (i - preLeft - 1) - 1);

else

unique = false;

in.push_back(post[postRight]);

getIn(i, preRight, postLeft + (i - preLeft - 1), postRight - 1);

}

int main() {

int n;

scanf("%d", &n);

pre.resize(n), post.resize(n);

for (int i = 0; i < n; i++)

scanf("%d", &pre[i]);

for (int i = 0; i < n; i++)

scanf("%d", &post[i]);

getIn(0, n-1, 0, n-1);

printf("%s\n%d", unique == true ? "Yes" : "No", in[0]);

for (int i = 1; i < in.size(); i++)

printf(" %d", in[i]);

printf("\n");

return 0;

}