BUPT新生暑假个人排位赛02 Solution

刚刚进行了为期5周的ACM集训，通过这次集训的确发现自己还有很大的不足，这次没有没有出线也并不意外，收拾心情，来年再战！

这是北邮新生排位赛第二场。

A. 丁神去谷歌

这是一道比较水的题。只要按照它给定的规则找出最大的一项即可。我们可以定义一个结构并重载他的<运算符，这样for一遍就行了，如果用sort的话有可能会超时。

很裸的一道01背包，注意开long long。

题目大意是求在1～n的排列中满足每位数都比与他相邻的两个数大或比他相邻两个数小的排列的个数。

不难发现满足这种条件的排列只有两种情况：1.<><><>… ，2.><><><… ，即M型和W型。我们可以发现这两种情况的个数是相等的。

设1～i的排列中M型排列的个数为f[i],W型排列的个数是g[i]。我们考虑最后一个数i在W型排列中放置的位置为j,则在j前面的j-1个数仍为W型，在j后面的i-j个数为M型。因此我们可以写出状态转移方程:

1	g[i] = max(C[i-1][j-1] * g[j-1] * f[i-j])

又由于f[i] = g[i]，因此该方程可写为g[i] = max(C[i-1][j-1] * g[j-1] * g[i-j])。最后只需要输出2*f[n]。

这是一道博弈论的题目。题目大意是在一个n个节点的树的节点上随机放置m个石子。两人轮流操作，每次操作必须把所有石子都向下移动一步（即把这个石子移动到他所在节点的子节点），如果一个石子已经移动到了叶子节点则不需要对它进行操作。在所有石子都无法移动的时候游戏结束，无法移动的人判为输。问先手是否必胜。

这是一道every-sg问题。

由于石子之间相互没有影响，对这个博弈问题，我们可以把它看成m个博弈问题，即有m棵树，每棵树上仅有1个石子，每次操作必须对这m棵树都进行操作。

由于树的结构相同，我们可以先求出树中每个节点是必败节点还是必胜节点，此外，由于游戏是在所有石子都无法移动之后才结束，那么我们只需要考虑移动步数最多的节点。

对所有节点来说，如果这个节点是必败的，那么我们希望这个节点的移动步数尽量少，否则我们希望他尽量多。在求出所有结点的移动步数之后我们只需比较所有放置了石子的节点中的必败节点和必胜节点的移动步数的最大值即可得知先手是否必胜。

若必胜节点的步数的最大值大于必败节点则先手必胜。

题目大意是在一场足球比赛中，所有人都是不能动的，对方的11名球员每人都有一个圆型的控制范围，如果球进入他们的控制范围就会被拦截。现在给出对方球员的的位置和每个圆的半径，并给出你的坐标和球门坐标，问你是否可以把球射入球门。（球只会沿直线运动）

这是一道有点恶心的计算机几何问题。对每个圆我们可以求出圆的两条切线，则如果射出的球在这两条切线之间的话就会被拦截。

我们求出所有圆的切线所对应的弧度范围，并求并集。如果球门所对应的弧度范围在这个区间之内的话就无法完成射门，否则可以成功射门。