Code – 第186页

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;

}

1118. Birds in Forest (25)-PAT甲级真题（并查集）

Some scientists took pictures of thousands of birds in a forest. Assume that all the birds appear in the same picture belong to the same tree. You are supposed to help the scientists to count the maximum number of trees in the forest, and for any pair of birds, tell if they are on the same tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number N (<= 104) which is the number of pictures. Then N lines follow, each describes a picture in the format:
K B1 B2 … BK
where K is the number of birds in this picture, and Bi’s are the indices of birds. It is guaranteed that the birds in all the pictures are numbered continuously from 1 to some number that is no more than 104.

After the pictures there is a positive number Q (<= 104) which is the number of queries. Then Q lines follow, each contains the indices of two birds.

Output Specification:

For each test case, first output in a line the maximum possible number of trees and the number of birds. Then for each query, print in a line “Yes” if the two birds belong to the same tree, or “No” if not.

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

题目大意：一幅画里面的鸟为同一棵树上的，问有多少棵树和多少只鸟，以及对于两只鸟判断是否在同一个树上～

分析：使用并查集就可以啦~将一幅画中鸟使用Union函数合并在同一个集合里面，cnt[i]数组保存以i为FindFather结点的集合里面的鸟的个数，exist[i]表示鸟的id——i在输入的鸟的序号里面是否出现过，遍历cnt数组并累加所有不为0的个数即可得知有多少棵树，累加所有出现过的鸟的id的cnt的值即可得知鸟的个数～判断两只鸟是否在同一棵树，只需要知道这两只鸟的findFather是否相等即可～

#include <iostream>
using namespace std;
int n, m, k;
const int maxn = 10010;
int fa[maxn] = {0}, cnt[maxn] = {0};
int findFather(int x) {
    int a = x;
    while(x != fa[x])
        x = fa[x];
    while(a != fa[a]) {
        int z = a;
        a = fa[a];
        fa[z] = x;
    }
    return x;
}
void Union(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB) fa[faA] = faB;
}
bool exist[maxn];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= maxn; i++)
        fa[i] = i;
    int id, temp;
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &k, &id);
        exist[id] = true;
        for(int j = 0; j < k-1; j++) {
            scanf("%d", &temp);
            Union(id, temp);
            exist[temp] = true;
        }
    }
    for(int i = 1; i <= maxn; i++) {
        if(exist[i] == true) {
            int root = findFather(i);
            cnt[root]++;
        }
    }
    int numTrees = 0, numBirds = 0;
    for(int i = 1; i <= maxn; i++) {
        if(exist[i] == true && cnt[i] != 0) {
            numTrees++;
            numBirds += cnt[i];
        }
    }
    printf("%d %d\n", numTrees, numBirds);
    scanf("%d", &m);
    int ida, idb;
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &ida, &idb);
        printf("%s\n", (findFather(ida) == findFather(idb)) ? "Yes" : "No");
    }
    return 0;
}

#include <iostream>

using namespace std;

int n, m, k;

const int maxn = 10010;

int fa[maxn] = {0}, cnt[maxn] = {0};

int findFather(int x) {

int a = x;

while(x != fa[x])

x = fa[x];

while(a != fa[a]) {

int z = a;

a = fa[a];

fa[z] = x;

}

return x;

}

void Union(int a, int b) {

int faA = findFather(a);

int faB = findFather(b);

if(faA != faB) fa[faA] = faB;

}

bool exist[maxn];

int main() {

scanf("%d", &n);

for(int i = 1; i <= maxn; i++)

fa[i] = i;

int id, temp;

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

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

exist[id] = true;

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

scanf("%d", &temp);

Union(id, temp);

exist[temp] = true;

}

for(int i = 1; i <= maxn; i++) {

if(exist[i] == true) {

int root = findFather(i);

cnt[root]++;

}

int numTrees = 0, numBirds = 0;

for(int i = 1; i <= maxn; i++) {

if(exist[i] == true && cnt[i] != 0) {

numTrees++;

numBirds += cnt[i];

}

printf("%d %d\n", numTrees, numBirds);

scanf("%d", &m);

int ida, idb;

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

scanf("%d%d", &ida, &idb);

printf("%s\n", (findFather(ida) == findFather(idb)) ? "Yes" : "No");

}

return 0;

}