2020csp-s 游记

~~真就搞心态~~ # Day -n 牛客6连，感觉比赛状态还行，刷了很多~~用不到的~~板子 # Day 0 初赛 ~~感谢教练的牛奶保佑~~ 临时抱佛脚，复习了一堆人名果然还是有用的，难得一次理论知识全会 然后阅读程序就去世了，一个O(n)map把我看傻了，看了半天懂了意思然而推不出结论 考场估分80左右，反正过了就彳亍 # Day 1 开场密码就奇奇怪怪，打开txt是(xxxxxxx)，然后复制了xxxxxx显示密码错误，试了半天发现密码是带括号的 瞟一眼题，t1大模拟，完了炸裂 先简单看了一下后面的题目，t2题面贼长，t3三个操作看上去就像数据结构，t4乍一看博弈论？不管不管先搞t1 分类各种东西，分公元前，公元后，到消失的10天，到1583，到1600，预处理了一堆东西，手造试了各种数据 然后写完就4点了（什么黑心t1啊！！）赶紧看t2 ~~读题就花了10多分钟~~，最后才看到q不相同，然后就意识到题目给了一堆干扰信息，c和q都用不到 然后发现只关心二进制下那几位固定为1，其他位置任意，再减去原来有的动物就好了，$ans=2^k-n$（然而我知道会炸ull也没特判）。写完就4：15了，感觉时间还够 t3乍一看以为是数据结构，然后发现并不好维护，打了个模拟滚去t4~~然后5分钟以后又滚了回来~~ 看了看部分分发现“调用关系成树形结构”，才意识到是图论。20多分钟发现第一个结论，可以倒着处理序列，对于一个乘法操作，转化成把它前面的加法操作全部乘上k，然后换了个方法写模拟，发现结论是对的。仔细想了想一个点的右边(倒序后先操作)乘法后代对左边的加法后代的影响是固定的，所以模拟的时候处理完一个子树就把k乘上字数内的乘法操作的积。然后发现这个东西可以用个分配率转化成标记，先O(q)打标记，再O(n)下放。然后发现对于一般dag也可以打标记。打了个对拍，好像没什么问题，写完就4:50了，赶快滚去t4 ~~果然什么都推不出来~~，盲猜了一个模拟，每次最大的吃最小的，如果这个最小的当过一次max，答案就等于这个最小的当max的那一轮，写了一个set去模拟，想了半天优化~~然后想着想着睡了半个小时~~ 考完听dalao们说t1细节很多，大样例全部都是一种情况，心中一凉；说t2要特判，又一凉；说t4大样例答案大1，是要特判偶数减一，仔细一想自己好像没注意输出到比大样例大1，又凉 ~~反正估分往低了去估，成绩出来再怎么都不会伤心~~ 考场估分60+90+100+0 你谷估分100+90+100+20 ## Upd 2020.11.17 官方数据100+95+100+20=315（果然要相信乱搞出奇迹） # 小结 ~~痛失370~~ 今年是真的搞心态，讨厌啥来啥（没错就是t1和t4） 感觉还是有点可惜吧，t4没有特判的原因其实是因为乍一看*感觉*自己的输出和大样例一样，果然还是应该fc一下 t2也是，都想到了1ull<<64的问题，也没有特判（其实是没看到nm可以等于0） 还是注意看清楚题面啊