2016.10.6 NOIP模拟赛总结

SMOJ/1426 最小生成树

我一开始是直接把所有的点两两连边,即N2N^2条边,使用kruskal解决,时间复杂度O(n2log2n)O(n^2*\log^2n),自然超时,过了一半的点。

对于边数过多的最小生成树,一般的策略就是删边。其实之前刘励行给我看的一道题就用了类似的思路,但是今天没想起来。

我们可以先转化一下问题:由于每两个点之间的距离为Disi,j=min(xixj,yiyj,zizj)Dis_ {i,j}=min(\left |x_ i-x_ j\right |,\left |y_ i-y_ j\right |,\left |z_ i-z_ j\right |),可以把它们拆成三条边xixj\left |x_ i-x_ j\right |yiyj\left |y_ i-y_ j\right |zizj\left |z_ i-z_ j\right |,在进行kruskal的时候会自动把较大的边筛选掉。这样我们转化成了三个数轴上的删边问题。

假设在x轴上有xi<xj<xkx_ i<x_ j<x_ k,我们只需要连接(xi,xj)(x_ i,x_ j)(xj,xk)(x_ j,x_ k)即可。因为这两条边比较短,一定会被kruskal先考虑。接着再考虑(xi,xk)(x_ i,x_ k),由于xix_ ixkx_ k已经被连起来了,处于同一个并查集中,所以一定不会是最小生成树的边。可以直接筛掉。所以一个数轴上只需要连接连续的边,三个数轴总共3(n1)3(n-1)条,时间复杂度O(nlogn)O(n\log n)

SMOJ/1427 荷叶

我真的想复杂了……直接爆搜,然后为了剪枝加上了二分荷叶增加数量,达得到就减少,达不到就增加。连样例都过不了。后来也没时间调试,直接交上去,果然爆零,十分惨烈。

这道题的做法大致可以分为两种。记得最后走不到的情况要输出-1。

动态规划

fx,y,p,wf_ {x,y,p,w}为到坐标为(x,y)(x,y)的点已经走了p步并且放置了w个荷叶时的方案数。那么状态转移就很好写了。再初始化fstartx,starty,0,0=1f_ {start_ x,start_ y,0,0}=1,数组空间为$$mncntwaterstepssize_ {int}$$

30301001004\approx 30*30*100*100*4

=36,000,000Bytes=36,000,000Bytes

\approx 34.332MiB$$,不超。 ### 最短路 把每个点向周围能走到的八个点连边,如果目标点为清水,边权为1,否则为0。从起点到终点用一次SPFA/Dijkstra,边的数量约为8n,不是很大。但是这样只能求出第一个问,第二问求最少步数,那么可以作为SPFA第二关键字。求完之后还要知道有多少种方案,这就比较麻烦了,我们一步一步分析。 #### 得到每个点到源点的最短路径 这个就靠SPFA或者Dijkstra就好了。虽然说SPFA感觉很快,但是其实不是特别稳定,最坏时间复杂度可以达到$O(VE)$。如果有条件的话尽量还是写Dijkstra。 #### 得到所有最短路径上的边 我们枚举边。如何判断一条边是否在最短路径上?假设这条边连着的两个节点为$i,j$。若$dis_ i=dis_ j+w_ {i,j}$,那么$i\to j$这条有向边一定是在最短路径上的。证明嘛,自己想一想就是这样的。否则的话就不是。双关键字也同理。 #### 统计通过这些边的路径有多少条 现在这个最短路径组成的图是一个DAG(有向无环图),深搜或者DP都能统计出条数,条数就是第三问的答案。 ### 别的方法 也可以用BFS来做。但是感觉和双关键字SPFA差不多,代码难度与思路和下面我的做法差不多,就不多讲了。 ## SMOJ/1428 过路费 我这道题竟然AC了!我自己在做题的时候发明了一种强大的最短路算法,后来在省队选拔的时候才知道这个最短路算法叫”SPFA”,还靠着这个算法A了一道题……所以一直应用的很好。在其他的题目上也强行套上去,造就很奇怪的做法以及读不懂的代码。 ### 我的SPFA 将每一个点都作为源点跑一边SPFA。在SPFA的时候要记录两个值:dis和maxc。dis表示到达该点的边权之和,maxc表示到达该点的路径上的所有的点权的最大值。这个值不能直接进行比较,所以我又对每一个节点开了链表存起来,放进队列里面的实际上是链表节点的编号。但是有的值是可以减掉的。对于点i,我们想要用新的dis和maxc更新/迭代/松弛这个点,我们先看这个点的到达链表中的$dis_ x$和$maxc_ x$,若有$dis_ x\leq dis$且$maxc_ x\leq maxc$,那么不需要更新,因为一定不会最佳。假如说只有一个小于,另一个大于,我们是没有办法判断的,没有办法用贪心,因为以后的路径长度和最大点权没有必然联系。假如说新的两个值都小于原来的两个值,那么直接覆盖这个节点,然后重新把这个链表节点加入队列,松弛。 最后把每个节点的dis和maxc加起来就能算出总代价了,全部跑一遍的话可以算出两两点对的询问的答案。 ### Floyd 先把点按照点权从小到大排序。这样在Floyd最外层的k作为中间点的时候,这个中间点一定是整个路径的最大点权!非常巧妙的思路!剩下的都好做了! ## 总结 今天的第一题水了50分,第二题没时间调试,第三题东凑西凑AC了,总共150分。其实这三题的难度都不是很大,但是学过的东西都想不太起来了,才沦落到这样的成绩。 有一些解题的思路还是十分巧妙的。但是没有这些思路的时候,我们只能尝试用普通方法,如DP、最短路来做,对没有后效性的问题慎用深搜。NOIP考的不难,考纲不广,这是否意味着提高区分度需要更多的思维游戏呢?

avatar
Kerry Su