Tag Archives: POJ

PKU Campus 2010 解题报告

此报告非官方版,不保证完全的正确性。另由于本人水平和时间有限,目前尚未做出最后两题,留待以后补充。比赛链接:http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1359

A. Bubble Sort

此题公式为 k! * (k+1) ^ (n-k) – (k-1)! * k ^ (n-k+1)。我是比赛时直接在网上搜的公式(汗),还没有仔细想这个公式是如何推出的。

B. The Bonus Salary!

最小费用流。把所有区间的端点当做图中的点,对于权值为w的区间[s,e),加边(s->e),容量为1,费用为-w。再对所有相邻的点加边(i->i+1),容量为K,费用为0。源点S到最左端点加边,容量为K,费用为0。最右端点到汇点T加边,容量为K,费用为0。容易发现每个流量都对应了某一天的安排。于是求最小费用最大流再将费用取反即可。

C. Tour in Wonder Land

树型DP。首先我们猜想,必然存在一种最优方案使得总是遍历完某子树的所有结点后再转到另一子树,而不是在不同子树间来回跳(证明略)。于是对每个结点i考虑遍历完它的所有后代的最小花费。我们用dp[i][0]表示遍历路线是从子树的根结点i进入然后走完子树所有点后从某一非根点跳出(或者是从某一非根点进入最后从i点走出,因为是无向图,这两者是等价的),用dp[i][1]表示遍历路线是从非根结点进入,又从非根结点跳出(当然,在过程中要经过i点)

于是,对于叶子结点有dp[i][0] = dp[i][1] = 0. 对其他点i,设i的儿子数为C,dp[i][0]有两种可能,一种是从i走进某个儿子j,这样走完j的花费是dp[j][0],然后对其他每个儿子k都花费dp[k][1],再加上在C个儿子间跳转的花费C-1;另一种是所有儿子k都走dp[k][1],再加上跳转的花费C。对于dp[i][1],一种可能是选择某两个儿子j,k,走花费dp[j][0]和dp[k][0](也就是经由j,k从根i绕一下),对其他儿子走dp[][1],再加上跳转花费C-2;另一种是所有儿子都走dp[][1],加上C+1的跳转花费(因为要跳到根再跳出来)。注意因为最后要回到1点,所以在总的树根处要再特殊处理一下。(我觉得我可能做复杂了……)

D. The xor-longest Path

首先一个关键的观察是,重合的路径经过XOR会“抵消”掉。于是我们求出从根结点到每个点x的XOR路径值a[x],则对于任意两点(x,y),他们之间路径的权值就是(a[x] XOR a[y])。而所有的a值可以用一个dfs简单完成,现在剩下的问题是,如何快速找出两个值使得其xor以后最大。

我们可以把全部的a值表示成二进制串,然后建立一个Trie。每个结点最多发出两条边,分别对应’0’和’1’。然后我们就可以在与a[i]的位数成比例的时间内对每个a[i]值求出它和哪个值异或后的结果最大。具体做法是先对a[i]按位取反,然后在trie上匹配。每次匹配时从trie的根开始,如果有相应的边,就沿着走一步,如果没有,就走另一条边,此时就出现了一个不一致的值,也就是结果的相应位置上有一个1。这样一直走完,得到的结果取反以后就是对a[i]来说最大可能的异或值。这样时间复杂度是O(31*N),此题时限较紧,写程序时要注意优化。我用vector建图直接TLE到死,杯具。

E. Xiang Hex

水题,不多说

F. Hexagon Coin Toss

关键在于计算六边形内的各种不同区域的情况,可以分为内部小六边形(盖住一个)、边缘(盖住两个)、角部(盖住三个)三部分考虑。其中小六边形和角的面积容易计算,总面积减去这两部分就是边部分的面积。如下图所示,红线围起来的部分即为可以覆盖三个正六边形的圆的圆心所在区域。(当然如果是在边界的话就不是了)总的大六边形减去小六边形再减去六个角部,就是可覆盖两个六边形的圆的圆心区域。然后把在外边界的情况处理一下就可以得到结果了。

f

G. I Wanna Go Home

对两种点分别求最短路,再枚举一下通过哪个边从某种点走到另一种边。

H. Repeater

简单题,递归写就可以。注意可能容易超时,实现上注意优化。

I.J.待续

贝叶斯公式在ACM比赛中的应用

我承认这个标题很囧,但是我今天确实用这个很囧的方法过了一道POJ月赛题:POJ 3716 Panda’s Birthday Present

题意是说,有4个六面的骰子,在一开始的时候对每一面各以50%的概率染成红色或蓝色,然后掷了两次,每次的得分为4个骰子里面掷出红色向上的数目。给定两次的得分x,y (0 <= x,y <= 4),问第三次的得分的期望是多少。

个人认为,这道题目最后的“期望”的定义不甚明确。如果按照解ACM题的思路,我会这样考虑问题:把四个骰子的红色面数组合成一个状态<s1,s2,s3,s4>,求出每个这种四元组的概率,然后利用x,y这两个值,可以排除掉肯定不可能的四元组,把剩下的概率重新归一化,再求第三次的期望,但是按这种算法无论如果对不上样例(也可能是我写错的),一囧之下我就yy出下面一个算法:

从贝叶斯概率的角度来想这个问题,在不知道x,y时计算出的四元组<s1,s2,s3,s4>的概率作为先验概率P(<s1,s2,s3,s4>),然后我们进行一次试验,设得到的值为x,则由贝叶斯公式,后验概率

$$P(<s_1,s_2,s_3,s_4>|x) = frac{P(x|<s_1,s_2,s_3,s_4>) P(<s_1,s_2,s_3,s_4>)}{P(x)}$$

在等号右面,先验概率P(<s1,s2,s3,s4>)通过dp和组合公式容易得出,似然函数P(x|<s1,s2,s3,s4>)也可由dp得到,P(x)是归一化因子,可以先不予考虑。于是得到观测值<x,y>的后验概率为

$$P(<s_1,s_2,s_3,s_4>|<x,y>) = \ frac{P(<s_1,s_2,s_3,s_4>) P(x|<s_1,s_2,s_3,s_4>) P(y|<s_1,s_2,s_3,s_4>) }{Z}$$

这里Z是归一化因子,即为对所有四元组<s1,s2,s3,s4>求得的P(<s1,s2,s3,s4>|<x,y>)之和。

求得了这个之后,第三次得分的期望即为 $$E = sum_{i=0}^{4} P(<s_1,s_2,s_3,s_4>|<x,y>) P(i|<s_1,s_2,s_3,s_4>) $$

ps. 据说有人得到超级简单的公式,最后结果就是(x+y+10)/7,我不知道是怎么推出来的,望大牛指点……

再ps. 这次月赛单挑拿了个第三,居然是在退役后拿到历史最好成绩……

进步

4293053 RoBa 2727 Accepted 488K 125MS G++ 2979B 2008-10-29 22:01:53
4293005 RoBa 2727 Wrong Answer     G++ 2952B 2008-10-29 21:53:59
966432 RoBa 2727 Wrong Answer     G++ 3741B 2006-01-13 17:08:37
966412 RoBa 2727 Wrong Answer     G++ 4109B 2006-01-13 16:51:28
966383 RoBa 2727 Wrong Answer     G++ 4068B 2006-01-13 16:20:57
966374 RoBa 2727 Wrong Answer     G++ 3934B 2006-01-13 16:15:08
966362 RoBa 2727 Wrong Answer     GCC 3739B 2006-01-13 16:00:34
966359 RoBa 2727 Wrong Answer     GCC 3712B 2006-01-13 15:58:40
966328 RoBa 2727 Wrong Answer     GCC 3163B 2006-01-13 15:35:49
966294 RoBa 2727 Wrong Answer     GCC 2887B 2006-01-13 15:17:39

2005 Beijing的Special Judge那题,两年多以前的时候,我要酝酿很长时间才鼓起勇气写,写了多长时间这上面看不出来了,但可以看出WA了以后调了两个小时仍然无效。现在这道题对我来说只是40分钟的代码量+8分钟找出一个弱智错误而已,从代码长度上也可以看出代码实现也更加聪明了。

最近做一些以前的比赛题,屡屡有这种自我提升的感觉,很高兴。