集训期间完成13道，补题3道。
比赛链接：http://vjudge.net/contest/123334#overview
A - Island of Survival(概率dp)
题意：
给定岛上老虎和鹿的个数，人、老虎和鹿每天随机有两只相遇。若人或鹿和老虎相遇，人或鹿被吃。若老虎相遇，两只老虎就会同归于尽，其余情况什么也不发生。问人存活下来的概率。
分析：
仔细分析，问题可以转化为老虎全部死亡的概率，而这只与老虎有关，鹿和人并不会影响老虎的数量。
若老虎数量奇数，人总会被吃掉。
若偶数，计算老虎两两同归于尽的概率即可。
代码：
|
|
B - Where to Run(概率dp)
题意:
给定$n个点(1 \le n \le 15)构成的$无向图，从$0$出发，在一个点处可以去往相邻的点，或者在该点继续呆5分钟，每个选择概率相等。问遍历完整个图的期望时间。
分析：
$n$只有$15$，容易想到状压
而对于某一点期望$dp[u]， dp[u] = 5 + dp[u] + \sum_{v与u相连且未访问过}{dp[v] + val[u][v]}$
整理一下再套个记忆化搜索外壳就好啦~
注意！要考虑不可达的状态！！！
代码：
|
|
C - Batting Practice(概率+公式推导)
题意：
已知一枚子弹命中概率，求连续$n$次不命中或连续$m$次命中时发射子弹数的期望。
分析：
较为复杂的公式推导，晚些把公式$markdown$上来了，占个坑。
！！！注意精度问题！！！
代码：
|
|
D - Race to 1 Again(概率dp)
题意：
给定一个数，每次可以选择数的一个因子，用该除上这个因子得到一个新的数，问该数变为1的期望操作次数为多少？
分析：
设$x$有因子$cnt$个，那么$dp[x]=1+dp[x]/cnt+dp[1]/cnt+…$
化简后为$dp[x]=(cnt+tot)/(cnt-1)$
其中$tot$为因数的$dp$之和。
代码:
|
|
E - Power of Matrix(二分+矩阵快速幂)
题意：
给定$n \times n$矩阵A，求$A+A^2+A^3+…+A^k$
分析：
QAQ清楚的记得线代老师讲过这个问题，构造出(都是$2 \times 2$ 的矩阵，不知为何换行显示不出来QAQ)
$B= \begin{bmatrix} A & E \ 0 & E \ \end{bmatrix}$
$B^k = \begin{bmatrix} A^k & E + A + A ^ 2 + A^3+…+A^K \ 0 & E \ \end{bmatrix}$
还有一个方法：倍增法
设 $f[k] = A + A^1 + … + A^k$
$若k为奇数$，
$f[k] = (A + A^1 + … + A^(k/2)) + (A + A^1 + … + A^(k/2)) \times A^(k/2) + A^k$
$ = f(k/2)\times (E+A^{k/2})+A^k$
$若k为偶数$，
$f[k] = (A + A^1 + … + A^(k/2)) + (A + A^1 + … + A^(k/2)) \times A^(k/2) $
$= f(k/2) \times (E+A^{k/2})$
递归下去即可~
代码：
|
|
F - Recurrences(矩阵快速幂)
分析：
$n$的大小很矩阵快速幂= =
代码：
|
|
H - Yet another Number Sequence(矩阵快速幂)
分析：
裸矩阵快速幂
代码:
|
|
I - 棋盘游戏(二分图匹配)
分析：
二分图匹配经典建图方式，每删除一条边，跑一遍二分图匹配，本以为会T，结果数据水水的 = =
代码：
|
|
J - Strategic Game(最少顶点覆盖问题)
分析：
最少顶点覆盖问题，原图为二分图，直接利用最少点覆盖等于二分图最大匹配除以2
代码：
|
|
N - I Hate It(线段树)
分析：
线段树单点更新，区间查询
代码：
|
|
O - 敌兵布阵(zkw线段树)
分析：
单点更新，区间查询，人生第一道zkw线段树，有趣！
代码：
|
|
P - Vases and Flowers(线段树)
题意：
有$n$个花瓶，标号$0到n-1$，每次输入$k,A,B$，有两种操作：
- $k=1,$ 从标号为$A$的花瓶开始顺序放$B$朵花，若花瓶非空，则跳过。问初始放花的花瓶和最后一个放花的花瓶的序号。可以不放完。
- $k=2$，标号为$A到B$的花瓶清空。问清空了多少个原本非空的花瓶。
分析：
线段树记录区间空花瓶的个数。
最初想法是：每次都更新到tree[i].cnt == tree[i].r - tree[i].l + 1即该区间内花瓶皆空，$ls，rs$必为这些区间的端点，比较一下即可。但是对于特殊情况，每次都要更新到叶节点，就变成了暴力。。。。
换个思路，我们可以先计算出$A$之前所有空花瓶的个数$cnt$，那么第$cnt+1$个空花瓶即为$ls$，同理第$cnt + B$即为$rs$，找第$cnt$个花瓶就利用线段树查询时递归的性质。
操作二直接区间更新，用一个全局变量记录区间内空花瓶个数。
代码：
|
|
Q - Jungle Roads(最小生成树)
分析：
裸最小生成树。
注意
除了cin>>之外，其他函数都不会忽略第一个有效字符之前的字符,也就是会读取之前输入残留的换行符\n。
代码：
|
|
R - Building a Space Station(最小生成树)
题意：
给定$n(n \le 100)$个圆的半径和圆心，若两个圆重叠或覆盖，则视为相连通。现在两个圆的圆周上建一条边，使得该两个圆联通。若使所有圆之间相互连通，问建边的最小长度和是多少。
分析：
$n只有100$，先$n^2$求出任两个圆之间的距离，并判断是否重叠或覆盖，若连通则将他们并在一起。最终形成若干连通块，而只要在连通块之间建边，求使连通块相连的最小花费即可。这样就转化为最小生成树问题。
建边必然是按照连通块之间的最小直线距离来建，最后再一次$n^2$枚举每个点，求出连通块之间的最小距离。最后求个最小生成树即可。
代码：
|
|
S - Borg Maze(最小生成树)
题意：
给定图，给定起点，每走到一个外星人点，可以拆分出两个及以上的其他人继续同时走其他未走过的点，问所有点都被访问过后，所有人走的最小距离和。
分析：
先$bfs$求出任意两点之间的最小距离，因为人拆分的个数不受限制，那么我们每到一个点(这里的点指外星人点，下同)，就假设拆分出足够多的人到其他所有点，即在任意两点之间建边，问题就转化为求将这些点连接起来的所有边的和的最小值，即为最小生成树问题。
一个大坑就是，$m$和$n$后面可能会有很多个空格，不能用$getchar()$，用$gets()$可以ac，可是用$getline()$就RE到哭，不懂为什么？路过的大神求赐教！
代码：
|
|
T - Constructing Roads(最小生成树)
分析：
裸最小生成树
代码：
|
|