CSP2019游记

迟到的游记啊,人菜少说话。 # Day-? 请了假一溜烟跑去石中集训。 # Day 1 第一题,格雷码?好像不是数论大毒瘤,20min玩过了几个样例就走了。 第二题,树上括号子序列?放到序列上就是个普及组T2。 欸好像回退一下复杂度正确,那好,40min码完调完。 2.5h,你T3能秒我,我当场把这个电脑屏幕吃掉! 第三题,又是树,不慌!交换?字典序最小?这个明显按位贪心嘛。 woc数据范围才2000,我以为是$10^5$,岂不是每次贪心都可以遍历整颗树啊。 这个LCA反手预处理一下,不慌。 每次找一个最优的换过来,好像能同时进行两个交换呢…… 1.5h过后…… 喵的这不是选删这是全删啊!!! 赶紧打了$O(n!)$暴力,又想了10min发现剩下的部分分都不会。 还有10分钟的时候想出了T3一个貌似正确的做法,可以转化成交换之间的顺序问题,但是此时只能检查检查文件了。 最后20s发现第二题文件名打错了,刺激! 大众分都是$100+100+10=210$。 出来广州之星myh跟我们说了一下T3,好像还真差不多…… # Day 2 我要翻盘!!! 第一题,这不就是个容斥吗?强制让每个菜过半,xjbDP一下不就$O(n^3m)$了?有84分,那就去开下一题了。 第二题,天啊CSP考斜率了,真的是传说中的考纲无限大? 玩了一阵子发现普通斜率并不可做,貌似要写平衡树。 直接弃疗,不写平衡树,莽了一个性质直接插入,祈祷这是单调的。 大样例跑过去了! 等会这怎么好要高精啊……强烈谴责出题人出高精不带模板的行为,以及毒瘤数据生成不带gen的行为!!! 88分跑了。 第三题,看着就很神仙,先20min打个暴力先。 欸这不是xjb换根一下维护最大重儿子分类讨论移动重心吗? 然而由于前几天做过一套模拟,用的是到重心路径和最短这个性质。 居然开始莽路径和的换根dp!那自然是调晕了…… 最后30min回头看了看T1,太慌了,在草稿纸上画了半天都没想到可以直接降维$O(n^2m)$,反倒去想二元多项式卷积去了…… 最终$84+88+40=212$ 出来和大佬交流了下。 woc最后一题序列有15分暴力!!! woc第一题正解这么simple!!! 白给31分.jpg 其实假如T3做出来了,一切都好说,可是没有假如…… # Day n 居然一分没挂,$422$苟了过去。 省里面排名还不如初二的时候高,欸,怎么说呢,OI真是个看脸的游戏。 还是不够熟练啊! # Day n+ 第三次月考语数英大爆炸,排名被踩了。