CSP-J 2020 第二轮 游记

2020-11-06 10:19:20


Day-2

复习,打了 $19$ 个模板,补了一下Dij的堆优化和prim,但是还是感觉要爆零,看了一下我的 ,感觉复赛很容易爆零啊
晚上回家几乎没有写作业,whk完全弃疗。遇到班主任,他和我说搞好CSP,回来之后再补whk

Day $e^{i\pi}$

来到学校完成最后一个模板 prim,然后一直颓废,貌似大家都一样啊。
下午出发去杭州了~~~~。
路途上一堆人在研究
晚上大约6:00到HZ,感觉HZ就是不一样。
get防爆零手册*1

说实话杭州的夜景也不错的。

Day1

PJ选手起得很早,世道变了,以前都是TG的起得早啊,吃早饭的路上遇到一群歪果仁,不愧是HZ,大城市。。。
早上很早来到考场,而且差点忘记带上身份证。 密码是Ta&Shan#Zhi@Shi% 就是他山之石,不过听说提高组是(ke2YI0gong2YU0)

开场先看T1,感觉比去年难多了,其实只要预处理出 $\left[\ \log_2N\ \right]$ 就可以了,切了切了。
然后看T2,只会 $\Theta\left(NT\right)$ 的暴力啊,诶不是可以用平衡树吗? 然后看一眼数据范围 $a_i\le 600$ ,开个桶乱搞即可。 30min切掉前两题,开始看看T3。
第一眼:把这个表达式扔二叉树上,使二叉树的后序遍历就是这个表达式,然后暴力求解即可。
然后开始优化。。。。
不难想到只需要处理这一条链就可以了,而且遇到 ! 运算符还可以直接先上跳,可以写个树形DP预处理优化掉。而且向上跳的过程中还可以判断有没有对答案造成影响,剪枝,反正大样例是过了。
写完对拍就挂着,看看T4。
然而T4不会做....
先写了个dfs SPFA,然后样例就没过...
算了算了,还是数据分治,小数据暴力,大数据贪心(也就是SPFA)
然后又感觉T4有点像DP,但是由于花在T3的时间上太长了,就只能放弃T4了,继续来看T3。
接下来的时间就是修一些T3代码的锅,处理了一些细节和边界值的处理,然后就没有什么大问题了。。。

估分 $100+100+80+20=300$
回QZ的路上在计蒜客测了一下民间数据, $100+100+95+10=305$
貌似T4的暴力写挂了。。。

Day2

betway必威体育官方出数据了,估分 $100+100+100+15=315$
(看来betway必威体育官方T3数据也很水啊,当然T4的暴力是真的挂了啊啊啊啊啊)
其实T3当时我差正解只有一步,就是剪枝是可以预处理掉的啊,然后就成为了 $\Theta\left(1\right)$ 的查询就可以过了。
嘤嘤嘤没有AK,但是1=应该没有什么问题。
T3 具体做法: 众所周知,a&0 无论 a 取什么值,最终的结果都不变, a|1 也是如此,就可以在预处理的时候把另外一棵子树打上懒惰标记就可以了。

最后宣传一下

Day 114514

score:$100+100+85+5=290$
CSP2020S1/2见。