联合训练赛第一场解题报告

A. A Sequence of Numbers

简单题。求等比数列的时候应该用二分法求幂。注意处理好64位整数的操作不要溢出。

B. Building Block

并查集,每个元素存了两个数。其中一个只在代表元上有效,存了这一堆积木的总个数;另一个数的作用是,对于每个元素,从它到代表元的路径上这些数的和,是在这个积木上方的积木的个数(不包括它自己)。

C. Matrix Swap

建立一个N*N的二分图,若第i行第j列为1,则在X集的第i个点与Y集的第j个点之间连边,若此图的最大匹配数小于N则无解。否则,我们就可以由匹配的情况得到一个交换方案,例如我们可以把与X集的每个点所匹配的Y集中的点编号列出,这样得到一个1..N的排列,然后可以通过交换序列中的数(即交换原矩阵的列)得到一个1,2,3…N的递增序列。最后这步实际就是找这个置换中的循环。

D. Permutation

状态压缩DP.我们考虑把数字从小到大依次插入序列之中某个位置的过程,有一个重要的观察是,若当前考虑插入的值是a,则现在序列中小于a-K的值就可以完全不予考虑,因为新的值不可能插入与这种值相邻的位置,例如K=3, 现在已经形成的序列是{4,1,2,5,6,3},目前要插入的元素是7,则可以发现7只能放在最左端或插入5,6之间,而1,2,3这几个值都可以不予考虑,故上述序列可以简化表示为{4,*,5,6,*},其中*表示不能在其邻位插入当前值的一个元素或连续一段元素.这样总的序列长度不超过2*K+1,每个位置的取值只有K+1种,所以状态总数不超过(K+1)^(2K+1),更精细的分析可以得到更小的结果.另外,此题实际上只要有一个复杂度相对可行的算法,能够在比赛时间内把表打出来即可,而用上面这种状态表示得到的DP已经足够满足要求。

E. Pusher boys

搜索题。标程的实现方法是DFS + Hash判重。数据没有出得很大,不需特殊的剪枝即可通过。另外,在题目给出的网站上提供了用程序自动获取迷宫数据的办法 http://www.hacker.org/forum/viewtopic.php?t=528 ,各关的难度是递增的,本题的数据取自最容易的若干关,感兴趣的同学可以用自己的程序看看能解出多少。

F. Prairie dogs V

BFS。当扩展到一个’X’点时把与其相连的所有X都入队即可。

G. The Wildest Road

其实就是求两个凸包的最短距离,要考虑只有一个点和所有点都在一条线上的情况。最短距离可以通过枚举顶点到另外一个多边形上的所有边的距离,同时加上相交判断和点再多边形内部的判断。注意考虑一个多边形完全包含另一个的情况,以及虽然两多边形相交但没有任何一个顶点在另一多边形内的情况。

H. Euler Function

设n的素因子分解为n = p1^k1 * p2^k2 * … * pm^km,则phi(n) = n * (1 – 1/p1) * (1 – 1/p2) … * (1 – 1/pm).利用此式可以用一个类似筛法求出所有的phi,再累加求和即可.

I. Wireless Network

在字符串自动机上进行状态压缩DP。首先以所有的密码串建立自动机,注意在自动机的终止结点上标记出其能匹配上哪些密码。设DP的状态为dp[len][pos][mask],表示当前长度为len的串,处于自动机编号为pos的结点处,之前已经匹配上的密码集合位串为mask。每次枚举下个字符的26种可能进行状态转移。边界条件为dp[0][0][0] = 1,最后结果为sum{dp[n][pos][mk]},这里pos取遍所有结点,mk取遍所有包含不少于k个1的位串,求总和即可。时限略紧,算法实现时要注意一下常数。

//以下为无责任废话

这九道题对应题目为TOJ 3293 –TOJ 3301,其中C,D,E三题是我出的。

C题是翻Algorithms Design那书的课后题时看到的,在已经知道那是讲网络流的那章的课后题的情况下,当时我居然愣了好一会儿才想到怎么做。想来这么经典的模型应该是早有人出过了,所以加了一个输出解的SPJ,算是加难了一点,本来想弄成要求交换次数最少,但是那样的话我觉得无法确定用匹配找到的就是最优解,所以作罢,各位如果有什么想法可以与我讨论。

D是从一个搞TCS的大牛的Blog(blogspot被盾,请设法翻墙)上看到的,据说是以前罗马尼亚国内OI比赛的一题,原题的范围更大,K好像到了十几,我上面说的DP方法应该过不了,不清楚还有什么更好的办法。这场比赛里AC了此题的TJU-T06所用的方法也与我的类似。

E是前几天从水木算法版看到的一个帖子得来的,数据取自此游戏的前三十关左右,我的几乎裸搜的程序能搜到60关左右,再后面的就搞不定了,也暂时没想到很好的剪枝手段或估价手段,网站上有人搞到了300多关,实在是orz。当然对于这道题来说,是只要敢写就可以过的,就看比赛中哪队能匀出时间来试一下了。

  1. 学习学习

  2. 还有些地方不是很清楚,要是提供标程就好了,我这样的菜鸟看了你的思路写不出来呀,能把D题标程给我膜拜下吧,thanks

  3. 第二题的并查集说得不是很清楚啊,roba哥能发个标程参考下吗?

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>