csp-s2025游记

· · 生活·游记

？我怎么高一了。

day -9

萌熊有点幽默了

day -8

初中小灯都在 \huge\color{red}\textbf{RDFZ} 考。

主播在大专考，懒得喷。

day -7

前一天晚上用 80 分钟从头到尾开始写，获取了 arena 84 分。

起床加了优化发现复杂度变成线性了。

卡卡常就在 qoj.ac 以 983ms 通过，不过 loj 不超过 0.8s。

day -6

互测喜提 0+5+70

萌熊模拟赛，t3 本地打表打了 60KB 没交上去，t4 用 q\sqrt n\log n 冲过去了。

day -5

宋氏联考

给小朋友讲题讲吐了。

day -4

t1 放平衡树，赛后发现能线性，绷。

t2 是 [NOIP2024] 树上查询，绷。

day -3

模拟赛 t1 没开 freopen，没看见输出 -1。

还不会做 t2，没写完 t4，总分 0+24+100+40=164。

csp 怎么办。

下午严肃打球。

day -2

t1 是 https://www.luogu.com.cn/problem/P14302。 喜欢斜二倍增？

打球，打不明白。

day -1

宋完了，怎么 day -1 了。

cdjx 的模拟赛真幽默。

t1，绷。t2，cdq 板子，绷。t3，分块板子，绷。t4 容易发现 [x^k]\prod\sum\frac{x^ta_i^t}{t!}=\frac{(\sum a_i)^k}{k!}，绷不住了。

出题人不会 egf 何意味啊。

赛后发现 t1 挂了 80，哈哈哈

day 0

宋完了，怎么 day 0 了。

二十分钟速通了昨晚 CF D,E,F

F 更是五分钟写完代码一发过样例

G 也是宋题，逗我呢？？？

找回了一点信心。

day 1

我声称我 AK 了。

先喷一下考点环境。

省流就是大专打不过 \huge\color{red}\textbf{RDFZ}。

开题，t1 读完会了，吧。t2 看成了可以对 1\sim k 进行修改，会了 \mathcal O(2^kkn\log n) 做法，先扔一边去。t3 简单做了一下意识到要把中间部分拿出来，要求两边部分各自是询问串的前后缀，我咋不会啊？？别急，先去写代码。

t1 写完了就把所有样例过了，摆烂了，不拍了。脑子很不清醒，大概写出来了这样的东西，希望没写错。

F(i,1,n){
        if(a[i][0]>=max(a[i][1],a[i][2]))col[i]=0,ans+=a[i][0],dt[i]=a[i][0]-max(a[i][1],a[i][2]);
        else if(a[i][1]>=max(a[i][0],a[i][2]))col[i]=1,ans+=a[i][1],dt[i]=a[i][1]-max(a[i][0],a[i][2]);
        else col[i]=2,ans+=a[i][2],dt[i]=a[i][2]-max(a[i][0],a[i][1]);
}

t2 写代码时才发现 k 个点是额外点！！！！当时很慌，10 分钟之内脑子里全是慌的，镇定下来后发现和读错题的版本并没有什么区别，先写个 \mathcal O(2^kkn\log n)，大样例 0.6，玩锤子。不过应该有 80 分了，先扔一下。

回去看 t3 那个问题，发现对于不同等价类建立一下 trie 就变成给一车点 (u,v)，查询 (x,y) 表示有多少 (u,v) 使得 T_1 上 u 是 x 的祖先，v 是 y 的祖先。写的挺快的，写完直接过所有样例，静态没查出错，摆烂换题了。

这时过去 80 分钟，嘟。

t4，哎，好难啊。哎我会 m=n，如果 a_i 以及 s_i 都 >0 那么输出 \boldsymbol{1}，先写上，感觉最后还是要拼暴力。做的很痛苦，n^5，倒着做，反转 dp，容斥，感觉啥都想了一遍，最终做法很简洁。修的时候发现转移没写错，最终答案统计错了。改掉之后，样例 1 的输出从 16 变成了 2，再测一下发现过了样例 1,2,3,5，样例 4 WA 了？？？再查了下代码，经典取模打少了。这样就全过了/jy

这时大概是 17:08，我通过了所有大样例。

后面一直在检查，以及发现使用 std::merge 以及每个集合只存有效的 MST 边那么所有东西的边量级都是 \mathcal O(n)，这样复杂度改到了 \mathcal O(2^kn\alpha(n)+kn\log n+m\log m)。感觉 n=10000 按秩合并没用所以删了。一测大样例怎么还是 0.6，真火大了。结果发现 m=10^6，瓶颈在于读入，那懒得管了。

18:15 时，我发现 m=n 应该输出 n! 或者 0，绷不住了，删了这个特判也能正常跑哦哦哦。

后面就摆烂了，不过这场心率一直没下去啊。中间修 t4 的时候一直在担心没修出来怎么办，哎。

《嘟嘟嘟，虽然哈集幂不是北京省队，但是他还是大专小子。》中有 6 个人声称自己 ak 了，绷。

出场问了几个人怎么有些倒闭了？？？？

t3 核心挂点是 map<string,int>，怕 TLE。我没写哈希，嘟嘟嘟。字符串比较是 \mathcal O(\min(|s|,|t|))，那我不是倒闭了？？但是我觉得卡不掉啊？这个锤子题核心在于区分前后缀，那他中间部分肯定是乱造的！这个题他肯定不会在中间部分造相似的串！不乱造的性质 B 大样例只有 0.15，那我不急了。

就算挂分了也应该有 noiwc 去吧。

day 5

生物考出了 47/100 的高分，不过大概是要换地理了/tx

查分，没挂。100+100+100+100=400。

那我失去的 rp 这块谁给我补啊/ll