VP 记录 - 2023 CCPC 桂林站

比赛链接

进度: 7 / 13

题目概览

题号 1标题 2做法
*AEasy Diameter Problem
BThe Game
CMaster of Both IV
*DSubway
*EPrefix Mahjong
*FRedundant Towers
GHard Brackets Problem
HSweet Sugar
IBarkley II
*JThe Phantom Menace
KRandias Permutation Task
*LAlea Iacta Est
MFlipping Cards

官方题解

A - Easy Diameter Problem

解题思路

复杂度

代码参考

Show code

B - The Game

解题思路

复杂度

代码参考

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
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>
template <typename... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
((++x), ...);
}
using namespace std;
#define int long long
void solve(int t_ = 0) {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
multiset<int> s1, s2;
int flag = 0, X = 0;
for (int i = 0; i < m; ++i) {
if (a[i + n - m] > b[i]) {
flag = 1;
break;
}
X += b[i] - a[i + n - m];
}
for (int i = 0; i < n; ++i) {
if (i < n - m) s1.insert(a[i]);
else s2.insert(a[i]);
}
if (X > n - m) flag = 1;
if (flag == 1) {
cout << "-1\n";
return;
}
vector<int> ans;
while (n - m > X) {
auto it = s1.begin();
auto mn = *it;
s1.erase(it);
ans.push_back(mn);
mn += 1;
s1.insert(mn);
if (*s1.rbegin() > *s2.begin()) {
int aa = *s1.rbegin(), bb = *s2.begin();
s1.erase(prev(s1.end()));
s2.erase(s2.begin());
s1.insert(bb);
s2.insert(aa);
X -= aa - bb;
if (*s2.begin() > b[0] || X < 0) {
flag = 1;
break;
}
}
s1.erase(s1.begin()), --n;
}
if (n - m != X) {
cout << "-1\n";
return;
} else {
int i = 0;
while (s2.size()) {
auto t = *s2.begin();
s2.erase(s2.begin());
while (t < b[i]) ans.push_back(t), ++t;
++i;
}
cout << ans.size() << '\n';
for (auto x : ans) cout << x << ' ';
cout << '\n';
}
}
signed 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;
}

C - Master of Both IV

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
template <class T>
using vec = std::vector<T>;
#define for_(i, l, r, v...) for (i64 i = (l), i##e = (r), ##v; i <= i##e; ++i)
template <typename... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
((++x), ...);
}
using namespace std;
struct basis {
vec<bitset<32>> base;
basis(u32 n = 21): base(n) {}
u32 rank() const {
u32 ans = 0;
for (u32 i = 0; i < base.size(); ++i) ans += base[i][i];
return ans;
}
bool ins(u32 x_) {
bitset<32> x = x_;
bool ok = 0;
for (u32 i = base.size() - 1; ~i; --i) {
if (!x[i]) continue;
if (base[i][i]) x ^= base[i];
else {
for (u32 j = 0; j < i; ++j)
if (x[j]) x ^= base[j];
for (u32 j = i + 1; j < base.size(); ++j)
if (base[j][i]) base[j] ^= x;
base[i] = x;
ok = 1;
break;
}
}
return ok;
}
};
constexpr u32 MOD = 998244353;
u64 qpow(u64 a, u64 b) {
u64 res = 1;
for (; b; b >>= 1, a = a * a % MOD)
if (b & 1) res = res * a % MOD;
return res;
}
void solve(int t_ = 0) {
u32 n;
cin >> n;
vec<u32> a(n);
for (u32 &i : a) cin >> i;
vec<basis> vbs(n + 1);
vec<u32> cnt(n + 1), scnt(n + 1);
for (u32 i : a) ++cnt[i];
for_(i, 1, n)
if (cnt[i])
for (u32 j = 0; i * j <= n; ++j) {
scnt[i * j] += cnt[i];
vbs[i * j].ins(i);
}
i64 ans = qpow(2, n - vbs[0].rank()) - 1;
for_(i, 1, n)
if (cnt[i]) { (ans += qpow(2, scnt[i] - vbs[i].rank())) %= MOD; }
cout << ans << '\n';
}
signed 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 - Subway

解题思路

复杂度

代码参考

Show code

E - Prefix Mahjong

解题思路

复杂度

代码参考

Show code

F - Redundant Towers

解题思路

复杂度

代码参考

Show code

G - Hard Brackets Problem

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
template <typename... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
((++x), ...);
}
using namespace std;
void solve(int t_ = 0) {
string str, ans = "";
cin >> str;
string str1 = str;
reverse(str.begin(), str.end());
int cntl = 0, cntr = 0;
for (auto i : str) {
if (i == '(') ++cntl;
else ++cntr;
if (cntl > cntr) {
cout << "impossible\n";
return;
}
}
cout << str1 << "\n";
}
signed 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;
}

H - Sweet Sugar

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
template <typename... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
((++x), ...);
}
using namespace std;
void solve(int t_ = 0) {
int n, k;
cin >> n >> k;
vector<int> c(n);
for (auto &x : c) cin >> x;
vector<vector<int>> dp(n, vector<int>(2));
int ans = 0;
vector<vector<int>> e(n);
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
--u, --v;
e[u].push_back(v), e[v].push_back(u);
}
auto dfs = [&](auto dfs, int u, int fa) -> void {
dp[u][c[u] & 1] = c[u];
for (auto v : e[u])
if (v != fa) {
dfs(dfs, v, u);
if (dp[v][k & 1] == -1) continue;
auto f0 = dp[u][0], f1 = dp[u][1];
if (f0 && dp[v][0]) dp[u][0] = max(dp[u][0], f0 + dp[v][0]);
if (f1 && dp[v][1]) dp[u][0] = max(dp[u][0], f1 + dp[v][1]);
if (f0 && dp[v][1]) dp[u][1] = max(dp[u][1], f0 + dp[v][1]);
if (f1 && dp[v][0]) dp[u][1] = max(dp[u][1], f1 + dp[v][0]);
}
if (dp[u][k & 1] >= k) dp[u][k & 1] = -1, ++ans;
};
dfs(dfs, 0, -1);
cout << ans << '\n';
}
signed 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;
}

I - Barkley II

解题思路

复杂度

代码参考

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using u32 = uint32_t;
template <class T>
using vec = std::vector<T>;
template <typename... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
((++x), ...);
}
using namespace std;
template <class T>
struct fenwick {
static constexpr u32 lowbit(u32 n) { return n & (-n); }
vec<T> a;
fenwick(u32 n): a(n + 1) {}
void add(u32 pos, T const &x) {
if (!pos) return;
for (; pos < a.size(); pos += lowbit(pos)) a[pos] += x;
}
T sum(u32 pos) {
T ans = 0;
for (; pos; pos -= lowbit(pos)) ans += a[pos];
return ans;
}
};
vector<int> lst(5e5 + 1, 0);
void solve(int t_ = 0) {
int n, m;
cin >> n >> m;
int ans = -1, mn = m;
vector<int> a(n + 1);
fenwick<int> Tree(n);
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
mn = min(mn, x);
a[i] = x;
if (x != 1) ans = max(ans, 0);
if (lst[x] + 1 <= i - 1) {
ans = max(ans, Tree.sum(i - 1) - Tree.sum(lst[x]) - x);
}
if (lst[x]) Tree.add(lst[x], -1);
lst[x] = i;
Tree.add(i, 1);
}
int mex = min(n, m) + 1;
for (int i = 1; i <= min(n, m); ++i)
if (!lst[i]) {
mex = i;
break;
}
for (int i = 1; i <= n; ++i)
if (lst[a[i]] + 1 <= n) {
ans = max(ans, Tree.sum(n) - Tree.sum(lst[a[i]]) - a[i]);
}
for (int i = 1; i <= n; ++i) { lst[a[i]] = 0; }
ans = max(ans, Tree.sum(n) - mex);
cout << ans << "\n";
}
signed 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;
}

J - The Phantom Menace

解题思路

复杂度

代码参考

Show code

K - Randias Permutation Task

解题思路

复杂度

代码参考

Show code

K.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
#include <bits/stdc++.h>
template <class T>
using vec = std::vector<T>;
template <typename... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
((++x), ...);
}
using namespace std;
void solve(int t_ = 0) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(m + 1);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int x;
cin >> x;
--x;
a[i].push_back(x);
}
}
auto op = [](vector<int> a, vector<int> b) {
vec<int> c(a.size());
for (int i = 0; i < a.size(); ++i) c[i] = a[b[i]];
return c;
};
if (m <= 20) {
int state = (1 << m) - 1;
map<vector<int>, int> ans;
for (int sta = 1; sta <= state; ++sta) {
vector<vector<int>> now;
for (int i = 0; i < m; ++i)
if ((sta >> i) & 1) { now.push_back(a[i]); }
vector<int> c = now[0];
for (int i = 1; i < now.size(); ++i) { c = op(c, now[i]); }
ans[c] = 1;
}
cout << ans.size();
} else {
map<vector<int>, int> ans;
for (int i = 0; i < m; ++i) {
auto ans1 = ans;
for (auto [x, y] : ans) { ans1[op(x, a[i])] = 1; }
ans = ans1;
ans[a[i]] = 1;
}
cout << ans.size();
}
}
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;
}

L - Alea Iacta Est

解题思路

复杂度

代码参考

Show code

M - Flipping Cards

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using i64 = int64_t;
template <class T>
using vec = std::vector<T>;
#define for_(i, l, r, v...) for (i64 i = (l), i##e = (r), ##v; i <= i##e; ++i)
template <typename... Ts>
void dec(Ts &...x) {
((--x), ...);
}
template <typename... Ts>
void inc(Ts &...x) {
((++x), ...);
}
using namespace std;
void solve(int t_ = 0) {
int n;
cin >> n;
int len = n / 2;
vec<int> a(n), b(n);
for_(i, 0, n - 1) cin >> a[i] >> b[i];
auto chk = [&](int k) -> bool {
int sx = 0;
vec<int> diff(n);
for_(i, 0, n - 1) sx += (a[i] >= k);
for_(i, 0, n - 1) diff[i] = (b[i] >= k) - (a[i] >= k);
int len1 = 0;
{
int cnt = 0;
for_(i, 0, n - 1) {
len1 = max(len1, cnt += diff[i]);
if (cnt < 0) cnt = 0;
}
}
return (sx + len1 >= len + 1);
};
int l = 2e9, r = 0;
for (int i : a) l = min(l, i), r = max(r, i);
for (int i : b) l = min(l, i), r = max(r, i);
int ans = l;
while (l <= r) {
int mid = l + (r - l) / 2;
if (chk(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);
std::cerr << std::fixed << std::setprecision(6);
int i_ = 0;
solve(i_);
return 0;
}

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

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