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

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终于把这个过了我才放了心。

Leave a comment ?

11 Comments.

  1. A题直接判断角度AC的飘过。。。

  2. 居然还有功夫出题,你可真闲-_-

  3. 膜拜飘过

  4. I 标程多块? O(T*N*N) 我 0.13s; toj 上面一大堆的 0.02s. 优化 idea?

  5. H题有点问题
    比如考虑两条路径:a->b->c->d,e->c->b->f,结果应为2,而按你的算法结果为1

  6. To winnie: 这个确实是题目没有说清楚,按照题目本意结果确实为1

  7. 请求交换链接,其实允许我加你的链接就成~~

  8. To paky: 可以啊,呵呵

  9. 搜spoj你的博客排第3啊,搜”roba blog”这个博客才排第5,orz….

  10. F. 直接按 V-D 就好吧? no?

  11. 求最后一题标程,谢谢!

    I. Girl Friend II
    ecjtuprimemusic@gmail.com

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>