# # Facebook Hacker Cup 2020 Round 2 题解

## # Problem A - Ca-pasta-ty (opens new window)

### # 题目描述

$N$个区域，每个区域现有$S_i$人，该区域允许的范围为$[L_i,R_i]$，问最少移动多少个人，可以让所有区域的人数都处在允许范围呢？

### # 题解

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

ll n, k;

void input(vector<ll> &v) {
ll a, b, c, d;
for (int i = 0; i < k; ++i)
for (int i = k; i < n; ++i)
v[i] = (a * v[i - 2] + b * v[i - 1] + c) % d;
}

class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
vector<ll> s(n), x(n), y(n);
input(s), input(x), input(y);
ll overflow = 0, extra = 0, vacancy = 0, require = 0;
for (int i = 0; i < n; ++i) {
ll hi = x[i] + y[i];
if (s[i] > hi)
overflow += s[i] - hi;
else
vacancy += min(hi - s[i], y[i]);
if (s[i] > x[i])
extra += min(s[i] - x[i], y[i]);
else
require += x[i] - s[i];
}
if (overflow >= require) {
if (overflow > require + vacancy)
printf("-1\n");
else
printf("%lld\n", overflow);
} else {
if (require > overflow + extra)
printf("-1\n");
else
printf("%lld\n", require);
}
}
};

int main() {
int t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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

## # Problem B - Elimination (opens new window)

### # 题目描述

$1,2,\cdots,N$$N$个选手进行一对一的比赛。编号大的选手一定不弱于编号小的选手。当任意两个选手比赛时，编号大的那个获胜概率为$P$$0.5\leq P\leq1$）。每次比赛后，输的一方立即被淘汰。求每个选手被淘汰（或最终胜利）时总比赛场数的期望。

## # Problem C - Circular Circles (opens new window)

### # 题目描述

$N$个小环，每个小环有$M$个节点。相邻两个小环之间有一条边相连。也就是说，一共有$NM+N$条边。初始时所有边的权重都为$1$

### # 题解

1. 大环去掉一条边，每个小环去掉一条边
2. 某一个小环去掉两条边，其他每个小环去掉一条边

#include <cstdio>
#include <iostream>
#include <set>
#include <vector>

#define INF 1e18
#define MOD 1000000007

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

ll n, m, e, k;

void input(vector<ll> &v, ll len, ll mod) {
ll a, b, c;
for (int i = 0; i < k; ++i)
for (int i = k; i < len; ++i)
v[i] = (a * v[i - 2] + b * v[i - 1] + c) % mod;
}

class Solution {
public:
void solve(int case_num) {
printf("Case #%d: ", case_num);
vector<ll> X(n), Y(n), I(e), W(e);
input(X, n, m);
input(Y, n, m);
input(I, e, n * m + n);
input(W, e, 1e9);
ll ans = 1, MST = n * m - 1;
ll MDT = INF;
vector<set<pair<ll, int>, greater<>>> lheap(n), rheap(n), heaps(n + 1);
vector<ll> value(n, -INF);
set<pair<ll, int>, greater<>> gheap;
vector<ll> edges(n * m + n, 1);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
heaps[i].insert({1, i * m + j});
for (int i = n * m; i < n * m + n; ++i)
heaps[n].insert({1, i});
for (int i = 0; i < n; ++i) {
if (X[i] == Y[i])
continue;
int xi = i * m + X[i], yi = i * m + Y[i];
if (xi > yi)
swap(xi, yi);
for (int j = xi; j < yi; ++j)
lheap[i].insert({1, j});
for (int j = i * m; j < xi; ++j)
rheap[i].insert({1, j});
for (int j = yi; j < i * m + m; ++j)
rheap[i].insert({1, j});
if (!lheap[i].empty() && !rheap[i].empty()) {
gheap.insert({1, i});
value[i] = 1;
}
}

for (int i = 0; i < e; ++i) {
int idx = min(I[i] / m, n);
if (I[i] != heaps[idx].begin()->second)
MST += heaps[idx].begin()->first - edges[I[i]];
heaps[idx].erase({edges[I[i]], I[i]});
heaps[idx].insert({W[i], I[i]});
MST += W[i] - heaps[idx].begin()->first;
if (idx != n) {
if (lheap[idx].count({edges[I[i]], I[i]})) {
lheap[idx].erase({edges[I[i]], I[i]});
lheap[idx].insert({W[i], I[i]});
}
if (rheap[idx].count({edges[I[i]], I[i]})) {
rheap[idx].erase({edges[I[i]], I[i]});
rheap[idx].insert({W[i], I[i]});
}
if (!lheap[idx].empty() && !rheap[idx].empty()) {
gheap.erase({value[idx], idx});
value[idx] = lheap[idx].begin()->first + rheap[idx].begin()->first -
heaps[idx].begin()->first;
gheap.insert({value[idx], idx});
}
}
if (!gheap.empty())
MDT = MST + heaps[n].begin()->first - gheap.begin()->first;
edges[I[i]] = W[i];
ans = min(MST, MDT) % MOD * ans % MOD;
}
printf("%lld\n", ans);
}
};

int main() {
int t;
for (int i = 1; i <= t; ++i) {
Solution solution = Solution();
solution.solve(i);
}
}
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
102
103
104
105
106
107
108
109
110
111
112