CSP2019 游记

# 初二蒟蒻的CSP游记 --- --- --- ### Day1上午是S组 --- --- #### 8:25开题，通览全卷~~发现都不可做~~ --- #### 先写T1 想了5min，写了个分治。看到数据范围，果断开了ull ~~为了方便 把k++，还是丢了5分，多么睿智~~ 15min时写好 ~~样例2都没过~~ 改到9:00，终于过了大样例。 试了下64 0，就跳过了。 --- #### 然后是恶心T2 看了10min，有了点思路。又想了10min，决定用DFS+栈。 码了20分钟，样例二没过。手动对拍 ~~（手捏数据）~~ 后发现错误。改了，还是没过。emming... 10:00，放弃原来代码，重构。 10:30，再次码好。试样例2，~~再次~~没过。 手动对拍，找不出错。 11:00，ZIxijianCHA代码，发现 ##### 全局数据没还原！（划重点！！！！）。改了一下，样例二终于过了。试了下样例三，崩溃了 ~~如心情一样~~ 调了一会，觉得是爆栈。改了下，还是爆栈。emming... 11:20，正式放弃（希望测评时栈够用 ~~强行甩锅~~ ）。 --- #### 接着是没时间做的T3 看题目到11:30，上厕所 ~~找灵感~~ 先想链，后直接码了个DFS，结果第三组小样例挂了。 --- #### 检查文件名，就滚粗了。 ---- #### 估分：100+（50~80）+（0~10）=150~190 #### 民间数据（oitiku）：95+100+0=195 （T2真是神奇） --- --- ### 下午是J组 --- --- #### 14:25 开题，觉得除了T1都不会。 --- #### T1共用3min完成 --- #### 然后看T2 一开始觉得不可做，直到看到这句话 ##### 且不会有两次乘车记录出现在同一分钟 然后5min切了 --- #### 接着是T3 想到%你赛中做过的贪心，似乎就是n=1的版本。 推广一下，就想到了完全背包。 15:00时码完 --- #### 然后是T4 看题，觉得像拓扑排序。想了一会儿，就是问能否使1~a距离为L。 ~~我个睿智竟然想到了bitset~~ 之后手捏了几组，发现只要有路径与L奇偶性相同且小于等于L就行了。 考场想到了某个死了的算法，觉得边权为一应该不会被卡，就写了。 15:45分，用SPFA-PLUS过了。 --- #### 检查了几个小时文件名，终于结束了 #### 估分 100+100+100+100=400 #### 民间数据（oitiku） 100+100+100+100=400 --- ### 总体Day1发挥不错，期待Day2表现 --- --- ### Day2来了 --- #### 8:32开题 --- #### 先想T1 推式子15min无果，码了DFS 炸了~~Wrong On Test 2~~ 看了下数据范围，就码了个针对m=2和m=3的DP，测了大样例1，手捏m=2样例，就过了。 后发现有64分，欢呼雀跃。 时间：9:35 --- #### 接着码T3 正解~~当然~~不会，先写了个链，然后码了个40分n^2。 ~~我个睿智差点不会求树的重心~~ 调了好久，终于过了。手捏了链的情况~~眼瞎没看见大样例~~，也跳过了。 时间:10：45 --- #### 然后是T2 先写了贪心1，Wrong On Test 1 后改成贪心2，Wrong On Test 2 然后想出了答案正确的贪心加DP，64pts get 时间：11:15 觉得还有时间，肝一下88pts能上400，就想了下nlogn的优化。 先写了个二分，不知道是写锅了还是没有单调性，Wrong On Test 2 后想到了堆优化，边码边调，88pts get 时间：11:45 想到了单调队列优化，发现爆空间+高精烦+时间不够，滚粗 #### 检查了下，就交卷了。 #### 估分：64+88+55=207 #### 民间数据（oitiku）：64+88+40=192，两天共387 #### 话说链的部分分数组开小RE可海星 #### 滚粗 ### 对于初二蒟蒻，387已经可以。但是没上400有些遗憾，省赛或明年CSP继续努力。 --- --- --- #### Update 11/23 #### 今天用源代码测了下，J组T4洛谷95（忘特判），其他OJ都AK了，希望CCF不毒瘤。 #### 听别人说AH的S组某网站民间数据成绩，我392（T1莫名100）rank25，很满意了。希望不出岔子。 --- --- --- #### Update 12/1 #### 官网成绩出了，J组400，S组387~~和估分一模一样~~，希望rank好看一点。