Tag Archives: 训练赛

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

A. The Troubles of Lmy

多边形相似,实际上是一个字符串匹配,利用相邻两边的比例和该顶点的角度作为一个节点,如果两个多边形相似,那么这样的n节点肯定是能够循环匹配的。注意不能光用角度来匹配,正方形和长方形就是一个反例。也不能用相邻边的比例来匹配。如菱形和正方形。

B. The Evaluation of Determinant

若m为素数,即可以用O(n^3)的高斯消元来解(与实数域的高斯消元类似,把除法变为乘以逆元即可,当m为素数时易知这样的逆元一定存在)。对于此题,需要把m拆成素数的积,对每个素因子求出一个结果,再利用中国剩余定理解模方程组,从而得到最终结果。

C. Lamp

此题实际上是一个特殊的SAT问题,每个开关对应一个变量,每个灯泡对应一个子式。关键条件是每个开关最多控制两个灯泡(注意这不是2-SAT问题)。我们可以通过一个构造的方法解决此题:首先,对于不控制任何灯泡的开关,它是任意状态都可以。然后,对于只控制一个灯泡的开关,或者控制两个灯泡但同亮同灭的开关,可以很容易地决定此开关的状态,只需令它控制的那一个或两个灯泡k(以及k’)亮着就可以了,然后灯泡k(以及k’)对应的子式就可以忽视掉了,这样就可能得到更多的只控制一个灯泡的开关。持续此过程,直到所有的灯泡都亮了,或者找不到满足上面情况的开关。在后面一种情况下,剩下的开关全部控制两个灯泡,并且若开关为ON时点亮其中一个灯泡,为OFF时点亮另一个。此时我们可以建立一个二分图,把剩下的灯泡作为X集,把开关作为Y集,若某灯泡被某开关控制,则在两者之间连边,求此图的最大匹配,若所有的灯泡都能被匹配上,则解存在,开关的状态就是满足使其对应的灯泡点亮的那个状态。

D. Lawrence of Arabia

这个去年North America的区域赛题目,dp模型很简单,dp[i][j]表示对前i段railroad进行j次attack所需要的最小值,那么转移方程为
dp[i][j]=min{dp[k][j-1]+weight(k+1,i):j<=k<=i-1}
对于固定的j,可以看出dp[i][j]的决策是随着i单调不减的,建立数组len[x]表示使决策x比之前所有的决策(y<x)都要好的最小的位置i。可以通过二分求出这个最小位置同时用栈维护所有的有效决策序列,这样对于每一维固定的j,复杂度可以降到nlogn,所以最后总的复杂度可以达到n^2logn。

E. Matrix Swapping II

对每个位置,计算出从它自身向下共有多少个连续的1,设此数为c[i][j]。这一步可以用O(n^2)解决。然后枚举每一行i,假设它是要找的子矩阵的最上一行,取出此行的所有c[i][j],容易发现只要把这些值排序后,即可用一遍扫描得出以i行为最上一行的全1子矩阵的最大面积。所以总的复杂度是O(NMlogM)。另外如果仔细考虑上一行和下一行之间c值的转换关系(-1或者赋一个新值),可以得到O(NM)的算法。

F. Plants VS Zombies

贪心,对于每个僵尸,求出要杀死它所需的最少种花时间x[j] = V[j] – ceil(D[j] / T) * T,将其时间从小到大排序,依次杀死即可。如果到某位置时时间不够,则无解。

G. Snail’s trouble

简单题。蜗牛每分钟走的距离占总长度的比例依次为 (k/100)/1, (k/100)/2, (k/100)/3, … 因为调和级数1+1/2+1/3+…+1/n不收敛,故蜗牛总能爬到终点。对于此题,精度要求不高,直接暴力或打表即可通过。也可以用Striling近似公式来解。

H. Wukong and Tang Monk

首先求出A和C到图中所有点的最短路径,然后分别从B和D倒推求出WuKong和Tangseng可能经过的结点(如果dist[i]==dist[j]+w(i,j),i在最短路中,那么j也必在一条最短路)。那么通过这些结点和最短路的边就可以得到两个有向无环图,问题就变为分别在这两个有向无环图中找出A到B的一条路径和C到D的一条路径,使其公共顶点最多。可以采用类似最长公共子序列的dp思想自下至上dp,dp[i][j]表示wukong沿着某条最短路径到达i结点,tangseng沿着某条最短路径到达j结点时的最多公共顶点数,那么通过枚举i和j的前驱结点,则有
if(i == j)dp[i][j]=1+max{dp[pre[i]][pre[j]]};
else dp[i][j]=max{dp[pre[i]][j],dp[i][pre[j]]};

I. Girl Friend II

此题实际上是在语音识别、机器学习等领域被广泛应用的所谓的隐马尔科夫模型(HMM),解决此问题的算法被称为Viterbi算法,实际上就是一个简单的DP。我们用dp[i][j]表示在第i分钟,女孩的状态为j时的似然概率,则有状态转移方程

dp[i][j] = max{dp[i-1][k] * p[k][j] * a[j][b[i]], for all state k}

边界条件 dp[0][j] = s[j] * a[j][b[0]]

这里p,a,b,s的含义和题目中一致。可以把所有概率取log后,变乘法为加法,这样可以避免最后得到过分接近零的小数。算法的复杂度为O(T*N*N)

//继续无责任废话

这次C,E,F,I是我出的。C题来自计算理论课本上的一道课后题(我还是很对得起老廖这课的),貌似有队伍的解法比我的更为简洁,大意也是二分匹配,但没有很多的预处理;E是从前几天刚结束的CEOI 2009抄的,囧,数据放宽了不少;F和I其实都是临时凑数想的,当时觉得这一场比上一场要难,根据前一场大家的表现,拿掉了本来的一道难题,换了这两个简单题,F题背景是最近很火的“植物大战僵尸”,本来想的是匹配,后来发现水了,贪心就可以过-_-;I题其实就是随便yy了一下HMM,结果发现挺不好描述的,所以弄了很长的题面,相信不少队伍是被超长的题面和里面的公式吓得不敢想了,其实真的不难,不过事前真没想到精度会导致这么大的问题,我当时随手用两种稍微不同的方法写了两个程序(一种是/100后连乘,一种是直接log相加),得到的结果非常接近,以为问题不大。后来交上的程序一开始全是WA,一度让我以为是我的数据错了,但是用程序算过以后发现他们的程序的概率确实都小于我的标准输出,后来TJU-T03终于把这个过了我才放了心。

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

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。当然对于这道题来说,是只要敢写就可以过的,就看比赛中哪队能匀出时间来试一下了。