VP 记录 - 2023 CCPC 哈尔滨站

比赛链接

进度: 5 / 13

题目概览

题号 1标题 2做法
*AGo go Baron Bunny!
BMemory
*CKarshilov's Matching Problem II
*DA Simple MST Problem
*ERevenge on My Boss
*FPalindrome Path
*GThe Only Way to the Destination
HEnergy Distribution
*IRolling For Days
JGame on a Forest
*KOmniscia Spares None
LPalm Island
MPainter

官方题解

A - Go go Baron Bunny!

解题思路

复杂度

代码参考

Show code

B - Memory

解题思路

复杂度

代码参考

Show code

B.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define for_(i, l, r, v...) for (i64 i = (l), i##e = (r), ##v; i <= i##e; ++i)
template <class... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <class... Ts>
void inc(Ts &...x) {
((++x), ...);
}
void solve(int t_ = 0) {
int n;
cin >> n;
i64 now = 0, rem = 0;
double now_ = 0;
auto div2 = [&]() {
if (rem == 0) rem = now % 2;
now /= 2;
now_ = now + .5 * rem;
};
auto add = [&](int x) {
now_ += x;
double fnow_ = floor(abs(now_));
if (abs(abs(now_) - fnow_) < .1) {
now = fnow_;
rem = 0;
} else {
if (now_ < 0) rem = -1;
else rem = 1;
now = fnow_;
}
if (now_ < 0) { now = -now; }
};
auto out = [&]() {
if (now_ > 0) cout << '+';
else if (now_ < 0) cout << '-';
else cout << '0';
};
for_(i, 0, n - 1) {
int x;
cin >> x;
div2();
add(x);
out();
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cerr << fixed << setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

C - Karshilov's Matching Problem II

解题思路

复杂度

代码参考

Show code

D - A Simple MST Problem

解题思路

复杂度

代码参考

Show code

E - Revenge on My Boss

解题思路

复杂度

代码参考

Show code

F - Palindrome Path

解题思路

复杂度

代码参考

Show code

G - The Only Way to the Destination

解题思路

复杂度

代码参考

Show code

H - Energy Distribution

解题思路

复杂度

代码参考

Show code

H.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
template <class Tp>
using vec = vector<Tp>;
template <class Tp>
using vvec = vector<vector<Tp>>;
template <class... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <class... Ts>
void inc(Ts &...x) {
((++x), ...);
}
double eps = 1e-8;
bool ge(vvec<double> &b) {
u32 n = b.size(), m = b[0].size();
for (u32 i = 0; i < n; ++i) {
{
u32 j = i;
for (u32 k = i + 1; k < n; ++k)
if (abs(b[j][i]) < abs(b[k][i])) j = k;
if (j != i) swap(b[i], b[j]);
if (abs(b[i][i]) < eps) return 1;
}
for (u32 j = i + 1; j < m; ++j) b[i][j] /= b[i][i];
b[i][i] = 1;
for (u32 j = 0; j < n; ++j) {
if (j == i) continue;
double d = b[j][i];
b[j][i] = 0;
for (u32 k = i + 1; k < m; ++k) b[j][k] -= d * b[i][k];
}
}
return 0;
}
void solve(int t_ = 0) {
int n;
cin >> n;
vector<vec<int>> w(n, vec<int>(n));
for (auto &y : w)
for (auto &x : y) cin >> x;
double ans = 0;
for (int sta = 1; sta < (1 << n); ++sta) {
vector<int> a;
for (int i = 0; i < n; ++i)
if ((sta >> i) & 1) a.push_back(i);
if (a.size() <= 1) continue;
vector<vec<double>> b(a.size() + 1, vec<double>(a.size() + 2));
for (int i = 0; i < a.size(); ++i) {
for (int j = 0; j < a.size(); ++j) b[i][j] = i == j ? 0 : w[a[i]][a[j]];
b[i][a.size()] = 1;
}
for (int i = 0; i < a.size(); ++i) b[a.size()][i] = 1;
b[a.size()][a.size() + 1] = 1;
if (ge(b)) continue;
double ret = 0;
bool flag = 0;
for (int i = 0; i < a.size(); ++i)
if (b[i].back() < 0) flag = 1;
if (flag) continue;
for (int i = 0; i < a.size(); ++i)
for (int j = i + 1; j < a.size(); ++j) {
ret += b[i].back() * b[j].back() * w[a[i]][a[j]];
}
ans = max(ans, ret);
}
cout << fixed << setprecision(8) << ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cerr << fixed << setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

I - Rolling For Days

解题思路

复杂度

代码参考

Show code

J - Game on a Forest

解题思路

复杂度

代码参考

Show code

J.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
template <class Tp>
using vec = vector<Tp>;
template <class... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <class... Ts>
void inc(Ts &...x) {
((++x), ...);
}
void solve(int t_ = 0) {
int n, m;
cin >> n >> m;
vector<vec<int>> e(n);
auto add = [&](int u, int v) { e[u].push_back(v), e[v].push_back(u); };
for (int i = 0, u, v; i < m; ++i) cin >> u >> v, --u, --v, add(u, v);
int sg = 0;
vector<int> rt, sz(n);
auto dfs = [&](auto dfs, int u) -> void {
sz[u] = 1;
for (auto v : e[u])
if (!sz[v]) dfs(dfs, v), sz[u] += sz[v];
};
auto ssg = [](int x) {
if (!x) return 0;
return x & 1 ? 1 : 2;
};
for (int i = 0; i < n; ++i)
if (!sz[i]) {
dfs(dfs, i), rt.push_back(i);
sg ^= ssg(sz[i]);
}
if (!sg) return void(cout << 0);
int ans = 0;
auto getans = [&](auto getans, int u, int fa, int ssz) -> void {
int t = ssg(ssz - sz[u]);
for (auto v : e[u])
if (v != fa) {
if (0 == (sg ^ (ssg(sz[v]) ^ ssg(ssz - sz[v])))) ++ans;
getans(getans, v, u, ssz);
t ^= ssg(sz[v]);
}
if (0 == (sg ^ t)) ++ans;
};
for (auto x : rt) {
sg ^= ssg(sz[x]);
getans(getans, x, x, sz[x]);
sg ^= ssg(sz[x]);
}
cout << ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cerr << fixed << setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

K - Omniscia Spares None

解题思路

复杂度

代码参考

Show code

L - Palm Island

解题思路

复杂度

代码参考

Show code

L.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
template <class... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <class... Ts>
void inc(Ts &...x) {
((++x), ...);
}
void solve(int t_ = 0) {
int n;
cin >> n;
deque<int> a(n), b(n), c(n);
for (auto &x : a) cin >> x, --x;
for (auto &x : b) cin >> x, --x;
for (int i = 0; i < n; ++i) c[b[i]] = i;
for (int i = 0; i < n; ++i) a[i] = c[a[i]], b[i] = (i + 1) % n;
string ans = "";
auto op1 = [&](deque<int> &a) {
int a0 = a.front();
a.pop_front();
a.push_back(a0);
ans += '1';
};
auto op2 = [&](deque<int> &a) {
int a0 = a.front();
a.pop_front();
int a1 = a.front();
a.pop_front();
a.push_front(a0);
a.push_back(a1);
ans += '2';
};
for (int i = 0; i < n; ++i) {
int t = a[0];
while (1) {
if (b[a[0]] == t) break;
op1(a);
}
while (1) {
if (a[1] == t) break;
op2(a);
}
}
while (1) {
if (a[0] == 0) break;
op1(a);
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cerr << fixed << setprecision(6);
int i_ = 0;
int t_ = 0;
cin >> t_;
for (i_ = 0; i_ < t_; ++i_) solve(i_);
return 0;
}

M - Painter

解题思路

复杂度

代码参考

Show code

M.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
template <class... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <class... Ts>
void inc(Ts &...x) {
((++x), ...);
}
struct op {
string opt;
i64 x1, y1, x2, y2, r;
string str;
};
void solve(int t_ = 0) {
int n;
cin >> n;
vector<op> oplist(n);
for (int i = 0; i < n; ++i) {
op opi;
cin >> opi.opt;
if (opi.opt == "Circle") {
cin >> opi.x1 >> opi.y1 >> opi.r >> opi.str;
} else if (opi.opt == "Rectangle") {
cin >> opi.x1 >> opi.y1 >> opi.x2 >> opi.y2 >> opi.str;
} else {
cin >> opi.x1 >> opi.y1 >> opi.x2 >> opi.y2;
for (i64 y = opi.y2; y >= opi.y1; --y) {
for (i64 x = opi.x1; x <= opi.x2; ++x) {
string now = ".";
for (int j = i - 1; j >= 0; --j) {
if (oplist[j].opt == "Circle") {
if ((oplist[j].x1 - x) * (oplist[j].x1 - x) +
(oplist[j].y1 - y) * (oplist[j].y1 - y) <=
oplist[j].r * oplist[j].r) {
now = oplist[j].str;
break;
}
} else if (oplist[j].opt == "Rectangle") {
if (oplist[j].x1 <= x && x <= oplist[j].x2 && oplist[j].y1 <= y &&
y <= oplist[j].y2) {
now = oplist[j].str;
break;
}
}
}
cout << now;
}
cout << "\n";
}
}
oplist[i] = opi;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cerr << fixed << setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

  1. 打 * 的是还没写的题↩︎

  2. 带超链接的是找到了原题或原型↩︎