PAT (Advanced Level) Practice 1041~1060

1041

---

1042

---

1043

---

1044

---

1045

---

1046

---

1047 Student List for Course

题意：
给出选课人数和课程数目，然后再给出每个人的选课情况，请针对每门课程输出选课人数以及所有选该课的学生的姓名。

思路：

1. 用二维数组 char[N][5] 存放输入的学生姓名，其中 char[i] 表示第 i 个学生姓名；
2. 用容器 vector 定义数组 course[] 存放选每门课的学生编号，其中 course[i] 存放所有选课程 i 的学生编号；
3. 在读入数据时，如果某学生（编号为 i）选择了课程 j，那么就将该学生的编号 i 存到 course[i] 中，即 course[j].push_back(i)；
4. 对于课程 i，将 course[i] 中的学生按姓名字典序从小到大排序，然后输出所需要的结果。

注意点

• 使用 string 来存储学生姓名，则最后一组数据容易超时。像这种数据范围很大的情况，一般最好用 char 数组来存放数据，用 string 很容易超时。
• 使用 vector 来存放每门课程的选课学生编号，可以有效防止所有学生选了所有课程的极端情况导致的空间超限，并且 vector 的使用十分简便，大大降低了编码复杂度，比直接用普通数组的优势更明显。
• 如果排序时直接对字符串排序，那么会导致大量的字符串移动，非常消耗时间。因此比较合适的做法是使用字符串的下标来代替字符串本身进行排序，这样消耗的时间会少得多。
• strcmp 的返回值不一定是-1、0、+1，也有可能是其他正数和负数。这是因为标准中并没有规定必须是-1、0、+1，所以不同编译器在这点上的实现不同。因此，在写 cmp 函数时不能写 strcmp 的返回值等于-1，而必须写小于0，否则不具有普适性，甚至直接出错。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int maxn = 40010; // 最大的学生数量
const int maxc = 2510; // 最大的课程数量// 定义为全局数组防止空间超限
// 同时可以使得 cmp 只传入数组下标即可
char name[maxn][5]; // maxn 个学生
vector<int> course[maxc]; // course[i] 存放第 i 门课的所有学生编号bool cmp(int a, int b) // 按姓名字典序从小到大排序
{
    return strcmp(name[a], name[b]) < 0;
}int main()
{
    int n, k, c; // n 为学生人数，k 为课程数量，c 为每个学生的选课数量scanf("%d%d", &n, &k);for (int i = 0; i < n; ++i){
    int d; // 学生的选课编号scanf("%s %d", name[i], &c);for (int j = 0; j < c; ++j){
    scanf("%d", &d);course[d].push_back(i); // 将学生 i 加入课程 d 中}}for (int i = 1; i <= k; ++i){
    printf("%d %d\n", i, course[i].size());sort(course[i].begin(), course[i].end(), cmp); // 对课程 i 下的学生姓名进行排序for (int j = 0; j < course[i].size(); ++j)printf("%s\n", name[course[i][j]]); // 输出选课程 i 的学生的姓名}return 0;
}

---

1048

---

1049 Counting Ones

思路：
如果从1枚举到 n 是必定会超时的，正确的做法是寻找其中的数字规律。假设 $n=n_5{n}_4{n}_3{n}_2{n}_1=30710$，其中 $x_m,1<m<5$ 表示 m 号位。思路就是，用 k 遍历 1 ~ n，固定 k 的某一位为1，对 k 的每一位进行分类讨论，然后看其两边的数能取到的范围（必须要满足最后的 k 小于等于 n）然后确定出该位为1的情况总数。

1. 当一号位 $k_1=1$，即 $k=k_5{k}_4{k}_3{k}_{2}1$ 时。

由于 n 的一号位为0（小于1），所以 k 的高四位即 $k_5{k}_4{k}_3{k}_2$ 的取值范围是 [0, 3070]，不能超过3070，否则 $k=30711>n=30710$。所以从 1 ~ n 的过程中，数 k 的一号位会出现3071（从0算起的）次1。

2. 当二号位 $k_2=1$，取 $k=k_5{k}_4{k}_{3}1k_1$ 时。

由于 n 的二号位为1（等于1），因此当 k 的高三位即 $k_5{k}_4{k}_3$ 的取值范围为 [0, 306] 时，k 的一号位的范围就为 [0, 9]。所以总共有 307 * 10 = 3070 种情况；

当 k 的高三位即 $k_5{k}_4{k}_3=307$ 时，此时 k 的一号位只能为0，否则又会导致 $k>n$，故只有30710这一种情况。综合起来就是从 1 ~ n 的过程中，数 k 的二号位会出现 3070 + 1 = 3071 次1。这种情况相对于 k 枚举到了 n。

3. 当三号位 $k_3=1$，取 $k=k_5{k}_{4}1k_2{k}_1$ 时。

由于 n 的三号位为7（大于1），因此 k 的高两位即 $k_5{k}_4$ 的取值范围为 [0, 30]，可以达到30而不会导致 k 超过 n 的范围。而 k 的低两位即 $k_2{k}_1$ 的取值范围为 [0, 99]，所以从 1 ~ n 的过程中，数 k 的三号位会出现 31 * 100 = 3100 次1。

4. 当四号位 $k_4=1$，取 $k=k_{5}1k_3{k}_2{k}_1$ 时。

由于 n 的四号位为0（小于1），因此 k 的高一位的取值范围为 [0, 2]，k 的低三位即 $k_3{k}_2{k}_1$ 的取值范围为 [0, 999]，总共有 3 * 1000 = 3000 种情况。当最高位为3时，不超过 n 的情况只存在30710，而它在前面已经计入了总数，故不重复计算。

5. 当五号位 $k_5=1$，取 $k=1k_4{k}_3{k}_2{k}_1$ 时。

由于 n 的五号位为3（大于1），因此 k 的低四位即 $k_4{k}_3{k}_2{k}_1$ 的取值范围为 [0, 9999]，无论如何都不会出现超过 n 的情况，所以从 1 ~ n 的过程中，数 k 的五号位会出现 10000 次1。

综上，从 1 ~ n 的过程中，总共会出现 3071 + 3071 + 3100 + 3000 + 10000 = 22242 次1。观察可以发现，高位的数的范围会根据当前位与1的大小关系而发生变化，而低位的数的范围永远只和低位有多少位有关。低位有一位范围就是 [0, 9]，有两位就是 [0, 99]。唯一的一次变化就是在当前位刚好为1时（前面的第二类讨论），需要多分一种高位和当前位都与 n 相等的特殊情况，此时低位的范围应为 [0, 低位所能表示的最大的数 - 1]。

总结一下步骤就是：

第一步以 ans 代表1的个数，初值为0。设 n 是一个 m 位的数，像前面的分类讨论一样从低位向高位枚举 n 的每一位。

第二步设立循环，令变量 p 的初值为1， 每过一轮循环它都自乘10。记 high 为当前位的高位（即当前位的左边）所表示的数，记 low 为当前位的低位所表示的数，记 now 为当前位上的数，然后进行分类讨论：

• 若 now == 0，由前面的讨论可知高位的范围为 [0, high - 1]，低位的范围为 [0, p - 1]，故 ans = (high - 1 + 1) * (p - 1 + 1) = high * p（从0开始的，所以要加1）；
• 若 now == 1，由前面可知此时要分两种情况：第一种，高位范围为 [0, high - 1]，此时低位范围可以达到 [0, p - 1]，故 ans = high * p；第二种，高位和当前位与 n 相等，此时高位只能为 high，低位的范围被压缩至 [0, low]，故 ans = low + 1。综合起来，ans = high * p + low + 1；
• 若 now >= 1，由前面可知高位的范围被彻底放开，可达到 [0, high]，低位的范围为 [0, p - 1]，故 ans = (high + 1) * p。

对代码中的关键部分进行一下解释：

• 首先一个很重要的变量就是 p。假设低位有 i 位，p 的值实际上是 $p^i$，即 10 的 i 次方。这很好理解：一位数最大为9，两位数最大为99，三位数最大为999，这同时也代表了 low 的范围上限。故令 p 在每一步循环后都自乘10，那么 p - 1 便是下一次循环中低位的上限值。而在具体的实现过程中，我们并不需要 low，因为 low = n % p。比如 n = 30710，若当前位为7，则 low = 10， 低两位的最大值为99，p 为100。此时 low 不就等于 30710 % 100吗？所以在 now == 1 时，我将 low 用 n % p 来替换掉了。
• 初始时 high 为 n，每次进入循环后，首先令 now = high % 10，目的是为了跟踪当前位上的数，再令 high /= 10，从而也得到了高位的值。比如刚开始进入循环，now = high % 10 = 0，high /= 10 得到 high = 3071。

这一道题目的内容写了我很久，就是希望读者能够理解的更轻松一点，如果学到了，别忘记点个赞鼓励支持我一下呀~~~

#include<cstdio>
using namespace std;int main()
{
    int n, ans, high, now, p;scanf("%d", &n);high = n, ans = 0, p = 1; // 别忘记初始化while (n / p != 0){
    now = high % 10;high /= 10;if (now == 0)ans += high * p;else if (now == 1)ans += high * p + n % p + 1; // low = n % pelseans += (high + 1) * p;p *= 10;}printf("%d", ans);return 0;
}

---

1050

---

1051 Pop Sequence

题意：
有一个容量限制为 M 的栈，入栈顺序固定为1, 2, 3… , n。输入给出一系列出栈顺序，问这些出栈顺序是否可能由该入栈顺序得到。

思路：
按照题目的要求进行模拟，将 1 ~ n 依次入栈，用一个标记指向出栈序列第一个待出栈元素。如果入栈的元素恰好等于出栈序列当前等待出栈的元素，那么就让栈顶元素出栈，同时让标记指向下一个待出栈元素。此时只要栈顶元素仍然等于出栈序列当前等待出栈的元素，则持续出栈。

1. 初始化栈，读入需要测试的出栈序列；
2. 由于入栈顺序为 1 ~ n，因此用 i 枚举 1 ~ n，对每一个 i，先将 i 入栈。然后检查栈顶元素和待出栈元素是否相等，相等则栈顶元素出栈，待出栈标记指向下一个，继续循环检查；
3. 如果循环检查结束了，发现栈是满的，说明此时栈顶元素与待出栈元素不相等，而无法继续入栈，故表明该出栈序列不能由该入栈序列得到，退出循环；
4. 如果上述操作结束后栈空，则说明该出栈顺序合法，输出“YES"；否则，输出“NO”。

注意点：

• 首先要注意的是题目对栈的大小有限制，不能忽视这一点，因此要在 for 循环末尾检查栈的状态。
• 栈满之后如果栈顶元素与待出栈元素不相等要退出循环，因为此时不论如何都无法得到该出栈序列。

#include <iostream>
#include <stack>
using namespace std;int main()
{
    int m, n, k;cin >> m >> n >> k;while (k--) // k 个需要判定的出队顺序{
    stack<int> st;int pop[n + 1];for (int i = 1; i <= n; ++i) // 输入出栈序列cin >> pop[i];for (int i = 1, j = 1; i <= n; ++i) // 入栈序列逐个入栈，j 指向待出栈元素{
    st.push(i);while (!st.empty() && st.top() == pop[j]) // 栈不空且入栈元素和出栈元素相等时循环{
    st.pop(); // 入栈元素出栈++j; // j 指向下一个待出栈元素}if (st.size() == m) // 栈满且栈顶与待出栈元素不相等break; // 退出循环}if (st.empty() == 1) // 栈空，说明由入栈顺序可以得到该出栈顺序cout << "YES\n"; // 输出 YESelse cout << "NO\n";}return 0;
}

---

1052 Linked List Sorting

题意：
首先给出结点的个数 N 以及头结点的地址，接下来是 N 个结点的信息，最后要求将结点按照关键值从小到大进行排序。其实就是排序 + 将每个结点的 next 域进行修改。

思路：

1. 定义静态链表，flag 表示结点是否在链表中；
2. 由题目给出的链表首地址 _begin 遍历整条链表，标记有效结点的 flag 为 true，同时计数有效结点的个数 count；
3. 对结点进行排序，排序函数 cmp 的排序原则是：如果 cmp 的两个参数结点中有无效结点的话，则按 flag 从小到大排序，以把有效结点排到数组左端；否则按数据域从小到大排序；
4. 由于有效结点已经按照数据域从小到大排序，因此按要求输出有效结点即可；

注意点：

• 直接使用 %05d 的输出格式，以在不足五位时再高位补0。但是要注意-1不能使用 %05d 输出，否则会输出-0001，因此必须要留意-1的输出。
• 题目可能会有无效结点，即不在题目给出的首地址开始的链表上。
• 数据里面还有均为无效的情况，这时就要根据有效结点的个数特判输出“0 -1”。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 100010;struct Node{
     // 定义静态链表int address, data, next; // 数据域bool flag = false; // 标志结点是否在链表上
}node[maxn];bool cmp(Node a, Node b)
{
    if (a.flag == false || b.flag == false)return a.flag > b.flag; // 只要 a 和 b 中有一个无效结点，就把它放到后面去elsereturn a.data < b.data; // 如果都是有效结点，则按要求排序
}int main()
{
    //freopen("input.txt", "r", stdin);int n, _begin, address; // s1 与 s2 分别代表两条链表的首地址scanf("%d%d", &n, &_begin);for (int i = 0; i < n; ++i){
    scanf("%d", &address);scanf("%d%d", &node[address].data, &node[address].next);node[address].address = address;}int _count = 0, p = _begin;// 枚举链表，对 flag 进行标记，同时计数有效结点个数while (p != -1){
    node[p].flag = true;++_count;p = node[p].next;}if (_count == 0) // 特判，新链表中没有结点时输出0 -1printf("0 -1");else{
    // 筛选有效结点，并按 data 从小到大排序sort(node, node + maxn, cmp);printf("%d %05d\n", _count, node[0].address); // 输出结果for (int i = 0; i < _count; ++i){
    if (i != _count - 1) // 防止-1被 %05d 化，提前判断printf("%05d %d %05d\n", node[i].address, node[i].data, node[i + 1].address);elseprintf("%05d %d -1\n", node[i].address, node[i].data);}}return 0;
}

1053

---

1054 The Dominant Color

比较简单，用 map 代替散列表记录一下每个数字出现的次数即可。注意点都写在注释中了。

#include <cstdio>
#include <map>
using namespace std;int main()
{
    map<int, int> image;int m, n, color;scanf("%d%d", &m, &n); // 图像的分辨率while (n--){
    int k = m; // 每行循环 m 次while (k--){
    scanf("%d", &color); // map 的类型为 int 型时，默认键值为0，故可以直接+1image[color] += 1;}}int c = 0, maxc = image[0]; // 最大数字及该数字出现的次数for (map<int, int>::iterator it = image.begin(); it != image.end(); ++it){
    if (it -> second > maxc){
    maxc = it -> second;c = it -> first;}}printf("%d", c);return 0;
}

---

1055

---

1056 Mice and Rice

题意：
给出 NP 只老鼠的质量，并给出它们的初始顺序（具体见样例解释)，按这个初始顺序把这些老鼠按每 NG 只分为一组，最后不够 NG 只的也单独分为一组。对每组老鼠，选出它们中质量最大的1只晋级，这样晋级的老鼠数就等于该轮分组的组数。对这些晋级的老鼠再按上面的步骤每 NG 只分为一组进行比较，选出质量最大的一批继续晋级，这样直到最后只剩下1只老鼠，排名为1。把这些老鼠的排名按原输入的顺序输出。

思路：

1. 开一个结构体 MICE，用以记录每只老鼠的质量和排名。定义一个队列，用来在算法过程中按顺序处理每轮的老鼠，初始时把老鼠们的编号按顺序加入队列；
2. 之后进入 while 循环，每一层循环代表一轮比赛。每轮比赛把老鼠分成 group 组：设当前轮的参赛老鼠数有 temp 只，如果 temp % ng 为0，那么说明能够把老鼠完整划分，因此 group = temp / NG；否则，说明最后会有少于 ng 只老鼠会单独分为一组，此时组数 group = temp / ng +1；
3. 对每一轮比赛，枚举队列内的当前轮的 temp 只老鼠，按每 ng 只老鼠一组选出组内质量最大的老鼠，并将其入队表示晋级，而当前轮老鼠的排名（即 group + 1）可在选出最大老鼠的过程中直接对每只老鼠都赋值（晋级的老鼠在下一轮比赛时会得到新的排名）；
4. 这样直到队列中只剩下1只老鼠，就把它的排名记为1。最后输出所有老鼠的排名。

注意点：

• 题目中给出的顺序其实是出场顺序而不是编号，编号就是它们存入数组时的下标。
• C++ 的容器 queue 中有一个出队函数 pop()，要注意它是用 void 定义的，没有返回值。因此想直接用 push 函数将弹出的元素压入队列即 match.push(wait.pop()) 是错误的语法。

#include <iostream>
#include <queue>
using namespace std;struct MICE{
     // 老鼠结构体int rk; // 排名int weight; // 体重
};int main()
{
    int np, ng, number;cin >> np >> ng; // 总的老鼠个数和每组老鼠个数MICE mice[np];for (int i = 0; i < np; ++i)cin >> mice[i].weight; // 输入每只老鼠的体重queue<int> q;for (int i = 0; i < np; ++i){
    cin >> number; // 输入编号q.push(number); // 编号入队}int temp = np, group; // temp 为当前轮比赛总老鼠数while (q.size() != 1) // 等待队列只剩一只老鼠时结束循环{
    if (temp % ng == 0) // 计算本轮比赛组数group = temp / ng;else group = temp / ng + 1;for (int i = 0; i < group; ++i){
    int index = q.front(); // k 存放该组质量最大的老鼠的编号for (int j = 0; j < ng; ++j){
    if (i * ng + j >= temp)break; // 最后一组老鼠数不足 ng 时退出循环int fi = q.front(); // 取队首老鼠编号if (mice[fi].weight > mice[index].weight)index = fi; // 找出质量最大的老鼠mice[fi].rk = group + 1; // 更新该轮被淘汰老鼠排名q.pop();}q.push(index); // 该组获胜老鼠晋级}temp = group; // group 只老鼠晋级，因此下一轮总老鼠数为 group}mice[q.front()].rk = 1; // 最后剩下的一只老鼠为最终获胜者，排名为1for (int i = 0; i < np; ++i) // 输出所有老鼠的排名{
    cout << mice[i].rk;if (i < np - 1)cout << " ";}return 0;
}

---

1057

---

1058

---

1059 Prime Factors

注意点：

• 因为是 long int (大多数情况下，long int 就是 int) 范围内的整数，素数表需要开到 $10^5$。
• 注意 n == 1 需要特判输出 “1=1”。
• 质因数分解的知识请看博客：PTA 算法笔记重点总结（二）第26、27的知识点。

#include<cstdio>
#include<cmath>
using namespace std;const int maxn = 100010;
int prime[maxn], pNum = 0, num = 0;
bool p[maxn] = {
    false};struct factor
{
    int x, cnt; // x 为质因子，cnt 为该质因子的个数
}fac[maxn];void decomposed(int n)
{
    int temp = n, sqr = (int)sqrt(n * 1.0); // 用 temp 暂存整数 n 的值for (int i = 0; i < pNum && prime[i] <= sqr; ++i){
     // 循环执行的条件要尤其注意if (temp % prime[i] == 0) // 如果 prime[i] 是 temp 的质因子{
    fac[num].x = prime[i]; // 记录该质因子fac[num].cnt = 0; // 初始化个数为0，在整除时才加1while (temp % prime[i] == 0) // 计算出质因子 prime[i] 的个数{
    ++fac[num].cnt; // 质因子个数加1temp /= prime[i]; // 整除}++num; // 不同质因子个数加1}if (temp == 1) break; // 及时退出循环节省时间}if (temp != 1) // 如果无法被根号 n 以内的质因子除尽{
    fac[num].x = temp; // 那么一定有一个大于根号 n 的质因子fac[num++].cnt = 1;}
}int main()
{
    int n;scanf("%d", &n);if (n == 1) printf("1=1");else{
    for (int i = 2; i < maxn; ++i) // 这个 for 循环为欧拉分解{
    if (p[i] == false)prime[pNum++] = i;for (int j = 0; i * prime[j] <= maxn; ++j){
    p[i * prime[j]] = true;if (i % prime[j] == 0)break;}}decomposed(n); // 进行质因子分解printf("%d=", n);for (int i = 0; i < num; ++i) // 该循环按格式输出结果{
    if (i > 0) printf("*"); // 第一个质因子前不输出 *printf("%d", fac[i].x);if (fac[i].cnt > 1) // 质因子个数大于1才以指数形式输出printf("^%d", fac[i].cnt);}}return 0;
}

---

1060 Are They Equal

题意：
将两个数改写成保留 N 位小数的科学记数法（不四舍五入）并检查它们是否相等。

思路：
科学计数法的写法一定是如下格式：$0.a_1{a}_2{a}_3???\times 10^e$，因此只需要获取到科学记数法的本体部分 $a_1{a}_2{a}_3$ 与指数 e 即可。
按整数部分是否为0分有两种情况：

1. $0.a_1{a}_2{a}_3???$
2. $b_1{b}_2???b_m.a_1{a}_2{a}_3???$

第一种情况下，本体是从小数点后第一个非零位开始的 n 位，即 $a_k{a}_{k+1}???a_{k+n?1}$，其中 $a_k$ 是第一个非零位。指数则是小数点与该非零位之间0的个数的相反数（例如0.001的指数为-2）。所以可令 e = 0，小数点后每有一个0，e 就减1，直到达到最后一位（有可能小数点后全为0）或是出现非零位为止。

第二种情况下，当 $b_1?=0$ 时，本体就是从$b_1$开始的 n 位，而指数则是小数点前的总位数 m。所以可令 e = 0，然后从前往后枚举，只要不达到最后一位（因为可能没有小数点）或是出现小数点，就让 e 加1。

如何区分输入的是数属于哪种情况呢，事实上题目还设了一个陷阱，就是数据有可能出现前导0例如000.01或者000123.45。所以我们要先去除前导0（包括小数点前面的0），然后根据字符串的第一位是否为小数点来判断属于哪种情况。

只剩最后一个问题了，怎么知道两者是否相等呢？因为我们要比较本体部分，所以比较合适的方法是：对于第一种情况，删除前导0、小数点、第一个非零位前的0，只保留本体部分；对于第二种数据，删除前导0和小数点。之后对剩余的部分取有效位数的部分赋值到新字符串中，长度不够时补0。最后比较本体部分与指数是否分别相等，按情况输出即可。

#include <iostream>
#include <string>
using namespace std;int n; // 有效位数string Deal(string s, int &e)
{
    int k = 0; // s的下标while (s.length() > 0 && s[0] == '0')s.erase(s.begin()); // 去掉 s 的前导0if (s[0] == '.') // 第一种情况，去掉前导0后是小数点，说明 s 是小于1的小数{
    s.erase(s.begin());while (s.length() > 0 && s[0] == '0'){
    s.erase(s.begin());--e;}}else // 第二种情况，去掉前导0后不是小数点，说明 s 是大于1的数，则找到后面的小数点删除{
    while (k < s.length() && s[k] != '.') // 寻找小数点{
    ++k; ++e; // 只要不碰到小数点就让指数加1}if (k < s.length()) // while 结束后如果 k < s.length()，说明碰到了小数点s.erase(s.begin() + k); // 把小数点删除}if (s.length() == 0)e = 0; // 如果去除前导0后 s 的长度变为0，说明这个数是0int num = 0;k = 0;string res;while (num < n) // 只要精度还没有到 n{
    if (k < s.length())res += s[k++]; // 只要还有数字，就加到 res 末尾elseres += '0'; // 否则 res 末尾添加0++num;}return res;
}int main()
{
    string a1, a2, b1, b2; // a2, b2为主体部分cin >> n >> a1 >> a2;int e1 = 0, e2 = 0; // e1, e2 为指数b1 = Deal(a1, e1);b2 = Deal(a2, e2);if (b1 == b2 && e1 == e2) // 主体相同且指数相同则YEScout << "YES 0." << b1 << "*10^" << e1 << endl;elsecout << "NO 0." << b1 << "*10^" << e1 <<" 0." << b2 << "*10^" << e2 << endl;return 0;
}

---

一定要自己写一遍哦~~