2021 暑假集训(福建师大附中)

Day 1

模拟赛(上午)

早上要排练毕业典礼上唱的歌,空闲时和另一位同学 Linshey 在场外想题,时代中学的同学在毕业典礼也没去。

看 T1,一眼觉得 DFS 一遍然后跑个 DP 就很正确的样子。

然后想了挺久都没 Hack 掉就觉得很稳。

看 T2,立马想到一个 (O(|s|^2)) 的暴力做法,然后一直没有进展。

但是它数据随机就希望多过几个点(

后面在地铁上想了想 T3,完全没有思路,只会巨难写的模拟,发现只有 (12) 分……

(12:30) 左右到了附中,发现还有一个小时左右的时间,就写了下 T1,然后把自己拍出错来了……

最后一题没交,而 Linshey 如此快速地写完了 (3) 题,拿到了 (15+70+12=97),排在 rk 4/9。

讲评(下午)

这套题是 PinkRabbit 出给山东省选集训的题(

T1 思路好像差不多,就构造方案想错了一点(怪不得拍出错来了)。

然后还有个另解,就是让叶子节点对应一个区间,然后跑最小生成树就好。

非常神秘的做法(((

T2 暴力就这么做可以拿到最高 (85) 分的好成绩!

然后加上个随机化可以卡到 (95) 分!

实际上仔细考虑一下这 (n^2) 个变量的最大值,发现期望值和 (m) 很接近。

于是暴力 check 一下即可。

T3 后面没听(

专题选讲——图论

咕咕咕……

Day 2

模拟赛(上午)

自闭了……

看完题发现一题都不会(

T1 想了挺久才发现是个上下界网络流。

写完板子一直调不过去,搞到了 (10:30)

仔细一想,这复杂度越看越高,能过的分在 (40) 以内……

然后觉得要 CSP 重演了就把 T1 弃了。

但是想后面的题时脑子很乱,T2 只会 (15) 分的做法,T3 看完题完全没有思路……

吃饭的时候心情挺低落的……

最后还是没有什么成果,T1 就交了个 puts("-1");,T2 就只交了 (15) 分的暴力……

评测的时候 zzr 说他没垫底就 nz,然后我比他低了 (1) 分,只有 (8+15+0=23),排在 rk 13/13。

成功垫底……

Day 3

模拟赛(上午)

毕业典礼,没去,也没想题。

Day 4

模拟赛(上午)

想着今天要考好点,弥补 Day 2 的失误。

看到 T1,发现很有意思,觉得见过类似的题。

想了一会,还是只有 (10) 分的枚举 (operatorname{lcm}) 的做法,但是卡卡常好像可以卡到接近 (50) 分,就去写了。

写完不过才 (8:40),还有大把时间给后面的题。

看到 T2,发现是字符串题,直接自闭……

想了半天只会暴力,然后还只有 (10) 分,就先等着。

看到 T3,发现了特殊性质:(2leq d_ileq 3),那不就变成了数学味道的构造题了嘛。。。

于是很快乐地去想,不久就想出了个看上去很正确的 DP 做法。

中途去上厕所的时候,Linshey 说这个做法他 Hack 了,但是忘记怎么 Hack 了。

于是很慌,但是由于代码似乎不怎么难写,就先写了。

写完改了好久过不了大样例,觉得这个做法真的假了……

后面发现有个地方忘开了 long long,加上后就过大样例了(((

不过空间复杂度是 (O(n^3)) 的,还过不了 (nleq 1000) 的数据,就很烦。

但是对于 (92\%) 的数据,(nleq 300),于是就不管它了。

最后交上去评测,拿到了 (30+0+92=122) 的成绩,排在 rk 5/9(有些人因为都没写出正解就没交代码了)

总体上感觉还是很不错的吧。

Day 5

模拟赛(上午)

最后的一次模拟赛了。

开题发现竟然有 (4) 题,然后 PinkRabbit 说 T2 不用交,只测 T1,T3,T4。

觉得很迷……

看到 T1,一眼就会了 (40\%) 的做法。

然后觉得正解很可做的样子,就在草稿纸上推了推规律。

发现循环节个数貌似不多的样子!

先快速写了份代码验证了这个思想的正确性,于是就以为有了 (O(3^8+Tn)) 的做法。

写代码的时候发现有点不对劲,好像 (3^8) 要放在 (n) 的循环里面,没办法预处理,然后时间复杂度直接 (O(3^8cdot Tn))……

就觉得很自闭……

于是重新推了推规律,发现根本不需要 (O(3^8)) 地去枚举,直接手打出 (33) 个本质不同的循环节就好了。

时间复杂度只有 (O(34cdot Tn)),非常正确的样子!!!

写完后不知道怎么对拍,就先放一边,时间到了 (9:00) 左右。

然后觉得很稳,就去上了个厕所,碰巧遇到了 Linshey,他说 T1 他是 (O(3^7cdot Tn)) 的做法,加了个剪枝就跑不满了。

仔细一想,好像确实……(但是我的做法显然更快的样子)

看到 T3,一眼有了 (10) 分的做法,然后感觉卡卡常可以到 (30) 分,但是后面的特殊性质和 (nleq 3000) 的部分分看上去很可做。

于是就先没写,但是想了挺久也不会更多的分数了……

想着先看 T4,毕竟已经有一题保底了,心态上也比较好。

看到 T4,一下子没有什么想法,想了一会儿才有了 (10) 分的思路。

后面对着特殊性质想,无法理解特殊性质的用意何在……

去上了个厕所,脑子一抽,发现这不就是个网络流题嘛?

仔细一想,觉得没有什么问题,一看数据范围,发现只能过 (40) 分,就很遗憾……

然后往着特殊性质上去靠,发现可以缩点,然后就会了。

刚开始码时,Linshey 十分震惊,问我真的会 T3 了吗?

我给他讲了下大概思路,可是他好像没听懂(

写完代码差不多 (11:00),然后回头发现 Linshey 也在码 T3 的网络流,看来他也是会了。

转念一想,我这种蒟蒻竟然都做出来了 (2) 题,那其他人不是要 AK 的节奏吗???

于是马不停蹄地开 T3,飞快地写了个 (10) 分的暴力,然后还挂了,调到大家都去吃饭了才调完……

吃完饭开始 generals,和那些弃赛的人打 2V2,胜率大概 (50\%) 吧……

然后 Linshey 和我交流了一下做法,基本上都相同,就 T1 有差别,感觉很不相上下。

评测时,Linshey 先测,我在他后两个。

发现 Linshey 的 T1 挂了 (10) 分,感觉要赢。

然后他的 T2 拿到了 (25) 分,又觉得很慌。

接着就测到我了,发现 T1 很稳没挂,T2 真就只拿了 (10) 分,T3 也稳。

最终是 (100+10+100=210),排在 rk 3/13。

比 Linshey 少了 (5) 分就非常气……

原文地址:https://www.cnblogs.com/kebingyi/p/15028434.html