CSP-S 2019游记

下午到了广州，酒店还不错，不好的是附近没有什么吃饭的地方

zyd和ljz巨神说如果上了450就女装。

晚上看了一下写过模板，本来准备敲几个新模板的的结果被卡常，心态没了。于是又把wys的卡常技巧ppt和一些巨佬总结的策略看了一遍。

希望明天的题目不要太多思维题

早上进考场，密码一开始输错了以为是自己手残，后来发现是监考老师写错了。

打开压缩包看到T1格雷码，一开始以为要自己找构造每一位不同的规律，后来发现直接模拟就好了。写了\(O(\log k)\)级别的递推，大样例样例一次过。突然想起来可能会溢出，改成unsigned long long，应该不用高精度吧。

T2一开始以为直接用栈做括号匹配就可以了，后来发现会被(()())这种数据卡掉。然后就写了个\(O(n)\)的dp，每次回溯时撤销对栈和dp数组的修改。大样例有点水，和暴力对拍了半个小时没出问题，希望能过。另外，大样例3唐突恶臭。

写完T1,T2还有一个半小时,看T3题面看了很久才理解题意，又看了一下样例，手玩没玩出来有点自闭。于是先敲了个\(O(n!)\)的暴力。然后试着打了一下菊花和链的情况，发现由于一个数可能被交换很多次，前面对后面有影响所以写的很孙。最后链的情况写挂了，菊花图的贪心也和知乎上出题人说的不一样。题解

下午先是把写过的一些好题(主要是博客里的题解)看了一下，然后去附近的中山纪念堂逛了一圈。晚上在酒店吃饭，回到房间感觉有点颓，写了一发数据结构模板就开始水群了。

T1原地爆炸，因为忘了可以做差dp数组多了一维，写成\(O(n^4m)\)了，期望得分64

T2一开始推了个dp，看起来很像斜率优化，搞了0.5h左右发现样例过不了。后来发现可以用线段树优化，\(O(n^2\log n)\)期望得分64,过了前几个大样例。一出考场lhx巨佬说随便贪心水80分，凉凉。

T3打了暴力，以及链和满二叉树的部分分，满二叉树似乎写挂了？

回家的动车上心情复杂

巴特西