这场考试我除了最后一题有些思路外其他全是部分分（特殊性质）
Task 1 数据恢复
是一道CF上的题，但是应该是mashup的，比赛看不了。子任务4和5的特殊性质好拿分，特殊性质5的菊花图是启发正解用的（但是还是不会正解）
正解：还是按照菊花图中的按 $a/b$ 排序的做法，记 $a/b$ 为 $k$ ，选择 $k$ 最小的点，这如果当前点满足了父子关系，就直接恢复这个点否则把它的依赖恢复之后再恢复一定是最优的。因此我们可以把 $i$ 和 $$f_i 进行一个捆绑，也就是把 $i$ 和 $f_i$ 合并成一个新的点，这个点按照 $f_i - i$ 的顺序包含了这两个点。而新的这个点的 $a$ 和 $b$ 是原来两个点的值的和。因此新点的 $k$ 也可以计算了。
如果把这个新的点代替原来两个点，重新建树，那么新问题可原问题是等价的。
因此只需要不断重复这个操作，直到所有点都合并成一个点即可。
找依赖关系可以使用并查集维护，找最小值可以用堆维护。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 1000010;
#define int int64_t
template <typename NBXIN>
NBXIN read() {
NBXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int a[maxn], b[maxn], ans;
class DJU {
public:
int fa[maxn];
void init(int n) {
For(i, 1, n) {
fa[i] = i;
}
}
int findFa(int x) {
return (x == fa[x]) ? x : fa[x] = findFa(fa[x]);
}
void join(int x, int y) {
x = findFa(x);
y = findFa(y);
if (x == y) return;
ans += a[y] * b[x];
fa[y] = x;
a[x] += a[y];
b[x] += b[y];
}
} dj;
struct PN {
int id;
double cmpp;
PN() {}
PN(int idd) {
id = idd;
cmpp = a[idd] * 1.0 / b[idd];
}
friend bool operator< (PN a, PN b) {
if (a.cmpp != b.cmpp) return a.cmpp < b.cmpp;
return a.id < b.id;
}
};
bool vis[maxn];
int fa[maxn];
multiset<PN> st;
int32_t main() {
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
int n = read<int>();
dj.init(n);
For(i, 2, n) {
fa[i] = read<int>();
}
For(i, 1, n) {
a[i] = read<int>();
b[i] = read<int>();
st.insert(PN(i));
vis[i] = true;
}
while (!st.empty()) {
multiset<PN>::iterator it = st.begin(), tmp;
int id = it -> id;
st.erase(it);
vis[id] = false;
if (!fa[id]) continue;
int f = dj.findFa(fa[id]);
if (vis[f]) {
tmp = st.find(PN(f));
dj.join(f, id);
st.erase(tmp);
st.insert(PN(f));
} else {
dj.join(f, id);
}
}
cout << ans << endl;
return 0;
}
|
Task 2 下落的小球
直接上码，可重集排列，移球游戏思想
Official Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 1000010;
#define int int64_t
template <typename NBXIN>
NBXIN read() {
NBXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int a[maxn], b[maxn], ans;
class DJU {
public:
int fa[maxn];
void init(int n) {
For(i, 1, n) {
fa[i] = i;
}
}
int findFa(int x) {
return (x == fa[x]) ? x : fa[x] = findFa(fa[x]);
}
void join(int x, int y) {
x = findFa(x);
y = findFa(y);
if (x == y) return;
ans += a[y] * b[x];
fa[y] = x;
a[x] += a[y];
b[x] += b[y];
}
} dj;
struct PN {
int id;
double cmpp;
PN() {}
PN(int idd) {
id = idd;
cmpp = a[idd] * 1.0 / b[idd];
}
friend bool operator< (PN a, PN b) {
if (a.cmpp != b.cmpp) return a.cmpp < b.cmpp;
return a.id < b.id;
}
};
bool vis[maxn];
int fa[maxn];
multiset<PN> st;
int32_t main() {
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
int n = read<int>();
dj.init(n);
For(i, 2, n) {
fa[i] = read<int>();
}
For(i, 1, n) {
a[i] = read<int>();
b[i] = read<int>();
st.insert(PN(i));
vis[i] = true;
}
while (!st.empty()) {
multiset<PN>::iterator it = st.begin(), tmp;
int id = it -> id;
st.erase(it);
vis[id] = false;
if (!fa[id]) continue;
int f = dj.findFa(fa[id]);
if (vis[f]) {
tmp = st.find(PN(f));
dj.join(f, id);
st.erase(tmp);
st.insert(PN(f));
} else {
dj.join(f, id);
}
}
cout << ans << endl;
return 0;
}
|
