出题人没发题解,于是我(lydrainbowcat)来简单说一下前两题的做法:
比赛开始后大概2小时,我上来发现做的人不多,鉴于我事先没有看题,于是也来做一做好了。
第一题
题如其名是一道送分题,不仅仅体现在其正解送分,更体现在出题人50000的数据实在是太藐视我站的评测机了……
我写了正解,对mod 6的六个剩余类分别维护一棵线段树,这样就只有加一个数、询问最大值、求和的操作了。比赛过程中我的代码921ms应该是最快的……
SJY(VariantF)果断O(n^2)暴力,5s+时间垫底同样AC此题……
第二题
后两题就不是那么简单了,这道题思想比较水,写起来比较麻烦。
可以根据编号相邻的关系建一张无向图,然后从给出的四个角开始各BFS一次,得到每个方块距离四个角的距离。
通过这四个距离就可以算出每个编号方块的坐标,于是就复原了……
然后建立a*b+a*c+b*c个set,维护每条线上的炫教(位置单调排序)
这样就可以通过寻找前驱后继找到各个方向上最近的炫教,判断两个颜色是否相同以及炸掉(删除)就很容易了。
至于最多能炸多少个炫教,就做一次类似于拓扑排序的过程。把所有能一次炸掉的“炫教对”扔进队列,然后开始bfs,队首炸掉以后就枚举12个方向上距离最近的炫教的颜色,判断这些颜色的“炫教对”现在能不能一次炸掉,如果能的话就扔进队尾。最后输出就好了。
第三题
喜闻乐见的烧卓亮游戏。
题目我没仔细看,因为本来我就晚参加2h,第二题又一直写到比赛结束也没弄对(实在是太™丧心病狂了)。
感觉是利用离线性质+后缀自动机/后缀数组来搞……
做了这题的童鞋在版聊发一下做法吧,然后我粘上来。
以上。