前言

发现自己还能再参加一次天梯赛，在高兴之余，决定把在赛前将所有的天梯赛真题过一遍，希望自己可以取得理想的成绩。目前 L1 的题目已经刷完，打算在赛前刷完 L2 的题目。

本来想 L2 的题目都写个相对详细的题解的，但是由于时间已经很紧张了，就只能像来记录 L1题目的形式来 L2 的题解了，让我们都好好加油吧。

文章目录

• 前言
• L2-001 紧急救援
• L2-002 链表去重
• L2-003 月饼
• L2-004 这是二叉搜索树吗?
• L2-005 集合相似度
• L2-006 树的遍历
• L2-007 家庭房产
• L2-008 最长对称子串
• L2-009 抢红包
• L2-010 排座位
• L2-011 玩转二叉树
• L2-012 关于堆的判断
• L2-013 红色警报
• L2-014 列车调度
• L2-015 互评成绩
• L2-016 愿天下有情人都是失散多年的兄妹
• L2-017 人以群分
• L2-018 多项式A除以B
• L2-019 悄悄关注
• L2-020 功夫传人
• L2-021 点赞狂魔
• L2-022 重排链表
• L2-023 图着色问题
• L2-024 部落
• L2-025 分而治之
• L2-026 小字辈
• L2-027 名人堂与代金券
• L2-028 秀恩爱分得快
• L2-029 特立独行的幸福
• L2-030 冰岛人
• L2-031 深入虎穴
• L2-032 彩虹瓶

L2-001 紧急救援

#include <bits/stdc++.h>using namespace std; const int inf = 0x3f3f3f; const int maxn =550; int n, m, s, d;int w[maxn], sum[maxn], total[maxn]; int dis[maxn], vis[maxn], path[maxn]; typedef pair<int, int> pii; vector<pii> E[maxn];void dijstra(int s) {memset(vis, 0, sizeof(vis));priority_queue<pii, vector<pii>, greater<pii> > q;for (int i = 0; i < n; i++) dis[i] = inf;dis[s] = 0;sum[s] = w[s];total[s] = 1;q.push(pii(dis[s], s));while (!q.empty()) {int u = q.top().second;q.pop();if (vis[u]) continue;vis[u] = 1;for (int i = 0; i < E[u].size(); i++) {int v = E[u][i].first;if (dis[v] > dis[u] + E[u][i].second) {dis[v] = dis[u] + E[u][i].second;sum[v] = sum[u] + w[v];total[v] = total[u];path[v] = u;q.push(pii(dis[v], v));} else if (dis[v] == dis[u] + E[u][i].second) {if (sum[v] < sum[u] + w[v]) {sum[v] = sum[u] + w[v];path[v] = u;}total[v] += total[u];}}} }void output(int s, int d) {if (s == d) {printf("%d", s);return ;} else {output(path[s], d);printf(" %d", s);} }int main() {scanf("%d %d %d %d", &n, &m, &s, &d);for (int i = 0; i < n; i++) scanf("%d", &w[i]);for (int i = 1; i <= m; i++) {int x, y, t;scanf("%d %d %d", &x, &y, &t);E[x].push_back(pair<int, int>(y, t));E[y].push_back(pair<int, int>(x, t));}dijstra(s);printf("%d %d\n", total[d], sum[d]);output(d, s);return 0; }

L2-002 链表去重

#include <bits/stdc++.h>using namespace std; const int maxn = 1e5 + 10; int n, cnt; int one, s, pre; /*** lb用于存储原始链表* re用于存储原始链表中的重复节点*/ pair<int, int> lb[maxn]; pair<int, int> re[maxn]; set<int> vis;int main() {cin >> one >> n;for (int i = 1; i <= n; i++) {int address, num, next;cin >> address >> num >> next;lb[address] = make_pair(num, next);}cnt = 0;for (s = one; s != -1; s = lb[s].second) {int num = lb[s].first;if (!vis.count(abs(num))) {vis.insert(abs(num));pre = s;} else {//链表删除重复节点操作lb[pre].second = lb[s].second;//将删除的节点存到另一条链表re[cnt].first = num;re[cnt].second = s;cnt++;}}for (s = one; s != -1; s = lb[s].second) {printf("%05d %d ", s, lb[s].first);if (lb[s].second != -1) printf("%05d\n", lb[s].second);else printf("-1\n");}for (int i = 0; i < cnt; i++) {printf("%05d %d ", re[i].second ,re[i].first);if (i != cnt - 1) printf("%05d\n", re[i + 1].second);else printf("-1\n");}return 0; }

L2-003 月饼

#include <bits/stdc++.h>using namespace std; const int maxn = 1005; const double eps = 1e-10;struct Food {double num, price;double pri; } f[maxn];bool cmp (const Food &A, const Food &B) {return A.pri > B.pri; }int main() {int n, need;scanf("%d %d", &n, &need);for (int i = 0; i < n; i++) scanf("%lf", &f[i].num);for (int i = 0; i < n; i++) {scanf("%lf", &f[i].price);f[i].pri = f[i].price / f[i].num;}sort(f, f + n, cmp);double ans = 0.0;for (int i = 0; i < n; i++) {if (f[i].num < need) {ans += f[i].price;need -= f[i].num;} else {ans += need * f[i].pri;break;}}printf("%.2f\n", ans);return 0; }

L2-004 这是二叉搜索树吗?

#include <bits/stdc++.h>using namespace std; const int maxn = 1e3 + 10; int n, flag; int a[maxn]; vector<int> ans; // 存储后序遍历的结果/*根据前序遍历的结果，后序遍历二叉搜索树l: 二叉树的r: 二叉树的flag: 是否根据镜像的规则进行遍历 */ void dfs(int l, int r, int flag) {if (l > r) return ;int p1 = l + 1, p2 = r;// 确定左右子树的范围if (flag) {while (p1 <= r && a[p1] >= a[l]) p1++;while (p2 > l && a[p2] < a[l]) p2--;} else {while (p1 <= r && a[p1] < a[l]) p1++;while (p2 > l && a[p2] >= a[l]) p2--;}if (p1 - p2 != 1) return ;dfs(l + 1, p1 - 1);dfs(p2 + 1, r);ans.push_back(a[l]); }int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];dfs(1, n, flag);if (ans.size() != n) {flag = 1;ans.clear();dfs(1, n, flag);}if (ans.size() != n) {cout << "NO" << endl;} else {cout << "YES" << endl;for (int i = 0; i < n; i++) {cout << ans[i] << (i == n - 1 ? '\n' : ' ');}}return 0; }

L2-005 集合相似度

#include <bits/stdc++.h>using namespace std; int n, m, t, k, a, b; const int maxn = 1e4 + 10; set<int> vis[maxn]; int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &m);while (m--) {scanf("%d", &t);vis[i].insert(t);}}scanf("%d", &k);while (k--) {scanf("%d %d", &a, &b);int cnt1 = vis[a].size(), cnt2 = vis[b].size(), cnt3 = 0;for (auto e : vis[a]) {if (vis[b].count(e))cnt3++;}printf("%.2f%\n", (double)cnt3 / (cnt1 + cnt2 - cnt3) * 100);}return 0; }

L2-006 树的遍历

#include <bits/stdc++.h>using namespace std; const int maxn = 50; int n; /*** in_order[]表示中序遍历序列* post_order[]表示后序遍历序列* tree[]用于存储树形结构* 其中，tree[i].first表示i节点左孩子编号，tree[i].second表示i号节点右孩子编号*/ int in_order[maxn], post_order[maxn]; pair<int, int> tree[maxn]; /*** [la, ra]表示中序遍历序列的范围* [lb, rb]表示后序遍历序列的范围*/ int build(int la, int ra, int lb, int rb) {if (la > ra || lb > rb) return 0;int rt = post_order[rb];//p表示根节点在中序遍历序列中的位置int p = la;while (in_order[p] != rt) p++;//cnt表示左子树的节点数int cnt = p - la;//根据已知量，求左右子树所在的遍历序列区间tree[rt].first = build(la, p - 1 , lb, lb + cnt - 1);tree[rt].second = build(p + 1, ra, lb + cnt, rb - 1);return rt; }/*** 利用bfs层序遍历二叉树* @param root表示二叉树的根节点*/ void bfs(int root) {vector<int> ans;queue<int> q;q.push(root);while (!q.empty()) {int node = q.front();q.pop();ans.push_back(node);if (tree[node].first) q.push(tree[node].first);if (tree[node].second) q.push(tree[node].second);}int len = ans.size();for (int i = 0; i < len; i++)cout << ans[i] << (i == len - 1 ? '\n' : ' '); }int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> post_order[i];for (int i = 1; i <= n; i++)cin >> in_order[i];int root = build(1, n, 1, n);bfs(root);return 0; }

L2-007 家庭房产

#include <bits/stdc++.h> #include <unordered_set> using namespace std; const int maxn = 1e4 + 10; int n, id, fid, mid, k, cid, cnt;struct People {double num, area; // num 表示房产数、area 表示房产总面积bool flag = false; // 标记是否作为“编号”出现过 } s[maxn];struct Answer {int id, num; // id 表示家庭成员的最小编号，num 表示家庭人口数double house, area; // house 表示人均房产套数，area 表示人均房产面积 } ans[1005];int p[maxn], mark[maxn]; unordered_set<int> vis;bool cmp(const Answer &A, const Answer &B) {if (A.area == B.area) return A.id < B.id;else return A.area > B.area; } // 并查集初始化 void init() {for (int i = 1; i < maxn; i++) p[i] = i; } // 并查集查询 int Find(int x) {return p[x] == x ? x : p[x] = Find(p[x]); } // 并查集合并，保证 id 最小的人在根节点 void Merge(int x, int y) {int tx = Find(x);int ty = Find(y);if (tx != ty) {if (tx < ty) p[ty] = tx;else p[tx] = ty;} }int main() {init();scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d %d %d", &id, &fid, &mid);vis.insert(id);if (fid != -1) {Merge(id, fid);vis.insert(fid);}if (mid != -1) {Merge(id, mid);vis.insert(mid);}scanf("%d", &k);for (int j = 1; j <= k; j++) {scanf("%d", &cid);if (cid != -1) {Merge(id, cid);vis.insert(cid);}}scanf("%lf %lf", &s[id].num, &s[id].area);s[id].flag = true;}for (auto i : vis) {int t = Find(i); // 获取所在家庭的成员的最小编号if (!mark[t]) {mark[t] = ++cnt; // mark[i] 用于标记i是否出现过，且记录i在ans数组未排序前的下标 ans[cnt].id = t;}ans[mark[t]].num++; // 统计家庭人口数if (s[i].flag) { // flag 为 true 的人才有房产ans[mark[t]].house += s[i].num;ans[mark[t]].area += s[i].area;}}// 计算人均值for (int i = 1; i <= cnt; i++) {ans[i].house /= ans[i].num;ans[i].area /= ans[i].num;}printf("%d\n", cnt);sort(ans + 1, ans + cnt + 1, cmp);for (int i = 1; i <= cnt; i++)printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].num, ans[i].house, ans[i].area);return 0; }

L2-008 最长对称子串

#include <bits/stdc++.h>using namespace std; int len, ans; string str;int main() {getline(cin, str);len = str.length();for (int i = 0; i < len; i++) {for (int j = 0; (i - j) >= 0 && (i + j < len) && str[i - j] == str[i + j]; j++)ans = max(j * 2 + 1, ans);for (int j = 0; (i - j) >= 0 && (i + j + 1) < len && str[i - j] == str[i + j + 1]; j++)ans = max((j + 1) * 2, ans);}cout << ans << endl;return 0; }

L2-009 抢红包

#include <bits/stdc++.h>using namespace std; const int maxn = 1e4 + 5; int n, k, m, p; struct People {int id, money, num; } s[maxn];bool cmp(const People &A, People &B) {if (A.money == B.money) {if (A.num == B.num) return A.id < B.id;else return A.num > B.num;} else {return A.money > B.money;} }int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> k;int sum = 0;for (int j = 1; j <= k; j++) {cin >> m >> p;s[m].money += p;s[m].num++;sum += p;}s[i].id = i;s[i].money -= sum;}sort(s + 1, s + n + 1, cmp);for (int i = 1; i <= n; i++)printf("%d %.2f\n", s[i].id, s[i].money / 100.0);return 0; }

L2-010 排座位

#include <bits/stdc++.h>using namespace std; typedef pair<int, int> pii; const int maxn = 105; int n, m, k; int p[maxn]; map<pii, int> vis;int Find(int x) {return p[x] == x ? x : p[x] = Find(p[x]); }int Merge(int x, int y) {int tx = Find(x);int ty = Find(y);if (tx != ty) p[tx] = ty; }int main() {cin >> n >> m >> k;for (int i = 1; i <= n; i++) p[i] = i;for (int i = 1; i <= m; i++) {int a, b, c;cin >> a >> b >> c;vis[make_pair(a, b)] = c;vis[make_pair(b, a)] = c;if (c == 1) Merge(a, b);}while (k--) {int a, b;cin >> a >> b;int res = vis[make_pair(a, b)];if (res == 1) {cout << "No problem" << endl;} else if (res == -1) {int tx = Find(a);int ty = Find(b);if (tx == ty) cout << "OK but..." << endl;else cout << "No way" << endl;} else {cout << "OK" << endl;}}return 0; }

L2-011 玩转二叉树

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。

#include <bits/stdc++.h>using namespace std; const int maxn = 50; int n; int pre_order[maxn], in_order[maxn]; pair<int, int> tree[maxn];int build(int la, int ra, int lb, int rb) {if (la > ra || lb > rb) return 0;int rt = pre_order[la];int p = 1;while (in_order[p] != rt) p++;int cnt = p - lb;tree[rt].first = build(la + 1, la + cnt, lb, p - 1);tree[rt].second = build(la + cnt + 1,ra, p + 1, rb);return rt; }void bfs(int rt) {vector<int> ans;queue<int> q;q.push(rt);while (!q.empty()) {int x = q.front();ans.push_back(x);q.pop();if (tree[x].second) q.push(tree[x].second);if (tree[x].first) q.push(tree[x].first);}for (int i = 0; i < ans.size(); i++) {if (i != 0) cout << " ";cout << ans[i];} }int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> in_order[i];for (int i = 1; i <= n; i++) cin >> pre_order[i];int rt = build(1, n, 1, n);bfs(rt);return 0; }

L2-012 关于堆的判断

#include <bits/stdc++.h>using namespace std; const int maxn = 1010; int n, m; int Heap[maxn]; map<int, int> mapper;void addNode(int temp, int idx) {while (idx > 1 && temp < Heap[idx / 2]) {Heap[idx] = Heap[idx / 2];idx /= 2;}Heap[idx] = temp; }int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {int t; cin >> t;addNode(t, i);}for (int i = 1; i <= n; i++) mapper[Heap[i]] = i;while (m--) {int x, y;string s, s1, s2, s3, s4;cin >> x >> s;if (s == "is") {cin >> s1 >> s2;s3 = s1 + s2;if (s3 == "theroot") {printf("%c\n", (mapper[x] == 1) ? 'T' : 'F');} else if (s3 == "theparent") {cin >> s4 >> y;printf("%c\n", (mapper[x] == mapper[y]/2) ? 'T' : 'F');} else {cin >> s4 >> y;printf("%c\n", (mapper[x]/2 == mapper[y]) ? 'T' : 'F');}} else {cin >> y >> s1 >> s2;printf("%c\n", (mapper[x]/2 == mapper[y]/2) ? 'T' : 'F');}}return 0; }

L2-013 红色警报

#include <bits/stdc++.h> #include <unordered_set>using namespace std; const int maxn = 510; int n, m, k, x, cnt; int p[maxn], mark[maxn]; pair<int, int> edge[maxn * 10];void init(int n) {for (int i = 0; i < n; i++) p[i] = i; }int Find(int x) {return p[x] == x ? x : p[x] = Find(p[x]); }void Merge(int x, int y) {int tx = Find(x);int ty = Find(y);if (tx != ty) p[tx] = ty; }int main() {cin >> n >> m;init(n);for (int i = 0; i < m; i++) {cin >> edge[i].first >> edge[i].second;Merge(edge[i].first, edge[i].second);}for (int i = 0; i < n; i++) {if (p[i] == i) cnt++;}cin >> k;for (int i = 1; i <= k; i++) {cin >> x;mark[x] = 1;init(n);for (int j = 0; j < m; j++) {if (!mark[edge[j].first] && !mark[edge[j].second]) {Merge(edge[j].first, edge[j].second);}}int ans = 0;for (int j = 0; j < n; j++) {if (!mark[j] && p[j] == j) ans++;}if (ans == cnt || ans + 1 == cnt) {cout << "City "<< x << " is lost." << endl;} else {cout << "Red Alert: City " << x << " is lost!" << endl;}cnt = ans;}if (k == n) {cout << "Game Over." << endl;}return 0; }

L2-014 列车调度

#include <bits/stdc++.h>using namespace std; const int maxn = 1e5 + 10; int n, x; set<int> s;int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> x;set<int>::iterator it = s.lower_bound(x);if (it == s.end()) {s.insert(x);} else {s.erase(it);s.insert(x);}}cout << s.size() << endl;return 0; }

L2-015 互评成绩

#include <bits/stdc++.h> using namespace std; const int maxn = 1e4 + 10; int n, k, m; double score[maxn]; int main() {cin >> n >> k >> m;for (int i = 1; i <= n; i++) {double sum = 0, t, maxx = 0, minn = maxn;for (int j = 1; j <= k; j++) {cin >> t;sum += t;maxx = max(maxx, t);minn = min(minn, t);}sum -= maxx + minn;score[i] = sum / (k - 2);}sort(score + 1, score + n + 1);for (int i = n - m + 1; i <= n; i++) {if (i != n - m + 1) putchar(' ');printf("%.3f", score[i]);}return 0; }

L2-016 愿天下有情人都是失散多年的兄妹

#include <bits/stdc++.h> #include <unordered_set>using namespace std; typedef pair<int, int> pii; const int maxn = 1e5 + 10; int n, m, id, fa, mo; vector<int> tree[maxn]; string sex[maxn]; unordered_set<int> vis;int bfs(int rt) {queue<pii> q;q.push(pii(rt, 0));while (!q.empty()) {pii p = q.front();q.pop();int id = p.first, level = p.second;if (level > 4) return 1;if (vis.count(id)) return 0;vis.insert(id);for (int i = 0; i < tree[id].size(); i++) {q.push(pii(tree[id][i], level + 1));}}return 1; }int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> id; //注意：两句输入必须分开写cin >> sex[id] >> fa >> mo;if (fa != -1) {sex[fa] = "M";tree[id].push_back(fa);}if (mo != -1) {sex[mo] = "F";tree[id].push_back(mo);}}cin >> m;while (m--) {int a, b;cin >> a >> b;if (sex[a] == sex[b]) {cout << "Never Mind" << endl;} else {vis.clear();bfs(a);if (bfs(b)) cout << "Yes" << endl;else cout << "No" << endl;}}return 0; }

L2-017 人以群分

#include <bits/stdc++.h>using namespace std; int n, out, in, diff; vector<int> a;int main() {cin >> n;for (int i = 0; i < n; i++) {int t; cin >> t;a.push_back(t);}sort(a.begin(), a.end());if (n & 1) {in = n / 2;out = in + 1;} else {out = in = n / 2;}for (int i = in; i < a.size(); i++) diff += a[i];for (int i = 0; i < in; i++) diff -= a[i];cout << "Outgoing #: " << out << endl;cout << "Introverted #: " << in << endl;cout << "Diff = " << diff << endl;return 0; }

L2-018 多项式A除以B

#include <bits/stdc++.h>using namespace std; const int maxn = 3010; int n, m, t, max1, max2; double c1[maxn], c2[maxn], c3[maxn];int getNum(double c[], int start) {int cnt = 0;for (int i = 0; i <= start; i++)if (abs(c[i]) >= 0.1) cnt++;return cnt; }void printPoly(double c[], int start) {printf("%d", getNum(c, start));if (!getNum(c, start)) printf(" 0 0.0");for (int i = start; i >= 0; i--)if (abs(c[i]) >= 0.1) printf(" %d %.1f", i, c[i]);putchar('\n'); }int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> t;max1 = max(max1, t);cin >> c1[t];}cin >> m;for (int i = 1; i <= m; i++) {cin >> t;max2 = max(max2, t);cin >> c2[t];}int t1 = max1, t2 = max2;while (t1 >= t2) {double c = c1[t1] / c2[t2];c3[t1 - t2] = c;for (int i = t1; i >= t1 - t2; i--)c1[i] -= c2[i - (t1 - t2)] * c;while (abs(c1[t1]) < 0.000001) t1--;}printPoly(c3, max1 - max2);printPoly(c1, t1);return 0; }

L2-019 悄悄关注

#include <bits/stdc++.h>using namespace std; const int maxn = 1e4 + 10; int n, m, num; double avg; set<string> follow; vector<string> ans; pair<string, int> a[maxn]; string name;int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> name;follow.insert(name);}cin >> m;for (int i = 0; i < m; i++) {cin >> a[i].first >> a[i].second;avg += a[i].second;}avg /= m;for (int i = 0; i < m; i++) {name = a[i].first;num = a[i].second;if (num > avg && !follow.count(name))ans.push_back(name);}sort(ans.begin(), ans.end());if (ans.size()) {for (int i = 0; i < ans.size(); i++)cout << ans[i] << endl;} else {cout << "Bing Mei You" << endl;}return 0; }

L2-020 功夫传人

#include <bits/stdc++.h>using namespace std; typedef pair<int, double> pid; const int maxn = 1e5 + 10; int n, k, t; double z, r; vector<int> a[maxn]; int mark[maxn];double bfs(int rt, double z, double r) {double ans = 0;queue<pid> q;q.push(pid(rt, z));while (!q.empty()) {pid p = q.front();q.pop();int id = p.first;if (mark[id]) {ans += mark[id] * p.second;continue;}for (int i = 0; i < a[p.first].size(); i++) {q.push(pid(a[p.first][i], p.second * (1.0 - r)));} // cout << p.first << " " << p.second << endl;}cout << (int)ans << endl; }int main() {cin >> n >> z >> r;for (int i = 0; i < n; i++) {cin >> k;if (k == 0) {cin >> t;mark[i] = t;}for (int j = 0; j < k; j++) {cin >> t;a[i].push_back(t);}}bfs(0, z, r / 100);return 0; }

L2-021 点赞狂魔

#include <bits/stdc++.h> #include <unordered_set>using namespace std; const int maxn = 110; int n, k, t; struct Person {char name[10];int num;double avg; } a[maxn];bool cmp(const Person &A, const Person &B) {if (A.num == B.num) return A.avg < B.avg;else return A.num > B.num; }int main() {cin >> n;for (int i = 0; i < n; i++) {unordered_set<int> vis;cin >> a[i].name >> k;for (int j = 0; j < k; j++) {cin >> t;vis.insert(t);}a[i].num = vis.size();a[i].avg = (double)k / a[i].num;}sort(a, a + n, cmp);int cnt = n > 3 ? 3 : n;for (int i = 0; i < cnt; i++) {if (i != 0) putchar(' ');cout << a[i].name;}for (int i = 0; i < 3 - cnt; i++)cout << " -";cout << endl;return 0; }

L2-022 重排链表

#include <bits/stdc++.h>using namespace std; const int maxn = 1e5 + 10; int head, n, id; struct Node {int data, next; } a[maxn]; pair<int, int> ans[maxn];int main() {cin >> head >> n;for (int i = 0; i < n; i++) {cin >> id;cin >> a[id].data >> a[id].next;}int num = 0;for (int p = head; p != -1; p = a[p].next, num++);int t1 = 2, t2 = (num & 1) ? num : num - 1;for (int i = 1, p = head; p != -1; p = a[p].next) {if (i <= num / 2) {ans[t1].first = p;ans[t1].second = a[p].data;t1 += 2;} else {ans[t2].first = p;ans[t2].second = a[p].data;t2 -= 2;}i++;}for (int i = 1; i <= num; i++) {printf("%05d %d ", ans[i].first, ans[i].second);if (i != num) printf("%05d\n", ans[i + 1].first);else printf("-1\n");}return 0; }

L2-023 图着色问题

#include <bits/stdc++.h>using namespace std; const int maxn = 510; int v, e, k, n; int a[maxn]; vector<pair<int, int> > edge;int judge() {for(int i = 0; i < edge.size(); i++) {int u = edge[i].first;int v = edge[i].second;if (a[u] == a[v]) return 0;}return 1; }int main() {cin >> v >> e >> k;for (int i = 0; i < e; i++) {int u, v;cin >> u >> v;edge.push_back(make_pair(u, v));}cin >> n;while (n--) {set<int> s;for (int i = 1; i <= v; i++) {cin >> a[i];s.insert(a[i]);}if (s.size() != k) {cout << "No" << endl;continue;}if (judge()) cout << "Yes" << endl;else cout << "No" << endl;}return 0; }

L2-024 部落

#include <bits/stdc++.h> #include <unordered_set> using namespace std; const int maxn = 1e4 + 10; int n, m, k, a, b, cnt; //题目给出：所有人的编号从1开始连续编号 int p[maxn]; unordered_set<int> vis;int Find(int x) {return p[x] == x ? x : p[x] = Find(p[x]); }void Merge(int x, int y) {int tx = Find(x);int ty = Find(y);if (tx != ty) p[tx] = ty; }int main() {//freopen("1.in", "r", stdin);cin >> n;for (int i = 1; i < maxn; i++) p[i] = i;for (int i = 0; i < n; i++) {cin >> k;cin >> a;vis.insert(a);for (int j = 1; j < k; j++) {cin >> b;vis.insert(b);Merge(a, b);a = b;}}for (int i = 1; i <= vis.size(); i++) {if (p[i] == i) cnt++;}cout << vis.size() << " " << cnt << endl;cin >> m;while (m--) {cin >> a >> b;if (Find(a) == Find(b)) {cout << "Y" << endl;} else {cout << "N" << endl;}}return 0; }

L2-025 分而治之

#include <bits/stdc++.h> #include <unordered_set>using namespace std; const int maxn = 1e4 +10; int n, m, k; pair<int, int> edge[maxn]; unordered_set<int> s;int main() {cin >> n >> m;for (int i = 0; i < m; i++)cin >> edge[i].first >> edge[i].second;cin >> k;while (k--) {int np; cin >> np;int flag = 1;s.clear();for (int i = 1; i <= np; i++) {int t; cin >> t;s.insert(t);}for (int i = 0; i < m; i++) {int u = edge[i].first, v = edge[i].second;if (!s.count(u) && !s.count(v)) {flag = 0;}}if (flag) cout << "YES" << endl;else cout << "NO" << endl;}return 0; }

L2-026 小字辈

#include <bits/stdc++.h>using namespace std; typedef pair<int, int> pii; const int maxn = 1e5 +10; int n, t, rt; vector<int> tree[maxn]; vector<pii> ans;void bfs(int rt) {int maxx = 0;queue<pii> q;q.push(pii(rt, 1));while (!q.empty()) {pii p = q.front();q.pop();int id = p.first;int level = p.second;if (!tree[id].size()) {ans.push_back(pii(level, id));maxx = max(maxx, level);}for (int i = 0; i < tree[id].size(); i++) {q.push(pii(tree[id][i], level + 1));}}int flag = 0;cout << maxx << endl;sort(ans.begin(), ans.end());for (int i = 0; i < ans.size(); i++) {if (ans[i].first == maxx) {if (flag) cout << " ";cout << ans[i].second;flag = 1;}} }int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> t;if (t == -1) rt = i;else tree[t].push_back(i);}bfs(rt);return 0; }

L2-027 名人堂与代金券

#include <bits/stdc++.h>using namespace std; const int maxn = 1e4 + 10; int n, g, k, sum, rate; struct Student{string name;int score; } s[maxn];bool cmp(const Student &A, const Student &B) {if (A.score == B.score) return A.name < B.name;else return A.score > B.score; }int main() {cin >> n >> g >> k;for (int i = 0; i < n; i++) {cin >> s[i].name >> s[i].score;if (s[i].score >= 60 && s[i].score < g) {sum += 20;} else if (s[i].score >= g) {sum += 50;}}sort(s, s + n, cmp);cout << sum << endl;rate = 1;for (int i = 0; rate <= k && i < n; i++) {cout << rate << " " << s[i].name << " " << s[i].score << endl;if (s[i].score != s[i + 1].score) {rate = i + 2;}}return 0; }

L2-028 秀恩爱分得快

#include <bits/stdc++.h> #include <unordered_set>using namespace std; const int maxn = 1010; int n, m, k, a, b; int sex[maxn]; double pa_, pb_, pa[maxn], pb[maxn]; vector<int> photo[maxn]; unordered_set<int> have[maxn];int getNum(char *s) {int num;if (s[0] == '-') {num = atoi(s + 1);sex[num] = 1;} else {num = atoi(s);}return num; }void printRes(int x, int y) {if (sex[x]) putchar('-');cout << x << " ";if (sex[y]) putchar('-');cout << y << endl; }int main() {cin >> n >> m;for (int i = 0; i < m; i++) {cin >> k;for (int j = 0; j < k; j++) {char t[10]; cin >> t;photo[i].push_back(getNum(t));have[i].insert(getNum(t));}}char s1[10], s2[10];cin >> s1 >> s2;a = getNum(s1), b = getNum(s2);for (int i = 0; i < m; i++) {int have_a = have[i].count(a);int have_b = have[i].count(b);if (have_a || have_b)for (int j = 0; j < photo[i].size(); j++) {int t = photo[i][j];if (have_a && sex[t] != sex[a]) {pa[t] += 1.0 / photo[i].size();pa_ = max(pa[t], pa_);} else if (have_b && sex[t] != sex[b]) {pb[t] += 1.0 / photo[i].size();pb_ = max(pb[t], pb_);}}}if (pa_ == pa[b] && pb_ == pb[a]) {printRes(a, b);} else {for (int i = 0; i < n; i++)if (pa_ == pa[i]) {printRes(a, i);}for (int i = 0; i < n; i++)if (pb_ == pb[i]) {printRes(b, i);}}return 0; }

L2-029 特立独行的幸福

#include <bits/stdc++.h> #include <unordered_set>using namespace std; typedef pair<int, int> pii; const int maxn = 1e4 + 10; int x, y, flag; int vis[maxn]; map<int, int> ans;int isPrime(int x) {for (int i = 2; i <= sqrt(x); i++)if (x % i == 0) return 1;return 2; }int fun(int x) {int ans = 0;while (x != 0) {int t = x % 10;ans += t * t;x /= 10;}return ans; }void solve(int l, int r) {for (int i = l; i <= r; i++) {int t = i;if (vis[t]) continue;set<int> s;while (t != 1) {t = fun(t);if (s.count(t)) break;s.insert(t);vis[t] = 1;}if (t == 1) ans[i] = s.size();} }int main() {cin >> x >> y;solve(x, y);for (auto i : ans) {if (!vis[i.first]) {cout << i.first << " " << i.second * isPrime(i.first) << endl;flag = 1;}}if (!flag) cout << "SAD" << endl;return 0; }

L2-030 冰岛人

#include <bits/stdc++.h> using namespace std; bool judge(vector<int> &F, int s1, int s2) {int n = F.size();vector<int> count(n, 0);vector<int> dist1(n, 0);vector<int> dist2(n, 0);int t ;count[s1]++;count[s2]++;while(F[s1] != -1){t = F[s1];count[t]++;dist1[t] = dist1[s1] + 1;if(t == s2) //直系祖宗return false;s1 = t;}while(F[s2] != -1){t = F[s2];count[t]++;dist2[t] = dist2[s2] + 1;if(count[t] > 1){if(dist2[t]>=4 && dist1[t] >= 4)return true;elsereturn false;}s2 = t;}return true; } int main() {int n;cin >> n;string f1, f2;vector<bool> sex(n);vector<vector<string> > record(n);map<string, int> M; //给每个人编号vector<int> F(n, -1); //父节点编号int cnt = 0;for(int i=0;i<n;i++) //编号{cin >> f1 >> f2;M.insert(make_pair(f1, cnt));int l = f2.size();if(f2[l-1] == 'm' || f2[l-1] == 'n')sex[cnt] = 1; //男elsesex[cnt] = 0;cnt++;record[i].push_back(f1);record[i].push_back(f2);}string par;for(int i=0;i<n;i++) //找父节点{f1 = record[i][0];f2 = record[i][1];int len = f2.size();if(f2[len-1] != 'r' && f2[len-1] != 'n') //老祖宗continue;if(sex[M[f1]] == true)par = f2.substr(0, len-4);elsepar = f2.substr(0, len-7);F[M[f1]] = M[par];}int m;cin >> m;string t1,t2;for(int i=0;i<m;i++){cin >> f1 >> f2 >> t1 >> t2;if(M.find(f1) == M.end() || M.find(t1) == M.end() ){cout << "NA" << endl;continue;}if(sex[M[f1]] == sex[M[t1]]){cout << "Whatever" << endl;continue;}if(judge(F, M[f1], M[t1])){cout << "Yes" << endl;}elsecout << "No" << endl;}return 0; }

L2-031 深入虎穴

#include <bits/stdc++.h>using namespace std; typedef pair<int, int> pii; const int maxn = 1e5 + 10; int n, k; vector<int> tree[maxn];void bfs(int rt) {int t;queue<int> q;q.push(rt);while (!q.empty()) {t = q.front();q.pop();if (!tree[t].size()) continue;for (int i = 0; i < tree[t].size(); i++) {q.push(tree[t][i]);}}cout << t << endl; }int main() {cin >> n;int root = n * (n + 1) / 2;for (int i = 1; i <= n; i++) {cin >> k;for(int j = 1; j <= k; j++) {int t; cin >> t;root -= t;tree[i].push_back(t);}}bfs(root);return 0; }

L2-032 彩虹瓶

#include <bits/stdc++.h>using namespace std; int n, m, k; stack<int> s;int main() {cin >> n >> m >> k;while (k--) {int num = 1, flag = 1;while (!s.empty()) s.pop();for (int i = 1; i <= n; i++) {int t; cin >> t;while (!s.empty() && s.top() == num) {num++;s.pop();}if (t == num) num++;else s.push(t);if (s.size() > m) flag = 0;}while (!s.empty() && s.top() == num) {num++;s.pop();}if (num == n + 1 && flag) cout << "YES" << endl;else cout << "NO" << endl;}return 0; }

---

2020年11月27日23:34:23 更新完毕，祝大家明天rp++。

2020年11月28日20:55:17 完赛，拖累了队友，确实应该退役了。

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的团体程序设计天梯赛 L2 题目合集的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。