CSP2019 游记

一些有趣的事情 =    Day 0 = - 上午颓废，下午到宾馆 - $15:40$ 左右去试机 - 试机题是 $\text{A+B Problem}$ ~~，发现是个线段树模板题，直接码上~~ - ~~某初二学弟写了主席树~~ - 回到宾馆颓了一段时间之后去外面吃饭 - 再次回来之后继续颓颓颓 - $22:00$ 要睡觉突然被叫起来（老董开会） - 开完会大概 $22:30$ - ~~辣鸡宾馆，晚上基本没睡着~~ Day 1 = - 考点在时代中学，感到恐慌 - $8:30$ 开场 - 前两题傻逼题，大概 $30\text{min}$ 做完 - 看 $\text{T3}$ ，看上去一脸不可做 - 不过不算很长的时间就想到了按字典序从左到右贪心后，每次决策时起点（数 $i$ 的初始位置）到终点（数 $i$ 的最终位置）连一条路径 - 一开始认为只要任意一条边最多被正向和反向经过一遍即可 - 但画了一个例子之后立刻意识到操作顺序问题仿佛十分棘手 - 搞懂了（一部分）操作之间的拓扑关系之后，意识到继续搞下去仿佛讨论细节巨多 - 根据经验，把之前的思路全部否定掉，去考虑其他做法 ~~（毕竟这是 D1T3）~~ - 显然，我最后没有搞出来，无奈写了 $10+25$ 的暴力，最后 $25$ 分甚至差点调不出来 - 考完感觉全世界都要 $\text{AK}$ ，心态十分崩溃 - 可让我预料不到的是，$\text{FJ}$ 我认识的选手 $\text{T3}$ 普遍低分，心态算好了一些 - $\text{orz nealchen Day1 AK}$ - 赛后听说 $\text{T2}$ 的大样例很水，感到恐慌 - 下午在宾馆继续颓颓颓 - 晚上在裙里又看到 $\text{rqy,EI,myh}$ 等人切掉了 $\text{T3}$ - 菜死了 - ~~辣鸡宾馆，晚上基本没睡着 × 2~~ Day 2 = - 奶一波 $\text{Day2}$ 最难的题会比 $\text{Day1}$ 最难的题简单 - 赛前 $\text{zip}$ 还未解压之前，看到三题的样例文件数都是 $4$ 或 $5$ ，预感毒瘤题即将出现 - 然后看到 $\text{T1}$ 第一眼看上去感觉不可做 - 想到了总方案减掉不合法的方案，并枚举不合法的方案中唯一选出超过一半的是哪个之后，算一算直接背包 DP 复杂度是 $O(mn^3)$ - 心想今天该不会是凉了吧，第一题就不会 - 后来突然意识到，由于只需知道是否选出超过一半，所以我可以把每个物品拆成两个体积为 $1$ 和 $-1$ 的之后进行分组背包 - 过大样例的时候已经 $\text{40min}$ 过去 - 同时看了后面两题，锁定暴力分 $64+75$ - 看完题目之后感觉 $\text{T3}$ 看上去更可做，于是先开 $\text{T3}$ - 什么？子树的重心？我突然回想起 $\text{pyz}$ 讲过的求子树重心的方法，仿佛还要 $\text{LCT}$ 什么的，感觉此题瞬间不可做 - 后来才看到此题只需要求和而不需要求删掉每一条边的答案 - 考虑每个点的贡献，推了推作为重心的条件之后强行写了个线段树合并 - 不知不觉代码就写了 $\text{3.5K}$ ，$150$ 行 - 调过样例时已经 $10:30$ ，还剩 $\text{1.5h}$ - 为了保险起见，$\text{T2}$ 先码了个 $64$ 分大暴力 - 期间题面有新通知对于 $type=0$ 的数据，满足答案不超过 $4\times10^{18}$ - 然后发现 $type=1$ 的数据占了 $12$ 分且 $n=4\times10^7$ ，这写高精哪能搞。果断放弃这一档 - 然后考虑 $88$ 分，不知道怎么回事搞了一个二分 $+$ 贪心，写完发现贪心策略假了，小样例都过不去 - UPD：后来发现这个贪心策略不全是假的，正确的那一部分仿佛就是正解的最优策略，感觉当时不应该在发现贪心策略假了之后就全盘否定 - 最后也没有对暴力的 $O(n^2)$ $\text{DP}$ 决策打表找规律，此题得分停留在 $64$ - 于是两天期望得分为 $235+264=499$ - 在退役之前没有一次 $\text{N(C)O(S)IP}$ 考到过 $500$ ，怕不是凉透了 - $\text{orz nealchen 504}$ ，$\text{FJ rk1}$ 预定 - $\text{orz rqy AK}$