csp 2022 总结

csp 2022 总结

三年来第一次挂这么惨，几乎把我送走。。

J

一看， T1, T2 水， 先写了。

觉得 T3 不对劲，好像建出树就可以做

发现我的建树是 n2" role="presentation">n2$n^2$ 的，换了几种做法后，无奈先看了一下 T4

好像是一个简单 dp ，花了几分钟解决，重写 T3

然后瞎写了一个 nlog⁡n" role="presentation">nlogn$n\log n$ 的，n=106" role="presentation">n=106$n={10}^6$ 会不会被卡也不知道了，可以开摆。

S

一看， 3 题图论，一个小清新数据结构，心中窃喜
t2 像一个分类讨论，t1 应该是优化暴力。
t3 是在若干操作后判断是否每一个点出度都是 1 。
t4 应该是某种倍增。

先看 t2 ，维护最大和最小的正数或负数。分了几类讨论。

大样例可信度蛮高，过了直接放了。

看 t1 ，首先脑抽一波，看错了题，打了一个高精度。

维护了 1→a→b" role="presentation">1→a→b$1\to a\to b$ 的最大、次大、第三大

然后我又脑抽了，又维护了 1→a→b→c" role="presentation">1→a→b→c$1\to a\to b\to c$ 的最大，次大值。。。

考完直呼 markdown ，因为这样是错误的。

其实直接枚举已经可以更新答案了。。。 代码反而更少。

想着 t3 一定又什么性质，考虑先写 t4 暴力。。直接在链上 dp" role="presentation">dp$dp$

结果发现第二个样例死活过不了，还自信地以为样例有问题。因为没时间了

结果： k=3" role="presentation">k=3$k=3$ 时不一定 要在简单路径上。暴力都挂了

出了考场，张口就是 240 ，

某网站没有 150 ，三题打假，一等无望。

分数甚至没有初一时的高

过了两天： WTF 居然 LHF 仅 800b 切 t3 ？

总结

1. 对于一些点要复习到。

2. 算法要考虑全面、正确性、实现难度

3. 时间安排问题