天梯赛练习（L2-007 ~ L2-012）

L2-007 家庭房产

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。

Input

输入第一行给出一个正整数N（≤1000），随后N行，每行按下列格式给出一个人的房产：

编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积

其中编号是每个人独有的一个4位数的编号；父和母分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0≤k≤5）是该人的子女的个数；孩子i是其子女的编号。

Output

首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：

家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积

其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。

思路：模拟一下即可，对于有父子关系的直接建树，遍历所有的树，家庭数就是树的棵树，每个家庭的人数就是树中节点数量多次使用BFS遍历即可。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e4 + 5;
int n;
std::vector<int> p[N];
bool vis[N];struct node {int num, f, m, x;int cnt, sum;
} e[N], g[N];struct Ans {int id, cnt;double x, are; 
};
std::vector<Ans> ans;bool cmp(Ans a, Ans b) {if(a.are > b.are) return true;else if(a.are == b.are && a.id < b.id) return true;else return false;
}void BFS(int u) {int min = 1e5, cnt = 0;int d = 0, sum = 0;std::queue<int> q;q.push(u);vis[u] = true;while(!q.empty()) {int now = q.front();min = std::min(now, min);cnt ++;d += g[now].cnt;sum += g[now].sum;q.pop();for(auto u : p[now]) {if(!vis[u]) {vis[u] = true;q.push(u);}}}Ans res = {min, cnt, d * 1.0 / cnt, sum * 1.0 / cnt};ans.push_back(res);
}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 >> e[i].num >> e[i].f >> e[i].m >> e[i].x;if(e[i].f != -1) {p[e[i].f].push_back(e[i].num);p[e[i].num].push_back(e[i].f);} if(e[i].m != -1) {p[e[i].m].push_back(e[i].num);p[e[i].num].push_back(e[i].m);}for(int j = 1; j <= e[i].x; j ++) {int y;std::cin >> y;p[e[i].num].push_back(y);p[y].push_back(e[i].num);}std::cin >> e[i].cnt >> e[i].sum;g[e[i].num] = e[i];}for(int i = 1; i <= n; i ++) {if(!vis[e[i].num]) {BFS(e[i].num);}}std::sort(ans.begin(), ans.end(), cmp);std::cout << ans.size() << '\\n';for(int i = 0; i < ans.size(); i ++) {std::cout << std::setw(4) << std::setfill('0') << ans[i].id;std::cout << ' ' << ans[i].cnt << ' ';std::cout << std::fixed << std::setprecision(3) << ans[i].x << ' ' << ans[i].are << '\\n';  }return 0;
}

L2-008 最长对称子串

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

Input

输入在一行中给出长度不超过1000的非空字符串。

Output

在一行中输出最长对称子串的长度。

思路：思路显然，将给出的字符串翻转之后两个字符串求最长公共子串即可。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 1e3 + 5;
std::string s;
int f[N][N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::getline(std::cin, s);std::string n = s;reverse(s.begin(), s.end());int len = s.length();int max = 0;for(int i = 1; i <= len; i ++) {for(int j = 1; j <= len; j ++) {if(s[i - 1] == n[j - 1]) {f[i][j] = f[i - 1][j - 1] + 1;if(f[i][j] > max)max = f[i][j];}}}std::cout << max << '\\n';return 0;
}

L2-009 抢红包

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

Input

输入第一行给出一个正整数N（≤10^4），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

K N1​ P1 ​⋯ NK​ PK​

其中K（0≤K≤20）是发出去的红包个数，Ni​是抢到红包的人的编号，Pi​（>0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

Output

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

思路：结构体模拟排序。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
typedef std::pair<int, double> PII;
const int N = 1e3 + 5;
int n;struct node {int id, cnt;double num;
};bool cmp(node a, node b) {if(a.num > b.num) return true;else if(a.num == b.num && a.cnt > b.cnt) return true;else if(a.num == b.num && a.cnt > b.cnt && a.id < b.id) return true;else return false;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> n;std::vector<node> v;std::unordered_map<int, PII> mp;for(int i = 1; i <= n; i ++) {int k;std::cin >> k;double sum = 0;for(int j = 1; j <= k; j ++) {int id;double num;std::cin >> id >> num;mp[id].second += num;mp[id].first ++;sum += num;}mp[i].second -= sum;}for(auto [x, y] : mp) {v.push_back({x, y.first, y.second});}std::sort(v.begin(), v.end(), cmp);for(auto [x, y, z] : v) {std::cout << x << ' ';std::cout << std::fixed << std::setprecision(2) << z / 100 << '\\n';}return 0;
}

L2-010 排座位

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

Input

输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2 关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

Output

对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but...；如果他们之间只有敌对关系，则输出No way。

思路：明显并查集问题。并查集维护朋友关系，另开二维数组存敌对关系，根据题意判断即可。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
typedef std::pair<int, double> PII;
const int N = 105;
int n, m, q;
int fa[N], mp[N][N];int getfa(int x) {return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}void emerge(int x, int y) {int xx = getfa(x);int yy = getfa(y);fa[xx] = yy;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> n >> m >> q;for(int i = 1; i <= n; i ++) {fa[i] = i;}for(int i = 1; i <= m; i ++) {int a, b, rel;std::cin >> a >> b >> rel;mp[a][b] = mp[b][a] = rel;if(rel == 1)emerge(a, b);}while(q --) {int a, b;std::cin >> a >> b;int x = getfa(a), y = getfa(b);if(x == y && mp[a][b] != -1)std::cout << "No problem" << '\\n';else if(x != y && mp[a][b] == -1)std::cout << "No way" << '\\n';else if(x != y && mp[a][b] != -1)std::cout << "OK" << '\\n';else if(x == y && mp[a][b] == -1)std::cout << "OK but..." << '\\n';}return 0;
}

L2-011 玩转二叉树

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

Input

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

Output

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

思路：和前面的树的遍历一题一样，但是有个结论可以注意：一棵树的前序遍历的转置就是它的镜像的后序遍历，而两种方式的中序遍历互为转置。转置在这里的意思是数组翻转。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 105;
int n;
int a[N], b[N];
std::vector<int> ans;struct node {int l, r;
} e[N];int DFS(int l1, int r1, int l2, int r2) {if(l1 > r1) return 0;int root = a[r2], p1 = l1, p2;while(b[p1] != root) p1 ++;p2 = p1 - l1;e[root].l = DFS(l1, p1 - 1, l2, l2 + p2 - 1);e[root].r = DFS(p1 + 1, r1, l2 + p2, r2 - 1);return root;
}void BFS(int u) {std::queue<int> q;q.push(u);while(!q.empty()) {int now = q.front();q.pop();ans.push_back(now);if(e[now].l) q.push(e[now].l);if(e[now].r) q.push(e[now].r);}
}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 >> b[i];}for(int i = 1; i <= n; i ++) {std::cin >> a[i];}std::reverse(a + 1, a + 1 + n);std::reverse(b + 1, b + 1 + n);DFS(1, n, 1, n);BFS(a[n]);for(int i = 0; i < n; i ++) {std::cout << ans[i] << " \\n"[i == n - 1];}return 0;
}

os：气死我啦，这个题花了1h去找扣得一分是在哪出的问题，结果换了g++就过了，，clang++害人啊

L2-012 关于堆的判断

将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：

• x is the root：x是根结点；
• x and y are siblings：x和y是兄弟结点；
• x is the parent of y：x是y的父结点；
• x is a child of y：x是y的一个子结点。

Input

每组测试第1行包含2个正整数N（≤ 1000）和M（≤ 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[−10000,10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。

Output

对输入的每个命题，如果其为真，则在一行中输出T，否则输出F。

思路：对于小根堆的模拟，对于数字插入时的时候需要不断更新数字应该位于的位置，注意给出的四个语句的处理，二叉树父子节点编号之间的关系。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 2e6 + 5;
int n, m, cnt;
int h[N];
std::string s;void up(int u) {while((u >> 1) && h[u >> 1] > h[u]) {std::swap(h[u >> 1], h[u]);u >>= 1;}
}void insert(int x) {h[++ cnt] = x;up(cnt);
}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 <= n; i ++) {int x;std::cin >> x;insert(x);}std::map<int, int> st;for(int i = 1; i <= n; i ++) {st[h[i]] = i;}for(int i = 1; i <= m; i ++) {int x, y;std::cin >> x >> s;if(s == "is") {std::cin >> s;if(s == "the") {std::cin >> s;if(s == "root")std::cout << (x == h[1] ? 'T' : 'F') << '\\n';else {std::cin >> s >> y;std::cout << (((st[x] < st[y] && (st[y] >> 1) == st[x])) ? 'T' : 'F') << '\\n';}}else {std::cin >> s >> s >> y;std::cout << ((st[y] < st[x] && (st[x] >> 1) == st[y]) ? 'T' : 'F') << '\\n';}}else {int y;std::cin >> y;std::getline(std::cin, s);std::cout << ((st[x] >> 1) == (st[y] >> 1) ? 'T' : 'F') << '\\n';}}return 0;
}