L2-1 盲盒包装流水线 (25 分)
众所周知，PAT 有 9 枚徽章，分别对应青铜、白银、黄金、白金、钻石、大师、王者、大圣、天神这 9 个段位，只有成绩非常优秀的考生才有资格获得刻有自己名字的徽章。现在，PAT 制作了徽章的小型纪念版，要制成盲盒给大家玩了！
下图是一条盲盒包装流水线的示意图。首先徽章通过进货口被压入货栈里，空盒在履带上从左向右传送。每次从货栈里弹出一枚徽章，进入打包机，装入一只空盒，打包后继续向右边传送。当货栈为空时，打包机会暂停，等待下一批徽章压入货栈。
每只盒子都有一个编号，小拼姐姐手里有进入流水线的空盒编号顺序表，也有每一批送往货栈的徽章顺序表，这样她其实可以知道每只盒子里装了哪种徽章。有些小朋友收到了盲盒，就想在拆封前问无所不知的小拼姐姐，盒子里的徽章是哪一种。但是因为盲盒总量有 10
5
这么多，小拼姐姐可记不住每只盒子里装的是什么，于是你就被请来写个程序帮小拼姐姐回复这种信息。
输入格式：
输入第一行给出 2 个正整数，分别为盲盒总量 N（≤105）和货栈容量 S（≤100）。接下来一行给出 N 只盒子的编号，编号由 5 位数字组成，给出的顺序是空盒进入传送带的顺序。随后 N/S（保证是整数）行，每行给出一批 S 枚徽章的类型，为 1-9 的数字，给出的顺序是从进货口入栈的顺序。
再下面给出一个正整数 K（≤104），为查询次数。随后 K 行，每行给出一个 5 位编号。
输出格式：
对每个查询编号，在一行中输出该盒子中装的徽章类型。如果编号是错误的，则在一行中输出 Wrong Number。
输入样例：
10 5 00132 10093 92001 23333 66666 88888 09009 34658 82750 69251 1 2 3 4 5 9 8 7 6 1 5 66666 88888 69251 55555 10093
输出样例：
1 1 9 Wrong Number 4
思路：咋一看这个题目是一个用堆栈实现的题目，实际上只需要根据题意模拟一遍就行了
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n,s; int a[N],f[N]; int main() { cin >> n >> s; for(int i=0;i<n;i++) cin >> a[i]; int m = n / s; int l = 0,r = s; while(m -- ) { int x; for(int i=r-1;i>=l;i--) { cin >> x; f[a[i]] = x; } l = r,r += s; } int k; cin >> k; while(k -- ) { int x; cin >> x; if(f[x]) cout << f[x] << endl; else cout << "Wrong Number\n"; } return 0; }
L2-2 点赞狂魔 (25 分)
微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。
输入格式：
输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F1⋯FK”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，Fi（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从 1 到 107编号。数字间以空格分隔。
输出格式：
统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。
输入样例：
5 bob 11 101 102 103 104 105 106 107 108 108 107 107 peter 8 1 2 3 4 3 2 5 1 chris 12 1 2 3 4 5 6 7 8 9 1 2 3 john 10 8 7 6 5 4 3 2 1 7 5 jack 9 6 7 8 9 10 11 12 13 14
输出样例：
jack chris john
思路：这题是一道对于结构体排序的题目，需要注意的统计点赞标记数量的时候需要去掉重复的
#include <bits/stdc++.h> using namespace std; const int N = 110; struct node { string name; int num; double ave; bool operator < (const node &a) { if(num != a.num) return num > a.num; return ave < a.ave; } }f[N]; int main() { int n; cin >> n; for(int i=0;i<n;i++) { int k,x; set<int>S; cin >> f[i].name >> k; for(int i=0;i<k;i++) cin >> x,S.insert(x); f[i].num = S.size(); f[i].ave = (k - S.size()) * 1.0 / S.size(); } sort(f,f + n); if(n == 0) cout << "- - -"; else if(n == 1) cout << f[0].name << " - -"; else if(n == 2) cout << f[0].name << ' ' << f[1].name << " -"; else cout << f[0].name << ' ' << f[1].name << ' ' << f[2].name; return 0; }
L2-3 浪漫侧影 (25 分)
“侧影”就是从左侧或者右侧去观察物体所看到的内容。例如上图中男生的侧影是从他右侧看过去的样子，叫“右视图”；女生的侧影是从她左侧看过去的样子，叫“左视图”。
520 这个日子还在打比赛的你，也就抱着一棵二叉树左看看右看看了……
我们将二叉树的“侧影”定义为从一侧能看到的所有结点从上到下形成的序列。例如下图这棵二叉树，其右视图就是 { 1, 2, 3, 4, 5 }，左视图就是 { 1, 6, 7, 8, 5 }。
于是让我们首先通过一棵二叉树的中序遍历序列和后序遍历序列构建出一棵树，然后你要输出这棵树的左视图和右视图。
输入格式：
输入第一行给出一个正整数 N (≤20)，为树中的结点个数。随后在两行中先后给出树的中序遍历和后序遍历序列。树中所有键值都不相同，其数值大小无关紧要，都不超过 int 的范围。
输出格式：
第一行输出右视图，第二行输出左视图，格式如样例所示。
输入样例：
8 6 8 7 4 5 1 3 2 8 5 4 7 6 3 2 1
输出样例：
R: 1 2 3 4 5 L: 1 6 7 8 5
感谢用户DSA修正数据！
思路：我们可以根据中序遍历和后序遍历建立一棵树，然后用层次遍历分别找出每一层最左边的数和每一层最右边的数
#include <bits/stdc++.h> using namespace std; typedef struct node *tree; const int N = 30; int a[N],b[N]; struct node { int data; tree lchild,rchild; }; tree build(int a[],int b[],int len) { if(!len) return NULL; int i; for(i=0;i<len;i++) if(b[i] == a[len - 1]) break; tree t = (tree) new (tree); t -> data = a[len - 1]; t -> lchild = build(a,b,i); t -> rchild = build(a + i,b + i + 1,len - i - 1); return t; } int main() { int n; map<int,int>level; vector<int>ans1,ans2; cin >> n; for(int i=0;i<n;i++) cin >> b[i]; for(int i=0;i<n;i++) cin >> a[i]; tree T = build(a,b,n); queue<tree>q; q.push(T); level[T -> data] = 1; while(q.size()) { auto t = q.front(); q.pop(); ans1.push_back(t -> data); if(t -> rchild) { q.push(t -> rchild); level[t -> rchild -> data] = level[t -> data] + 1; } if(t -> lchild) { q.push(t -> lchild); level[t -> lchild -> data] = level[t -> data] + 1; } } cout << "R:"; int it = 1; for(auto p:ans1) if(level[p] == it) { cout << ' ' << p; it ++; } q.push(T); level[T -> data] = 1; while(q.size()) { auto t = q.front(); q.pop(); ans2.push_back(t -> data); if(t -> lchild) { q.push(t -> lchild); level[t -> lchild -> data] = level[t -> data] + 1; } if(t -> rchild) { q.push(t -> rchild); level[t -> rchild -> data] = level[t -> data] + 1; } } cout << endl; cout << "L:"; it = 1; for(auto p:ans2) if(level[p] == it) { cout << ' ' << p; it ++; } return 0; }
L2-4 哲哲打游戏 (25 分)
哲哲是一位硬核游戏玩家。最近一款名叫《达诺达诺》的新游戏刚刚上市，哲哲自然要快速攻略游戏，守护硬核游戏玩家的一切！
为简化模型，我们不妨假设游戏有 N 个剧情点，通过游戏里不同的操作或选择可以从某个剧情点去往另外一个剧情点。此外，游戏还设置了一些存档，在某个剧情点可以将玩家的游戏进度保存在一个档位上，读取存档后可以回到剧情点，重新进行操作或者选择，到达不同的剧情点。
为了追踪硬核游戏玩家哲哲的攻略进度，你打算写一个程序来完成这个工作。假设你已经知道了游戏的全部剧情点和流程，以及哲哲的游戏操作，请你输出哲哲的游戏进度。
输入格式：
输入第一行是两个正整数 N 和 M (1≤N,M≤105 )，表示总共有 N 个剧情点，哲哲有 M 个游戏操作。接下来的 N 行，每行对应一个剧情点的发展设定。第 i 行的第一个数字是 Ki ，表示剧情点 i 通过一些操作或选择能去往下面 Ki个剧情点；接下来有 Ki个数字，第 k 个数字表示做第 k 个操作或选择可以去往的剧情点编号。
最后有 M 行，每行第一个数字是 0、1 或 2，分别表示：
0 表示哲哲做出了某个操作或选择，后面紧接着一个数字 j，表示哲哲在当前剧情点做出了第 j 个选择。我们保证哲哲的选择永远是合法的。
1 表示哲哲进行了一次存档，后面紧接着是一个数字 j，表示存档放在了第 j 个档位上。
2 表示哲哲进行了一次读取存档的操作，后面紧接着是一个数字 j，表示读取了放在第 j 个位置的存档。
约定：所有操作或选择以及剧情点编号都从 1 号开始。存档的档位不超过 100 个，编号也从 1 开始。游戏默认从 1 号剧情点开始。总的选项数（即 ∑Ki）不超过 106
输出格式：
对于每个 1（即存档）操作，在一行中输出存档的剧情点编号。
最后一行输出哲哲最后到达的剧情点编号。
输入样例：
10 11 3 2 3 4 1 6 3 4 7 5 1 3 1 9 2 3 5 3 1 8 5 1 9 2 8 10 0 1 1 0 3 0 1 1 2 0 2 0 2 2 2 0 3 0 1 1 1 0 2
输出样例：
1 3 9 10
样例解释：
简单给出样例中经过的剧情点顺序：
1 -> 4 -> 3 -> 7 -> 8 -> 3 -> 5 -> 9 -> 10。
档位 1 开始存的是 1 号剧情点；档位 2 存的是 3 号剧情点；档位 1 后来又存了 9 号剧情点。
思路：这是一道模拟题，我们先用一个二维的动态数组把游戏图存进去，然后根据游戏规则模拟一遍
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n,m; int path[N]; vector<int>v[N]; int main() { cin >> n >> m; for(int i=1;i<=n;i++) { int k,x; cin >> k; while(k -- ) { cin >> x; v[i].push_back(x); } } int p = 1,a,b; while(m -- ) { cin >> a >> b; if(a == 0) p = v[p][b - 1]; else if(a == 1) { cout << p << endl; path[b] = p; } else p = path[b]; } cout << p; return 0; }
L3-1 直捣黄龙 (30 分)
本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。
输入格式：
输入第一行给出2个正整数N（2 ≤ N ≤ 200，城镇总数）和K（城镇间道路条数），以及己方大本营和敌方大本营的代号。随后N-1行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有K行，每行按格式城镇1 城镇2 距离给出两个城镇之间道路的长度。这里设每个城镇（包括双方大本营）的代号是由3个大写英文字母组成的字符串。
输出格式：
按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式己方大本营->城镇1->…->敌方大本营输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数，其间以1个空格分隔，行首尾不得有多余空格。
输入样例：
10 12 PAT DBY DBY 100 PTA 20 PDS 90 PMS 40 TAP 50 ATP 200 LNN 80 LAO 30 LON 70 PAT PTA 10 PAT PMS 10 PAT ATP 20 PAT LNN 10 LNN LAO 10 LAO LON 10 LON DBY 10 PMS TAP 10 TAP DBY 10 DBY PDS 10 PDS PTA 10 DBY ATP 10
输出样例：
PAT->PTA->PDS->DBY 3 30 210
思路：这是一道最短路径的题目，因为各个城镇的名称都是字符串，所以我们需要把把字符串映射成为整数，然后根据题意跑一遍dijkstra算法
#include <bits/stdc++.h> using namespace std; const int N = 210,inf = 0x3f3f3f3f; int n,m; int g[N][N],dist[N]; int num[N],pre[N],sum[N],cnt[N],city[N]; bool st[N]; void dijkstra(int u) { memset(dist,inf,sizeof dist); dist[u] = 0; cnt[u] = city[u] = 1; for(int i=0;i<n;i++) { int t = -1; for(int j=0;j<n;j++) if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; for(int j=0;j<n;j++) { if(dist[j] > dist[t] + g[t][j]) { dist[j] = dist[t] + g[t][j]; pre[j] = t; cnt[j] = cnt[t]; sum[j] = sum[t] + num[j]; city[j] = city[t] + 1; } else if(dist[j] == dist[t] + g[t][j]) { cnt[j] += cnt[t]; if(city[j] < city[t] + 1) { pre[j] = t; sum[j] = sum[t] + num[j]; city[j] = city[t] + 1; } else if(city[j] == city[t] + 1) { if(sum[j] < sum[t] + num[j]) { pre[j] = t; sum[j] = sum[t] + num[j]; } } } } } } int main() { string s1,s2; cin >> n >> m >> s1 >> s2; memset(g,inf,sizeof g); map<string,int>p1; map<int,string>p2; p1[s1] = 0,p2[0] = s1; for(int i=1;i<n;i++) { string s; int x; cin >> s >> x; p1[s] = i; p2[i] = s; num[i] = sum[i] = x; } while(m -- ) { string a,b; int w; cin >> a >> b >> w; g[p1[a]][p1[b]] = g[p1[b]][p1[a]] = w; } int start = p1[s1],ed = p1[s2]; dijkstra(start); vector<int>ans; int a = start,b = ed; while(b != a) { ans.push_back(b); b = pre[b]; } cout << p2[a]; for(int i=ans.size()-1;i>=0;i--) cout << "->" << p2[ans[i]]; cout << endl; cout << cnt[ed] << ' ' << dist[ed] << ' ' << sum[ed]; return 0; }
L3-2 拼题A打卡奖励 (30 分)
拼题 A 的教超搞打卡活动，指定了 N 张打卡卷，第 i 张打卡卷需要 mi分钟做完，完成后可获得 ci枚奖励的金币。活动规定每张打卡卷最多只能做一次，并且不允许提前交卷。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币？
输入格式：
输入首先在第一行中给出两个正整数 N（≤103）和 M（≤365×24×60），分别对应打卡卷的数量和以“分钟”为单位的活动总时长（不超过一年）。随后一行给出 N 张打卡卷要花费的时间 mi≤600），最后一行给出 N 张打卡卷对应的奖励金币数量 ci≤30）。上述均为正整数，一行内的数字以空格分隔。
输出格式：
在一行中输出最多可以赢得的金币数量。
输入样例：
5 110 70 10 20 50 60 28 1 6 18 22
输出样例：
40
样例解释：
选择最后两张卷子，可以在 50+60=110 分钟内获得 18+22=40 枚金币。
看作背包容量，把原来的背包容量当作获利，这样我们这个过程就代表 我当前的获利需要牺牲多少背包容量，最后我们按获利倒序枚举每个dp[i],输出第一个小于等于m的i即可。
思路：这题咋一看是一个01背包的模板题，尝试了一下发现数据量比较大卡了两个点，分析可以发现NM>1e7，我们可以把获得金币的数量看成背包容量,这样最大容量为100030=30000，求出来后我们按金币倒序枚举每个f[i],输出第一个小于等于mi
#include <bits/stdc++.h> using namespace std; const int N = 3e4 + 10,inf = 0x3f3f3f3f; int n,m,sum; int f[N],w[N],t[N]; int main() { cin >> n >> m; for(int i=1;i<=n;i++) cin >> t[i]; for(int i=1;i<=n;i++) cin >> w[i],sum += w[i]; memset(f,inf,sizeof f); f[0] = 0; for(int i=1;i<=n;i++) for(int j=sum;j>=w[i];j--) f[j] = min(f[j],f[j - w[i]] + t[i]); while(f[sum] > m) sum --; cout << sum; return 0; }
L3-3 可怜的简单题 (30 分)
补题链接
https://pintia.cn/market/item/1515917073728122880
