籟·来·也

偶然发现今晚5点开始的UVA，于是抓庄立来做，这厮居然说要去火车站接MM……于是自己4点30就去吃饭了，回来发现UVA挂了，开始15分钟了才正常，最后又延长了15分钟，UVA真是越换机器越不稳定，好像中间也挂过一下。

比赛链接：here

一共9题，最后只过了7题排第四，教主早早圆满，LayCurse神也提早半小时圆满了，还有个8题的在我前面。下面是我做了的题的题解：

(A) The Super Powers

一个正整数可以写成a^b，那么称为Power数；一个正整数可以写成两种或者两种以上不同的a^b形式，则称为Super Power数。输出1~264-1之间的所有Super Power数。

首先题目对于Super Power数的定义我觉得有问题，按照我上面的描述的话，1也是Super Power数，而按原题的描述，怎么看1都不能算……

事实上，Super Power数一定可以表示成某个a^b的形式，其中a不是一个Power数，而b不是一个质数（证明略）。于是可以知道b至少要4，因此a最多为2¹⁶。于是只要暴力求出2¹⁶内不能表示成某个数的幂次的数，然后这些数的合数次幂就是合法的Super Power数了。需要注意溢出，我因为有个地方溢出WA了一次。

(B) Creating Palindrome

这题给一个长度为N<=10000的整数序列，要求插入最多K<=20个数，使这个序列成为回文序列。要求输出最少插入的数的个数，或者无法满足要求。

这题乍一瞧，不就应该是N^2的dp嘛，或者好像可以转化成求LCS，也是N²的。最后才发现给我们的那个K是有用的，K比较小，可以大大降低有效的状态。还是按照N²的方法进行dp，dp[i][j]表示把i-j弄成回文的最小开销。考虑i的对称点i’=N-i-1，如果j和i’离得很远，那么显然在做到这个状态之前，已经插入了很多的数了。因此对于每个i，有效的状态只有离i’距离不超过K的那些j，于是是一个2K*N的dp。

(C) Code Feat

Snapdragon的数论题。给定最多9个条件，求最多10个符合条件的正整数。其中每个条件的形式为%x=a₁|a₂|…|a_k，其中k最大为100，也就是说模某个数的结果为某100个数中的任意一个。其中任意两个不同的x之间互质，所有x的乘积为32位整数。

这题比较郁闷的就是对于每个x，取余的结果可以有最多100个，如果是1个的话，那整个题目就是求模线性方程组了。因为所有的x都是互质的，因此其实每两个条件都可以合并成一个新的大的条件，但是一共有9个条件，这样全部合并起来的话，取余的可能性会多达100⁹，这显然是无法接受的……但是考虑到，如果可能性大的话，也就意味着解是很稠密的，整个整数区间只有2³²，如果解的可能性大于10W了，那平均几万个数里面就有一个解了，这完全是可以暴力的。于是我就合并合并，直到大小要超过10W了，然后从小到大枚举符合这个大条件的数，判断是否符合剩下的小条件，理论上不用枚举多少就能找到10个了。最后发现去1W的时候比较快，不过我还是觉得这个方法比较没啥保障- -还有题目要求是正整数，一开始输出了0WA了。

(D) Table Tennis

 两个人打乒乓球，第一个人开始轮流发球，每人每次连发5个球，谁先到21分谁就赢。当比分为20:20的时候，比分会变成15:15。现在给出比赛开始到现在为止的每一分得分情况，还有第一个人发球和接发球时得分的概率，求第一个人获胜的概率，或者输出当前的得分情况是不合法的。

好的，读完题就是邪恶的陷阱的开始。首先，那个到当前位置的胜负情况的字符串可能是空串，记得要用gets。然后要判断这个是否合法，不合法的情况就是某个人已经赢了，但是仍然在继续，这里注意一下20:20要变15:15。除此之外，还有一个比较容易忽略的不合法的情况，就是某人得分的概率为100%，却失分了，或者相反的情况。

于是就得到了当前的比分，从这个比分递推，打满40分，可以分别得到第一个人赢，输和平（20:20，即15:15）的概率。接下去就是要处理平的概率，我们再从15:15的分数开始递推，得到胜负平的概率。我们注意到，这个时候如果再打平，就要再次从15:15开始递推了。所以，其实15:15平的概率，可以按照胜负的概率按比例分配给胜负。这里又要注意一个特殊情况，即永远无法分出胜负的情况。处理好这个后，再把原来的平的概率按这个比例平分下，就得到最后需要的胜的概率了。

这题trick很多，我居然1Y，可见我是多么的猥琐。。最后发现我是唯一1Y的，我都觉得自己强大。。其实这是因为我做过T_T同学的一个有点类似的题目，有兴趣的同学可以去试试：ZOJ 2929

(E) Bounded by Lines

二维平面上有N<=100000条直线，给x₁和x₂，求x₁到x₂之间这些直线包围的面积。一个点被这些直线包围，当且仅当这个点上方有直线，这个点下方也有直线。

这题没过，不过做法是知道的，也就是所谓的理论上AC。其实题目就是求这些直线的上轮廓和下轮廓，求出来以后就是一些梯形面积求和了。ZOJ上有道很类似的题ZOJ 2967，是求上轮廓的直线的条数，做法是一模一样的，先按照斜率排序，然后用类似凸包的Graham scan的方法，线性扫描即可。具体可以网上搜2008年浙江省省赛的解题报告，有上面这题的解答。

(F) Winger Trial

一个矩形的足球场，场地里有N<=100个固定位置的机器人，一个人要从矩形的左边线走到右边线，路径任意，但是当离一个机器人的距离小于等于d的时候，就会触发这个机器人，每个机器人最多只会被触发一次。现在为从左边到右边，最少触发几个机器人。

这题一看是个几何题，其实居然是个网络流的题目。题目可以稍微转化一下：最少去掉几个机器人，使得人可以从左到右不触发任何一个机器人。每个机器人就是一个圆，如果一组圆把上边和下边连起来了，那么人从左走到右就一定会触发某个机器人。于是我们可以把上边看成源点，下边看成汇点，相交的圆之间互相连边，我们要做的就是把这个图割开，让上边和下边没有路相连，那么人就可以从左走到右而不触发任何一个机器人了。于是这就是一个简单的最小割了，记得机器人要拆点~

继续推荐一道类似的题目，HDOJ 2798，据说也可以用网络流搞，有兴趣的可以去yy下。

(G) Left Right

不好意思，题目都没看- -

(H) IBM Fencing

平面上有N<=500个凸包，每个凸包有P<=1000个点，保证了凸包和凸包是不相交的。其中每个最外层的凸包包围的区域是一个社团。每个社团最外面的一圈凸包要用铁链条围，然后铁链里面的一层凸包是木头链，木头链里面又是铁链，这样交替围，再告之铁链和木头链的单位长度的价格，输出一共有多少个社团，以及两种链条各花费多少钱。

这题数据量比较大，所以需要有效的方法来判断凸包的包含关系。关键的一点就是意识到：一个凸包在另一个凸包内部，当且仅当这个凸包的所有点坐标xy最大值小于另一个凸包的最大值，最小值大于另一个凸包的最小值。有了这个，我们就可以O(1)地判断两个凸包是否为包含关系。（根据LAF队员的指出，这个并不是充要条件，只是包含的一个必要条件，所以只能用来剪枝，于是这题我是水过去的。）

这里的包含关系是一个格(Lattice)，因此我们可以按照任意一个坐标的最大或者最小值对所有凸包排序，这样对于每个凸包，从后往前找，找到第一个包含它的就是刚好包住它的凸包。剩下的计算就比较简单了，不再赘述。

这题的数据有点问题，坐标范围比描述给出的要大，害我wa了一次然后死活都找不到错。。给UVA发了邮件结果没理我，悲剧。

(I) Brother Arif, Please feed us!

10000*10000个方阵中，有N<=2000个坏人和1个好人。当好人和某个坏人在同一行或者同一列的时候，就会被抓住。现在给定所有人的坐标，好人可以不动或者向四个方向之一前进一格，问是否可以达到一个安全的不被任何人抓到的地方。

唯一的水题，枚举不动和四个方向，然后扫描一遍坏人的坐标判断就可以了。悲剧的是一开始忘记考虑不动WA了一次- -