此报告非官方版，不保证完全的正确性。另由于本人水平和时间有限，目前尚未做出最后两题，留待以后补充。比赛链接：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

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

G. I Wanna Go Home

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

H. Repeater

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

I.J.待续