2023 Jiangsu Collegiate Programming Contest
2023 National Invitational of CCPC (Hunan)
The 13th Xiangtan Collegiate Programming Contest
比赛链接
| Problems |
AC |
| A. Today’s Word |
○ |
| B. Honkai in TAIKULA |
|
| C. GG and YY’s Game |
|
| D. Star Rail |
|
| E. LCM Plus GCD |
⊕ |
| F. Timaeus |
○ |
| G. Moving Boxes |
|
| H. Neil’s Machine |
○ |
| I. Elevator |
○ |
| J. Similarity (Easy Version) |
○ |
| K. Similarity (Hard Version) |
○ |
| L. Architect |
○ |
I 签到
1
2
3
4
| void solve() {
int n = read(), m = read();
cout << n - m + 1 << '\n';
}
|
H 差分
挺好玩的其实，像个 div2 c 题。
区间加相当于差分数组上的 2 点修改。
后缀加相当于差分数组上的 单点修改。
判断差分数组在 mod 26 意义下是否相等即可
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
| void solve() {
int n;
cin >> n;
vector<char> a(n + 1);
vector<char> b(n + 1);
vector<int> da(n + 1);
vector<int> db(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
da[i] = (a[i] - a[i - 1] + 26) % 26;
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
db[i] = (b[i] - b[i - 1] + 26) % 26;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (da[i] != db[i]) {
ans++;
}
}
cout << ans << "\n";
}
|
J 最长公共子串
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
| void solve() {
int n = read();
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int la = s[i].size();
int lb = s[j].size();
vector dp(la + 1, vector<int>(lb + 1));
for (int x = la - 1; x >= 0; x--) {
for (int y = lb - 1; y >= 0; y--) {
if (s[i][x] == s[j][y]) {
dp[x][y] = 1 + dp[x + 1][y + 1];
}
ans = max(ans, dp[x][y]);
}
}
}
}
cout << ans << '\n';
}
|
A 字符串循环移位
和 24 ccpc 网络赛那个题很像，但是做法不太一样。
长度 >= 2m 之后最后 m 个字符就确定了，之后只是会一直循环移位。
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
| void solve() {
int n = read(), m = read();
string s;
cin >> s;
int p = 16;
int len = s.size();
while (len < 2 * m) {
int m = len / 2;
s = s.substr(0, m) + s + s.substr(m);
len *= 2;
for (int i = len - m; i < len; i++) {
s[i] = s[i] == 'z' ? 'a' : s[i] + 1;
}
p = (p + 25) % 26;
}
s = s.substr(len - m);
for (auto &ch : s) {
int t = ch - 'a';
t = (t + p) % 26;
ch = 'a' + t;
}
cout << s;
}
|
K 构造
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
| signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
if(m == 0) {
if(n <= 26) {
cout << "Yes" << endl;
for(int i = 0;i < n;i ++) {
for(int j = 0;j < k;j ++) {
cout << char(i + 'a');
}
cout << endl;
}
}else {
cout << "No" << endl;
}
return 0;
}
if(m < k) {
cout << "Yes" << endl;
char s1 = 'b', s2 = 'c';
for(int i = 0;i < n;i ++) {
for(int j = 0;j < m - 1;j ++) {
cout << "a";
}
for(int j = m - 1;j < k;j ++) {
cout << ((j - m + 1) % 2 == 0 ? s1 : s2);
}
cout << endl;
if (s2 == 'z') {
s1++;
s2 = s1 + 1;
} else {
s2 ++;
}
}
}else {
cout << "No" << endl;
}
return 0;
}
|
F 期望 DP
赛时 wa 了一发，第一眼没看出来。
状态转移的 dag 上面不能有自环。
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
| void solve() {
int A = read(), B = read();
double P = read(), Q = read();
P /= 100, Q /= 100;
std::cout << std::fixed << std::setprecision(15);
if (B == 1) {
double x = A * (P * 2 + (1 - P) * 1);
double y = A * (1.0 / (1 - Q));
cout << max(x, y);
return;
}
vector<double> dp(A + 1);
for (int i = B; i <= A; i++) {
dp[i] = max(
P * (dp[i - B] + 2) + (1 - P) * (dp[i - B] + 1),
Q * (dp[i - B + 1] + 1) + (1 - Q) * (dp[i - B] + 1)
);
}
cout << dp[A] << "\n";
}
|
L
给出 n 个长方体，询问其是否拼接成一个 W × H × L 的立方体，没有重叠和空隙。
把原来大长方体等价代换成WHL个111的小方块，想象一下挖走一块移到另一个地方，会使中空的地方的8个顶点必然有奇数次覆盖，如果移到相邻位置，原来的点还是偶数次，但会造成新的点变成奇数次。所以所有顶点覆盖偶数次是充要条件。
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
| void solve() {
int W = read(), H = read(), L = read();
int n = read();
vector<std::array<int, 6>> a(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < 6; j++) {
a[i][j] = read();
}
}
i128 V = (i128)W * H * L;
for (auto c : a) {
i128 v = (i128)(c[3] - c[0]) * (c[4] - c[1]) * (c[5] - c[2]);
V -= v;
}
if (V) {
puts("No");
return;
}
std::map<std::array<int, 3>, int> f;
a.push_back({0, 0, 0, W, H, L});
for (auto c : a) {
for (int x : {c[0], c[3]}) {
for (int y : {c[1], c[4]}) {
for (int z : {c[2], c[5]}) {
++f[{x, y, z}];
}
}
}
}
for (auto [x, y] : f) {
if (y & 1) {
puts("No");
return;
}
}
puts("Yes");
}
|
E 容斥、数论
输入 $x, k$，求大小为 $k$ 的 distinct 集合个数，其中所有数的 $\gcd + \operatorname{lcm} = x$。
设 $\gcd = G$，$\operatorname{lcm} = A \times G$
那么 $(1 + A) \times G = x$，故我们可以对 $x$ 枚举因子得到 $G$
把集合中每个数除掉 $G$，那么限制就转化为 $gcd = 1$, $lcm = A$
设 $A = \prod_{j = 1}^m{p_j^{b_j}}$, $a_i^{\prime} = \prod_{j = 1}^m{p_j^{c_{ij}}}$
限制转化为 $2m$ 条约束 $\min{c_{ij}} = 0, \max{c_{ij}} = b_j$
假设不考虑约束（也就是 $\min$ 不一定取到 $0$，$\max$ 不一定取 $b_j$），一共有 $B = \prod_{j = 1}^m{(b_j - 0 + 1)}$ 个数，在其中选 $k$ 个就是 $\binom{B}{k}$
考虑上约束，我们可以使用容斥原理：两个约束任意满不满足 - 约束1一定不满足 - 约束2一定不满足 + 约束12都一定不满足
假设约束 1 一定不满足，则 $\min$ 一定不为 $0$，可选的数变为 $B^{\prime} = \prod_{j = 1}^m{(b_j - 1 + 1)}$，在其中选 $k$ 个就是 $\binom{B^{\prime}}{k}$
约束 2 一定不满足也类似。
我们可以枚举 $2m$ 个约束分别有没有满足来进行容斥。
总的时间复杂度为 $O(Fm2^{2m})$
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
| void solve() {
int x = read(), k = read();
Z ans = 0;
auto calc = [&](int G) {
int A = x / G - 1;
if (A == 0) return;
vector<int> p, e;
for (int i = 2; i * i <= A; i++) {
if (A % i != 0) continue;
e.eb(0);
while (A % i == 0) {
A /= i;
e.back()++;
}
p.eb(i);
}
if (A > 1) {
e.eb(1);
p.eb(A);
}
int m = p.size();
for (int s = 0; s < (1 << m); s++) {
for (int t = 0; t < (1 << m); t++) {
int res = 1;
int coef = 1;
for (int i = 0; i < m; i++) {
int v = e[i] + 1;
if (s >> i & 1) {
coef *= -1;
v--;
}
if (t >> i & 1) {
coef *= -1;
v--;
}
res *= v;
}
ans += comb.binom(res, k) * coef;
}
}
};
for (int G = 1; G * G <= x; G++) {
if (x % G != 0) continue;
calc(G);
if (G * G != x) {
calc(x / G);
}
}
cout << ans;
}
|