PAT甲级2016夏真题

算法并查集字符串哈希排序二叉搜索树

字数统计: 2k阅读时长: 11 min

 2023/08/25 

PAT考试真题解析

[1112] Stucked Keyboard (20)

STL, Map的应用, 字符串处理

题目

On a broken keyboard, some of the keys are always stucked. So when you type some sentences, the characters corresponding to those keys will appear repeatedly on screen for k times.

Now given a resulting string on screen, you are supposed to list all the possible stucked keys, and the original string.

Notice that there might be some characters that are typed repeatedly. The stucked key will always repeat output for a fixed k times whenever it is pressed. For example, when $k=3$, from the string thiiis iiisss a teeeeeest we know that the keys i and e might be stucked, but s is not even though it appears repeatedly sometimes. The original string could be this isss a teest.

Input Specification:

Each input file contains one test case. For each case, the 1st line gives a positive integer $k (1<k≤100)$ which is the output repeating times of a stucked key. The 2nd line contains the resulting string on screen, which consists of no more than 1000 characters from {a-z}, {0-9} and _. It is guaranteed that the string is non-empty.

Output Specification:

For each test case, print in one line the possible stucked keys, in the order of being detected. Make sure that each key is printed once only. Then in the next line print the original string. It is guaranteed that there is at least one stucked key.

注意点与解析

注意在判断连续字符的时候，连续字符的个数必须得是题目stucked数目 k 的整数倍，因为坏键每次都应该重复 k 次（测试点1）

代码

int n;
string ori, alt;
map<char, bool> mp;
map<char, bool> prt;

int main() {
  cin >> n >> ori;
  int i = 0;
  while (i < ori.size()) {
    int k = i + 1;
    while (k < ori.size() && ori[i] == ori[k])  k++;
    if (k - i >= n) {
      if ((k - i) % n == 0) {
        mp[ori[i]] = true;
        prt[ori[i]] = true;
      } else {
        mp[ori[i]] = false;
        prt[ori[i]] = false;
      }
      i = k;
    } else {
      mp[ori[i]] = false;
      prt[ori[i]] = false;
      i++;
    }
  }
  i = 0;
  while (i < ori.size()) {
    if (mp[ori[i]] == false) {
      alt.push_back(ori[i]);
      i++;
    } else {
      int k = i + 1;
      while (k < ori.size() && ori[i] == ori[k])  k++;
      int cur = k - i;
      while (cur > 0) {
        alt.push_back(ori[i]);
        cur -= n;
      }
      if (prt[ori[i]] == true) {
        cout << ori[i];
        prt[ori[i]] = false;
      }
      i = k;
    }
  }
  cout << endl << alt;
  return 0;
}

[1113] Integer Set Partition (25)

排序

题目

Given a set of $N (>1)$ positive integers, you are supposed to partition them into two disjoint sets $A_1$ and $A_2$ of $n_1$ and $n_2$ numbers, respectively. Let $S_1$ and $S_2$ denote the sums of all the numbers in $A_1$ and $A_2$, respectively. You are supposed to make the partition so that $\left| n_1−n_2 \right|$ is minimized first, and then $\left| S_1−S_2 \right|$ is maximized.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer $N (2≤N≤10^5)$, and then $N$ positive integers follow in the next line, separated by spaces. It is guaranteed that all the integers and their sum are less than $2^{31}$.

Output Specification:

For each case, print in a line two numbers: $\left| n_1−n_2 \right|$ and $\left| S_1−S_2 \right|$, separated by exactly one space.

代码

int n, sum, hs;
vector<int> num;

int main() {
  cin >> n;
  num.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> num[i];
    sum += num[i];
  }
  sort(num.begin(), num.end());
  for (int i = 0; i < n / 2; i++)
    hs += num[i];
  printf("%d %d", n % 2, sum - 2 * hs);
  return 0;
}

[1114] Family Property (25)

并查集

题目

This time, you are supposed to help us collect the data for family-owned property. Given each person’s family members, and the estate info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer $N (≤1000)$. Then $N$ lines follow, each gives the infomation of a person who owns estate in the format:

ID Father Mother $k Child_1⋯Child_k$ $M_{estate}$ Area

where ID is a unique 4-digit identification number for each person; Father and Mother are the ID’s of this person’s parents (if a parent has passed away, -1 will be given instead); $k (0≤k≤5)$ is the number of children of this person; $Child_i$’s are the ID‘s of his/her children; $M_{estate}$ is the total number of sets of the real estate under his/her name; and Area is the total area of his/her estate.

Output Specification:

For each case, first print in a line the number of families (all the people that are related directly or indirectly are considered in the same family). Then output the family info in the format:

ID M $AVG_{sets}$ $AVG_{area}$

where ID is the smallest ID in the family; M is the total number of family members; $AVG_{sets}$ is the average number of sets of their real estate; and $AVG_{area}$ is the average area. The average numbers must be accurate up to 3 decimal places. The families must be given in descending order of their average areas, and in ascending order of the ID‘s if there is a tie.

注意点与解析

分别⽤两个结构体数组，⼀个 info ⽤来接收数据，接收的时候顺便实现了并查集的操作union，另⼀个数组 ans ⽤来输出最后的答案；
因为要计算家庭⼈数，所以⽤ vis 标记所有出现过的结点，对于每个结点的⽗结点，num++ 统计⼈数。标记 flag == true，计算 true 的个数 cnt 就可以知道⼀共有多少个家庭。

代码

struct Node {
  int id, fid, mid, sets, area;
  vector<int> child;
};
struct Res {
  int id, num;
  double area, sets;
  bool flag = false;
};

int n;
const int N = 10000;
vector<Res> ans(N);
vector<Node> info;
vector<bool> vis(N, false);
vector<int> father(N);

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);
  // where ID is the smallest ID in the family
  if (faA > faB)
    father[faA] = faB;
  else if (faA < faB)
    father[faB] = faA;
  return;
}

void init() {
  for (int i = 0; i < N; i++)
    father[i] = i;
  return;
}

int main() {
  cin >> n;
  info.resize(n);
  init();

  int nchild, ichild, cnt = 0;
  for (int i = 0; i < n; i++) {
    scanf("%d %d %d %d", &info[i].id, &info[i].fid, &info[i].mid, &nchild);
    vis[info[i].id] = true;
    if (info[i].fid != -1) {
      vis[info[i].fid] = true;
      Union(info[i].fid, info[i].id);
    }
    if (info[i].mid != -1) {
      vis[info[i].mid] = true;
      Union(info[i].mid, info[i].id);
    }
    for (int j = 0; j < nchild; j++) {
      scanf("%d", &ichild);
      vis[ichild] = true;
      info[i].child.push_back(ichild);
      Union(ichild, info[i].id);
    }
    scanf("%d %d", &info[i].sets, &info[i].area);
  }
  for (int i = 0; i < n; i++) {
    int cur = findFather(info[i].id);
    ans[cur].id = cur;
    ans[cur].sets += info[i].sets;
    ans[cur].area += info[i].area;
    ans[cur].flag = true;
  }
  for (int i = 0; i < N; i++) {
    if (vis[i]) ans[findFather(i)].num++;
    if (ans[i].flag)  cnt++;
  }
  for (int i = 0; i < N; i++) {
    if (ans[i].flag) {
      ans[i].sets = (double)(ans[i].sets * 1.0 / ans[i].num);
      ans[i].area = (double)(ans[i].area * 1.0 / ans[i].num);
    }
  }
  sort(ans.begin(), ans.end(), [&](Res a, Res b) {
    if (a.area != b.area) return a.area > b.area;
    else  return a.id < b.id;
  });
  cout << cnt << endl;
  for(int i = 0; i < cnt; i++)
    printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].num, ans[i].sets, ans[i].area);
  return 0;
}

[1115] Counting Nodes in a Binary Search Tree (30)

二叉搜索树

题目

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer $N (≤1000)$ which is the size of the input sequence. Then given in the next line are the N integers in $[−1000,1000]$ which are supposed to be inserted into an initially empty binary search tree.

Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format: n1 + n2 = n, where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

注意点与解析

注意 maxDepth 的值为实际最大深度加上1；

代码

struct TreeNode {
  int val;
  TreeNode *left, *right;
};
int maxDepth = 0, n;
vector<int> num(1000);

void insert(TreeNode* & root, int x) {
  if (!root) {
    root = new TreeNode;
    root -> val = x;
    root -> left = root -> right = NULL;
    return;
  }
  if (x > root -> val) insert(root -> right, x);
  else  insert(root -> left, x);
}

void dfs(TreeNode* root, int depth) {
  if (!root) {
    maxDepth = max(depth, maxDepth);
    return;
  }
  num[depth]++;
  dfs(root -> left, depth + 1);
  dfs(root -> right, depth + 1);
}

int main() {
  cin >> n;
  TreeNode* root = NULL;
  int k;
  for (int i = 0; i < n; i++) {
    cin >> k;
    insert(root, k);
  }
  dfs(root, 1);
  printf("%d + %d = %d", num[maxDepth-1], num[maxDepth-2], num[maxDepth-1] + num[maxDepth-2]);
  return 0;
}

Next Post

PAT并查集笔记
Previous Post

PAT甲级2016春真题