VP 记录 - 2021 CCPC 威海站

比赛链接

进度: 5 / 13

题目概览

题号 1标题 2做法
AGoodbye, Ziyin!签到
*BSubsetDP, 卷积
*CAssign or Multiply原根,bitset, 二分,树状数组
DPeriod二分,KMP
*ECHASE!DP, 双指针
*FStone博弈论
GDesserts数学
*HCity Safety最小割
*IDistance整除分块,min25 筛
JCircular Billiard Table签到
*KTiny Stars构造
*LShake Hands贪心 + 最大匹配
M810975容斥

官方题解

A - Goodbye, Ziyin!

解题思路

复杂度

代码参考

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
#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> deg(n + 1);
for_(i, 1, n - 1, u, v) {
cin >> u >> v;
++deg[u];
++deg[v];
}
if (any_of(deg.begin() + 1, deg.end(), [](int x) { return x > 3; })) {
cout << "0\n";
return;
}
int cnt = count_if(deg.begin() + 1, deg.end(), [](int x) { return x <= 2; });
cout << cnt << '\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;
}

B - Subset

解题思路

复杂度

代码参考

Show code

C - Assign or Multiply

解题思路

复杂度

代码参考

Show code

D - Period

解题思路

复杂度

代码参考

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
#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;
namespace KMP {
const int N = 1e6 + 5;
int nxt[N];
void kmp(string const &a) {
int n = a.size();
int i, j;
for (nxt[0] = j = -1, i = 1; i < n; nxt[i++] = j) {
while (~j && a[j + 1] != a[i]) j = nxt[j];
if (a[j + 1] == a[i]) ++j;
}
}
} // namespace KMP
using KMP::kmp, KMP::nxt;
void solve(int t_ = 0) {
string s;
cin >> s;
int len = s.size();
kmp(s);
vector<int> ans(len);
int j = len - 1;
while (~nxt[j]) {
ans[nxt[j]]++;
j = nxt[j];
}
Rep(i, 1, len - 1) ans[i] += ans[i - 1];
cin >> t_;
while (t_--) {
int x;
cin >> x;
int tem = min(x - 1, (int)len - x);
cout << (tem <= 0 ? 0 : ans[tem - 1]) << '\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;
}

E - CHASE!

解题思路

复杂度

代码参考

Show code

F - Stone

解题思路

复杂度

代码参考

Show code

G - Desserts

解题思路

复杂度

代码参考

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
#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 rfor_(i, r, l, v...) for (ll i = (r), i##e = (l), ##v; i >= i##e; --i)
#define Rep for_
#define rep rfor_
template <class Tp>
Tp dec(Tp &i) {
return --i;
}
template <class Tp>
Tp inc(Tp &i) {
return ++i;
}
using namespace std;
const int MOD = 998244353;
void solve(int t_ = 0) {
map<int, int> Map;
int n, m;
cin >> n >> m;
vector<int> a(n + 1), tong(n + 1), b(n + 1);
int cnt = 0;
vector<int> fac(n + 1), inv(n + 1);
auto KSM = [&](int x, int p) -> int {
int ret = 1;
while (p) {
if (p & 1) ret = 1ll * ret * x % MOD;
x = 1ll * x * x % MOD, p >>= 1;
}
return ret;
};
fac[0] = 1;
Rep(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % MOD;
inv[n] = KSM(fac[n], MOD - 2);
rep(i, n - 1, 0) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
auto C = [&](int n, int m) -> int {
return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
};
Rep(i, 1, n) {
cin >> a[i];
if (!Map[a[i]]) Map[a[i]] = inc(cnt), b[cnt] = a[i];
inc(tong[Map[a[i]]]);
}
int MAX = 0;
Rep(i, 1, n) MAX = max(MAX, a[i]);
int Ans = 0;
Rep(k, 1, m) {
if (k == MAX) {
Ans = 1;
Rep(i, 1, n) Ans = 1ll * Ans * C(k, a[i]) % MOD;
}
if (k > MAX) {
int ret = KSM(k, n);
Rep(i, 1, cnt) {
ret = 1ll * ret *
KSM(k - b[i], (1ll * (MOD - 2) * tong[i]) % (MOD - 1)) % MOD;
}
Ans = 1ll * Ans * ret % 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;
solve(i_);
return 0;
}

H - City Safety

解题思路

复杂度

代码参考

Show code

I - Distance

解题思路

复杂度

代码参考

Show code

J - Circular Billiard Table

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using ll = long long;
using i64 = ll;
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) {
i64 a, b;
cin >> a >> b;
cout << (b * 180) / gcd(a, b * 180) - 1 << '\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;
}

K - Tiny Stars

解题思路

复杂度

代码参考

Show code

L - Shake Hands

解题思路

复杂度

代码参考

Show code

M - 810975

解题思路

复杂度

代码参考

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
#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 rfor_(i, r, l, v...) for (ll i = (r), i##e = (l), ##v; i >= i##e; --i)
#define Rep for_
#define rep rfor_
template <class Tp>
Tp dec(Tp &i) {
return --i;
}
template <class Tp>
Tp inc(Tp &i) {
return ++i;
}
using namespace std;
const int MOD = 998244353;
#define int long long
void solve(int t_ = 0) {
int n, m, k;
cin >> n >> m >> k;
if (k == 0) return (void)(cout << (m == 0 ? 1 : 0));
vector<int> fac(n + 1), inv(n + 1);
auto KSM = [&](int x, int p) -> int {
int ret = 1;
while (p) {
if (p & 1) ret = ret * x % MOD;
x = x * x % MOD, p >>= 1;
}
return ret;
};
fac[0] = 1;
Rep(i, 1, n) fac[i] = fac[i - 1] * i % MOD;
inv[n] = KSM(fac[n], MOD - 2);
rep(i, n - 1, 0) inv[i] = inv[i + 1] * (i + 1) % MOD;
auto C = [&](int n, int m) -> int {
return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
};
auto f = [&](int i, int k) -> int {
return C(n - i * (k + 1), n - m) * C(n - m + 1, i) % MOD;
};
auto g = [&](int k) -> int {
int ans = 0;
Rep(i, 0, n) {
if (i > n - m + 1 || n - i * (k + 1) < n - m) break;
(ans += (i & 1 ? -1 : 1) * f(i, k)) %= MOD;
}
return ans;
};
cout << ((g(k) - g(k - 1) % MOD) + MOD) % MOD;
}
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. 带超链接的是找到了原题或原型↩︎