前几天打了BUPT的新生归来赛，感觉题目难度还可以吧，有几道题的确是需要费一些脑筋。下面我就来写一下这次比赛的解题报告。
A. Hard Game
题目大意是给你n堆硬币，每堆有k个，每次只能从一堆硬币中取若干个，不能不取。谁最后没有石子可取就判为输。Alice先手取，Bob后手取，问对给定的n，k，谁会获胜。
很明显，在堆数为奇数时，Alice有必胜策略。我们可以给Alice这样的策略，第一次取k个，这样会剩下k-1堆。若Bob也取k个，则Alice再取k个；若Bob取a个(a < k)则Alice在另外一堆里同样取a个。这样总会剩下偶数堆，并且这些堆中的硬币数两两相同。这样Alice必定会最后取完所有的硬币。
事实上，这个问题是Nim问题的简化版。Nim问题为，有n堆硬币，每堆有ki个，每次只能从一堆硬币中取若干个，不能不取。谁最后没有石子可取就判为输。这个问题可通过判断S=k1 ^ k2 …… ^ kn的值来判断是否先手必胜(不为0则先手必胜)。
附证明：
称一个先手必胜的局面为P局面，反之称之为N局面。
当k1=k2=……=kn=0时，满足中状态时P局面。
若S=0，若从堆i中取若干硬币使其剩下ki’个(ki’ < ki)，
则ki ^ ki’ != 0。又S’ ^ ki ^ ki’ = S = 0，故S’ = ki ^ ki’ != 0。
满足P局面的所有子局面都是N局面。若S != 0，设S的二进制位为A1A2……An，考虑第一位是1的。
在P中取出该位同是1的，不放设为P1。可知P1 ^ S < P1，令P1’ = P1 ^ S，则P1’ ^ P2 ^ …… ^ Pn=0。满足N局面存在至少一个P局面。
证毕。
而这道题其实就是所有的ki相等的情况，则在n为奇数时，S不为零。这也验证了我们的结论。
Nim问题还有很多扩展问题，这里就不再赘述了，有兴趣的可以自行google。
附源代码
B. Prime Judge
题目大意是给你一个复数判断它是不是复素数。复素数的定义为
如果a+bi能被分解为(a1 + b1i) * (a2 + b2i)的形式，那么该数不是素数；否则，该数是素数。
其中a1 、b1、 a2 、b2均为整数，且1，-1，0，i，-i不能作为被分解的因子。
刚开始拿到这题确实没什么思路。因为a、b、a1、b1、a2、b2都有可能是负数，枚举也无从下手。后来，通过whn同学的提醒，我终于找到了解题思路。
我们可以发现如果a + bi=(a1 + b1i) × (a2 + b2i),则|a + bi| = |a1 + b1i| × |a2 + b2i|，即a^2 + b^2 = (a1^2 + b1^2) × (a2^2 + b2^2)。这样，就把原问题转化为一个正数的分解因数。而这我们可以在O(sqrt(n))的时间内解决。
不过还有一个要求就是这两个因数都必须是两个数的平方和，判断这个问题可以通过枚举a1，然后a2 = 因数1 - a1^2 ;
再判断sqrt(a2)^2 是不是等于a2，如果相等，证明因数1是合法的对因数，对因数2可采取同样措施。这个复杂度为O(sqrt(sqrt(n)))。而n为a^2 + b^2 ，因此总的时间复杂度为O(a*sqrt(a))，可以接受。
whn同学还告诉我一种更加简洁的解法，具体可以参考这篇博文
附源代码
C. Freeway
题目大意是给你一个无根树，这个树的一些边是有向的，一些边是无向的。现在希望改变一些边的方向，使得我们可以从某一个点出发到达任意一点。改变边的方向的花费即为这条边的权值。现在请你找出花费最小的方案。
这道题出的很有迷惑性。刚拿到题目时，我以为从每一个点出发都有许多方案可以选择，而且还有可能从不同的点出发，感觉这题太难了。
赛后才发现，原来这是一棵树。也就是说如果你确定了要从某一个点出发，那么这个图的所有边的方向已经都确定了。而且我们还可以发现，从某个点出发所需的花费与从与它相邻的点出发所需的花费之间的差别仅在这两点间的边上。
因此我们可以任选一个点来遍历整个树，求出他的花费，然后再遍历一次，更新所有点的花费。时间复杂度仅为O(n)。
附源代码
D. Who Is Joyful
题目大意是给你n个点，每个点都有一个高度值。接下来有q次询问。每次询问指定闭区间[l,r]，问在该区间内有多少点是joyful的。一个点是joyful的当且仅当它前面有比他小的点并且它后面有比他大的点，每次询问的区间外的点对区间内的点没有影响。
这道题由于每次询问的区间是变化的，而一个点是否是joyful的也随着区间的变化而变化，因此没有想出有效的算法。赛后通过阅读大神AC的代码，我才恍然大悟。
其实这道题等价于在区间中寻找三元组(a< b < c)的个数。而这样的三元组我们只用考虑长度最短的即对每个b找到它后面第一个比他大的和它前面第一个比他小的即可。
但是这样还是没有简化问题。我们先把所有的询问按区间右端点排序，然后依次求解。我们把这个三元组的个数记录在a点，添加三元组的标记记录在c点，也就是说，对每一次询问，我们把所有c点位于上次的r到这次的r之间的三元组添加到树状数组的a点中，这样，我们就可以通过树状数组来实现log(n)的维护和查询。并且时间复杂度允许。
附源代码
E. 最小距离查询
题目大意是初始时给你一个字符串，接下来有m次操作，操作共有两种，一种是在已有的字符串末尾添加一个字符，一种是询问对于位置x，在S当中和S[x]相等且距x最近的字符与x的距离
这道题也比较水，通过两个数组front[i][j]，behind[i][j]分别记录下来i点前后距离i点最近的j字母的位置。初始化可以通过递推完成，维护的时间复杂度也不高，询问就直接取front、behind中的最小值。
这道题whn同学还有另一种解法，具体可以参考这篇博文。
附源代码