CSP-S 2022 游记

· · 个人记录

\texttt{?}

为什么准考证号是 514，也太臭了吧。

\texttt{7:23}

会不会考矩阵快速幂优化 DP 啊。（做了 ABC256G 后的感想）

\texttt{14:25}

Belief2022

\texttt{14:26}

belief2022

\texttt{14:27}

扫了一眼，传统题，O2，c++14。

\texttt{14:30}

认真读 T1，一眼 meet in the middle。
仔细思考发现好像是 O(n^3)。

\texttt{14:40}

然后成了 O(n^2\lg n+nm)，开写。

\texttt{15:00}

过大样例了，跑路。

\texttt{15:01}

T2 博弈论？跑路。

\texttt{15:02}

T3 好像是数据结构，看题。

\texttt{15:05}

我草这题怎么那么复杂。

\texttt{15:10}

没思路，看 T4。

\texttt{15:30}

终于在 k=2 的时候推出一个 f_i=\min\{f_{i-1},f_{i-2}\}+a_i 的式子。
这种东西好像是可以矩阵快速幂的？？？但是我不会动态 DP，寄。
依稀记得 LA 群友的发言。

把树高 2\lg n 的特殊性质写了跑路。

\texttt{15:45}

等下这个 T2 好像不是博弈论。

\texttt{15:55}

懒得分类讨论了，直接把负数最小，负数最大，零，正数最小，正数最大拎出来枚举不就完事。

\texttt{16:10}

大样例过了，跑路，看 T3。

\texttt{16:12}

先给 T2 写个对拍再说。

\texttt{16:20}

也给 T1 写个对拍吧？

\texttt{16:21}

等下我不会造数据，跑路。

\texttt{16:35}

先把 T4 的 k=3 暴力分拿了。

\texttt{16:50}

主要是刚好做过 ABC256E，那道题就是每个点只有一个出度。
某篇题解说这样的图只有简单环，所以一直在往那个方向想。
接着猛然发现出度全部为 1 那不就是基环树森林了吗？？？

\texttt{16:51}

但是要怎么维护出度全部为 1？

\texttt{17:00}

逐渐头晕，感觉有东西卡在喉咙里，思考能力逐渐低下。

\texttt{17:05}

这种题目看上去太像根号分治了。
但我分不出来，而且 5e5 的数据貌似也不能根号分治。

\texttt{17:30}

实在受不了了去厕所干呕。
受到了监考人员的温馨照顾。

\texttt{17:50}

还是不会 T3，但是先把 60pts 暴力干出来。

\texttt{18:05}

等下是不是可以建虚拟节点什么的啊。

\texttt{18:20}

没调出来，而且好像也假了。

\texttt{18:29}

往草稿纸上写了一个 Belief2022。

\texttt{18:30}

跑路。

\texttt{23:00}

在大巴车上看窗外的星星。

\texttt{次日 0:20}

到家了。

\texttt{0:35}

洛谷 90+100+?+64=254+?。

\texttt{11:00}

INFOJ 100+100+60+64=324。

\texttt{21:12}

计蒜客 100+100+100+64=364。
希望 CCF 可以像计蒜客一样脚造数据。

\texttt{次日 9:53}

洛谷 90+100+60+64=314。

\texttt{15:28}

LA 群有人测了 ZJ 省，好像是 INFOJ 的数据。

# $\texttt{15:41}

XJOI 100+100+60+64=324。

\texttt{18:33}

然后说之前那个 ZJ 省用的不是 INFOJ 数据。
现在回到 100+100+60+64=324，rk51。
貌似是校内 rk2（被集训队学长吊打了），高一 rk1。

\texttt{19:53}

小图灵 90+100+60+64=314，被 zyp 316 薄纱了。

\texttt{次日 7:07}

HydroOJ 100+100+60+78=338，ZJ rk55。

\texttt{2022.11.7}

虽然好像是明天早上出分但是通过神秘方法摸到了分数的屑。