2025 CCPC 网络赛

第十一届中国大学生程序设计竞赛网络预选赛(CCPC Online 2025)
Date 2025/09/20
Solved(Upsolved) 9/13

A B C D E F G H I J K L M
O Ø Ø Ø O Ø O Ø O

B - 魔塔

对怪物 $i$,它会被攻击 $\lceil h_i/(X-d_i)\rceil$ 次,因此会反击
$$
v_i = \left\lfloor \frac{h_i-1}{X-d_i}\right\rfloor
$$
次。

设 $Y$ 为遇到怪物时的防御力,怪物对勇士生命的净变化为

$$
\Delta_i = v_i\cdot (Y - a_i)
$$

目标是从根出发遍历所有点,最大化

$$
\sum_{i=2}^{n} \Delta_i
$$

$$
\sum_{i=2}^{n} \Delta_i
= \sum_{\text{怪}} v_i Y - \sum_{\text{怪}} v_i a_i
$$

后一项和顺序无关,因此就是最大化 $\sum_{\text{怪}} v_i Y$

问题转化为:有两种物品 怪物和蓝宝石,遇到蓝宝石让 $Y \leftarrow Y + 1$,遇到怪物产生 $v_i Y$ 的贡献,安排顺序最大化贡献。

贪心让蓝宝石在前面,怪物在后面,且 $v_i$ 越大越后面

具体来说,放在 dfs 上面,$u$ 可以安排子树的合并顺序。

首先可以启发式合并,然后维护一个单调队列来维护合并

在维护 $u$ 的合并的时候,如果 $v_i < v_u$ 的话,都是可以确定在 $u$ 之前合并的,其他的可以放着等后面的来确定

因为用了 multiset::merge 复杂度只有一只 log

时间复杂度 $O(n \log n)$

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
struct Frac {
int num;
int den;
};
bool operator<(const Frac &a, const Frac &b) {
return a.num * b.den < b.num * a.den;
}
Frac &operator+=(Frac &a, const Frac &b) {
a.num += b.num;
a.den += b.den;
return a;
}

void solve() {
int n = read(), X = read();

vector<vector<int>> g(n + 1);
for (int i = 1; i < n; i++) {
int u = read(), v = read();
g[u].eb(v), g[v].eb(u);
}

int ans = 0;
vector<int> v(n + 1);
vector<multiset<Frac>> s(n + 1);

int sum = 0;
for (int i = 2; i <= n; i++) {
int t = read();
if (t == 1) {
v[i] = -1;
} else {
int a = read(), d = read(), h = read();
v[i] = (h - 1) / (X - d);
ans -= v[i] * a;
}
}

int tot = 0;

auto dfs = [&](this auto&& dfs, int u, int fa) -> void {
for (auto v : g[u]) {
if (v == fa) continue;

dfs(v, u);
if (s[u].size() < s[v].size()) {
swap(s[u], s[v]);
}

s[u].merge(s[v]);
s[v].clear();
}

if (v[u] == -1) {
s[u].ep(0, 1);
} else if (s[u].empty()) {
tot += v[u];
} else {
Frac f {v[u], 0};
do {
auto g = s[u].extract(s[u].begin()).value();

ans += f.den * g.num;
f += g;
} while (!s[u].empty() and *s[u].begin() < f);
s[u].ep(f);
}
};
dfs(1, 0);

int now = 0;
for (auto [num, den] : s[1]) {
ans += now * num;
now += den;
}
ans += tot * now;

cout << ans << '\n';
}

H - 教师

类似 SOSdp 的思想,直接钦定某个老师给某个课程,状态就是每个课程有没有被钦定

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
void solve() {
int n = read(), m = read();
int k = read(), T = read();

vector v(n, vector(k + 1, 0ll));
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
v[i][j] = read();
}
}

vector t(m, 0ll);
vector val(m, vector(n, 0ll));

for (int i = 0; i < m; i++) {
int k = read();
t[i] = read();

for (int j = 0; j < k; j++) {
int x = read() - 1, y = read();
val[i][x] = y;
}
}

int maxS = 1 << n;
vector dp(T + 1, vector(maxS, -inf));
dp[0][0] = 0;


vector ans(T + 1, 0ll);
for (int i = 0; i < m; i++) {
for (int p = 0; p + t[i] <= T; p++) {

auto ndp = dp[p];
int np = p + t[i];

for (int s = 0; s < maxS; s++) {
for (int j = 0; j < n; j++) {
if ((s >> j) & 1) continue;

int ns = s | (1 << j);
ndp[ns] = max(ndp[ns], ndp[s] + v[j][val[i][j]]);
}
}

for (int s = 0; s < maxS; s++) {
dp[np][s] = max(dp[np][s], ndp[s]);
}
ans[np] = max(ans[np], dp[np][maxS - 1]);
}
}

for (int i = 0; i < n; i++) ans[0] += v[i][0];
for (int i = 1; i <= T; i++) ans[i] = max(ans[i], ans[i - 1]);
for (int i = 1; i <= T; i++) cout << ans[i] << '\n';
}

F - 连线博弈

若干条线段会分成若干个子局面,子局面的 sg xor 起来就是答案

对 sg 打表,会发现有神秘循环节

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
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int _sg[5000];
int sg(int x) {
int t = (x - 100) / 34;
t = max(t, 0ll);
return _sg[x - (t * 34)];
}

void solve() {
int n = read(), m = read();

map<int, u64> diff;
while (m--) {
int l = read(), r = read();

auto x = rnd();
diff[l] ^= x;
diff[r] ^= x;
}

map<int, u64> a;
diff[n] = 0;
u64 sum = 0;
for (int las = -1; auto [i, val] : diff) {
a[sum] += i - las - 1;
sum ^= val;
las = i;
}

int ans = 0;
for (auto [_, x] : a) {
ans ^= sg(x);
}
if (ans) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}

signed main() {
for (int i = 1; i <= 200; i++) {
_sg[i] = -1;
}
_sg[0] = 0;
_sg[1] = 0;
_sg[2] = 1;
_sg[3] = 1;
for (int n = 2; n <= 200; n++) {
set<int> st;
for (int i = 0; i <= n - 2; i++) {
int j = n - 2 - i;
st.insert(_sg[i] ^ _sg[j]);
}

int mex = 0;
for (auto s : st) {
if (s != mex) break;
mex++;
}
_sg[n] = mex;
}

// for (int i = 0; i < 200; i++) {
// cout << _sg[i] << " ";
// }

for (int T = read(); T--; solve());
return 0;
}

D - 通配符匹配

设 $s$ 被 * 分成了 $k$ 个串

每个 $s_1$ 匹配上以后,第 $2$ 到 $k - 1$ 个贪心匹配最前面的位置

那么后面的所有 $s_k$ 匹配数量就是当前 $s_1$ 匹配的答案

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
vector<int> getFail(string s) {
int n = s.size();
vector<int> f(n + 1);
for (int i = 1, j = 0; i < n; i++) {
while (j and s[i] != s[j]) {
j = f[j];
}
j += (s[i] == s[j]);
f[i + 1] = j;
}
return f;
}
vector<pii> kmp(string s, string t) {
int n = s.size();
int m = t.size();
auto fail = getFail(s);
vector<pii> pos;
if (s == "") pos.eb(0, 0);
for (int i = 0, j = 0; i < m; i++) {
while (j and t[i] != s[j]) j = fail[j];
if (t[i] == s[j]) j++;
if (j == n) {
pos.eb(i - j + 1, i + 1);
j = fail[j];
}
}
return pos;
}

void solve() {
string s, t;
cin >> s >> t;

int n = s.size();
int m = t.size();

if (s == string(n, '*')) {
cout << (m + 1) * m / 2;
return;
}

vector<string> ss;
if (s[0] == '*') ss.eb("");
for (int l = 0, r = 0; r <= n; r++) {
if (r == n or s[r] == '*') {
string tmp = s.substr(l, r - l);
if (tmp != "") ss.eb(tmp);
l = r + 1;
}
}
if (s.back() == '*') ss.eb("");

// debug(ss);

int k = ss.size();
vector<vector<pii>> pos(k);
vector next(k, vector(m + 1, pii{inf, inf}));

for (int i = 0; i < k; i++) {
auto s = ss[i];

pos[i] = kmp(s, t);

auto &nex = next[i];
for (auto [l, r] : pos[i]) {
nex[l] = {l, r};
}
for (int j = m - 1; j >= 0; j--) {
nex[j] = min(nex[j], nex[j + 1]);
}
}

vector<int> cnt(m + 1);
for (auto [l, r] : pos.back()) {
cnt[l]++;
}
if (k > 1) {
for (int i = m - 1; i >= 0; i--) {
cnt[i] += cnt[i + 1];
}
}

// debug(ss[0]);
// debug(pos[0]);

int ans = 0;
for (auto [l, r] : pos[0]) {
for (int i = 1; i < k; i++) {
if (l > m) break;
tie(l, r) = next[i][r];
}
// debug(l);
if (l > m) continue;

ans += cnt[l];
}

cout << ans << '\n';
}

C - 造桥与砍树

TosakaUCW: 09-21 13:44:50
唉,理解prim了。感觉我原来是,只会kruskal

TosakaUCW: 09-21 13:44:55
普及组算法没学好

TosakaUCW: 09-21 13:45:02
[呲牙][流泪]

xxx: 09-21 13:53:38
不会prim

xxx: 09-21 13:53:50
有没有这题prim省流

TosakaUCW: 09-21 13:54:57
边做边维护最优的边

TosakaUCW: 09-21 13:55:22
每个x最优的边,就是最靠近,k-x的。

TosakaUCW: 09-21 13:55:34
只需要动态维护这个就行了

TosakaUCW: 09-21 13:56:10
[图片]

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
struct node {
int dis, v, u;
bool friend operator < (node a, node b) {
return a.dis > b.dis;
};
};

void solve() {
int n = read(), k = read();
vector<int> a(n);
multiset<int> s;
for (auto &x : a) {
x = read() % k;
s.ep(x);
}

priority_queue<node> q;

auto x = *s.begin();
s.erase(s.begin());

auto get = [&](int x) -> int {
auto it = s.lower_bound(k - x);
return *(it == s.end() ? s.begin() : it);
};

auto y = get(x);
q.ep((x + y) % k, y, x);

int ans = 0;
while (!s.empty()) {
int y;
auto [w, x, p] = q.top(); q.pop();

if (!s.contains(x)) continue;

s.extract(x);
ans += w;

y = get(p);
q.ep((p + y) % k, y, p);

y = get(x);
q.ep((x + y) % k, y, x);
}

cout << ans << "\n";
}

A - 整点正方形计数2

需要解决的是一个子问题:给定 $a, b, c$,统计有多少个正整数 $x, y$ 满足 $1 \le x \le a, 1 \le y \le b, 1 \le x + y \le c$。

时间复杂度 $O(nm)$

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
void solve() {
int n = read(), m = read();

auto calc = [&](int a, int b, int c) -> int {
if (a < 1 or b < 1) return 0;
if (c - 1 <= 0) return 0;

a = min(c, a);
if (b >= c - 1) {
return (c - 1 + c - a) * a / 2;
} else {
int k = min(c - b, a);
int res = b * k;
res += (a - k) * (c - k - 1 + c - a) / 2;
return res;
}
};

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
int res = 0;

res += max(0LL, min(i, j));
res += max(0LL, min(i, m - j));
res += max(0LL, min(n - i, j));
res += max(0LL, min(n - i, m - j));

res += calc(j, m - j, n - i);
res += calc(j, m - j, i);
res += calc(i, n - i, j);
res += calc(i, n - i, m - j);

cout << res << " \n"[j == m];
}
}
}

G - 序列与整数对

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
void solve() {
int n = read();
int m = read();

vector<int> a(n), v;
vector<pii> q(m);
for (auto &x : a) {
x = read();
v.eb(x);
}
for (auto &[x, y] : q) {
x = read(), y = read();
v.eb(x), v.eb(y);
}

ranges::sort(v);
v.erase(unique(v.begin(), v.end()), v.end());
for (auto &x : a) {
x = ranges::lower_bound(v, x) - v.begin();
}
for (auto &[x, y] : q) {
x = ranges::lower_bound(v, x) - v.begin();
y = ranges::lower_bound(v, y) - v.begin();
}

auto vv = q;
sort(vv.begin(), vv.end());
vv.erase(unique(vv.begin(), vv.end()), vv.end());
map<pii, int> ans;

int N = v.size();
vector<vector<int>> buk(N);
for (int i = 0; i < n; i++) {
buk[a[i]].eb(i);
}

for (auto [x, y] : vv) {
auto& v1 = buk[x];
auto& v2 = buk[y];

if (v1.empty() or v2.empty()) {
ans[{x, y}] = 0;
continue;
}

int n1 = v1.size();
int n2 = v2.size();
int res = 0;

if (n1 <= n2) {
for (auto i : v1) {
int j = ranges::upper_bound(v2, i) - v2.begin();
res += n2 - j;
}
} else {
for (auto j : v2) {
int i = ranges::lower_bound(v1, j) - v1.begin();
res += i;
}
}

ans[{x, y}] = res;
}

for (auto t : q) cout << ans[t] << '\n';
}

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
void solve() {
int n = read();

vector<int> a(n);

auto best_a = a;
auto best_res = 0;


for (int i = 0; i < n; i++) a[i] = i + 1;
do {

// for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
auto calc = [&](vector<int> a) -> int {
int ans = 0;
for (int k = 0; k < n; k++) {
vector<vector<int>> g(n + 1);
for (int i = 0; i < n; i++) {
int u = a[i];
int v = (i + k) % n;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
int res = 0;
vector<int> vis(n + 1);
auto dfs = [&](auto self, int u) -> void {
vis[u] = 1;
for (int v : g[u]) if (!vis[v]) self(self, v);
};
for (int i = 0; i < n; i++) {
if (!vis[i]) res++, dfs(dfs, i);
}
ans += res;
}
return ans;
};

int res = calc(a);
// cout << res << '\n';

if (best_res < res) {
best_res = res;
best_a = a;
}
} while (next_permutation(a.begin(), a.end()));

cout << best_res << '\n';
for (int i = 0; i < n; i++) cout << best_a[i] << " \n"[i == n - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
int n = read();

int ans = (1 + n) * n / 2;

vector<int> a(n + 1);
a[1] = 1;
int t = 2;
for (int i = n; i >= 2; i--) {
a[i] = t;
t++;
}

cout << ans << '\n';
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
}

E - 看比赛回放

1
2
3
4
5
6
7
8
void solve() {
int n, m;
cin >> n >> m;

int x = (n + 1) / 2;
int ans = (m - x) * 2 + 1;
cout << ans << '\n';
}
Author

TosakaUCW

Posted on

2025-09-22

Updated on

2025-09-28

Licensed under

Comments