天梯赛真题模拟第六场"/>
中国石油大学天梯赛真题模拟第六场
中国石油大学天梯赛真题模拟第六场
L2-007 家庭房产 (25 分)给定每个人的家庭成员和其自己名下的房产,请你统计出每个家庭的人口数、人均房产面积及房产套数。
输入格式:
输入第一行给出一个正整数N(≤),随后N行,每行按下列格式给出一个人的房产:
编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积
其中编号
是每个人独有的一个4位数的编号;父
和母
分别是该编号对应的这个人的父母的编号(如果已经过世,则显示-1
);k
(0k
≤)是该人的子女的个数;孩子i
是其子女的编号。
输出格式:
首先在第一行输出家庭个数(所有有亲属关系的人都属于同一个家庭)。随后按下列格式输出每个家庭的信息:
家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积
其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出,若有并列,则按成员编号的升序输出。
输入样例:
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100
输出样例:
3 8888 1 1.000 1000.000 0001 15 0.600 100.000 5551 4 0.750 100.000
并查集,一开始cmp函数写错了,de了一晚上。。。。
韩宗志牛逼!
#include <bits/stdc++.h>using namespace std; const int maxn = 1e6 + 100; int vis[maxn], fa[maxn]; vector<int> all;struct node {int cnt;double size; } e[maxn]; struct out {int minid, cnt, perc;double persi; } ans[maxn];bool cmp(out a, out b) {if (a.persi * bt != b.persi * at) {return a.persi * bt > b.persi * at;}return a.minid < b.minid; }int fi(int x) {return fa[x] == x ? x : fa[x] = fi(fa[x]); }void uni(int x, int y) {int p1 = fi(x);int p2 = fi(y);if (p1 != p2) {fa[p2] = p1;} }void add(int x) {if (!vis[x]) {vis[x] = 1;all.push_back(x);} }void init() {for (int i = 0; i < maxn; i++)fa[i] = i; }int main() {freopen("input.txt", "r", stdin);init();int n;int id, f, ma, k, kid;cin >> n;for (int i = 0; i < n; i++) {cin >> id >> f >> ma >> k;add(id);if (f != -1) uni(id, f), add(f);if (ma != -1) uni(id, ma), add(ma);for (int j = 0; j < k; j++) {cin >> kid;if (kid != -1) {add(kid);uni(id, kid);}}cin >> e[id]t >> e[id].size;}int tot = 0;for (int p:all) {if (fi(p) == p) {ans[tot].minid = 0x3f3f3f3f;for (int x:all) {if (fi(x) == p) {ans[tot].minid = min(ans[tot].minid, x);ans[tot]t++;ans[tot].perc += e[x]t;ans[tot].persi += e[x].size;}}tot++;}}cout << tot << endl;sort(ans, ans + tot, cmp);for (int i = 0; i < tot; i++) {printf("%04d %d %.3f %.3f\n", ans[i].minid, ans[i]t, 1.0 * ans[i].perc / ans[i]t,ans[i].persi / ans[i]t);}return 0; }View Code
L2-4 链表去重 (25 分)
给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15,你需要输出去重后的链表 21→-15→-7,还有被删除的链表 -15→15。
输入格式:
输入在第一行给出 L 的第一个结点的地址和一个正整数 N(≤105,为结点总数)。一个结点的地址是非负的 5 位整数,空地址 NULL 用 -1 来表示。
随后 N 行,每行按以下格式描述一个结点:
地址 键值 下一个结点
其中地址
是该结点的地址,键值
是绝对值不超过104的整数,下一个结点
是下个结点的地址。
输出格式:
首先输出去重后的链表,然后输出被删除的链表。每个结点占一行,按输入的格式输出。
输入样例:
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
输出样例:
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
训练时老老实实模拟的链表没过。。。。
#include"bits/stdc++.h"using namespace std;const int maxn = 1e6 + 1000; int vis[maxn];struct node {int val, as;int last, next; } e[maxn], d[maxn]; int last = -1; int rootd = -1;void del(int id) {if (last == -1) {last = 0;rootd = 0;d[0].val = e[id].val;d[0].next = -1;} else {d[last].next = id;d[id].val = e[id].val;d[id].next = -1;last = id;}e[e[id].last].next = e[id].next;e[e[id].next].last = e[id].last;}void dfs(int now) {if (now == -1) return;if (!vis[e[now].as]) {vis[e[now].as] = 1;dfs(e[now].next);} else {int next = e[now].next;del(now);dfs(next);} }int main() {int root, n;int id, val, next;cin >> root >> n;for (int i = 0; i < n; i++) {cin >> id >> val >> next;e[id].val = val;if (val < 0) val *= -1;e[id].as = val;e[id].next = next;if (next != -1) {e[next].last = id;}}dfs(root);while (root != -1) {if(e[root].next==-1){printf("%05d %d %d\n", root, e[root].val, e[root].next);}elseprintf("%05d %d %05d\n", root, e[root].val, e[root].next);root = e[root].next;}while (rootd != -1) {if (d[rootd].next == -1) {printf("%05d %d %d\n", rootd, d[rootd].val, d[rootd].next);} elseprintf("%05d %d %05d\n", rootd, d[rootd].val, d[rootd].next);rootd = d[rootd].next;}return 0; }至今不知道为什么WA的代码
#include"bits/stdc++.h"using namespace std;const int maxn = 1e6 + 1000; struct node {int val, next; } a[maxn]; int b[maxn]; int vis[maxn];int main() {int head, n;cin >> head >> n;int pos, val, ne;for (int i = 0; i < n; i++) {cin >> pos >> val >> ne;a[pos].val = val;a[pos].next = ne;}printf("%05d %d", head, a[head].val);vis[abs(a[head].val)] = 1;int t = head;int tot = 0;while (1) {t = a[t].next;if (t == -1) {printf(" -1\n");break;}int ab = abs(a[t].val);if (vis[ab]) {b[tot++] = t;} else {vis[ab] = 1;printf(" %05d\n%05d %d", t, t, a[t].val);}}if (tot > 0) {printf("%05d %d", b[0], a[b[0]].val);for (int i = 1; i < tot; i++) {printf(" %05d\n%05d %d", b[i], b[i], a[b[i]].val);}printf(" -1\n");}return 0; }AC
posted @ 2019-03-18 23:58 Albert_liu 阅读( ...) 评论( ...) 编辑 收藏
更多推荐
中国石油大学天梯赛真题模拟第六场
发布评论