D. Snuke Panic (DP)
https://atcoder.jp/contests/abc266/tasks/abc266_d
定义 $dp[x][i]$: The maximum sum of size of Snukes that Takahashi captures until he reaches at the coordinate $x$ at time $t$
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
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<long long>> a(5, vector<long long>(1e5 + 5));
for (int i = 1; i <= n; i++)
{
int t, x;
cin >> t >> x;
cin >> a[x][t];
}
vector<vector<long long>> dp(5, vector<long long>(1e5 + 5, -1e18));
dp[0][0] = 0;
for (int i = 1; i <= 1e5; i++)
{
dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]) + a[0][i];
dp[1][i] = max(dp[1][i - 1], max(dp[0][i - 1], dp[2][i - 1])) + a[1][i];
dp[2][i] = max(dp[2][i - 1], max(dp[1][i - 1], dp[3][i - 1])) + a[2][i];
dp[3][i] = max(dp[3][i - 1], max(dp[2][i - 1], dp[4][i - 1])) + a[3][i];
dp[4][i] = max(dp[4][i - 1], dp[3][i - 1]) + a[4][i];
}
long long ans = 0;
for (int i = 0; i < 5; i++)
{
ans = max(ans, dp[i][1e5]);
}
cout << ans << endl;
return 0;
}
E. Throwing the die (DP)
https://atcoder.jp/contests/abc266/tasks/abc266_e
定义 $dp[i]$: the maximum expected score if we can roll a die $i$ more times
转移时, 若当前数字为 $x$:
- 结束游戏, 获得 $x$ 得分
- 继续游戏, 获得 $dp[i - 1]$ 得分
即: $dp[i] = \sum {\frac{1}{6} * \max {(x, dp[i - 1])}}, 1 \le x \le 6$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<double> dp(n + 1, 0);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= 6; j++)
{
dp[i] += (1.0 / 6.0) * max(dp[i - 1], (double)j);
}
}
cout << fixed << setprecision(10) << dp[n] << endl;
return 0;
}
F. Well-defined Path Queries on a Namori (DSU)
https://atcoder.jp/contests/abc266/tasks/abc266_f
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
#include <bits/stdc++.h>
using i64 = long long;
struct DSU {
std::vector<int> f, siz;
DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }
int leader(int x) {
while (x != f[x]) x = f[x] = f[f[x]];
return x;
}
bool same(int x, int y) { return leader(x) == leader(y); }
bool merge(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) return false;
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) { return siz[leader(x)]; }
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
std::vector<bool> cyc(n);
std::vector<int> parent(n, -1), vis(n, -1);
int cur = 0;
std::function<void(int)> dfs = [&](int x) {
vis[x] = cur++;
for (auto y : adj[x]) {
if (y == parent[x]) {
continue;
}
if (vis[y] == -1) {
parent[y] = x;
dfs(y);
} else if (vis[x] > vis[y]) {
for (int i = x; i != y; i = parent[i]) {
cyc[i] = true;
}
cyc[y] = true;
}
}
};
dfs(0);
DSU dsu(n);
for (int i = 0; i < n; i++) {
for (auto j : adj[i]) {
if (!cyc[i] || !cyc[j]) {
dsu.merge(i, j);
}
}
}
int q;
std::cin >> q;
for (int i = 0; i < q; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
std::cout << (dsu.same(u, v) ? "Yes" : "No") << "\n";
}
return 0;
}