1 Knuth洗牌法 (20分)
题目描述
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 个空格分隔，行首尾不得有多余空格。
输入样例
10
7 4 4 5 10 6 9 9 10 10
输出样例
7 4 2 5 10 6 9 1 3 8
思路
水题，用三变量交换法，交换数组的值即可。
题解
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e3 + 5;
int a[maxn] = {0}, b[maxn] = {0};
int main() {
#ifdef ONLINE_JUDGE
#else
freopen("input.txt", "r", stdin);
#endif
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = i;
}
for(int i = 1; i <= n; i++) {
int t1 = i, t2 = a[i];
int temp = b[t1];
b[t1] = b[t2];
b[t2] = temp;
}
for(int i = 1; i <= n; i++) {
if(i == 1) {
cout << b[i];
} else {
cout << " " << b[i];
}
}
return 0;
}
2 三阶幸福数 (20分)
题目描述
对一个十进制数的各位数字做一次立方和，称作一次迭代。如果一个十进制数能通过 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 行，每行给出一个不超过 $10^{4}$ 的正整数。
输出格式
对于每一个输入的数字，如果其是三阶幸福数，则在一行中输出它的幸福度；否则输出最早遇到的循环点。
输入样例
3
1579
97
1
输出样例
4
352
0
思路
- 用 $set$ 存储每次迭代生成的数据，如果 $sum$ 为 $1$，输出 $ans$ ，跳出循环。如果找到相同的值，则输出。
- 注意 $17$ 行，对 $st$ 清空操作。
- 注意对特例 $1$ 的处理。
题解
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
set<int> st;
int main() {
#ifdef ONLINE_JUDGE
#else
freopen("input.txt", "r", stdin);
#endif
int n;
cin >> n;
for(int i = 0; i < n; i++) {
int num, ans = 0;
st.clear();
cin >> num;
if(num == 1) {
printf("0\n");
continue;
}
while(true) {
st.insert(num);
int sum = 0;
while(num) {
sum += (num % 10) * (num % 10) * (num % 10);
num /= 10;
}
ans++;
if(sum == 1) {
printf("%d\n", ans);
break;
} else if(st.find(sum) != st.end()) {
printf("%d\n", sum);
break;
}
num = sum;
}
}
return 0;
}
3 垃圾分类 (20分)
题目描述
据香港《南华早报》2019 年 7 月 15 日文章，上海严格的垃圾分类新规令不少居民抓狂。这催生出大量帮助找出正确分类答案的 App 和小程序。目前仅微信上就至少有 280 种与垃圾处理有关的 App，在苹果应用商店也达 130 种。支付宝表示，已有 60 多家独立 App 开发商申请为该平台提供类似服务。
本题就请你现场实现一个简单的垃圾分类小助手。
输入格式
输入首先给出官方分类指南中每种物品的归属。在一行中给出一个正整数 N（≤ $10^5$），即物品数量；随后 N 行，每行给出一个物品名称（长度不超过 10 的、由小写英文字母和下划线组成的字符串）和该物品所属的分类（1 代表干垃圾、2 代表湿垃圾、3 代表可回收物、4 代表有害垃圾）。题目保证所有物品名称无重复。
随后每行给出一个查询物品的名称（格式与指南物品名称相同）。最后一行给出结束符#，表示查询终止，这一行不需要查询。
输出格式
对每个查询的物品，在一行中给出其所属分类：
Gan laji代表干垃圾；Shi laji代表湿垃圾；Ke Hui Shou代表可回收物；You Hai laji代表有害垃圾。如果查询的物品不在指南中，则输出?表示不知道。
输入样例
4
bao_zhi 3
dian_chi 4
dan_ke 2
bei_ke 1
dan_ke
dian_chi
ren_zha
bao_zhi
bei_ke
#
输出样例
Shi laji
You Hai laji
?
Ke Hui Shou
Gan laji
思路
- 用一个 $char$ 数组和 $map$ 存储，反向取值即可。
- 注意 $23$ 行，存在多次输入时，用 $cin$ 会运行超时。
题解
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
using namespace std;
char chr[5][20] = {"?", "Gan laji", "Shi laji","Ke Hui Shou","You Hai laji"};
map<string, int> mp;
char str[20];
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("input.txt", "r", stdin);
#endif
int n;
cin >> n;
for(int i = 0;i < n;i++){
int num;
cin >> str >> num;
mp[str] = num;
}
// while((cin >> str) && (str != "#")){
while(scanf("%s", str) != EOF && strcmp("#", str) != 0){
puts(chr[mp[str]]);
}
return 0;
}
