CH Round #43 - 那些年我们一起参加过的ZJOI2014

OI - Official

From fcuk_zjoi_2014


小时

尚未报名

送分题 19/67 From
炸炫饺 1/4 From
烧捉凉游戏 1/7 From

出题人没发题解,于是我(lydrainbowcat)来简单说一下前两题的做法:

比赛开始后大概2小时,我上来发现做的人不多,鉴于我事先没有看题,于是也来做一做好了。

第一题

题如其名是一道送分题,不仅仅体现在其正解送分,更体现在出题人50000的数据实在是太藐视我站的评测机了……

我写了正解,对mod 6的六个剩余类分别维护一棵线段树,这样就只有加一个数、询问最大值、求和的操作了。比赛过程中我的代码921ms应该是最快的……

SJY(VariantF)果断O(n^2)暴力,5s+时间垫底同样AC此题……

第二题

后两题就不是那么简单了,这道题思想比较水,写起来比较麻烦。

可以根据编号相邻的关系建一张无向图,然后从给出的四个角开始各BFS一次,得到每个方块距离四个角的距离。

通过这四个距离就可以算出每个编号方块的坐标,于是就复原了……

然后建立a*b+a*c+b*c个set,维护每条线上的炫教(位置单调排序)

这样就可以通过寻找前驱后继找到各个方向上最近的炫教,判断两个颜色是否相同以及炸掉(删除)就很容易了。

至于最多能炸多少个炫教,就做一次类似于拓扑排序的过程。把所有能一次炸掉的“炫教对”扔进队列,然后开始bfs,队首炸掉以后就枚举12个方向上距离最近的炫教的颜色,判断这些颜色的“炫教对”现在能不能一次炸掉,如果能的话就扔进队尾。最后输出就好了。

第三题

喜闻乐见的烧卓亮游戏。

题目我没仔细看,因为本来我就晚参加2h,第二题又一直写到比赛结束也没弄对(实在是太™丧心病狂了)。

感觉是利用离线性质+后缀自动机/后缀数组来搞……

做了这题的童鞋在版聊发一下做法吧,然后我粘上来。

以上。