联合省选 2023 游记
前言
noip T3 大样例一条链加上T4没取模被送走了,比队线低了 100 pts 左右。
希望能冲个C
Day 0
坐火车去南京,到宾馆开摆,没打板子。
下午试机,我校 fft 的蝴蝶变换都写错了(
吃晚饭时我和 yuyue 奶明天会考网络流。
吃饭时, sgc,yy,wxq都吃了芥末味的鱿鱼,我没有吃,zhk和zyx都没和我们一起吃。 (flag1)
Day 1
8: 30 开题,先花了 10 min 看了题面,发现 T1 不是很难,但没有一眼秒,T2 应该是圆方树,但是不太会,T3 感觉很典, 一眼看出费网络流模型,直接从大到小贪心就是对的,然后看出 hall 定理,接着看出 线段树分治。
T3 不会这么简单吧,5 min就做出来了,那我不是没救了。想想细节,先冲个T3,希望不会调很久。
40 min later
好像快写完了,先去上个厕所,冷静一下。我仔细一想感觉1h写T3,1.5h调T3,0.5h写T1,剩下时间写T2暴力,应该能翻一点了。
写完后测了一个T3样例,调了几个线段树的bug,发现就过了,当时十分震撼。看了一眼时间发现才9:45。感觉AK 有望。(flag2)
回去重读一遍T1,感觉可能会了,开始码码码,结果调了很久10:10左右才过。
还有3h左右,大概可以有1.5h左右时间想正解。我先写了一个圆方树板子,调了一调,应该对了。
自己手搓了几个数据,我发现了一个假的规律,我以为只要在圆方树上选若干点就行。先写了一个假的k=0,发现居然过了样例,我以为它对了于是去冲k=1,发现小样例就没过,经过小小的手玩,发现假了。心里慌了一下,自己又重新手造了几个小样例,发现可能是要选一个连通块的点,并且一个点双要么选一个,要么全选。
我先改了改k=0,发现仍然能过样例。再改了改k=1,发现仍然过不了大样例,我发现已经11:30了,权衡了一下,准备开始冲暴力,先写一个
出来的时候,听见tzc说T2很简单,出来的时候,遇到zyx。听他自己说 T2 假了,T3 写的暴力,感觉比zyx高了一点点,明天估计还要再翻50。
Day 2
开场看T1感觉很hard,看到数据范围发现是大模拟搜索,就先跳了,看一眼T2感觉又是网络流,看眼T3发现是DDP,我想了一下T3发现10分都不会,就先跳了,前40 min在看T2,和写T1之间反复横跳,结果啥都没干。
发现过去了40min,于是开始冲T1,写写写,过了1h后终于写完了,开始了恶心的调题,调了30min,崩溃了,于是犹豫着要不要重构,大概过了10min,开始重构。过了40min重构完了,又调了15min终于跳出来了,中间还遇到了一个很离谱的错误unordered_map一直TLE巨慢,大样例都出不来,于是换成了手写。
已经过去了3h,于是开始冲暴力,先写了一个网络流check T2是否合法,在写了一个指数级暴力,发现自己读错题了,改了改才过。此时大概还有50min,先去看了看T3,写了一个第一问假的DP,于是删掉写了一个puts("1 0")感觉要没分了 flag3。
回去看T2,发现是基环树和书,但只有20min了,于是开摆,回去查了查文件。
flag1: 吃鱿鱼的好像都寄了。
flag2: 我 CSP 写完T4 也是这么想的,结果没过T3,T1还fst了。
flag3: 有 1 分