NOI2021 网上同步赛游记

CSP_Sept · 2021-07-26 15:29:18 · 个人记录

Day 1

严格来说并不算参加了同步赛，因为几乎没摸到电脑（大悲

T1 发现 50 分应该毫无难度（大嘘

测试点 1\sim 10 随便过（

然后越打越感觉不对劲，写 LCA 写炸了。

【思路】（假的，\bm{50} 分的）

给每个点分配一个 vector 数组 son，储存子节点。
每次对于数 a,b，求出 \text{LCA}(a,b) 的值 anc。
查询 a\to anc,b\to anc 两条路径，对于每次查询到的点 x，遍历 \tt{x}\mathcal{.son} 找到 x 的所有子节点 u，然后将 x\to u 设为轻边。
将经过的所有边设为重边。

然后一度以为特殊性质 B 是操作 1,2 中都存在 a\to b\text{ or }b\to a 的边，一度以为自己能拿 70。

好！！！

乱写了个特殊性质 A 的部分分。人没了。

结果就这样过了 15:00，而我 T2 和 T3 看都没看

就这样吧，看完 T2 T3 再更（

还是太菜了 /kk

不过比去年有了质的飞跃（确信

那时我还不知道有 LCA 这种东西（

UPD 15:37：三道题似乎都是原题：

T1：/kk
T2：/kk
T3：据说已经有大部分思路存在。

UPD 15:55

人傻了，白写了 dfs。

UPD 16:18 哦 T3 k=0 有 \tt18pts 白送。

Day 2

打的时间也不长，中途被家长拉去吃饭+午休（迫真），浪费了约 \text{2.5 h}。

早上 10:00 到家，先开 T1，发现是伪的人类智慧题。

仔细研读了题目，发现我只会暴力。

（这个强制在线是什么鬼

然后就迫不及待地敲完了代码，情不自禁地使用了 \tt string，一看空间限制：\text{384 MB}。

我草你还卡空间？！

跑了一下样例，样例 1 跑得飞快，样例 2 跑了 \text{1.1 s}。

人傻了。

（此时我忘记了时限是 \text{2.0 s}，还开了 \text O_2。

然后我赶紧把 \tt string 改成了 \tt bool，光荣 \text{0.4 s}。

于是抱着试一试的心态跑了跑样例 3，放张图吧：

好活（

（虽然确实 qi.out 和 qi3.ans 一模一样

时间复杂度 O(kmn)，k 是常数，大概是 2^8。

开 T2，哦我也只会暴力。

于是乱写了个分数加法和暴力算法，调了半天 RE，结果是 i-- 写成了 i++。

好，过了样例 1 就好。

人傻了。

T3 不会，puts("1") 走人（我也不知道有没有分

人傻了。

结果：

分数估测（红色表示能拿但是因为种种原因没拿到的分，红色后面用括号表示实际估测得分）：

\text{\color{Violet}[day 1] }{\color{red}\textbf{40}}(0)+{\color{red}\textbf{20}}(0)+{\color{red}\textbf{18}}(0)+\text{\color{Violet}[day 2] }{\color{red}\textbf{28}}\textbf{(16)}+\textbf{20}+\textbf4=\underline{{\color{red}\textbf{130}}\textbf{(40)}}

UPD 2021.07.29 D2T2 炸了，因为乱取了个 \gcd，所以炸的一分没有。