Toxophily
XY轴速度分量Vx = V * sin(theta), Vy = V * cos(theta).
设S = G * X * X / (2 * V * V).其中G为重力加速度。
设T = tan(theta).
得到T*X ?C (1 + T * T) * G = Y.
然后解一元二次方程就可以了。

Run
本题是一道计算几何中的半平面交的问题。
以T为X轴，以距起点的距离为Y轴，这样建立平面图之后，得到的是N条射线。设这N条射线的上部分为半平面的话，求这N个半平面的交。
如果某条射线在半平面交的解里面，那他就有可能领先。
要注意三线相交于一点的情况。

Ring
根据给定的字典建立一棵Trie树
为了实现多串模式匹配，在原Trie树基础上加入类似于KMP算法Next函数的Fail边
Aho-Corasick Automaton
F[i][j]表示当前构建的Romantic String的前i位所对应自动机上的状态j时能得到的最大积分
记W[]为各个单词的分值，Contain[i]为自动机状态i上所包含的单词，那么
  F[i][j] = max{F[i - 1][k] + W[Contain[j][t]]}
其中状态k存在一条通往状态j的边（正向边或Fail边）
因为长度要尽量小，因此Romantic String中不能包含“废字母”.

Radar
本题是一道计算几何+搜索题。
做法是先二分圆的半径，然后建立一种二分图的支配集的模型。（用左边最少的点来控制右边的点）。
剩下的就是用搜索算法来解决这个东西。
标程是用的IDA*+DancingLinks

Pendant
很容易想到DP的做法
F[i][j]表示长度为i的pendant，用了j种珍珠，所构成的方案数
F[i][j]=F[i-1][j]*j+F[i-1][j-1]*(k-j+1)
我们要计算F[1][k]+…+F[n][k]
N<=1,000,000,000
普通的DP无法解决
这类问题可以用矩阵乘法解决
F[i-1]到F[i]的转移可以用矩阵来描述，相当于一个k*k的线性变换矩阵
因此F[i]=A*F[i-1]，这里A是转移矩阵
因此F[i]=Ai-1*F[1]
F[1]+…+F[n]=A0*F[1]+…+An-1*F[1]
=(I+A+A2+…+An-1)*F[1]
I+A+A2+…+An-1的计算可以用二分或者构造矩阵，时间复杂度为O(k3logn)
这里是简单的二分法说明
I+A+A2+…+A2p+1
=(I+A2+A4+…+A2p)+(A+A3+…A2p+1)
=(I+A2+A4+…+A2p)(I+A)问题规模减半
偶数的情况也可以类似的解决

NamePK
这是一道简单的模拟题。
题目来源于网上比较流行的MD5的人名PK。
做法就是看懂题意之后，按照题意来做。

Minimum heap
这个问题很明显有递归性质
F[n]=F[left]*F[right]*C(n-1,left)
left为左子树的结点数，right为右子树的结点数
显然right=n-1-left
left很容易通过完全二叉树的定义计算
剩下的事情就是AC它！

Five in a Row, Again
一个最基本的结论：各个AI可以增长的经验值均为正值，因此最优策略必定是趁其他AI还未变强之前让1号与所有人打一轮
可以用一个N ?C 1位的二进制数记录2-N号AI是否与1号AI进行过PK.
能得到的积分范围为[0, 10 * 12]，很小。而能得到的经验值范围为[0, 1000 * 12].
因此不妨将积分作为DP状态。
F[p][x]表示“赛况”为p，1号AI获得x积分时所能得到的最大经验值。
找寻所有还未进行过PK的AI，记为i，那么
F[p][x] = max{F[p + 2 ^ i][x + (F[p][x] > E[i]) × W[i]] + E[i]}
其中E[i]表示i号AI的经验值，W[i]表示打赢i后1号AI所能获得的积分
所有有效状态中最大的x即为答案

Find The Path
本题可以用floyd算法解决。
平时我们应用的floyd是简化后的版本，原始的floyd是一种基于DP的算法。
F[i][j][k]表示i到j之间只经过k之前的点的最短路。
从状态上，我们就可以很容易的想到，只要事先对所有的点排序，然后在DP过程中就可以求得所有解的答案。再用二分来处理询问就可以了。

CUP
本题做法是二分答案+圆台体积公式来求解。
可以直接推出公式来而不用二分，但是精度有可能不够。
Pi=acos(-1.0)，如果取的精度不够有可能导致WrongAnswer。
还要注意杯子是有高度的，水有可能溢出