正式训练
A. Boxes and Balls
易知答案一定可以表示为前 $m$ 个自然数的和。二分找出最大的 $m$ 即可。
L. Multiplication Table
实际上整个矩阵被左上角的坐标 $(x, y)$ 完全确定,而每个给出的数实际上是一个形如 $(x + i)(y + j) = a_{i, j}$ 的条件。
- 若矩阵中全是
?
,直接输出 Yes
即可。 - 若非
?
的数至少有两个,则一定可以通过解二次方程确定出至多两组可能的 $(x, y)$,分别验证即可。 - 若非
?
的数有且仅有一个,确定其是否可以被分解为两个不太小的因子相乘即可。
上面的后两种情况均可通过枚举因子实现。时间复杂度 $O(T \cdot RC \sqrt{V})$。
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
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MX = 1003;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for(int _ = 1; _ <= T; _++) {
int r, c;
cin >> r >> c;
vector<tuple<int, int, int>> info;
for(int i = 0; i < r; i++) {
for(int j = 0; j < c; j++) {
string qwq;
cin >> qwq;
if(qwq != "?") {
info.emplace_back(i, j, atoi(qwq.c_str()));
}
}
}
auto check = [&] (int x, int y) {
for(auto [i, j, val] : info) {
if((LL)(x + i) * (y + j) != val) {
return false;
}
}
return true;
};
if(info.empty()) {
printf("Case #%d: Yes\n", _);
} else if(info.size() == 1) {
bool result = false;
int i, j, target;
tie(i, j, target) = info[0];
for(int t = min(i, j) + 1; t * (max(i, j) + 1) <= target; t++) {
if(target % t == 0) {
result = true;
break;
}
}
if(result) {
printf("Case #%d: Yes\n", _);
} else {
printf("Case #%d: No\n", _);
}
} else {
bool result = false;
int i, j, target;
tie(i, j, target) = info[0];
int p, q, trigger;
tie(p, q, trigger) = info[1];
for(int t = min(i, j) + 1; t * (max(i, j) + 1) <= target; t++) {
if(target % t != 0) {
continue;
}
int s = target / t;
// s, t
if((LL)(s - i + p) * (t - j + q) == trigger) {
if(check(s - i, t - j)) {
result = true;
break;
}
}
// t, s
if((LL)(t - i + p) * (s - j + q) == trigger) {
if(check(t - i, s - j)) {
result = true;
break;
}
}
}
if(result) {
printf("Case #%d: Yes\n", _);
} else {
printf("Case #%d: No\n", _);
}
}
}
return 0;
}
|
B. Business Cycle
我们考虑沿着环走完一整圈会发生什么。不妨设 $S$ 为环上所有数的和,$m$ 为环上前缀和中的最小值,即 $\displaystyle\min_{1 \leq k \leq n} \sum_{i=1}^{k} V_i$。若我们当前手里的钱是 $x$,一圈之后手里的钱数 $f(x)$ 可表示为
$$
f(x) = \begin{cases}
x + S, & x + m \geq 0 \newline
S - m, & x + m < 0
\end{cases}
$$
处理完不是整圈的部分之后暴力沿着 $f$ 的反函数往回跳即可。
这里需要注意有两种情况。不妨设 $p = kn + r$,我们既可以选择跳不超过 $k$ 圈之后走一个不超过 $r$ 的弧段,又可以选择跳不超过 $k - 1$ 圈之后走一个长度任意的弧段。
时间复杂度 $O(Tn)$。
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
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL solve() {
int n;
LL g, p;
cin >> n >> g >> p;
vector<int> arr(n);
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
LL sum = 0, min_sum = numeric_limits<LL>::max();
for(int val : arr) {
sum += val;
if(sum < min_sum) {
min_sum = sum;
}
}
LL max_round = p / n;
LL ans1 = g, ans2 = g;
for(int i = n - 1; i >= 0; i--) {
ans2 = min(g, max(0LL, ans2 - arr[i]));
if(i < p % n) {
ans1 = min(g, max(0LL, ans1 - arr[i]));
}
}
if(max_round == 0) {
return ans1;
}
if(sum <= 0) {
if(ans1 <= sum - min_sum) {
ans1 = 0;
}
if(max_round > 1 && ans2 <= sum - min_sum) {
ans2 = 0;
}
return min(ans1, ans2);
}
if(ans1 / sum < max_round) {
ans1 = 0;
} else {
ans1 -= max_round * sum;
}
if(ans2 / sum < max_round - 1) {
ans2 = 0;
} else {
ans2 -= (max_round - 1) * sum;
}
LL ans = min(ans1, ans2);
if(ans <= -min_sum || ans <= 0) {
return 0;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for(int _ = 1; _ <= T; _++) {
printf("Case #%d: %lld\n", _, solve());
}
return 0;
}
|
赛后补题
J. Dome and Steles
这个题其实训练还剩 80min 的时候就想出做法了,不过因为没有完全想清楚所有细节导致没写出来。
可以发现每个方块会给半径贡献一个 $\left( d^2 + a^2 + \dfrac{b^2}{4} \right)^{1/2}$ 的下界,其中 $d$ 是球心到方块外立面的距离。
显然,对每个方块取长宽中较小的作为 $a$ 是更好的。其次,当半径确定后,$a^2 + \dfrac{b^2}{4}$ 越大的方块越靠近球心。
我们的想法是二分答案,然后判定能不能放得下所有方块。判定的话注意到球心一定会被某个方块压住,不妨设球心离这个方块两边的长度分别为 $l$ 和 $r$,然后左半序列和右半序列会分别给出 $l$ 和 $r$ 的上界。我们最后只需要判断这两个上界是否与 $l + r = 1$ 相容即可。
时间复杂度 $O(T n \log n)$。
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
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
using LD = long double;
int read() {
string str;
cin >> str;
str.erase(str.length() - 5, 1);
return atoi(str.c_str()) * 2;
}
LL sqr(LL x) { return x * x; }
LD solve() {
int n;
cin >> n;
vector<LL> bricks;
for(int i = 1; i <= n; i++) {
int a = read(), b = read();
if(a < b) {
swap(a, b);
}
LL chr = (LL)a * a / 4 + (LL)b * b;
bricks.push_back(chr);
}
sort(bricks.begin(), bricks.end(), greater<LL>());
LD l = sqrtl(bricks[0] / 4e8), r = 1.5e5;
for(int i = 1; i <= 40; i++) {
LD mid = (l + r) / 2, tmp = mid * mid;
long double supr = 0.5;
for(int i = 1; 2 * i - 1 < bricks.size(); i++) {
supr = min(supr, sqrtl(tmp - bricks[2 * i - 1] / 4e8) - i);
}
long double supl = 1;
for(int i = 0; 2 * i < bricks.size(); i++) {
supl = min(supl, sqrtl(tmp - bricks[2 * i] / 4e8) - i);
}
if(supl + supr < 1 - 1e-6) {
l = mid;
} else {
r = mid;
}
}
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
for(int _ = 1; _ <= t; _++) {
printf("Case #%d: %.9Lf\n", _, solve());
}
return 0;
}
|
I. Champions League
很莫名其妙的一个状压 DP。由于对来自相同国家的球队分组有一个很麻烦的规则,我们自然可以想到逐个国家来处理。
同一国家的同一档次的球队在 DP 的过程中很难区分开来,我们索性在 DP 过程中只分配集合,最后再把那些阶乘统一乘进去。这样一来每个国家对 DP 的更新就可以通过逐档次枚举分组来实现。
注意到每个档次枚举的代价至多是 $\displaystyle \binom{8}{4} = 70$,考虑到同一国家的球队至多有 $5$ 个,每个国家的转移代价实际上只有 $10^4$ 数量级。因此总复杂度是可以接受的。
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
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
union data_t {
unsigned mask;
unsigned char ranks[4];
};
vector<unsigned> masks[6];
LL solve() {
map<string, int> teams_id;
map<int, array<int, 4>> teams_info;
LL factor = 1;
for(int i = 0; i <= 3; i++) {
for(int j = 1; j <= 8; j++) {
string str;
cin >> str;
if(!teams_id.count(str)) {
teams_id[str] = teams_info.size();
}
factor *= ++teams_info[teams_id[str]][i];
}
}
map<unsigned, LL> lst, cur;
lst[0] = 1;
for(const auto &[_, team] : teams_info) {
for(const auto &[mask, val] : lst) {
data_t S;
S.mask = mask;
function<void(size_t, unsigned)> dfs =
[&] (size_t rnk, unsigned groups) {
if(rnk == 4) {
cur[S.mask] += val;
return;
}
for(unsigned new_mask : masks[team[rnk]]) {
if(new_mask & (groups | S.ranks[rnk])) {
continue;
}
unsigned tmp = new_mask | groups;
if(abs(popcount(tmp & 0x0F) - popcount(tmp & 0xF0)) > 1) {
continue;
}
S.ranks[rnk] ^= new_mask;
dfs(rnk + 1, tmp);
S.ranks[rnk] ^= new_mask;
}
};
dfs(0, 0);
}
lst = cur;
cur.clear();
}
return lst[-1] * factor;
}
int main() {
for(unsigned i = 0; i < (1 << 8); i++) {
int pc = popcount(i);
if(pc <= 5) {
masks[pc].push_back(i);
}
}
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
for(int _ = 1; _ <= t; _++) {
printf("Case #%d: %lld\n", _, solve());
}
return 0;
}
|
E. Colorful Floor
实际上手做了之后感觉两三句话说不清楚,因此新开了一篇文章专门讲这个。
由于期末考试,南京站之后就没写过代码。南京站我们队打得稀烂,再往前杭州站和南京站之间的那次训练也因为我得病被迫取消。这么其实算来已经有一个多月没好好写代码了。
这次训练打得磕磕绊绊的,先权当找回状态吧。希望之后能好一些。
补题的话 DFM 训练时候队友解决了,其他题感觉赛场上我们也不太可能做出来,就先咕了。