CSP-J/S 2025 游记

· · 生活·游记

CSP-J/S 2025 游记

Day -rand()

开始写。

今天校赛考炸了，橙黄黄黄加起来才 318.2 分，才过两道题。

[HAOI2012] 音量调节

水题，直接 dp 就行（但有某人写了 dfs 还没加记忆化）。

[HAOI2016] 食物链

跑拓扑即可，但是我忘判断单个点的情况了。

[HAOI2016] 放棋子

注意到有 n 个障碍，错排板题。

但是我赛时没看到有 n 个障碍，暴力打表找规律，设 dp_{i,j} 为在 i\times i 的矩阵中有 j 个障碍物（障碍物顺序不影响），则当 j=0 时 dp_{i,j}=i!，否则 dp_{i,j}=dp_{i,j-1}-dp_{i-1,j-1}。

所以 O(n) 能过的题为什么 n 才 200？

[HAOI2012] 容易题

给每个限制排个序再算一下方案数即可，但不知道为什么挂了 30 分。

upd：n 没开 longlong

不是怎么有人三道黄都过了橙没过？

离开学还有 5 天，暑假作业只写了 eps 点。

9.19

明天初赛。

9.20 初赛

上午考 J 组，8点到9点半才开考，结果又考炸了，一堆低级错误，估分才85。

下午的 S 组初赛免了（这就是级八的力量！）。

初赛成绩

J：84.5。

10.1 国庆

前三天去机构上课，后五天去学校上课，要炸了。

10.8

今天考试，两黄两绿，结果后面两道题数据出问题了，有个人只做了后面两道题。

[USACO21OPEN] Acowdemia S

二分答案，但我忘开longlong挂了15分。

[USACO21JAN] Dance Mooves S

将每个牛可能运动到的位置的点合并，统计一下答案，写起来细节挺多的。

[USACO21FEB] Year of the Cow S

贪心加优先队列优化。

[USACO21FEB] Just Green Enough S

感觉最妙的一道题，统计最小值大于等于100和101的子矩阵数量，再相减就是答案，但我 O(n^4) 莽了80分。

Day -5

开始脱产。

Day 1

8：27 解压密码是#Shang4Shan3Ruo6Shui4。

8：30 去蹲坑

8：42 开始写题

T1记录一下数字最后从大到小输出，T2排序后模拟一下，9：00左右做完。

T3感觉似曾相识，用队列记录前缀和，再记录一下当前选的最右边的区间，大样例跑了1s多，把队列换成数组就快了，这时候是9：30左右。

T4一开始没什么思路，想到了背包但以为要开 250000 的背包，铁超时，所以先打了暴力和 a_i 全为 1 的部分分，然后突然意识到背包只用开最大值的两倍+1即可，所以乱胡了个一会儿，调了半天背包递推式，10：30左右写完了。

摆

11：37 发现T3数组开小了，赶紧开到 2^{21}，然后继续摆。

发现西西艾弗checker出锅了检测不了。

12：00 走了。

估分：100+100+100+100=400

Day 1.5

8：27 解压密码是#Ren?Jie?Di?Ling，问号是数字，具体忘了。

8：30 开始看题，一题不会，先写了T1的暴力，突然想到一个贪心，先全部选最大值，然后如果某个社团人数超过 \frac{n}{2} 就将多的人改为次大值，写完大样例也过了。

T2不会，写了个最小生成树就跳了。

T3更不会，写了个哈希暴力就跳了。

T4更更不会，写了暴力就跳了，甚至连 n \le 18 都过不去。

回去看T2，写了个 O(2^km\ log\ m) 的暴力，可是就是没想到先跑最小生成树在枚举时间复杂度就只有 O(m\ log\ m+2^kn\ log\ n) 了，痛失 52 pts。

看T3，把特殊性质B写了，然后一直想T2，就是想不到，直到比赛结束。

出来一听同学的思路就想到T2做法了。

估分：100+48+50+8=206

希望有勾七。

UPD

J：100+100+100+100=400

S：100+40+30+12=182

S组T2常数大挂了8分，T3没判Ti!=Tj居然有30分，T4暴力8分+输出0有4分