VP 记录 - 2022 CCPC 绵阳站

比赛链接

进度: 6 / 13

题目概览

题号 1标题 2做法
ABan or Pick, What’s the TrickDP
*BCall Me Call Me线段树套线段树
CCatch You Catch Me签到
*DGambler’s Ruin三分
*EHammer to FallDP, 分块
*FInfinite Strife计算几何
GLet Them Eat Cake签到
HLife is Hard and Undecidable, but...构造
*IMental Abuse To HumansMöbius 反演
JMiddle Race三分
*KPattern Matching in A Minor “Low Space”论文题
*LPor Una Cabeza
MRock-Paper-Scissors Pyramid思维

官方题解

A - Ban or Pick, What’s the Trick

解题思路

复杂度

代码参考

Show code

A.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
#include <bits/stdc++.h>
using ll = long long;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
#define Rep for_
template <class Tp>
Tp dec(Tp &i) {
return --i;
}
template <class Tp>
Tp inc(Tp &i) {
return ++i;
}
using namespace std;
#define int long long
void solve(int t_ = 0) {
const int INF = 1e14;
int n, k;
cin >> n >> k;
vector<int> A(2 * n + 1), B(2 * n + 1);
vector<vector<vector<int>>> Dp(
2 * n + 2, vector<vector<int>>(k + 2, vector<int>(k + 2, -INF)));
Rep(i, 1, n) cin >> A[i];
Rep(i, 1, n) cin >> B[i];
sort(A.begin() + 1, A.end(), greater<int>());
sort(B.begin() + 1, B.end(), greater<int>());
ll Ans = -1e14;
function<int(int, int, int)> DP = [&](int m, int a, int b) -> int {
if (m == 2 * n + 1) return 0;
if (Dp[m][a][b] != -INF) return Dp[m][a][b];
int Ret;
if (m & 1) {
Ret = -INF;
if (a != k && a != n) Ret = DP(m + 1, a + 1, b) + A[(m / 2) - b + a + 1];
Ret = max(Ret, DP(m + 1, a, b));
} else {
Ret = INF;
if (b != k && b != n) Ret = DP(m + 1, a, b + 1) - B[(m / 2) - a + b + 1];
Ret = min(Ret, DP(m + 1, a, b));
}
return Dp[m][a][b] = Ret;
};
cout << DP(1, 0, 0);
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cerr << std::fixed << std::setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

B - Call Me Call Me

解题思路

复杂度

代码参考

Show code

C - Catch You Catch Me

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using ll = long long;
using i64 = ll;
template <class Tp>
using vc = std::vector<Tp>;
template <class Tp>
using vvc = std::vector<std::vector<Tp>>;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
template <class Tp>
Tp dec(Tp &i) {
return --i;
}
template <class Tp>
Tp inc(Tp &i) {
return ++i;
}
using namespace std;
void solve(int t_ = 0) {
int n;
cin >> n;
vvc<int> g(n + 1);
for_(i, 1, n - 1, u, v) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vc<int> dep(n + 1), ndep(n + 1);
function<void(int, int)> dfs = [&](int now, int fa) {
dep[now] = dep[fa] + 1;
ndep[now] = 1;
for (auto &&to : g[now]) {
if (to == fa) continue;
dfs(to, now);
ndep[now] = max(ndep[now], ndep[to] + 1);
}
};
dfs(1, 0);
i64 ans = 0;
for (auto &&i : g[1]) ans += ndep[i];
cout << ans;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cerr << std::fixed << std::setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

D - Gambler’s Ruin

解题思路

复杂度

代码参考

Show code

E - Hammer to Fall

解题思路

复杂度

代码参考

Show code

F - Infinite Strife

解题思路

复杂度

代码参考

Show code

G - Let Them Eat Cake

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using ll = long long;
template <class Tp>
using vc = std::vector<Tp>;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
template <class Tp>
Tp dec(Tp &i) {
return --i;
}
template <class Tp>
Tp inc(Tp &i) {
return ++i;
}
using namespace std;
void solve(int t_ = 0) {
int n;
cin >> n;
vc<int> a(n);
for (auto &i : a) cin >> i;
int ans = 0;
for_(__, 1, 32) {
n = a.size();
if (n <= 1) break;
++ans;
if (n <= 2) break;
vc<bool> vis(n);
vis[0] = a[0] < a[1];
vis[n - 1] = a[n - 1] < a[n - 2];
for_(i, 1, n - 2) vis[i] = a[i] < a[i - 1] || a[i] < a[i + 1];
vc<int> b;
for_(i, 0, n - 1)
if (!vis[i]) b.push_back(a[i]);
a = b;
}
cout << ans << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cerr << std::fixed << std::setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

H - Life is Hard and Undecidable, but...

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
template <class Tp>
Tp dec(Tp &i) {
return --i;
}
template <class Tp>
Tp inc(Tp &i) {
return ++i;
}
using namespace std;
void solve(int t_ = 0) {
int k;
cin >> k;
k = 2 * k - 1;
cout << k << '\n';
int x = 1;
while (k--) {
cout << x << ' ' << x << '\n';
inc(x);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cerr << std::fixed << std::setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

I - Mental Abuse To Humans

解题思路

复杂度

代码参考

Show code

J - Middle Race

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using ll = long long;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
template <class Tp>
Tp dec(Tp &i) {
return --i;
}
template <class Tp>
Tp inc(Tp &i) {
return ++i;
}
using namespace std;
void solve(int t_ = 0) {
int n, a_[3];
cin >> n >> a_[0] >> a_[1] >> a_[2];
sort(a_, a_ + 3);
int a = a_[0], b = a_[1], c = a_[2];
auto print__ = [](int x) {
cout << x << endl;
int _1, _2;
cin >> _1 >> _2;
if (_1 == -1 && _2 == -1) exit(0);
};
auto print = [&](auto... x) { (print__(x), ...); };
auto f = [&](ll x, ll y, ll z) -> ll {
return abs((x * a + y * b + z * c) * 3 - 1ll * n * (a + b + c));
};
auto bi = [&](int x) -> tuple<int, int> {
int l = 0, r = n - x;
int y = 0, z = n - x;
while (r - l >= 5) {
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if (auto z1_ = n - x - m1, z2_ = n - x - m2;
f(x, m1, z1_) < f(x, m2, z2_))
r = m2;
else l = m1;
}
for_(i, l, r)
if (f(x, i, n - x - i) < f(x, y, z)) tie(y, z) = make_tuple(i, n - x - i);
return {y, z};
};
int x = 0, y = 0, z = n;
for_(x_, 0, n)
if (auto [y_, z_] = bi(x_); f(x_, y_, z_) < f(x, y, z))
tie(x, y, z) = make_tuple(x_, y_, z_);
for_(i, 1, x) print(a);
for_(i, 1, y) print(b);
for_(i, 1, z) print(c);
}
int main() {
std::ios::sync_with_stdio(false);
std::cerr << std::fixed << std::setprecision(6);
int i_ = 0;
int t_ = 0;
std::cin >> t_;
for (i_ = 0; i_ < t_; ++i_) solve(i_);
return 0;
}

K - Pattern Matching in A Minor “Low Space”

解题思路

复杂度

代码参考

Show code

L - Por Una Cabeza

解题思路

复杂度

代码参考

Show code

M - Rock-Paper-Scissors Pyramid

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using ll = long long;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
#define Rep for_
template <class Tp>
Tp dec(Tp &i) {
return --i;
}
template <class Tp>
Tp inc(Tp &i) {
return ++i;
}
using namespace std;
map<pair<char, char>, int> Map;
void solve(int t_ = 0) {
string S;
cin >> S;
vector<int> A(S.size());
int Max = 0, Ans = 0;
Rep(i, 1, S.size() - 1) {
A[i] = A[i - 1] + Map[{S[i], S[i - 1]}];
if (A[i] > Max) Max = A[i], Ans = i;
}
cout << S[Ans] << '\n';
}
int main() {
Map[{'S', 'P'}] = 1;
Map[{'S', 'R'}] = -1;
Map[{'S', 'S'}] = 0;
Map[{'P', 'S'}] = -1;
Map[{'P', 'R'}] = 1;
Map[{'P', 'P'}] = 0;
Map[{'R', 'S'}] = 1;
Map[{'R', 'R'}] = 0;
Map[{'R', 'P'}] = -1;
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cerr << std::fixed << std::setprecision(6);
int i_ = 0;
int t_ = 0;
std::cin >> t_;
for (i_ = 0; i_ < t_; ++i_) solve(i_);
return 0;
}

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

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