CSP2025

· · 生活·游记

9.20

初赛。

没什么好说的（除了某个金牌✌坐我右边），J86/S86。

噢 J 是不是过不了了，那很好了。

我只能说 CCF 不给时限和数据范围还是太 牛牛 了。

To 10.17

模拟赛。模拟赛。模拟赛。

经历了 n^2 过 100000，n^3 过 10000，还有胃酸获得 100 和 95 分。

RP 要没了。

To 10.29

继续模拟赛，没什么说的。

随便打了一下洛谷比赛，好像还行？

现在状态正在慢慢回升吗？

10.30

随机写一下。

最后一场模拟赛。进行了一个随机开题，随机写伪算，随机写暴力，随机写dp，随机优化。

在 宇宙射线 的影响下随机获得 260 分。

诶不是我怎么登顶了？

哦怎么有 3 个 大师 没来，那没事了。

能赢吗？！

11.1

来了。

J组

开场通读一遍题，诶这个 T3T4 我怎么不会？

算了，直接开写。

首先花了 10min 写完了 T1T2。

T3

我们发现 T3 中对于固定的 l 一定会选离它最近的 r。

那问题就是选最多的区间使它们两两不交。

这个按 r 排序贪心即可。

怎么已经了 1h 了。

T4

首先写出 O(N^2V^2) 的 dp。

发现 max 和 sum 都有影响，考虑定一求一。

枚举 max，钦定 max 选 A 个，发现问题转为求在小于 max 的数中选且 sum + max \times A > 2 \times max 的方案数。

可以做到 O(NV^2)。

发现瓶颈在选的数之和最大为 N \times V。

考虑正难则反，用总方案减不满足要求的，这样和就最多为 V 了。

容易做到 O(NV)。

严肃 2h 沉浸式 AK。

考完

发现 T4 有一万种做法。

发现有人 T3 写的决策单调性优化 dp，根本不是人。

发现 80% 的人都说自己 < 200 分。

S组

这个 T1 是什么鬼。

这个 T2 是什么鬼。

这个 T3 是什么鬼。

这个 T4 是什么鬼。

好的我要认真了。

T1

好的我们发现人数 >n/2 的只可能有一组。

好的所以我们先随便分，把人数 >n/2 的那一组找出来。

好的再用分到其他组的变化量给他们排序，再直接改变分组就行。

发现已经 30min 了。

T2

发现 K 很小，直接枚举子集看要不要改造。

发现 MST 的边只有可能为新加的和原图的 MST 上的。

发现直接做可以 O(2^K \times nk \log nk)。

发现可能不能过。

发现提前排序后归并就能 O(2^K \times nk)，大概有 5 左右的常数，希望能过。

注意到又过了 1h。

T3

注意到 S 的二元组可以变成 S_1(S_2-S_3)S_4 的形式。（以样例一的 S_1 为例，变成 xa(bc-de)x 的样子）

注意到将 T 也如此分解后问题转化为：在满足 (S_2-S_3)=(T_2-T_3) 的 S 中，满足 S_1 是 T_1 的后缀且 S_4 是 T_4 的前缀的数量。

注意到我不会做这个鬼东西。

注意到我就直接暴力跑路了。

注意到暴力的大样例跑的飞快。

回归正题，注意到这个东西可以转成二维数点用 trie树 + BIT。

然后写完暴力已经 2.5h 了。

T4

然后猛攻 1h T4，发现不会 N \le 18。

然后 8 分。

出场

发现并非很低。

能赢吗？

11.3

自测。

J : 100 + 100 + 100 + 100 = 400。

S : 100 + 100 + 50 + 12 = 262。

11.5

官方。

J : 100 + 100 + 95 + 100 = 395。

S : 65 + 100 + 50 + 8 = 223。

为何 J T3 答案可能为 0。

为何 S T1 大样例没有最大值等于次大值。