VP 记录 - 2022 CCPC 威海站

比赛链接

进度: 7 / 13

怎么一堆福瑞啊 🤔

难度相对较低的一场,官方题解很详细,孩子很喜欢

题目概览

题号 1 标题 做法
A Dunai 签到
*B Recruitment BFS
C Grass 计算几何
D Sternhalma 状压 DP
E Python Will be Faster than C++ 签到
*F Mooncake Delivery 最短路
G Grade 2 签到 (找规律) / Möbius 反演
*H Party Animals 平衡树
I Dragon Bloodline 贪心,二分
J Eat, Sleep, Repeat 贪心
*K I Wanna Maker
*L Novice Magician 构造
*M String Master

官方题解

Sildes

视频

link

A - Dunai

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using namespace std;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
map<string, int> M;
cin >> T;
int tot = 0;
for (int i = 1; i <= T; ++i)
for (int j = 1; j <= 5; ++j) {
string S;
cin >> S;
M[S] = 1;
}
int m;
cin >> m;
vector<int> cnt(6);
for (int i = 1; i <= m; ++i) {
string S;
int opt;
cin >> S >> opt;
tot += M[S];
++cnt[opt];
}
int Min = cnt[1];
for (int i = 2; i <= 5; ++i) { Min = min(Min, cnt[i]); }
cout << min(Min, tot);
return 0;
}

B - Recruitment

解题思路

复杂度

代码参考

Show code

C - Grass

解题思路

复杂度

代码参考

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
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 ll = long long;
using pii = std::pair<int, int>;
using namespace std;
constexpr bool in_same_line(pii const &u, pii const &v, pii const &w) {
ll x1 = v.first - u.first, y1 = v.second - u.second;
ll x2 = w.first - u.first, y2 = w.second - u.second;
return (x1 * y2 - x2 * y1) == 0;
}
bool in_same_dir(pii const &u, pii const &v, pii const &w) {
ll x1 = v.first - u.first, y1 = v.second - u.second;
ll x2 = w.first - u.first, y2 = w.second - u.second;
return in_same_line(u, v, w) && ((x1 * x2 + y1 * y2) > 0);
}
void print__(
pii const &c, pii const &p1, pii const &p2, pii const &p3, pii const &p4) {
cout << "YES\n";
cout << c.first << ' ' << c.second << '\n';
cout << p1.first << ' ' << p1.second << '\n';
cout << p2.first << ' ' << p2.second << '\n';
cout << p3.first << ' ' << p3.second << '\n';
cout << p4.first << ' ' << p4.second << '\n';
}
void print(
pii const &p0, pii const &p1, pii const &p2, pii const &p3, pii const &p4) {
auto cond = [](pii const &x,
pii const &p1,
pii const &p2,
pii const &p3,
pii const &p4) {
return !(in_same_dir(x, p1, p2) || in_same_dir(x, p1, p3) ||
in_same_dir(x, p1, p4) || in_same_dir(x, p2, p3) ||
in_same_dir(x, p2, p4) || in_same_dir(x, p3, p4));
};
if (cond(p0, p1, p2, p3, p4)) {
print__(p0, p1, p2, p3, p4);
return;
}
if (cond(p1, p0, p2, p3, p4)) {
print__(p1, p0, p2, p3, p4);
return;
}
if (cond(p2, p0, p1, p3, p4)) {
print__(p2, p0, p1, p3, p4);
return;
}
if (cond(p3, p0, p1, p2, p4)) {
print__(p3, p0, p1, p2, p4);
return;
}
if (cond(p4, p0, p1, p2, p3)) {
print__(p4, p0, p1, p2, p3);
return;
}
}
void solve(int t_ = 0) {
int n;
cin >> n;
vector<pii> v(n);
for (auto &i : v) cin >> i.first >> i.second;
if (n < 5) {
cout << "NO\n";
return;
}
pii p0 = v[0], p1 = v[1], p2 = v[2], p3 = v[3], p4;
for (int i = 4; i < n; ++i) {
p4 = v[i];
if (!(in_same_line(p0, p1, p2) && in_same_line(p0, p1, p3) &&
in_same_line(p0, p1, p4))) {
print(p0, p1, p2, p3, p4);
return;
}
}
cout << "NO\n";
}
int main() {
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;
}

D - Sternhalma

解题思路

复杂度

代码参考

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using ll = long long;
#define int long long
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; ++i)
using namespace std;
const int GO[19][6] = {{1, 3, 4, -1, -1, -1},
{4, 5, -1, -1, -1, -1},
{1, 5, 6, -1, -1, -1},
{4, 8, -1, -1, -1, -1},
{5, 8, 9, -1, -1, -1},
{4, 9, 10, -1, -1, -1},
{5, 10, -1, -1, -1, -1},
{3, 8, 12, -1, -1, -1},
{4, 9, 13, -1, -1, -1},
{4, 5, 8, 10, 13, 14},
{5, 9, 14, -1, -1, -1},
{6, 10, 15, -1, -1, -1},
{8, 13, -1, -1, -1, -1},
{8, 9, 14, -1, -1, -1},
{9, 10, 13, -1, -1, -1},
{10, 14, -1, -1, -1, -1},
{12, 13, 17, -1, -1, -1},
{13, 14, -1, -1, -1, -1},
{14, 15, 17, -1, -1, -1}};
const int GO2[19][6] = {{2, 7, 9, -1, -1, -1},
{8, 10, -1, -1, -1, -1},
{0, 9, 11, -1, -1, -1},
{5, 13, -1, -1, -1, -1},
{6, 12, 14, -1, -1, -1},
{3, 13, 15, -1, -1, -1},
{4, 14, -1, -1, -1, -1},
{0, 9, 16, -1, -1, -1},
{1, 10, 17, -1, -1, -1},
{0, 2, 7, 11, 16, 18},
{1, 8, 17, -1, -1, -1},
{2, 9, 18, -1, -1, -1},
{4, 14, -1, -1, -1, -1},
{3, 5, 15, -1, -1, -1},
{4, 6, 12, -1, -1, -1},
{5, 13, -1, -1, -1, -1},
{7, 9, 18, -1, -1, -1},
{8, 10, -1, -1, -1, -1},
{9, 11, 16, -1, -1, -1}};
const int N = (1 << 20) + 7;
const ll MIN = -1000000010ll;
ll Dp[N], n;
vector<int> E, A;
ll DP(int State) {
if (Dp[State] != MIN) return Dp[State];
Rep(i, 0, n - 1)
if ((State >> i) & 1) {
int to = State ^ (1 << i);
Dp[State] = max(Dp[State], DP(to));
Rep(j, 0, 5)
if (~GO[i][j] && ((State >> GO[i][j]) & 1) &&
((State >> GO2[i][j]) & 1) == 0) {
to = State ^ (1 << GO[i][j]) ^ (1 << GO2[i][j]) ^ (1 << i);
Dp[State] = max(Dp[State], DP(to) + E[GO[i][j]]);
}
}
return Dp[State];
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
n = 19;
E.resize(n, 0);
A.resize(n, 0);
Rep(i, 0, n - 1) cin >> E[i];
int T;
cin >> T;
Rep(i, 0, (1 << 20) - 1) Dp[i] = MIN;
Dp[0] = 0;
while (T--) {
int State = 0;
Rep(i, 0, n - 1) {
char C;
cin >> C;
State |= (C == '#' ? 1 : 0) * (1 << i);
}
cout << DP(State) << '\n';
}
return 0;
}

E - Python Will be Faster than C++

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using i64 = int64_t;
using namespace std;
void solve(int t_ = 0) {
int n;
cin >> n;
i64 t;
cin >> t;
i64 x, y;
for (int i = 1; i <= n - 2; ++i) cin >> x;
cin >> x >> y;
if (x <= y) {
cout << "Python will never be faster than C++\n";
return;
}
i64 k = x - y;
cout << "Python 3." << n + (y - t + k) / k << " will be faster than C++\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;
}

F - Mooncake Delivery

解题思路

复杂度

代码参考

Show code

G - Grade 2

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using ll = long long;
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; ++i)
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int x, T;
cin >> x >> T;
int lim = 1 << (32 - __builtin_clz(x));
vector<ll> f(lim + 1);
Rep(i, 1, lim) f[i] = (gcd(((ll)i * x) ^ x, x) == 1);
Rep(i, 2, lim) f[i] += f[i - 1];
while (T--) {
ll l, r;
cin >> l >> r;
if (x % 2 == 0) {
cout << "0\n";
continue;
} else {
auto get = [&](ll y) -> ll {
ll shang = y / lim, yu = y % lim;
return shang * f[lim] + f[yu];
};
cout << get(r) - get(l - 1) << '\n';
}
}
return 0;
}

H - Party Animals

解题思路

复杂度

代码参考

Show code

I - Dragon Bloodline

解题思路

复杂度

代码参考

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define dec(i) (--(i))
#define int long long
using namespace std;
#define WW(i) (1 << (i))
void Solve() {
int n, k;
int Sum = 0, tot = 0;
cin >> n >> k;
vector<int> A(n), B(k);
for (int i = 0; i < n; ++i) cin >> A[i], tot += A[i];
for (int i = 0; i < k; ++i) cin >> B[i], Sum += B[i] * WW(i);
int l = 0, r = Sum / tot, Mid, Ans = 0;
while (r >= l) {
int Mid = (r + l) >> 1;
auto Pd = [&](int x) -> bool {
vector<int> C(n), D(k);
priority_queue<int> Q;
for (int i = 0; i < n; ++i) Q.push(A[i] * x);
D = B;
for (int i = k - 1; ~i; --i) {
while (!Q.empty() && D[i] && WW(i) >= Q.top()) {
Q.pop();
dec(D[i]);
}
while (!Q.empty() && D[i] && WW(i) < Q.top()) {
int t = Q.top(), tt = t / WW(i), ttt = min(tt, D[i]);
Q.pop();
t -= ttt * WW(i), D[i] -= ttt;
if (t) Q.push(t);
}
while (!Q.empty() && D[i] && WW(i) >= Q.top()) {
Q.pop();
dec(D[i]);
}
}
if (Q.size()) return 0;
return 1;
};
if (Pd(Mid)) Ans = Mid, l = Mid + 1;
else r = Mid - 1;
}
cout << Ans << '\n';
;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
cin >> T;
while (T--) { Solve(); }
return 0;
}

J - Eat, Sleep, Repeat

解题思路

复杂度

代码参考

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
62
63
64
#include <bits/stdc++.h>
using ll = long long;
using pii = std::pair<int, int>;
using namespace std;
const int N = 100010;
int a[N];
void solve(int t_ = 0) {
int n, k;
cin >> n >> k;
ll ss = 0;
for (int i = 1; i <= n; ++i) cin >> a[i], ss += a[i];
vector<pii> cons;
priority_queue<int, vector<int>, greater<int>> lim;
for (int i = 1; i <= k; ++i) {
int x, y;
cin >> x >> y;
if (y == 0) lim.push(x);
else cons.emplace_back(x, y);
}
lim.push(1e9);
a[n + 1] = 1e9 + 1;
sort(a + 1, a + n + 2);
sort(cons.begin(), cons.end());
int now = 0, cnt = 0;
ll sum = 0;
while (!lim.empty() && lim.top() == now) ++now, lim.pop();
auto it = cons.begin();
while (!lim.empty()) {
int nxt = upper_bound(a + 1, a + n + 2, lim.top()) - a;
int count1 = nxt - (lower_bound(a + 1, a + n + 2, now) - a);
while (count1 && it != cons.end() && it->first < lim.top() &&
it->first == now) {
sum += min(count1, it->second) * it->first;
count1 -= min(count1, it->second);
++now;
++it;
}
sum += count1 * now;
while (it != cons.end() && it->first < lim.top()) { ++it; }
now = lim.top();
while (!lim.empty() && lim.top() == now) ++now, lim.pop();
}
int count1 = n + 1 - (lower_bound(a + 1, a + n + 2, now) - a);
while (count1 && it != cons.end() && it->first < lim.top() &&
it->first == now) {
sum += min(count1, it->second) * it->first;
count1 -= min(count1, it->second);
++now;
++it;
}
sum += now * count1;
if ((ss - sum) & 1) cout << "Pico\n";
else cout << "FuuFuu\n";
}
int main() {
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;
}

K - I Wanna Maker

解题思路

复杂度

代码参考

Show code

L - Novice Magician

解题思路

复杂度

代码参考

Show code

M - String Master

解题思路

复杂度

代码参考

Show code


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