PAT_05_01-测试赛

本来这原文中应该在昨天就发出来的，于是乎，偷了一下懒，就到今天了...
废话不多说直接看题！

7-1 knuth 洗牌法

Knuth 洗牌法是生成 { 1, 2, …, n } 的一个随机重排列的算法。与每次反复随机生成一个数字，直到获得一个不重复的新数字的算法不同，Knuth 洗牌法从原始序列 { 1, 2, …, n } 开始，逐次洗牌。洗牌的方法是从左到右，每轮从没确定的数字中随机抽取一个数，把它放到确定的位置上。
例如令 n 等于 4。我们从 { 1, 2, 3, 4 } 开始。记 i 到 N 之间的随机抽牌数为 random(i,N)。假设我们生成的随机数序列 random(i,4) (i=1, 2, 3, 4) 为 { 2, 4, 3, 4 }。则 Knuth 洗牌法是这样执行的：

• random(1,4) = 2; 将位置 1 与位置 2 的数字交换，得到 { 2, 1, 3, 4 }
• random(2,4) = 4; 将位置 2 与位置 4 的数字交换，得到 { 2, 4, 3, 1 }
• random(3,4) = 3; 将位置 3 与位置 3 的数字交换，得到 { 2, 4, 3, 1 }
• random(4,4) = 4; 将位置 4 与位置 4 的数字交换，得到 { 2, 4, 3, 1 }

现给定随机抽牌数字序列，请你输出 Knuth 洗牌法的结果序列。
输入格式：
输入在第一行中给出一个正整数 N（≤ 1000）。随后一行给出 N 个随机抽牌数字，数字间以空格分隔。题目保证第 i 个数在 i 到 N 之间。
输出格式：
在第一行中输出 Knuth 洗牌法的结果序列。数字间必须以 1 个空格分隔，行首尾不得有多余空格。

Input

10
7 4 4 5 10 6 9 9 10 10

Output

7 4 2 5 10 6 9 1 3 8

Analysis

题目字太多了，不知道是不是姥姥故意这样，来迷惑人，隐藏题意。

其实这个题目就是让你交换数字（算是简单模拟），以样例为例：第一次，处于第一位的数字与处于第七位的数字交换；以第一次得到的结果序列为初始序列，交换处于第二位的数字和处于第四位的数字；依次类推即可。

Code

#include <iostream>
using namespace std;
const int maxn = 1000 + 10;
int seq[maxn];
void init() {
    for(int i = 1; i < maxn; i++) {
        seq[i] = i;
    }
}
int main() {
    int n;
    cin >> n;
    init();
    for(int i = 1; i <= n; i++) {
        int tmp = seq[i], random;
        cin >> random;
        seq[i] = seq[random];
        seq[random] = tmp;
    }
    for(int i = 1; i <= n - 1; i++) {
        cout << seq[i] << ' ';
    }
    cout << seq[n];
    return 0;
}

7-2 三阶幸福数

对一个十进制数的各位数字做一次立方和，称作一次迭代。如果一个十进制数能通过 h 次迭代得到 1，就称该数为三阶幸福数，迭代的次数 h 称为幸福度。例如 1579 经过 1 次迭代得到 1198，2 次迭代后得到 1243，3 次迭代后得到 100，最后得到 1。则 1579 是幸福数，其幸福度为 4。
另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。例如 97 迭代得到 1072、352、160、217、352、…… 可见 352 到 217 形成了死循环，所以 97 就不幸福，而 352 就是它最早遇到的循环点。
本题就要求你编写程序，判断一个给定的数字是否有三阶幸福。

输入在第一行给出一个不超过 100 的正整数 N，随后 N 行，每行给出一个不超过 104 的正整数。

对于每一个输入的数字，如果其是三阶幸福数，则在一行中输出它的幸福度；否则输出最早遇到的循环点。

Input

3
1579
97
1

Output

4
352
0

Analysis

这个题目本质上其实是个数字游戏...
按照题目给定的“游戏规则”来处理就行了，由于需要判断数字是否“幸福”，借助哈希表无疑是最快捷、方便的选择。

Code

下面是当时写的代码，有点乱见谅，这段代码其实用到的思想都是 C 里面的东西，将 cin 和 cout 换成 scanf 和 printf 说不定还能快点呢。

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 100000 + 5;
int hashtable[maxn];
void init() {
    for(int i = 0; i < maxn; i++) {
        hashtable[i] = 0;
    }
}
int main() {
    int n;
    cin >> n;
    while(n--) {
        int num, degree = 0;
        cin >> num;
        init();
        if(num == 1) {
            cout << 0 << endl;
            continue;
        }
        int tmp = num;
        while(1) {
            int digit, res = 0;
            hashtable[tmp] = 1;
            while(tmp) {
                digit = tmp % 10;
                res += pow(digit, 3);
                tmp /= 10;
            }
            degree++;
            hashtable[res]++; 
            if(res == 1) {
                cout << degree << endl;
                break;
            } else if(hashtable[res] == 2) {
                cout << res << endl;
                break;
            }
            tmp = res;
        }
    }
    return 0;
}

7-3 三阶幸福数

据香港《南华早报》2019年7月15日文章，上海严格的垃圾分类新规令不少居民抓狂。这催生出大量帮助找出正确分类答案的App和小程序。目前仅微信上就至少有280种与垃圾处理有关的App，在苹果应用商店也达130种。支付宝表示，已有60多家独立App开发商申请为该平台提供类似服务。
本题就请你现场实现一个简单的垃圾分类小助手。

输入首先给出官方分类指南中每种物品的归属。在一行中给出一个正整数 N（≤10​5≤10​5 \le10​^5≤10​5​​），即物品数量；随后 N 行，每行给出一个物品名称（长度不超过 10 的、由小写英文字母和下划线组成的字符串）和该物品所属的分类（1 代表干垃圾、2 代表湿垃圾、3 代表可回收物、4 代表有害垃圾）。题目保证所有物品名称无重复。
随后每行给出一个查询物品的名称（格式与指南物品名称相同）。最后一行给出结束符 #，表示查询终止，这一行不需要查询。

对每个查询的物品，在一行中给出其所属分类：Gan laji 代表干垃圾；Shi laji 代表湿垃圾；Ke Hui Shou 代表可回收物；You Hai laji 代表有害垃圾。如果查询的物品不在指南中，则输出 ? 表示不知道。

Input

4
bao_zhi 3
dian_chi 4
dan_ke 2
bei_ke 1
dan_ke
dian_chi
ren_zha
bao_zhi
bei_ke
#

Output

Shi laji
You Hai laji
?
Ke Hui Shou
Gan laji

Analysis

考试时，做这个题只想到了 map，没想到 unordered map，单纯只用 map，3分，unordered map，AC。感觉损失惨重...

另外，能不用 cin 和 cout，还是尽量不用...

Code

下面是当时用 map 写的代码：

#include <iostream>
#include <string>
#include <map>
using namespace std;
map<string, int> rab2id;

int main() {
    int n, id;
    cin >> n;
    string str;
    for(int i = 0; i < n; i++) {
        cin >> str >> id;
        rab2id[str] = id;
    }
    while(cin >> str && str != "#") {
        if(rab2id[str] == 1) {
            cout << "Gan laji\n";
        } else if(rab2id[str] == 2) {
            cout << "Shi laji\n";
        } else if(rab2id[str] == 3) {
            cout << "Ke Hui Shou\n";
        } else if(rab2id[str] == 4) {
            cout << "You Hai laji\n";
        } else cout << "?\n";
    }
    return 0;
}

下面是 AC 的代码（如果不想那么多 if-else，也可以利用字符串数组来输出）：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
unordered_map<string, int> rab2id;
char s[20];
 
int main() {
    int n, id;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%s %d", s, &id);
        rab2id[s] = id;
    }
    while(scanf("%s", s) != EOF) {
        string str(s);
        if(str == "#") {
            break; 
        } else if(rab2id[str] == 1) {
            printf("Gan laji\n");
        } else if(rab2id[str] == 2) {
            printf("Shi laji\n");
        } else if(rab2id[str] == 3) {
            printf("Ke Hui Shou\n");
        } else if(rab2id[str] == 4) {
            printf("You Hai laji\n");
        } else printf("?\n");
    }
    return 0;
}

总结

三道 20 分的题目，应该就是乙级 20 分题目的难度？

可能是我太久没有写代码的缘故了，第一道题目被迷惑了挺久的，原本应该十几分钟就搞定的，结果好像快半个小时才搞定...

第二道题目果然解决起来就快了许多（稍微熟悉了一点），不过意外的是没想到有这么多测试点...

第三道题目只想到了 map 无疑是个败笔，不过也反映了自己忘记了太多东西了...😱
而且面对这种卡超时的题目，莫名的有点虚。

反正三道题目都不难就是了，没全部 AC，该检讨。特别是最后一题，几分钟就拿到了 3 分，后面 40 分钟都阵亡了...

PS：前两道题都是一次 AC

---