VP 记录 - 2021 CCPC 哈尔滨站

比赛链接

进度: 7 / 12

题目概览

题号 1标题 2做法
*ASo Many Lucky Strings
BMagical Subsequence
CColorful Tree
DMath master
EPower and Modulo
*FMaster Spark
GDamaged Bicycle
*HWhat logic for?
IPower and Zero
JLocal Minimum
*KWonder Egg Priority
*LKarshilov's Matching Problem

官方题解

A - So Many Lucky Strings

解题思路

复杂度

代码参考

Show code

B - Magical Subsequence

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using namespace std;
void solve(int t_ = 0) {
int n;
cin >> n;
vector<int> pos(101);
vector<vector<int>> f(n + 1);
vector<int> a(201, 0);
f[0] = a;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
f[i] = f[i - 1];
for (int j = 1; j <= 100; ++j) {
if (pos[j]) f[i][x + j] = max(f[i][x + j], f[pos[j] - 1][x + j] + 2);
}
pos[x] = i;
}
int ans = 0;
for (int i = 1; i <= 200; ++i) ans = max(ans, f[n][i]);
cout << ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cerr << fixed << setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

C - Colorful Tree

解题思路

复杂度

代码参考

Show code

C.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
#include <bits/stdc++.h>
using namespace std;
void solve(int t_ = 0) {
int n;
cin >> n;
vector<vector<int>> e(n);
for (int i = 1, x; i < n; ++i) cin >> x, --x, e[x].push_back(i);
vector<int> col(n);
for (auto &x : col) cin >> x;
int cnt = 0;
vector<int> ans(n), mx(n), id(n);
vector<set<int>> s(n);
vector<map<int, int>> m(n);
auto merge = [&](int u, int x) {
++m[u][x];
if (m[u][x] > mx[u]) mx[u] = m[u][x], s[u].clear();
if (mx[u] == m[u][x]) s[u].insert(x);
};
auto dfs = [&](auto dfs, int u) -> void {
int maxson = -1;
id[u] = cnt++;
for (auto v : e[u]) {
dfs(dfs, v);
if (maxson == -1 || s[id[maxson]].size() < s[id[v]].size()) maxson = v;
}
if (maxson == -1) {
merge(id[u], col[u]), ans[id[u]] = 1;
return;
}
id[u] = id[maxson];
for (auto v : e[u])
if (v != maxson) {
for (auto x : s[id[v]]) merge(id[u], x);
ans[id[u]] += ans[id[v]];
}
ans[id[u]] -= mx[id[u]] - 1;
if (mx[id[u]] > 1) {
mx[id[u]] = 1, m[id[u]].clear();
for (auto x : s[id[u]]) m[id[u]][x] = 1;
}
};
dfs(dfs, 0);
cout << ans[id[0]];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cerr << fixed << setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

D - Math master

解题思路

复杂度

代码参考

Show code

D.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;
using i128 = __int128_t;
void solve(int t_ = 0) {
string strp, strq;
cin >> strp >> strq;
i64 p = stoll(strp), q = stoll(strq);
int n = strp.size();
i64 ans = p;
for (int i = 1; i < (1 << n); ++i) {
string strp1 = "";
for (int j = 0; j < n; ++j)
if ((i >> j) & 1) strp1 += strp[j];
i64 p1 = stoll(strp1);
if (!p1 || p1 >= ans) continue;
int si = ((1 << n) - 1) ^ i;
vector<int> a(10);
for (int j = 0; j < n; ++j)
if ((si >> j) & 1) ++a[strp[j] - '0'];
i128 q1 = i128(p1) * q;
if (q1 % p) continue;
q1 /= p;
stringstream ss;
string strq1;
ss.clear();
ss << i64(q1);
ss >> strq1;
auto revq = strq, revq1 = strq1;
reverse(revq.begin(), revq.end());
reverse(revq1.begin(), revq1.end());
int nowq1 = 0;
bool flag = 0;
for (int j = 0; j < revq.size(); ++j) {
if (nowq1 < revq1.size() && revq[j] == revq1[nowq1]) {
++nowq1;
continue;
}
if (a[revq[j] - '0']) --a[revq[j] - '0'];
else if (nowq1 == revq1.size() && revq[j] == '0') {
} else {
flag = 1;
break;
}
}
for (int j = 0; j < 10; ++j)
if (a[j]) flag = 1;
if (nowq1 != revq1.size()) flag = 1;
if (flag) continue;
ans = min(ans, p1);
}
pair<i64, i64> ans1 = {ans, i64(i128(ans) * q / p)};
cout << ans1.first << ' ' << ans1.second << '\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;
}

E - Power and Modulo

解题思路

复杂度

代码参考

Show code

E.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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
template <class Tp>
using vec = vector<Tp>;
#define for_(i, l, r, v...) for (i64 i = (l), i##e = (r), ##v; i <= i##e; ++i)
void solve(int t_ = 0) {
int n;
cin >> n;
vec<i64> a(n);
for (auto &i : a) cin >> i;
if (a[0] > 1) {
cout << "-1\n";
return;
}
if (a[0] == 0) {
for_(i, 1, n - 1)
if (a[i]) {
cout << "-1\n";
return;
}
cout << "1\n";
return;
}
auto chk = [&](i64 m) -> bool {
if (m < 2) return 0;
for_(i, 1, n - 1)
if (a[i] != a[i - 1] * 2 % m) return 0;
return 1;
};
int idx = -1;
for_(i, 1, n - 1)
if (a[i] != a[i - 1] * 2) {
idx = i;
break;
}
if (idx == -1) {
cout << "-1\n";
return;
}
i64 m = 2 * a[idx - 1] - a[idx];
if (!chk(m) || chk(m * 2) || chk(m / 2)) {
cout << "-1\n";
return;
}
cout << m << '\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;
}

F - Master Spark

解题思路

复杂度

代码参考

Show code

G - Damaged Bicycle

解题思路

复杂度

代码参考

Show code

G.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
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>
using namespace std;
using i64 = int64_t;
template <class Tp>
using vec = vector<Tp>;
template <class Tp>
using vvec = vector<vector<Tp>>;
#define for_(i, l, r, v...) for (i64 i = (l), i##e = (r), ##v; i <= i##e; ++i)
vec<int> dijkstra(vvec<pair<int, int>> const &g, int s) {
vec<int> dis(g.size(), 0x3f3f3f3f);
vec<bool> vis(g.size());
priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>>
q;
q.emplace(dis[s] = 0, s);
while (!q.empty()) {
auto [dis_now, now] = q.top();
q.pop();
if (vis[now]) continue;
vis[now] = 1;
for (auto [to, w] : g[now])
if (dis[now] + w < dis[to]) {
dis[to] = dis[now] + w;
if (!vis[to]) q.emplace(dis[to], to);
}
}
return dis;
}
void solve(int t_ = 0) {
int t, r;
cin >> t >> r;
int n, m;
cin >> n >> m;
vvec<pair<int, int>> g(n + 1);
for_(i, 1, m, u, v, w) {
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
int k;
cin >> k;
vec<int> a(k);
vec<double> p(k);
for_(i, 0, k - 1) cin >> a[i] >> p[i], p[i] /= 100;
auto dis0 = dijkstra(g, 1);
if (dis0[n] == 0x3f3f3f3f) {
cout << "-1\n";
return;
}
vvec<int> dis;
for_(i, 0, k - 1) dis.push_back(dijkstra(g, a[i]));
int state = 1 << k;
vec<vec<double>> ans(state, vec<double>(k, 1e50)),
pi(state, vec<double>(k, 0));
for (int i = 0; i < k; ++i) {
ans[1 << i][i] = 1.0 * dis0[a[i]] / t;
pi[1 << i][i] = 1;
}
double mn = 1. * dis0[n] / t;
for (int sta = 1; sta < state; ++sta) {
for (int i = 0; i < k; ++i) {
if ((sta >> i) & 1) {
for (int j = 0; j < k; ++j) {
if (!((sta >> j) & 1)) {
if (p[i] < 1e-6) {
mn = min(mn,
ans[sta][i] + pi[sta][i] * dis[i][n] *
((1.0 - p[i]) / r + p[i] / t));
} else {
ans[sta | (1 << j)][j] =
min(ans[sta | (1 << j)][j],
ans[sta][i] + pi[sta][i] * (1. - p[i]) * dis[i][n] / r +
pi[sta][i] * p[i] * dis[i][a[j]] / t);
pi[sta | (1 << j)][j] = pi[sta][i] * p[i];
}
}
}
}
}
}
for (int sta = 1; sta < state; ++sta) {
for (int i = 0; i < k; ++i) {
if ((sta >> i) & 1) {
mn = min(mn,
ans[sta][i] +
pi[sta][i] * dis[i][n] * ((1.0 - p[i]) / r + p[i] / t));
}
}
}
cout << fixed << setprecision(8) << mn << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cerr << fixed << setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

H - What logic for?

解题思路

复杂度

代码参考

Show code

I - Power and Zero

解题思路

复杂度

代码参考

Show code

I.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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
void solve(int t_ = 0) {
int n;
cin >> n;
vector<int> a(40);
for (int i = 0; i < n; ++i) {
i64 x;
cin >> x;
for (int j = 0; j < 40; ++j)
if ((x >> j) & 1) a[j] += 1;
}
while (a.back() == 0) a.pop_back();
int ans = 0;
while (a.size()) {
++ans;
int flag = -1;
for (int i = 0; i < a.size(); ++i) {
if (a[i] && flag != -1) a[i] -= 1, a[flag] += 1, flag = -1;
if (a[i]) a[i] -= 1;
else if (flag == -1) flag = i;
}
while (a.size() && a.back() == 0) a.pop_back();
}
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;
}

J - Local Minimum

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
template <class Tp>
using vec = vector<Tp>;
template <class Tp>
using vvec = vector<vector<Tp>>;
#define for_(i, l, r, v...) for (i64 i = (l), i##e = (r), ##v; i <= i##e; ++i)
void solve(int t_ = 0) {
int n, m;
cin >> n >> m;
vvec<int> mat(n, vec<int>(m));
for (auto &i : mat)
for (auto &j : i) cin >> j;
auto mata = mat, matb = mat;
for_(i, 0, n - 1) {
int mina = 0;
for_(j, 1, m - 1)
if (mat[i][j] < mat[i][mina]) mina = j;
for_(j, 0, m - 1) mata[i][j] = mat[i][mina];
}
for_(j, 0, m - 1) {
int minb = 0;
for_(i, 1, n - 1)
if (mat[i][j] < mat[minb][j]) minb = i;
for_(i, 0, n - 1) matb[i][j] = mat[minb][j];
}
int ans = 0;
for_(i, 0, n - 1)
for_(j, 0, m - 1) ans += mat[i][j] == mata[i][j] && mat[i][j] == matb[i][j];
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cerr << fixed << setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

K - Wonder Egg Priority

解题思路

复杂度

代码参考

Show code

L - Karshilov's Matching Problem

解题思路

复杂度

代码参考

Show code


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

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