Lunarmony’s Journal

题外话..一会儿的TCO 显然又不能做...

哎，TC这个TCO/TCCC的年龄限制有意思么……难道仅仅参加比赛都不可以。。。还是Baidu厚道-_-

================================

BAPC 2007 题目分析

整体难度中等吧，比较适合Warmup的一套题……

题目数据请参考官方网站或ZOJ 2912 - 2921.

Problem A: Average distance

描述：求一棵树上所有点对距离总和的平均值。(N <= 10⁴)

经典题。直接DFS统计。

Problem B: Bus Pass

描述：给出一张图及公交线路(|V|<= 10⁴)。要求选择点集S: {距点P距离不超过X的所有点}, 使给出的所有点对(<= 200组)均在以S为点集构成的新图中连通。最小化X。

简单的BFS。

Problem C: Cutting Banknotes

PKU Monthly 2008 – 01第一题简化版本。略过。

Problem D: Dice Password Security

描述：给出一些单词，求长度为K且恰好包含P个单词的组合数目。

简单DP。

Problem E: Lingo

描述：给出一个8*8的棋盘。棋盘中一些格子被染成黑色。现在需要将恰好K个格子变成白色，使得存在同行/同列/同对角线全白色格子。问随机选择K个格子成功的概率。

容斥原理(2¹⁸ * 状态生成复杂度)，或者状态压缩DP (一般方法：8 * 64 * 2^{8 + 2 + 1} * 256，需要剪枝).

P.S., 在ZOJ上状态压缩DP必须写整行转移的版本，否则状态是存不下的……

Problem F: Splitting the Loot

描述：给出集合S,初始仅包含一个数X <= 10⁵, 每次我们可以从S中删除一个数Y并插入P, Q，且Y, P, Q需要满足(P + Q) * ratio = Y (0 <= ratio < 1). 要求最后S中包含由不少于N(<= 50)个数组成的集合S’，且S’中的数分别不小于S[0] .. S[N -1]。最大化S -S’中所有数之和。

TC流的经典题目，二分+check。

P.S., 注意这里最显然的思路不能保证利润最大化。

Problem G: Pachinko

描述：小球从棋盘顶下落。碰到障碍物时有均等概率落向左边/右边。小球落到某些格子中有固定得分并中止下落。问从棋盘顶哪一列放手期望得分最大。

模拟题。

Problem H:  Hiking

描述：给出平面上等半径的N个圆 (N <= 100), 问从S到T且保证路径中每一段都在至少一个圆内的最短路长度。

易见交点个数很容易达到O(N²)级别，而判断一条线段是否在圆内的复杂度是O(NlogN), 所以总建图复杂度高达O(N⁵logN)。 而这个复杂度是确实可以达到的。

但是上面的分析忽略了一个事实，就是那些被圆严格包含的点其实是会在求最短路过程被忽略的。考虑我们得到的区域的特殊性，由边界构成方式知有效点个数不超过2*N个。因此直接求最短路即可，总时间复杂度是O(N³logN)。

P.S., 注意这里我们可以一边求最短路一边处理出路径长度。

Problem I: Ranking

描述：模拟ACM排名系统……具体规则看题目

唯一需要注意的问题：两个队需要通过比较它们最晚排名不同的时间来break tie。

Problem J: Stock

描述：给出N <= 10⁵天中每天的买入股票数量，最大卖出数量和卖出价格，求最大化利润方案。

易见最大卖出价格->最后天的卖出顺序一定是最优的。那么直接模拟即可，时间复杂度为O(N).

================================

其实写了分析才发现这套题其实没什么特别值得说的……

所以以上内容仅供参考……