省选游寄

· · 生活·游记

成都石室，SC-052，校门很有意思

Day1

酒店早饭好难吃。
怎么忘了带吃的。
开T1，花了30min把小样例手磨咖啡出来，然后想到理所应当的背包
我去怎么感觉背包复杂度都有n^3啊
0光一现。
某人向我教授过含siz的树上背包只有n^2?
嘢嘢嘢好像是的
然后就不会了，原因是前后缀的背包合并n^3是真的
咋办呐 想到很早的bitset题用了回退背包，balticoi还是哪里
好像可搞啊
把每个概率逆元处理出来不就可以回退了么

（此处伏笔） 然后开打 10:00写完，小样例调了30min之后一路顺风 \#7跑了1.3s，不妙啊，而且还是个链挂树 果断换exgcd. 快了一倍,0.7s跑完 赛后意识到是因为我的概率从重链长度为1的可能性计算，实则有一大堆0/1，这种东西费马依旧$\log$，ex直接$O(1)

然后还是不满意，毕竟NOIPT1数据那么水，这个#7长得还那么端正
于是加了个优化：单子节点直接继承，链卡不了我了
0.5s啊，感觉挺快的
（我绝对不会告诉你赛后班长说一堆人暴力0.1s我有多绝望）
然后开T2，sub1会的，sub2略想想会DP了
sub3研究0.5h无果
开T3
只会sub1和m=1啊，打完回去继续检查T1，然而无果
结束了。
被外校教练问候了

Day2

更难吃的早饭。
但是家长买士力架了。
梦回WC，但T1咋是真交互
T1研究半天只会 n\log n，然后发现预期太低。
发现没找到新的变化点之前的空位不用定出来，走过去即可。
现在会2n+\log n了，但是必须先找到0
接着发现左右两边不相关，分别跑左右的时候询问区间拉到端点就可以找到瓶颈值，两个方向各做一遍
好现在是 n+\log n，不会了
我去这个石室windows cmd敲 g++怎么没反应
并行两种措施：把grader粘到perm里，用virtual machine
然后去做T2.

$k=3$，想贪心，抓出一个点1改剩下的边，然而并没有想到还可以改边使得1的邻边产生more contribution.理所应当被$n=4$hack了 于是砸2h于T2然后获得0pts 问题在自己吧 回到T1 问题是0 受特殊性质启发发现是找下凸壳 然后突然意识到倒着做也没有问题 会了 从右边倒着找，找到0反向 然而用了$n+2$次 意识到$(0,n-1)$的两次询问不用回答 perfect ~~为啥Day1T1没有意识~~ 突然发现0在最左边我会询问(0,-1)，吓死了，特判然后查其他cornercase 看T3 出题人咋把阅读理解搬这了 深合伟大前班主任对我们做数学应用题的评价： 题干看着看着就看晕了 猜了一波菊花图靠近根更大，打了4pts（1.5k换$[0,4]$，诗人） 好然后完全不会一点 又看了一会T2依旧不会 果断对拍T1 嘢咋个自造30000跑了1min+还没出来 检查checker实现发现 #### 他打的暴力求mex 气笑了 拍了几组3000，过了，不管了 end contest # After contest 高一，但是教练对我没有今年进队的计划，打的心态其实还好 但是3.9中午躺在床上意识到回退背包我只用了最长可能性的逆元 我天我好像把正解打假了 崩溃日常罢了 祈祷少挂点分吧 模拟赛单day次均挂了50+， 咋办呢 Arena,recall,replace recollector考不考虑出道一下？