天梯赛练习（L2-021 ~ L2-028）

L2-021 点赞狂魔

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。

Input

输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F1​⋯FK​”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，Fi​（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从 1 到 107 编号。数字间以空格分隔。

Output

统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。

思路：模拟。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e5 + 5;
int n, x, ss;
std::string s;
std::unordered_map<std::string, std::unordered_map<int, int>> mp;struct node {std::string name;int cnt;double ave;
};
std::vector<node> v;bool cmp(node a, node b) {if(a.cnt > b.cnt) return true;else if(a.cnt == b.cnt && a.ave < b.ave) return true;else return false; 
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> n;for(int i = 1; i <= n; i ++) {std::cin >> s >> x;for(int j = 1; j <= x; j ++) {std::cin >> ss;mp[s][ss] ++;}v.push_back({s, mp[s].size(), x * 1.0 / mp[s].size()});}std::sort(v.begin(), v.end(), cmp);int len = v.size();for(int i = len + 1; i <= 3; i ++) {node xx = {"-", 0, 0};v.push_back(xx);}for(int i = 0; i < 3; i ++) {std::cout << v[i].name << " \\n"[i == 2];}return 0;
}

L2-022 重排链表

给定一个单链表 L1​→L2​→⋯→Ln−1​→Ln​，请编写程序将链表重新排列为 Ln​→L1​→Ln−1​→L2​→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

Input

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

Output

对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

思路：结构体模拟链表，然后对于一前一后取数用deque实现。学习了C++格式化补0输出hhh

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 2e5 + 5;
int st, n;struct node {int add, next, num;
} e[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> st >> n;for(int i = 1; i <= n; i ++) {int l, val, r;std::cin >> l >> val >> r;e[l] = {l, r, val};}std::deque<node> dq;for(int i = st; i != -1; i = e[i].next) {dq.push_back(e[i]);}std::vector<node> v;int pos = 1;while(!dq.empty()) {if(!pos) {v.push_back(dq.front());dq.pop_front();}else {v.push_back(dq.back());dq.pop_back();}pos ^= 1;}for(int i = 0; i < v.size(); i ++) {if(i != v.size() - 1) {std::cout << std::setw(5) << std::setfill('0') << v[i].add << ' ';std::cout << v[i].num << ' ';std::cout << std::setw(5) << std::setfill('0') << v[i + 1].add << '\\n';}else {std::cout << std::setw(5) << std::setfill('0') << v[i].add << ' ';std::cout << v[i].num << ' ';std::cout << -1 << '\\n';}	}return 0;
}

L2-023 图着色问题

图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？

但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。

Inuput

输入在第一行给出3个整数V（0<V≤500）、E（≥0）和K（0<K≤V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（≤20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。

Output

对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。

思路：暴力即可，对于每种配色方案，遍历所有边，保证每条边的两个端点颜色不同即可，注意判断染色种类，不等于k输出“No”。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e6 + 5;
int n, m, k, q;
int a[N];struct node {int u, v;
} e[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> n >> m >> k;for(int i = 1; i <= m; i ++) {int u, v;std::cin >> u >> v;e[i] = {u, v};}std::cin >> q;std::unordered_map<int, int> mp;while(q --) {mp.clear();for(int i = 1; i <= n; i ++) {std::cin >> a[i];mp[a[i]] ++;}bool flag = true;for(int i = 1; i <= m; i ++) {if(a[e[i].u] == a[e[i].v]) {flag = false;break;}}if(mp.size() != k)flag = false;std::cout << (flag ? "Yes" : "No") << '\\n';}return 0;
}

L2-024 部落

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

Input

输入在第一行给出一个正整数N（≤10^4），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：

K P[1] P[2] ⋯ P[K]

其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104。

之后一行给出一个非负整数Q（≤10^4），是查询次数。随后Q行，每行给出一对被查询的人的编号。

Output

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

思路：并查集模拟即可。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e4 + 5;
int n, x, y, c, q;
int fa[N];int getfa(int x) {return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> n;for(int i = 0; i <= N - 3; i ++) {fa[i] = i;}std::unordered_map<int, int> mp;for(int i = 1; i <= n; i ++) {std::cin >> x;std::cin >> c;mp[c] ++;for(int j = 2; j <= x; j ++) {std::cin >> y;mp[y] ++;int xx = getfa(y), yy = getfa(c);fa[xx] = yy;}}int cnt = 0;for(auto [u, v] : mp)if(fa[u] == u)cnt ++;std::cout << mp.size() << ' ' << cnt << '\\n';std::cin >> q;while(q --) {int x, y;std::cin >> x >> y;int xx = getfa(x), yy = getfa(y);std::cout << (xx == yy ? "Y" : "N") << '\\n';}return 0;
}

L2-025 分而治之

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

Input

输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：

Np v[1] v[2] ... v[Np]

其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。

Output

对每一套方案，如果可行就输出YES，否则输出NO。

思路：和023一样，直接暴力。注意本质是去掉部分点后所有点都不相连，对于每条边去判断有没有点使得这条边断掉即可。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e4 + 5;
int n, m, x, q, c;struct node {int u, v;
} e[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> n >> m;for(int i = 1; i <= m; i ++) {int u, v;std::cin >> u >> v;e[i] = {u, v};}std::cin >> q;std::unordered_map<int, int> mp;while(q --) {std::cin >> x;mp.clear();for(int i = 1; i <= x; i ++) {std::cin >> c;mp[c] ++;}int cnt = 0;for(int i = 1; i <= m; i ++) {if(mp[e[i].u] || mp[e[i].v])cnt ++;}std::cout << (cnt == m ? "YES" : "NO") << '\\n';}return 0;
}

L2-026 小字辈

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

Input

输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

Output

首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

思路：存一下给出的家庭情况，BFS找到最大深度，同时将同深度的节点放在一起。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e5 + 5;
int n, max, x;
std::vector<int> vec[N], ans[N];
bool vis[N];struct node {int u, deep;
};void BFS(int u) {std::queue<node> q;q.push({u, 1});while(!q.empty()) {auto now = q.front();q.pop();vis[now.u] = true;max = std::max(max, now.deep);ans[now.deep].push_back(now.u);for(auto v : vec[now.u]) {if(!vis[v]) q.push({v, now.deep + 1});}}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> n;int root;for(int i = 1; i <= n; i ++) {std::cin >> x;if(x == -1)root = i;elsevec[x].push_back(i);}BFS(root);std::sort(ans[max].begin(), ans[max].end());std::cout << max << '\\n';for(int i = 0; i < ans[max].size(); i ++) {std::cout << ans[max][i] << " \\n"[i == ans[max].size() - 1];}return 0;
}

L2-027 名人堂与代金券

对于在中国大学MOOC（http://www.icourse163.org/ ）学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，并且有另加福利：总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60, G) 区间内者，可以得到 20 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。

Input

输入在第一行给出 3 个整数，分别是 N（不超过 10 000 的正整数，为学生总数）、G（在 (60,100) 区间内的整数，为题面中描述的代金券等级分界线）、K（不超过 100 且不超过 N 的正整数，为进入名人堂的最低名次）。接下来 N 行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间 [0, 100] 内的整数），其间以空格分隔。题目保证没有重复的账号。

Output

首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以 1 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。

思路：结构体排序，，麻了，今晚上怎么水题这么多

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e4 + 5;
int n, m, k;struct node {std::string name;int gra;int rk;
} e[N];bool cmp(node a, node b) {if(a.gra > b.gra) return true;else if(a.gra == b.gra && a.name < b.name) return true;else return false;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> n >> m >> k;ll sum = 0;for(int i = 1; i <= n; i ++) {std::string s;int x;std::cin >> s >> x;e[i] = {s, x};if(x >= m)sum += 50;else if(x >= 60)sum += 20;}std::sort(e + 1, e + 1 + n, cmp);std::cout << sum << '\\n';for(int i = 1; i <= n; i ++) {if(i == 1 || e[i].gra != e[i - 1].gra)e[i].rk = i;elsee[i].rk = e[i - 1].rk;}for(int i = 1; i <= n; i ++) {if(e[i].rk <= k)std::cout << e[i].rk << ' ' << e[i].name << ' ' << e[i].gra << '\\n';elsebreak;}return 0;
}

L2-028 秀恩爱分得快

古人云：秀恩爱，分得快。

互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？

Input

输入在第一行给出 2 个正整数：N（不超过1000，为总人数——简单起见，我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的负号表示女性）和 M（不超过1000，为照片总数）。随后 M 行，每行给出一张照片的信息，格式如下：

K P[1] ... P[K]

其中 K（≤ 500）是该照片中出现的人数，P[1] ~ P[K] 就是这些人的编号。最后一行给出一对异性情侣的编号 A 和 B。同行数字以空格分隔。题目保证每个人只有一个性别，并且不会在同一张照片里出现多次。

Output

首先输出 A PA，其中 PA 是与 A 最亲密的异性。如果 PA 不唯一，则按他们编号的绝对值递增输出；然后类似地输出 B PB。但如果 A 和 B 正是彼此亲密度最高的一对，则只输出他们的编号，无论是否还有其他人并列。

思路：暴力，注意处理男女的负值，所以采用string输入。

代码源自

AC Code：

#include<bits/stdc++.h>
using namespace std;int n,m,k;
vector<int>a,b;
set<int>A,B;
double g[1005][1005], maxn[1005];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;string s;while(m--){cin>>k;a.clear();b.clear();for(int i=0; i<k; i++){cin>>s;if(s[0] == '-'){a.push_back(abs(stoi(s)));A.insert(abs(stoi(s)));}else{b.push_back(stoi(s));B.insert(abs(stoi(s)));}}for(int i=0; i<a.size(); i++){for(int j=0; j<b.size(); j++){g[a[i]][b[j]] += 1.0/k;g[b[j]][a[i]] += 1.0/k;if(maxn[a[i]] < g[a[i]][b[j]])maxn[a[i]] = g[a[i]][b[j]];if(maxn[b[j]] < g[b[j]][a[i]])maxn[b[j]] = g[b[j]][a[i]];}}}string s1, s2;cin>>s1>>s2;int aa = abs(stoi(s1));int bb = abs(stoi(s2));if(maxn[aa] == g[aa][bb] && maxn[bb] == g[bb][aa]){cout<<s1<<" "<<s2;return 0;}if(s1[0] == '-'){for(auto p:B){if(maxn[aa] == g[p][aa])cout<<s1<<" "<<p<<endl;}}else {for( auto p:A){if(maxn[aa] == g[p][aa])cout<<s1<<' '<<'-'<<p<<endl; }}if(s2[0]=='-'){for(auto p:B)if(maxn[bb]==g[bb][p])cout<<s2<<' '<<p<<endl;}else{for(auto p:A)if(maxn[bb]==g[bb][p])cout<<s2<<' '<<'-'<<p<<endl;}return 0;
}