0%

icpc22南京 replay

由于疫情原因,本次南京站由 \(\text{J}\color{red}\text{BY}\) 一人单挑,最后取得金尾的好成绩,本篇总结由 \(\text{J}\color{red}\text{BY}\) 一人完成。

ICPC南京小记

无营养的题目记录

A(转变操作顺序)

先把不管洞会走出边界的去掉后,只需要枚举每一个位置看有多少个会走到里面去就是了

B(DP合并)

不带修改的话直接暴力找最小,用单调队列可以线性。考虑修改,因为 \(k\)\(q\) 都很小,直接暴力修改那附近的 \(k\) 个然后拼接左右拼接就可以了

D(二分答案/主席树)

二分答案,然后先看每一个判断一下,然后枚举每一段加,那么对于其实位置为 \(i\) 的那一段 \(a_k'=a_k+(k-i)d+c\geq t\) 的,发现是 \(a_k+dk\geq id+t-c\),一开始建出主席树找数量就是了

E(虚树/线段树合并)

赛时:显然每一层的的答案之间互相独立,对于每一层所有节点建出虚树后暴力DP

赛后:DP直接可以用线段树合并对于所有的深度一起维护

G(贪心)

手算一下发现合并操作比取的操作优,那么直接贪心对于每个0能合并就合并,判断只需要预处理一下前缀和即可。

I(签到)

完美回文是全部一样,直接找最多的换就可以了。

考场小结

考场做的比较好的地方是心态比较稳,一开始过题比较快,也先判断了M不是自己擅长的题先跳了(后来看题解发现就有一点没判对),直到后面卡M挺久心态才比较蹦,再加上这次疫情原因很多队也缺员,还有中文题面大大加快读题速度最后罚时苟了个金牌。

做的不好的地方就是有几个

1.没有做出来M后比较急,虽然M是一个分类讨论的题加一个几何的背景,本身不是我擅长的题,但是这么多人过,确实应该想想哪里有漏洞,想个好方法讨论好一点,希望之后有队友能够帮我解决这方面的问题(当然自己会尽量增进这种题的水平)。

2.还没完全想清就还是开写了,E和M都有这个问题,虽然E对我来说是比较简单的题,所以我还是过了,但是假如我想清楚一点,不选择我讨厌的虚树,而是直接使用我喜欢的线段树合并做法的话,码量和我调的时间都会少很多。而M就是因为自己不擅长加没完全想清楚所以最后虽然过的人很多却依然没过。

3.作为高中时期不会做图论题的图论手(队友图论都是更菜),这次没有做出图论题,还是需要在多连连,图论的奇怪玩意儿很多,我就会一些很常规的,需要去总结一些另外的题的方法。