PAT甲级2016秋真题

算法素数逻辑题并查集树的遍历

字数统计: 1.9k阅读时长: 10 min

 2023/08/26  6

PAT考试真题解析

[1116] Come on! Let’s C (20)

素数

题目

“Let’s C” is a popular and fun programming contest hosted by the College of Computer Science and Technology, Zhejiang University. Since the idea of the contest is for fun, the award rules are funny as the following:

0、 The Champion will receive a “Mystery Award” (such as a BIG collection of students’ research papers…).
1、 Those who ranked as a prime number will receive the best award – the Minions (小黄人)!
2、 Everyone else will receive chocolates.

Given the final ranklist and a sequence of contestant ID’s, you are supposed to tell the corresponding awards.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer $N (\leq 10^{4})$ , the total number of contestants. Then N lines of the ranklist follow, each in order gives a contestant’s ID (a 4-digit number). After the ranklist, there is a positive integer K followed by K query ID’s.

Output Specification:

For each query, print in a line ID: award where the award is Mystery Award, or Minion, or Chocolate. If the ID is not in the ranklist, print Are you kidding? instead. If the ID has been checked before, print ID: Checked.

注意点与解析

0和1注意特判，不是素数也不是合数；
排名从1开始。

代码

const int N = 1e4;
int n, id, k;
vector<int> info(N), vis(N, 0);
vector<bool> p(N + 1, false);

void findPrime() {
  p[1] = p[0] = true;
  for (int i = 2; i <= N; i++) {
    if (!p[i]) {
      for (int j = i + i; j <= N; j += i)
        p[j] = true;
    }
  }
}

int main() {
  cin >> n;
  findPrime();
  for (int i = 0; i < n; i++) {
    scanf("%d", &id);
    info[id] = i;
    vis[id] = 1;
  }
  cin >> k;
  for (int i = 0; i < k; i++) {
    scanf("%d", &id);
    if (!vis[id])
      printf("%04d: Are you kidding?\n", id);
    else if (vis[id] == -1)
      printf("%04d: Checked\n", id);
    else {
      if (info[id] == 0)
        printf("%04d: Mystery Award\n", id);
      else if (p[info[id]+1] == false)
        printf("%04d: Minion\n", id);
      else
        printf("%04d: Chocolate\n", id);
      vis[id] = -1;
    }
  }
  return 0;
}

[1117] Eddington Number (25)

逻辑题

题目

British astronomer Eddington liked to ride a bike. It is said that in order to show off his skill, he has even defined an “Eddington number”, $E$ – that is, the maximum integer $E$ such that it is for $E$ days that one rides more than $E$ miles. Eddington’s own $E$ was 87.

Now given everyday’s distances that one rides for $N$ days, you are supposed to find the corresponding $E (\leq N)$ .

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer $N (\leq 10^{5})$ , the days of continuous riding. Then $N$ non-negative integers are given in the next line, being the riding distances of everyday.

Output Specification:

For each case, print in a line the Eddington number for these $N$ days.

注意点与解析

满足有E天骑⻋超过E英⾥的最大整数E，从大到小排序后找到第d天，当前 d > vec[d] ，此时满足条件，而前一天 vec[d-1] 不满足条件，vec[d-1]-1 满足，且是最大的E。

代码

vector<int> vec;

int main() {
  int n, i;
  cin >> n;
  vec.resize(n);
  for (int i = 0; i < n; i++)  cin >> vec[i];
  sort(vec.begin(), vec.end(), greater<int>());
  for (i = 0; i < n; i++)
    if (i + 1 > vec[i])  break;
  cout << vec[i-1] - 1;
  return 0;
}

[1118] Birds in Forest (25)

并查集

题目

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 (\leq 10^{4})$ which is the number of pictures. Then $N$ lines follow, each describes a picture in the format:

$K$ $B_{1}$ $B_{2}$ $\dots$ $B_{K}$

where $K$ is the number of birds in this picture, and $B_{i}$ ’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 $10^{4}$ .

After the pictures there is a positive number $Q (\leq 10^{4})$ 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.

代码

const int maxn = 1e4 + 1;
vector<bool> vis(maxn, false);
vector<int> father(maxn, 0), isRoot(maxn, 0);

int findFather(int x) {
  int a = x;
  while (x != father[x])
    x = father[x];
  while (a != father[a]) {
    int z = a;
    a = father[a];
    father[z] = x;
  }
  return x;
}

void Union(int a, int b) {
  int faa = findFather(a);
  int fab = findFather(b);
  if (faa != fab) {
    father[faa] = fab;
  }
}

void init() {
  for (int i = 1; i <= maxn; i++)
    father[i] = i;
}

pair<int, int> countTrees() {
  int ans = 0, birds = 0;
  for (int i = 1; i <= maxn; i++) {
    if (vis[i]) {
      isRoot[findFather(i)]++;
      birds++;
    }
  }
  for (int i = 1; i <= maxn; i++)
    if (isRoot[i])  ans++;
  pair<int, int> num = make_pair(ans, birds);
  return num;
}

int main() {
  int n, k, b, q, c1, c2;
  cin >> n;
  init();
  for (int i = 0; i < n; i++) {
    cin >> k;
    if (k != 0) {
      cin >> c1;
      vis[c1] = true;
    }
    for (int j = 1; j < k; j++) {
      cin >> c2;
      vis[c2] = true;
      Union(c1, c2);
      c1 = c2;
    }
  }
  pair<int, int> ans = countTrees();
  cout << ans.first << " " << ans.second << endl;
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> c1 >> c2;
    if (findFather(c1) == findFather(c2))
      cout << "Yes" << endl;
    else  cout << "No" << endl;
  }
  return 0;
}

[1119] Pre- and Post-order Traversals (30)

前序和后序求树中序

题目

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 (\leq 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.

注意点与解析

前序和后序不能唯一确定一颗树，前序是根左右，后序是左右根，前序遍历的第一个节点 preL 肯定是等于后序遍历的最后一个节点 postR，preL + 1 是左孩子（当左孩子不存在，就是右孩子），postR - 1 是右孩子（同理若有孩子不存在则是左孩子）；
如果发现 preL + 1 的节点是等于 postR - 1 的节点，那么根据遍历的性质，它即可以是左孩子也可以是右孩子，这里我们就无法确定了，题目要求不唯一就随便输出一条，所以我们把他当成左右都可以。因此我们可以在前序找点，也可以在后序找点，然后划分左右区间。
中序的求解可以直接放在求解树结构的函数里，由于是递归，将中序的访问放在左右孩子递归之间即可。
注意特判，preL == preR.

代码

struct TreeNode {
  int val;
  TreeNode *left, *right;
};
bool flag = true;
vector<int> pre, post, in;

TreeNode* create(int preL, int preR, int postL, int postR) {
  TreeNode *root = new TreeNode;
  root -> val = pre[preL];
  root -> left = root -> right = NULL;
  if (preL == preR) {
    in.push_back(pre[preL]);
    return root;
  }
  int k = preL + 1;
  while (k <= preR && pre[k] != post[postR-1])  k++;
  int len = k - preL - 1;
  if (len > 0)
    root -> left = create(preL + 1, k - 1, postL, postL + len - 1);
  else  flag = false;
  in.push_back(post[postR]);
  root -> right = create(k, preR, postL + len, postR - 1);
  return root;
}

int main() {
  int n;
  cin >> n;
  pre.resize(n);
  post.resize(n);
  for (int i = 0; i < n; i++) cin >> pre[i];
  for (int i = 0; i < n; i++) cin >> post[i];
  TreeNode *root = create(0, n - 1, 0, n - 1);
  printf("%s\n%d", flag == true ? "Yes" : "No", in[0]);
  for (int i = 1; i < in.size(); i++)
    printf(" %d", in[i]);
  cout << endl;
  return 0;
}

Next Post

PAT甲级2016冬真题
Previous Post

PAT并查集笔记