Day -1(10.27)

运动会,本来打算第二天出发,结果当晚晚读刚结束就走了。

于是坐大巴。

车上,吃运动会时剩下的运动员福利:吮指原味鸡。

Day 0(10.28)

0:47,抵达酒店。然后同学开始打 CSGO 我开始激情 AI 作图。

2:00,睡觉。

起来先去做了个核酸。中午进行了贵族餐品的吃。

晚上吃火锅。前后打了几把狼人杀,感觉很猛阿!

Day 1(10.29)

起来以后讲解了一下 CSP-S2021 T4、平衡树 以及 单源最短路,很困,全程在水群。

中午吃盒饭,然而发现我没有带帆布袋。

大家很激动,想要面基,结果就帮一个老哥带了瓶水。


激动,14:20 到考场,然后开始看题!

先看 T1 阿,感觉很奇怪。于是开始试着写。

令 dp[i][j] 表示路线上第 i 个地点是 j 的最优答案,然后 O(kn^2) 预处理一下就可以开始转移。

测了下样例,发现读错题了,不能重复,浅维护了一下序列,虽然感觉很不对,但是一发过了小、中样例,就不管了。于是小的暴力,大的暴力 dp。

这时已经 16:00 了,而我刚刚拍完 T1,拍了 2w+ 组,感觉挺舒服的。于是开始 T2。

看完题我感觉很牛逼,因为我一眼 ST 表/线段树,然而我都懒得写。

再看了一下发现要分正负维护,好牛逼啊我草。

于是我觉得我很牛逼地想出了一个只维护 B 的做法,感觉是 O(qn\log m) 的,很正确。于是马上开始写,大概 40 min 完成了工作,对拍无误。

突然发现数据范围是 10^5,不敢乱写了!老老实实地写了个维护 A 的。

本来要分讨拿出下面 5 个数的:

  • 最大(小)正(负)数 和 0(特判)

后面一想,懒得分讨,最优答案必定出在它们之间,全部扔了出来。

时间复杂度 $O(wq\log n\log m)$,其中 w 约等于 4.5。

写完,17:30,拍了 1.6w+ 组,感觉很正确,不管了。

还剩一个小时阿,看完 T3T4 用了半个小时,剩下感觉只能莽 T4 暴力了。

然而我写的是 dfs 而不是 bfs,令人感叹。最后摆了,懒得写了。


回来车上吃了肯德基,测了一下:

  • Luogu:100+100+0+0=200
  • InfOJ:85+100+0+0=185

睡觉。

Day 2(10.30)

已经开始返校了。

【更新】 计蒜客:100+100+0+0=200

Day 3(10.31)

InfOJ & LHQ 测试:100+85+0+0=185,全省 rk19。