csp2019游记

才踏出考场半步,迎来的不是解放的欢呼,而是你谷讨论版上考生漫天的哀嚎,而是某乎题解贴中出题人集体的匿名——这究竟是人性的扭曲,还是道德的沦丧?请看本周的今日说法

读完三道题的题面后,我对次试的直观印象就是——题目都巨**长,让我心生厌烦。由于题面长的原因,我并不能看出哪道题会做,便只好先试一下T1。

D1T1 格雷码

这是今年csp唯一一道良心的题......思路很简单,从数据所给的(n,k)开始,如果(kleqfrac{n}{2}),那么(k)不变,把(n)折半;否则给(k赋值n-k),也把(n)折半。每次操作时给答案按照题目要求加上0或1。如此循环往复,当(n)减小为1时,按照题目所给的边界值处理即可。最后5分要开ull。(出题人呢?

D1T2 括号树

怀揣着切掉T1带来的信心,我开始看T2,然后被泼了冷水。看了估计十来分钟,有点思路了,心想:这不是傻逼题吗?然而考虑实现时,我却遇到了问题:如何快速把所有桶里面存的值,移动到比他的桶大1的桶里面去?在千辛万苦掉了几撮头发后,我想到了一个指针数组的实现方式,用线段树维护即可。但神使鬼差地,我自己捏了一组样例,hack掉了我的做法(也有可能是我手玩的时候算错了)。由于这个做法的代码难度太高,而且时间只剩下不到1h,我决定先打个(n^2)的暴力之后看一下T3,然后再做决定——要不要继续做T2。

D1T3 树上的数

被称为noip史上和csp史上最难的题。我本来就没有抱着A掉它的想法,便首先打完了10分的(2^n)暴力。然后觉得链的部分分可用贪心做,正确性显然,便试着写了一下。结果就发现,数据的链不保证编号从1到n,链头链尾也不保证是1和n。于是这个部分分就变为不可做的了。此时已时间殆尽、即将交卷了。我便删了调试语句,去收拾纸笔了。

D2T1 Emiya 家今天的饭

奇奇怪怪的一道题,题面巨长,意思巨难懂,细节还巨**多。在不断发现题目中隐晦的条件,并且不断修改着思路的同时,我觉得只有(n^m)那堆数据是我可以做的。于是跟着自己的思路敲好代码。此时条件仍然尚未发现完全,我自然就进入了焦灼的改代码阶段。这起码花了我一个小时的时间,改得头皮发麻。

D2T2 划分

起初以为是斜率优化,这个东西在长沙练过许多。于是就推了推式子,成功地在理论上优化掉一个n的复杂度。但是仍然是(n^2)的。我便十分头疼,斜率优化只是部分分?nmsl。然后发现设置的状态里面,划分了多少段并没有意义,于是便设置了另一个(n^2)的状态。然而此时(可能是因为写T1写傻了)出了个很大的失误,我算错了复杂度,把(n^3)算成(n^2)了。我的算法还缺一个单调队列优化才能做到(n^2),但是没打。于是只拿了(nleq400)的分。

D2T3 树的重心

此时我很有自知之明地察觉到:想得出正解?这辈子都不可能。于是直接打了(n^2)暴力。链的情况也可以做,但是时间不够了。完美二叉树的情况应该也是可做的,也是时间不够了。


总的来说,这次考试就是:用头发想题、用头发敲代码、用头发写优化、用头发改bug、用生命在A题。所以只A了一道

原文地址:https://www.cnblogs.com/akura/p/11959171.html