首先为本人很挫的英语向各位看题看得郁闷的大牛深表歉意。
由于本人能力有限,比赛的筹备一直到赛前30分钟才弄好,并且没有仔细检查题面和数据出现的问题,特别是E题,数据和题面均出现较大问题是本人准备工作没有做到位,还请各位大牛海涵。
另外,十分遗憾的是,原本所出的一道求圆和多边形面积交的计算几何题不小心和武大等校的十校联赛第10场中的某题本质一样,并且已作为训练题给大家练习,所以不得已临时换题,在此特别向补上计算几何题目空缺的Isun大牛表示感谢。
下面简单评述本次比赛,并给出简要解题报告:
本次比赛大部分题目不难,主要解法均为基本算法,部分题目可能需要注意细节,部分题目题面出得有点猥琐。但总体来说,算法覆盖面比较广,没有侧重考哪一方面的算法。所有题目的解法覆盖 搜索、动态规划+线段树维护单调性优化、背包、高精度(或Java大整数的应用)、基本最小生成树、字符串的细节处理、AC自动机、 简单数制转换、计算几何。
其中E、G属于水题,D题可能题目描述没说清楚,抱歉,C题有点小麻烦(Java可能好点),B、F、H属于较难题,A题属于较巧妙题。
在3小时40分钟的时候被电子科技大学的队伍全切了,是命题中的失误。但F、H被迅速解决,A题撑到最后是意料之外的。总得来说他们还是很强的,这里小小的赞许下,基地的队伍也要加油啊。
下面是解题报告,其中F题由Rocket323提供,H题由Isun提供:
A题,整场比赛中很少有人开动的一题,也是AC队伍最少的题。最初一看题,状态数无论怎么算都是一个暴大的数。仔细想想,也只能猜测要达到目标走的步数不会很多,但并不能确定上限是多少。DFSID?经验证数据最多走7步即可出解,7^7大约80万,但题目给出了10000组数据,不出意外的话,应该会TLE。另一个想法是双向广搜,首先最多7步出解这个很难证明,然后双向广搜很难写,然后10000组数据话应该会很悬。其实换种思维方式,如果我们在移动某种颜色的时候不考虑其他颜色,那么这种颜色在魔环中的状态数只有C(20,4),只有4845种状态,这样已经没有状态压缩的必要了,当然如果会写排列数生成,用用也无妨。只要从目标状态开始BFS,把4845种状态到目标状态需要的最少步数求出来,不需要多少时间。而题目所求无非是5种颜色,分别处理取5种颜色里面的最小值就是解了,如果之前预处理了,这里的效率应该只是常数级的。
B题,过得人很多,有些意外。之前写的时候有想过要把某些可能退化到N^2的算法卡掉,后来不记得加强数据了。这题我的做法是,设w(i,j)是从i到j的Value的最大值,那么固定j,i从1枚举到j,w(i,j)一定是单调不上升的,再使用一个队列来处理Point的情况,用线段树来处理值,可以做到NlogN。
C题,枚举的话可能要100^4,加上这题需要高精度,就会TLE。这题我的做法是背包,再写一个高精度。这题用Java的人会比较方便,其实时限如果开小点Java也可能会TLE,这里特意放过的。
D题,可能题面没写清楚,如果看懂了就知道是一个不需要任何优化的N^2的最小生成树问题,需要注意的是在求两个灯塔之间的距离时,如果是用int来求double,很有可能中间值越界。
E题,出问题最多的一个题目,其实是很水的题。当时看到很多人RE,WA,后来一查数据才发现,本来要加入11750个数的一行手误多加了10000个,本题没加特别的数据来刁难人,但还是有很多人在这上面郁闷了。
F题,原本我是想出成AC自动机+状态dp的题的,后来有神牛用了很诡异的方法彪悍的过掉了,看了一下他的代码,貌似是枚举m个不合法的串的组合形式,然后统计?
我的做法是f[i][j]表示目前状态为i,且走到了自动机的第j个节点用多少种方法,然后枚举下一个数字转移,貌似时间不是很好,窘。。。
G题,就是一个简单的数制转换的题目,想清楚本质应该是很简单的水题。
H题,我的方法是:以三角形2为基准,如果
1.三角形1有两个或以上顶点落在三角形2所在平面,则输出NO
2.三角形1恰有1个顶点落在2所在平面,那么(这个顶点在三角形2内)和(这个顶点的对边穿过三角形2)两者恰有一个为真时,输出YES
2.三角形1没有顶点落在2所在平面,那么当且仅当三角形1有且仅有1条边穿过三角形2时,输出YES。
这个题提示大家3D几何的模板也要精心准备。很多AC的代码都很短,应该有更简洁的方法。
===========================
筹备这次月赛,花了不少时间,但也学会了很多东西。
细节很重要,英语也很重要。
预计时间从8月3日一直拖延到8月21日,导致本次比赛不可能在呼喊生日邀请赛,不得不说是一种遗憾。十分狼狈的是直到比赛前半个小时还在测数据是否正确也是导致了某些不应该发生的悲剧发生的原因。
校内最强的kissworld同学精准的提交和高AC率实在让人敬佩。但这次比赛我们过得最多的队伍也只有4题,跟外校比起来确实也是一种差距,大家要加油了。
另外,本次比赛得到了很多大牛的协助,特别向Rocket323、Isun、yh等同学的协助表示感谢。同时也感谢各校牛队的捧场。