PKU2011ACM校赛总结&简要解题报告





昨日和wrj组队去打PKU校赛,本来觉得队内阵亡一人(有事出差)之后,应该元气大伤,却出乎意料的超常发挥,拿到了很不错的名次。准备按照当时的做题顺序一一记录一下每个题目的思路,希望对同去参加的其他队伍有所帮助。
题目链接在此http://poj.openjudge.cn/campus2011/
昨日比赛延迟半个小时开始,9点半正式开始后,发现发下来的题目居然只有一份……于是只好撕开题目各自看。
J题
此题可以首先分别扫描三个aspect,然后统计出每个aspect的最小值,再重新扫描一遍每一个team,如果该team的三个aspect都等于最小值,则计数加一,最后输出总的计数即可。复杂度O(n)。此题开场后10分钟内即顺利1y(经赛后讨论,此题我们可能理解错误题意,估计当时比我们更快AC的队伍都是理解错了题意吧……我们AC的代码赛后提交已经不能AC,并且该题目在比赛时被rejudge过,还好有规矩AC的题目不能rejudge成错的)
A题
过了J题后发现A题通过人数较多,此题讲的比较绕,看了半天才明白怎么回事,好在输入是按照时间顺序给出的,节约了不必要的麻烦。首先读入每一个时间即对比和上一个读入的日期是否相同,如果相同则放到一组继续读入,如果日期有更换则可以处理之前读入的日期的所有数据。把同一日期的所有时间都转换成秒便于处理,然后首先检查是否有morning exercise的时间,如果有则该项计数一次,然后O(N^2)复杂度检查是否有两个half-hour exercise的时间并且间距大于1800秒。题目并没有给时间的个数,当时看了一眼状态发现其他AC的队伍里面几乎没有TLE的,所以果断用最简单的办法。此题也比较快的1y,只是理解题目耽误了一点时间。
C题
做完A题后,wrj说B题和C题都可做,并且现场也已经有较少的几个队伍通过了,当时C过的人还更多一些,并且C的思路相对更容易一些,所以转去做C题。C题就是给定一个词典,一个起始词一个目标词,要计算从起始词开始每次改变一个字母成为字典中的另外一个词,直到改成目标词一共至少需要多少个词。此题同样由于发现通过的队伍较多且较少出现TLE,于是果断使用map去写。首先把词典读入数组并且也放入map,然后检查词典是否包含起始词和目标词,如果不包含直接输出-1(不清楚是否有这种数据),然后从起始词出发做BFS,做BFS的时候方法是枚举该词需要修改成什么词,也即枚举要修改的字母位置以及要修改成的字母,然后用map检查字典里是否有这个词。复杂度是O(N*26*logN*字符串最大长度),此题也是1y,根据提问区的管理员回答,字符串最大长度不超过100
B题
此时发现B题是全场过的人比较多的了,转去做B题。首先先随意指定一个根,建树。如果换根的话,受到影响的只有从原来的根到现在的根这条路径上的点,其余的点结果不变。于是需要扫描一下这条路径,极端情况下其实复杂度还是比较危险的,要达到O(NQ),不过还好PKU的服务器速度不错,顺利1y
H题
此时已经四个1y,信心大增,可惜下面跟风转做H题的时候没有继续1y。此题是单纯模拟。首先按照比赛之间的从属关系建树,注意题中说输入中一行是两个比赛的时候,表示一个比赛直接从属于另外一个比赛,但是并没有说是后一个比赛从属于前一个比赛,所以是没有顺序关系的,我因此WA了一次。需要建立双向边,然后根据1点是final建树。然后树上的每个比赛节点存储参加的队伍编号。于是可以从1号节点开始DFS,每次搜索计算出实际可以参加本次比赛的所有队伍(包括由其他比赛晋级来的),并将队伍由强到弱排序。此题WA了一次后AC
F题
我在写H题的时候wrj一直在算F题,不过因为是立体的,可想而知画起来还是有一定难度的。由于此题N最大到10亿,因此觉得必然需要在纸上推导出个公式。由于此时除F题外没有明显可做的题目,所以我打算做点辅助工作。wrj已经大致对题目有点了解,基本上2*2*n的结果可以从2*2*(n-1)的结果推出来,也就是说用DP的思想可以算出结果。于是我让他猜一下递推公式的形式,他说大概是两个dp数组:dp1,dp2,然后dp1[n]+dp2[n]就是输入n的输出结果,而dp1[n]=a*dp1[n-1]+b*dp2[n-1],dp2[n]=c*dp1[n-1]+d*dp2[n-1],其实需要两个dp数组也可以理解,因为状态转移的时候有四个插头和有两个插头的转移情况应该是不一样的。于是我利用题目给的输入10输出221542这个样例数据和wrj猜测的递推公式形式,枚举参数a,b,c,d,发现有唯一的一组四个都在10以内的整数参数可以从n=2顺利推出n=3和n=10的正确结果。当然n=1和2的时候属于特殊情况,不应该用递推公式。于是由于状态转移矩阵是2*2的矩阵,需要使用二分法计算矩阵的N次方。此题顺利1y,不得不说此题完全靠的是比赛经验,而不是严谨的推导。此题需要使用long long。
D题
此时发现D题和G题都大概可做,但是都没有明确的思路,D题当时我一根筋了以为DP的时候状态转移需要枚举三个人的位置,所以是O(N^3)的空间复杂度,会超内存。过了好一会才明白原来只需要枚举两个人的位置,因为状态转移从i-1到i的时候,第三个人的起始位置一定是在i-1处的。因此只需要O(N^2)的空间复杂度和O(N^3)的时间复杂度。由于DP的时候已经需要到三次方复杂度,因此求任意两点间最短路直接用Floyd就可以了,不需要用Dijkstra。DP的时候按照1号城市到N号城市的顺序,状态转移只需枚举三个人是哪一个走到新的城市的就可以了。此题顺利1y
G题
剩下时间已经不多,我们纠结了一会G题和E题究竟去做哪一个,然后还是屈服于过的人数更多一些的G题。G题如果考虑给每两个不能一起选择的苹果树之间连一条无向边的话,问题就转换为从一个顶点带权的图中选取若干顶点,他们互相两两独立(没有边),并且顶点权重和最大。一开始想到了网络流,然后又觉得如果顶点权重都是1,这就是最原始的最大独立集问题,应该是NP难的,对于N=3000的情况怎么可能短时间内有解呢……于是猜想图必须有特殊性,否则对于一般图那是绕不开NP难的。根据题中的描述,必须是互质的勾股数之间才会有边,直观上就觉得应该边非常非常少,但是少到什么程度呢?于是我大胆猜测这个图是一个森林,应该是不存在环的。时间还有40分钟,我们就去尝试这个猜想了,如果猜想正确,题目应当可以利用树型DP解决,从每个树的顶点开始搜索,假设必须选择顶点和必须不选择顶点两种情况分别进行状态转移,维护两个DP数组即可。提交后RE,发现是没有初始化,加上初始化之后WA了,我们很高兴……因为如果猜想不正确,应该会TLE才对。由于题目用到long long,wrj提醒long long输出是要用%lld的,我之前以为是%I64d,然后翻了一下OJ的帮助,发现果然是%lld,修改后提交AC。猜想还不知道如何证明,此题能过纯属RP。正规做法详见此日志下面Roba大神的评论。
E题
此时还剩下大约20分钟,剩下E题和I题,过的人都不多,我们I题完全没有思路,E题稍微有一点思路就继续想。题目大致是说需要在一个树上寻找从每个顶点出发的第K短路。第K短路的一般算法用在这里的话复杂度是O(N*K*logN)的,如果K取最大的情况,必然超时,于是应该利用树的特殊性。我们发现题目中说树的深度不超过30,所以就考虑必然是用到了这个之后才能做出来。题目说是以1为根的时候深度才不超过30,于是应当先用1点做根建树,计算每个点到1的距离存好。然后需要存储树的前序遍历,对于每个新的顶点做根的时候,受到影响的应该是新的根到1点之间的路径之间的点以及他们的子树,此时需要二分答案,然后对路径之间的这些节点以及之前算好的前序遍历的数组,再次进行二分来判断答案是第几大的,此时最多需要二分30次,因为树的深度是那么大,并且由于二分的时候互相有包含关系,还需要利用容斥原理扣掉重复计算的部分。复杂度是O(N*30*logAnswer*logN),当时时间不多,只想到了二分答案和利用前序遍历数组,以及30次二分,还没有考虑到容斥原理这个细节。剩余时间只有10分钟多一点,应该不可能写完,所以就放弃去休息了,后来这些细节是比赛后经讨论想到的。

这次比赛RP成分和比赛经验成分比较多,确实是算做得最顺的一次了,比较happy,不过本科学校的几个队伍发挥都不太好,希望他们,尤其是几个新人能吸取经验,以后勤学苦练,创造好成绩。
另外还有I题我现在也不会做,据说是贪心,但是我还不知道具体怎么做。

本文来自Dora Blog,题目为PKU2011ACM校赛总结&简要解题报告,转载请注明出处。
如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读
欢迎关注我的新浪微博:http://weibo.com/diaorui1987