【x义x游记】CSP-S2019二试游记

# Day1 文渊怎么这么大啊QAQAQAQ 这种规模的学校简直是窝这种小地方的学生想象不了的啊QAQAQAQ 起码有2个金外吧QAQAQAQ 而且好新啊QAQAQAQ 右手边是杭阿的xhw神仙orz 右手边的对面是@[世墨](https://www.luogu.org/user/68824) 同校神仙orz 在考场喝了几口维他柠檬茶再发了下呆就开考了…… T1看了一下，sb题切了。 T2看了一下，马上可以想到根据右端点找左端点。设对于一个右端点``u``，以它结尾的合法序列有``ans[u]``个。然后可以发现一个右括号有且仅有一个左括号与它配对，这个很好找，开个可以撤销操作的栈就好，设当前右括号为``u``，配对的左括号为``v``，那么``ans[u]=ans[fa[v]]+1``。于是$\Theta(N)$切了。 中间还脑抽写了个堆……9:30的时候写完过了所有样例（出题人怎么当众恶臭啊）。 然后去上了个厕所，移动厕所太尴尬了QAQAQAQ 接下来是sb操作了……一开始我以为我能切了T3，后来我以为我能写菊花部分分，然后我以为我能写链的部分分，最后暴搜都来不及打了……（其实还有半个小时完全来得及，但是我心态已经炸了） 最后半个小时一直在自闭。反复检查文件名，文件操作，调试删没删，数组开小没有等sb问题。 考试结束前5min，突然发现我T2还没拍QAQAQAQ我tm是睿智吧QAQAQAQ 然后考试结束。出来和各位大爷交流了下想法。貌似人均210？我200傻逼炸了QAQAQAQ 为什么不写T3的10分呢……可能我tm就是这么一个傻逼吧。 然后吃了一顿文渊食堂。餐盘放上去就能读出盘子里菜的价格的科技好强啊qwq又和大家交流了一下。听说zzy说今天T3比保卫王国难？ cnm那我还死磕T3 在大巴上还在拼命想自己T1T2挂了没有…… 然后发现自己T1给``K``开了``ull``但是我的代码里有一句``1LL<<(N-1)``…… 完了.jpg T2他们说大样例很水于是我更慌了QAQAQAQ 回了机房打了一下T1，发现竟然可以过？原来是出现``1LL<<(N-1)``的地方都是``K>=(1LL<<(N-1)),K-=(1<<(N-1))``这种，于是``ll``就被转成和``K``一样的``ull``了。也过了luogu数据。应该也不会在CCF机上出问题。 然后就开始颓以撒颓到了晚上QAQ，吃完晚饭写了这篇游记的Day1。 希望T2不挂吧。T2挂了我就真退役了。 估分100+100+0=200。 # Day2 普及小朋友怎么吃个蛋糕吃得满键盘都是啊草 T3开场打了个N方暴力和链的部分分。sb操作：没有去看完美二叉树的部分分。这20分好拿得跟sb一样。 T1康了一会，想了一个$\Theta(N^3M)$的DP，发现有84分就去写了。sb操作：没去把这玩意优化成$\Theta(N^2M)$。只需要把两维压成它们的差值，简直就是普及内容却没想到。 然后死磕T2。胡了一个结论：从$N$开始倒退，不断分尽可能小的组。于是把以每个下标结尾的最小的组的大小DP出来就好。即： $$F_i=\max_{S_i-S_j\ge F_j} S_i-S_j$$ 然后容易发现每次决策的$j$递增。然后我还是不知道怎么维护……写了一个记录上次决策点$j$，每次暴力扫$j$到$i=1$的思博玩意，目测可以卡到N方，但是随机能过5e5。然后发现可以线段树，**但是没写**。考试结束前15分钟发现可以单调序列，**但是没写**。 我tm脑子里在想什么？不写高精你88都拿不到吗？线段树确实难调，但是单调队列难道你都调不出来？ 然后开始扫雷。扫雷？？？在？有这点时间为什么不去想T1，写T2？ 估分84+64+55=203。运气好的话227。两天总分403/427。 对于本届CSP的评价？可以康康[这里](https://www.zhihu.com/question/351347604/answer/896421398)。 我可能需要修一下脑子，哦，我好像没有脑子，先去装一个脑子吧。 pku和thu的冬令营？大概稳定去不了了吧。两天都是略低于大众分去个毛啊。 zblzbl # Day3 玩了一天Minecraft。 # Day4 玩了半天Minecraft和半天以撒。 选手程序公布。把自己的程序交洛谷的时候心都快跳出来了……一看D2T1怎么爆0了草，心如死灰……草原来是忘删freopen了，丢人了丢人了 测完427？竟然一分没挂？ 拿[数据删除]的数据又测了一下，418~427，发现是D2T2的那24分能拿多少得看评测机心情。顿时很慌。听说毛爷爷要卡？？？那我完了/dk 似乎pkuwc稳了？也许如果D2T2放我过的话可以去thuwc？ [hehezhou](https://www.luogu.org/user/67371)神仙依然稳健，到哪里去测都是498大爷 [Loveti](https://www.luogu.org/user/53807)两天T2炸了，D2T2莫名RE，到现在都不知道原因，惨惨 [蝳队](https://www.luogu.org/user/68085)D2T1数组开小了，~~痛失阿克~~383->351 反正等最终成绩吧草 # Day ? 最终成绩403 =.=