CSP-S 2019游记

Day 0

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

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

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

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

Day 1

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

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

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

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

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

Day 2

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

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

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

回家的动车上心情复杂

原文地址:https://www.cnblogs.com/birchtree/p/11869645.html