程序设计天梯赛L2解题思路（025-036）

目录25.分而治之26.小字辈*27.名人堂与代金券28.秀恩爱分得快*29.特立独行的幸福30.冰岛人**31.深入虎穴32.彩虹瓶33.简单计算器34.口罩发放35.完全二叉树的层次遍历*36.网红点打卡攻略25.分而治之题目思路考察并查集先存储每条道路开一个vis数组表示某个城市是否可用在后面每个方案中开一个新的并查集和vis数组并构建并查集判断根的数量是否等于n-Np。代码#include iostream #include bits/stdc.h using namespace std; struct Node { int rank; int parent; }; struct Rel { int x; int y; }; void MakeSet(Node nodes[], int n) { for (int i 0; i n; i) { nodes[i].rank 0; nodes[i].parent i; } } int Find(Node nodes[], int x) { int rx x; while (nodes[rx].parent ! rx) { rx nodes[rx].parent; } int y x; while (y ! rx) { int tem nodes[y].parent; nodes[y].parent rx; y tem; } return rx; } void Union(Node nodes[], int x, int y) { int rx Find(nodes, x); int ry Find(nodes, y); if (rx ry) { return; } else { if (nodes[rx].rank nodes[ry].rank) { nodes[rx].parent ry; } else if (nodes[rx].rank nodes[ry].rank) { nodes[ry].parent rx; } else { nodes[rx].parent ry; nodes[ry].rank; } } } int Count(Node nodes[], int vis[], int n) { int ret 0; for (int i 0; i n; i) { if (vis[i] 0 nodes[i].parent i) { ret; } } return ret; } int main() { int n, m; cin n m; Rel rels[m]; for (int i 0; i m; i) { int x, y; cin x y; x--, y--; rels[i].x x; rels[i].y y; } int k; cin k; for (int i 0; i k; i) { int np; cin np; Node nodes[n]; MakeSet(nodes, n); int vis[n] {0}; for (int j 0; j np; j) { int num; cin num; vis[num - 1] 1; } for (int j 0; j m; j) { if (vis[rels[j].x] 0 vis[rels[j].y] 0) { Union(nodes, rels[j].x, rels[j].y); } } if (Count(nodes, vis, n) n - np) { cout YES\n; } else { cout NO\n; } } return 0; }26.小字辈*题目思路先根据给出的祖宗数组来构建一个哈希表键为祖宗id值为祖宗为对应键的id的vector然后构建一个哈希表表示每个人的辈分。后面利用队列BFS来更新每个人的辈分最后转为结构体vector通过自定义的cmp排序输出就行了。注意这道题先给出了N的取值范围为10^6级别所以不用队列的话暴力搜索的复杂度至少为n^2一定会超时所以利用队列来降低时间复杂度。代码#include iostream #include bits/stdc.h using namespace std; struct Peo { int id; int count; }; bool cmp(Peo x, Peo y) { if (x.count y.count) { return x.id y.id; } return x.count y.count; } int main() { int n; cin n; int nums[n]; for (int i 0; i n; i) { cin nums[i]; } unordered_map int, vector int nums_mp; for (int i 0; i n; i) { nums_mp[nums[i] - 1].push_back(i); } unordered_map int, int mp; queue int q; for (int i 0; i n; i) { if (nums[i] -1) { mp[i] 1; q.push(i); } } while (q.size()) { int t q.front(); q.pop(); if (nums_mp[t].size()) { for (auto p nums_mp[t].begin(); p ! nums_mp[t].end(); p) { q.push(*p); mp[*p] mp[t] 1; } } } vector Peo peo(n); for (int i 0; i n; i) { peo[i].id i; peo[i].count mp[i]; } sort(peo.begin(), peo.end(), cmp); cout peo[0].count endl; cout peo[0].id 1; int t 1; while (t n) { if (peo[t].count peo[0].count) { cout peo[t].id 1; t; } else { break; } } return 0; }27.名人堂与代金券题目思路开一个结构体数组排序然后更新排名。代码#include iostream #include bits/stdc.h using namespace std; struct Stu { string zh; int grade; int rank; }; bool cmp(Stu x, Stu y) { if (x.grade y.grade) { return x.zh y.zh; } return x.grade y.grade; } int main() { int n, g, k; cin n g k; string t; getline(cin, t); vector Stu stu; int sum 0; for (int i 0; i n; i) { Stu tem; cin tem.zh tem.grade; tem.rank 0; stu.push_back(tem); if (tem.grade g tem.grade 100) { sum 50; } else if (tem.grade 60 tem.grade g) { sum 20; } } sort(stu.begin(), stu.end(), cmp); stu[0].rank 1; int flag 1; for (int i 1; i n; i) { if (stu[i].grade stu[i - 1].grade) { stu[i].rank stu[i - 1].rank; flag; } else { stu[i].rank stu[i - 1].rank flag; flag 1; } } cout sum endl; for (int i 0; i n; i) { if (stu[i].rank k) { cout stu[i].rank stu[i].zh stu[i].grade endl; } else { break; } } return 0; }28.秀恩爱分得快*题目思路开一个二维数组来存储亲密度一维数组来存储每个人的性别在每张照片中输出的id应该为字符串然后使用sscanf来判断读取字符串中的数字并修改亲密度数组和一维数组最后判断性别和亲密度并输出就行了。注意1注意特殊值-0所以在输出时不能直接存储id并输出应该存储绝对值并根据sex数组判断输出2无需特定排序只需要先找出异性的最大值在遍历时挨个判断性别和亲密度并相应输出即可3注意异性的最大值应该前提是异性而不是单纯地找最大值4一开始使用cin、cout以及string和绝对值函数、vector等会超时因为cin和cout本身就时间复杂度高所以这里能用scanf和printf就直接用就行了对于提取字符串中的数字用sscanf数组直接用c中的数组定义而不是容器。、代码#include iostream #include bits/stdc.h using namespace std; const double INF 1e-7; static double s[1005][1005]; static int sex[1005]; static int ids[505]; static char str[20], sa[20], sb[20]; int main() { int n, m; scanf(%d %d, n, m); for (int i 0; i n; i) { sex[i] -1; } for (int i 0; i m; i) { int k; scanf(%d, k); for (int j 0; j k; j) { scanf(%s, str); int id 0; if (str[0] -) { sscanf(str 1, %d, id); sex[id] 1; } else { sscanf(str, %d, id); sex[id] 0; } ids[j] id; // 只存绝对值编号 } double w 1.0 / k; for (int j 0; j k; j) { int x ids[j]; for (int l j 1; l k; l) { int y ids[l]; s[x][y] w; s[y][x] w; } } } scanf(%s %s, sa, sb); int a 0, b 0; int sexA, sexB; if (sa[0] -) { sscanf(sa 1, %d, a); sexA 1; } else { sscanf(sa, %d, a); sexA 0; } if (sb[0] -) { sscanf(sb 1, %d, b); sexB 1; } else { sscanf(sb, %d, b); sexB 0; } sex[a] sexA; sex[b] sexB; double max_a 0, max_b 0; for (int i 0; i n; i) { if (sex[i] ! -1 sex[i] ! sexA s[a][i] max_a) { max_a s[a][i]; } if (sex[i] ! -1 sex[i] ! sexB s[b][i] max_b) { max_b s[b][i]; } } if (fabs(s[a][b] - max_a) INF fabs(s[b][a] - max_b) INF) { printf(%s %s\n, sa, sb); } else { for (int i 0; i n; i) { if (sex[i] ! -1 sex[i] ! sexA fabs(s[a][i] - max_a) INF) { if (sex[i] 1) printf(%s -%d\n, sa, i); else printf(%s %d\n, sa, i); } } for (int i 0; i n; i) { if (sex[i] ! -1 sex[i] ! sexB fabs(s[b][i] - max_b) INF) { if (sex[i] 1) printf(%s -%d\n, sb, i); else printf(%s %d\n, sb, i); } } } return 0; }29.特立独行的幸福题目思路开两个大小为10001的数组分别记录某个数是否为幸福数以及记录每个目标数的独立性计算就按题目所说的循环就行判断素数时的循环上界应该是sqrtx并且必须是小于等于。在更新数组时判断该数是否是起点数如果是并且是幸福数将对应的幸福数组记为1中途中的数都记为2然后将起点数计算其独立性并记录最后遍历输出就行了。注意判断素数循环时上界必须是小于等于平方根一是保证不超时二是对于平方数如果不是小于等于上界的话会误判。代码#include iostream #include bits/stdc.h using namespace std; #define N 10001 int xf[N]; int ind[N]; bool Judge(int x) { for (int i 2; i (int)sqrt(x); i) { if (x % i 0) { return false; } } return true; } int Cal(int x) { int sum 0; while (x) { sum (x % 10) * (x % 10); x / 10; } return sum; } int main() { int a, b; scanf(%d %d, a, b); for (int i a; i b; i) { int vis[N] {0}; vis[i] 1; int t i; int flag 0; while (1) { t Cal(t); if (vis[t] 1) { break; } else { vis[t] 1; if (t 1) { flag 1; break; } } } if (flag) { int sum 0; for (int j 1; j N; j) { if (vis[j]) { if (j ! i) { sum; } if (xf[j] 1 j ! i) { xf[j] 2; } else if (xf[j] 0 j i || xf[j] 1 j i) { xf[j] 1; } else { xf[j] 2; } } } if (Judge(i)) { ind[i] 2 * sum; } else { ind[i] sum; } } } int count 0; for (int i a; i b; i) { if (xf[i] 1) { printf(%d %d\n, i, ind[i]); count; } } if (!count) { printf(SAD\n); } return 0; }30.冰岛人**题目思路这道题和之前做过的一道五代内找共同祖先的题很像但那道题需要考虑父母两个人所以需要建树这道题只需要考虑父辈就行了所以可以无需建树直接用vector存。先开一个哈希表来存储完整名字和名字对应的id与性别键是名字值是自定义结构体然后开一个string数组来存储每个人的父亲的名也就是本人的姓去掉后缀再开一个int数组来存储每个人的父亲id表示祖先关系这里和前面那道题类似了只不过之前的是直接给出的这里我们自己建然后开一个哈希表键是每个人的名值是这个人的id用来建立祖先关系时使用哈希查找降低时间复杂度不然每次遍历会超时。最后开两个vector判断即可。注意1一开始建立哈希关系时使用的是全名然后找子串十分麻烦而且时间复杂度很高这里可以将每个名字单独读入名和姓然后分别做处理和建立关系2注意题目说的是所谓“五代以内无公共祖先”是指两人的公共祖先如果存在的话必须比任何一方的曾祖父辈分高。与前面那个在五代之内找共同祖先的不同这个的约束条件不是两个都在五代之内找而是应该对其中一个人遍历其祖先然后判断另一个人五代之内是否存在重合最后反过来再比较一次这就是为什么一开始老是有两个测试用例不过。代码#include iostream #include bits/stdc.h using namespace std; struct Node { int id; int sex; }; int main() { int n; scanf(%d, n); unordered_map string, Node mp; int rels[n]; for (int i 0; i n; i) { rels[i] -1; } string f_na[n]; unordered_map string, int ids; string t; getline(cin, t); for (int i 0; i n; i) { string t_x, t_n; cin t_x t_n; string t_wz, real_n; int len_n t_n.length(); if (t_n[len_n - 1] m) { real_n t_n.substr(0, len_n - 1); t_wz t_x real_n; mp[t_wz].sex 1; mp[t_wz].id i; f_na[i] ; ids[t_x] i; } else if (t_n[len_n - 1] f) { real_n t_n.substr(0, len_n - 1); t_wz t_x real_n; mp[t_wz].sex 0; mp[t_wz].id i; f_na[i] ; } else if (t_n.substr(len_n - 4) sson) { real_n t_n.substr(0, len_n - 4); t_wz t_x real_n; mp[t_wz].sex 1; mp[t_wz].id i; f_na[i] real_n; ids[t_x] i; } else { real_n t_n.substr(0, len_n - 7); t_wz t_x real_n; mp[t_wz].sex 0; mp[t_wz].id i; f_na[i] real_n; } } for (int i 0; i n; i) { string f f_na[i]; if (f || !ids.count(f)) { rels[i] -1; } else { rels[i] ids[f]; } } int m; scanf(%d, m); getline(cin, t); for (int i 0; i m; i) { string a_x, a_n, b_x, b_n; cin a_x a_n b_x b_n; string a, b; a a_x a_n; b b_x b_n; if (!mp.count(a) || !mp.count(b)) { printf(NA\n); } else { if (mp[a].sex mp[b].sex) { printf(Whatever\n); } else { int num_a, num_b; num_a num_b 0; int id_a[4], id_b[4]; int t_a, t_b; t_a mp[a].id; t_b mp[b].id; int tt_a t_a, tt_b t_b; while (t_a ! -1 num_a 4) { id_a[num_a] t_a; t_a rels[t_a]; } while (t_b ! -1 num_b 4) { id_b[num_b] t_b; t_b rels[t_b]; } int flag 0; while (tt_a ! -1 !flag) { for (int j 0; j num_b !flag; j) { if (tt_a id_b[j]) { flag 1; } } tt_a rels[tt_a]; } while (!flag tt_b ! -1) { for (int j 0; j num_a !flag; j) { if (tt_b id_a[j]) { flag 1; } } tt_b rels[tt_b]; } if (!flag) { printf(Yes\n); } else { printf(No\n); } } } } return 0; }我这里变量定义时把名和姓搞反了题目中给出的顺序应该是先名再姓看的时候转换一下思维吧...31.深入虎穴题目思路看到这道题是找最短路并且没给权重只是单纯的道路因此可以用多起点BFS来更新每个门点的距离。注意这道题没给出特定的起点蕴含的条件就是入度为0的门是起点可以开一个数组先存储。代码#include iostream #include bits/stdc.h using namespace std; #define N 100000 int vis[N]; bool cmp(int x, int y) { return x y; } int main() { int n; scanf(%d, n); vector int dis(n, 0); vector int starts; vector vector int rels(n); int degree[n] {0}; for (int i 0; i n; i) { int k; scanf(%d, k); for (int j 0; j k; j) { int num; scanf(%d, num); rels[i].push_back(num - 1); degree[num - 1]; } } for (int i 0; i n; i) { if (degree[i] 0) { starts.push_back(i); } } queue int q; for (int i 0; i starts.size(); i) { dis[starts[i]] 0; vis[starts[i]] 1; q.push(starts[i]); } while (q.size()) { int t q.front(); q.pop(); for (int i 0; i rels[t].size(); i) { if (!vis[rels[t][i]]) { dis[rels[t][i]] dis[t] 1; vis[rels[t][i]] 1; q.push(rels[t][i]); } } } int max dis[0]; int pos 1; for (int i 1; i n; i) { if (dis[i] max) { max dis[i]; pos i 1; } } printf(%d\n, pos); return 0; }32.彩虹瓶题目思路对每个序列开一个栈来模拟货架定义一个num变量来模拟当前需要的颜色按题目所说遍历给定顺序的数组时先判断是否等于当前的num等于就再判断栈顶是否是下一个num是的话就依次出栈不等于就入栈并判断栈是否爆满。最后依次出栈并和num比较如果不能全部出栈就输出NO否则YES。代码#include iostream #include bits/stdc.h using namespace std; int main() { int n, m, k; cin n m k; for (int i 0; i k; i) { int sq[n]; for (int j 0; j n; j) { cin sq[j]; } stack int s; int num 1; int flag 0; for (int j 0; j n; j) { if (sq[j] num) { num; while (s.size()) { int t s.top(); if (t num) { s.pop(); num; } else { break; } } } else { s.push(sq[j]); if (s.size() m) { flag 1; break; } } } if (flag) { cout NO\n; } else { while (s.size()) { if (s.top() num) { s.pop(); num; } else { break; } } if (s.size()) { cout NO\n; } else { cout YES\n; } } } return 0; }33.简单计算器题目思路开两个栈分别表示数和运算符循环条件是运算符栈不空然后每次出栈一个运算符随之出栈两个数并计算除0时就报错结束否则将结果入栈最后再输出数栈顶元素。代码#include iostream #include bits/stdc.h using namespace std; int main() { int n; cin n; stack int nums; stack char ops; for (int i 0; i n; i) { int num; cin num; nums.push(num); } string t; getline(cin, t); for (int i 0; i n - 1; i) { char c; scanf(%c, c); getchar(); ops.push(c); } while (ops.size()) { int num1, num2; num1 nums.top(); nums.pop(); num2 nums.top(); nums.pop(); char op ops.top(); ops.pop(); if (op ) { nums.push(num1 num2); } else if (op -) { nums.push(num2 - num1); } else if (op *) { nums.push(num2 * num1); } else { if (num1 ! 0) { nums.push(num2 / num1); } else { cout ERROR: num2 / num1 \n; return 0; } } } cout nums.top() \n; return 0; }34.口罩发放题目思路由于没给出总人数所以开一个map来存储每个人的天数键是身份证号因为唯一值是该人拿到口罩的天数然后开一个vector记录身体状态为1的申请人注意要去重。每天的输入都先用vector存储该天所有申请人的信息若身份证满足18位并且全是数字就存入如果map中没有这个人的身份证号就添加并初始化为0然后对vector进行稳定排序即可读入每个人的申请时间时可以将小时和分钟按%2d读入。在每次判断这个人是否可以拿到口罩时就判断map中这个人对应的天数是否为0或者加上p1是否小于等于当天的天数即可满足就输出并更新并且注意s的取值范围可以是0所以循环条件中要加上。主要还是stable_sort的使用和一堆小细节的注意。代码#include iostream #include bits/stdc.h using namespace std; struct Node { string name; string id; int flag; int h; int m; }; bool cmp(Node x, Node y) { if (x.h y.h) { return x.m y.m; } return x.h y.h; } bool Find(vector Node peo, Node t) { for (int i 0; i peo.size(); i) { if (t.id peo[i].id) { return true; } } return false; } bool Judge(string s) { for (int i 0; i s.length(); i) { if (!(s[i] 0 s[i] 9)) { return false; } } return true; } int main() { int d, p; cin d p; map string, int mp; vector Node peo; string tem; int day 1; for (int i 0; i d; i) { int t, s; cin t s; getline(cin, tem); vector Node nodes; for (int j 0; j t; j) { Node t_node; cin t_node.name t_node.id t_node.flag; scanf(%2d:%2d, t_node.h, t_node.m); getline(cin, tem); if (t_node.id.length() 18 Judge(t_node.id)) { nodes.push_back(t_node); if (!mp.count(t_node.id)) { mp[t_node.id] 0; } if (t_node.flag 1 !Find(peo, t_node)) { peo.push_back(t_node); } } } stable_sort(nodes.begin(), nodes.end(), cmp); int count 0; for (int j 0; j nodes.size() count s; j) { if (mp[nodes[j].id] 0 || mp[nodes[j].id] p 1 day) { mp[nodes[j].id] day; cout nodes[j].name nodes[j].id \n; count; if (count s) { break; } } } day; } for (int i 0; i peo.size(); i) { cout peo[i].name peo[i].id \n; } return 0; }35.完全二叉树的层次遍历*题目思路层次遍历开队列就行了关键在于如何创建完全二叉树这里还是利用递归的思想和前面的中前/中后序列建树差不多都是用递归只是这里只给出了后序遍历也就是左子树和右子树的数目需要自己判断。判断时如果不是满二叉树就先根据树的节点来得到树的深度然后判断最后一层节点的数目来得到左子树和右子树的节点数如果是满二叉树节点数是pow2d-1则节点数就是n-1/2直接递归就行了。代码#include iostream #include bits/stdc.h using namespace std; struct TreeNode { int num; TreeNode* lchild; TreeNode* rchild; }; TreeNode* BuildTree(int nums[], int n, int start, int end) { if (n 0) { return NULL; } else { TreeNode* t (TreeNode *)malloc(sizeof(TreeNode)); t - num nums[end]; if (n 1) { t - lchild t - rchild NULL; } else if (n 2) { t - lchild BuildTree(nums, n - 1, start, end - 1); t - rchild NULL; } else { int count_l, count_r; int d 1; while ((int)(pow(2, d) - 1) n) { d; } d--; if ((int)(pow(2, d) - 1) n) { t - lchild BuildTree(nums, (n - 1) / 2, start, start (n - 1) / 2 - 1); t - rchild BuildTree(nums, (n - 1) / 2, start (n - 1) / 2, end - 1); } else { int add n - (int)pow(2, d) 1; if (add (int)(pow(2, d)) / 2) { count_l add; count_r 0; } else { count_l (int)pow(2, d) / 2; count_r add - count_l; } t - lchild BuildTree(nums, (n - add - 1) / 2 count_l, start, start (n - add - 1) / 2 count_l - 1); t - rchild BuildTree(nums, (n - add - 1) / 2 count_r, start (n - add - 1) / 2 count_l, end - 1); } } return t; } } void Disp(TreeNode* r) { cout r - num; queue TreeNode * q; if (r - lchild ! NULL) { q.push(r - lchild); } if (r - rchild ! NULL) { q.push(r - rchild); } while (q.size()) { TreeNode* t q.front(); q.pop(); cout t - num; if (t - lchild ! NULL) { q.push(t - lchild); } if (t - rchild ! NULL) { q.push(t - rchild); } } } int main() { int n; cin n; int nums[n]; for (int i 0; i n; i) { cin nums[i]; } TreeNode* r BuildTree(nums, n, 0, n - 1); Disp(r); return 0; }36.网红点打卡攻略题目思路开一个维度均为n1的二维数组来表示两个点之间的路径长度不存在路径就是-1。在后面每个需要判断的路线中先判断网红点数是否等于n然后从0开始依次判断相邻两点之间是否存在路径存在就记录不存在直接退出本次循环最后判断是否能到家以及每个点都访问一遍满足就计数加一并判断是否更小最后输出就行了。代码#include iostream #include bits/stdc.h using namespace std; #define N (int)1e9 1 int main() { int n, m; scanf(%d %d, n, m); int rels[n 1][n 1]; for (int i 0; i n 1; i) { for (int j 0; j n; j) { rels[i][j] -1; } } for (int i 0; i m; i) { int x, y, cost; scanf(%d %d %d, x, y, cost); rels[x][y] rels[y][x] cost; } int k; scanf(%d, k); int min_pos -1; int min N; int count 0; for (int i 0; i k; i) { int t_n; scanf(%d, t_n); int nums[t_n]; for (int j 0; j t_n; j) { scanf(%d, nums[j]); } int vis[n 1] {0}; int flag 0; int now 0, sum 0; if (t_n n) { for (int j 0; j t_n !flag; j) { if (rels[now][nums[j]] ! -1) { sum rels[now][nums[j]]; now nums[j]; vis[nums[j]] 1; } else { flag 1; } } if (!flag) { if (rels[now][0] ! -1) { vis[0] 1; sum rels[now][0]; } else { flag 1; } if (!flag) { for (int i 0; i n; i) { if (vis[i] 0) { flag 1; } } if (!flag) { if (sum min) { min sum; min_pos i 1; } count; } } } } } printf(%d\n, count); printf(%d %d\n, min_pos, min); return 0; }