集训期间完成13道，补题3道。
比赛链接：http://vjudge.net/contest/121106#overview
A - SPF(割点)
题意：
求无向图割点,以及除去割点后的连通子图的数量
分析：
tarjan求割点
代码：
|
|
B - Boonie and Clyde(割点)
题意：
给定无向图，去掉两个点，使得图不再连通，问有多少种选择方式？
分析：
枚举每个点，求剩下的图的割点个数。如果枚举的点为割点，则在剩下的图中任选一点都可以，如果非割点，即去掉这个点，剩下的图连通性不变，则只能再选剩下图的割点。这样复杂度为$O(n \times m)$，可以一试。
但是情况并没有这么简单= =
如果枚举的点是割点，剩下的图被分成若干部分，这些部分之间的点不再连通。最后我们还要在剩下的部分中再随便去掉一点，但是如果仅有两部分且其中一部分只有一个点，那么去掉这个点之后相当于只剩下了一部分，显然此时是这个选择是无解的QAQ
所以我们必须对去掉割点后，剩下图被分为两部分，且至少有一部分仅有一个点剩下的情况进行特判。
代码：
|
|
D - Matrix Decompressing【网络流】
题意：
给定各行各列的和，求出一个满足条件的矩阵。
分析：
最初没想到，听陈鹏说是网络流突然觉得好有道理，这样想来好像也是很裸的样子。各行各列相连，从超级源点到每行连线，流量为各行的和，从各列向超级汇点连线，流量为各列的和。这样跑一下网络流再往回找一各边的流量即为答案。注意此题有流量至少为1的下界， 所以初始就为每条边安排1的流量，那么行列之间边的容量为19，从源点流入和汇点流出的值要进行相应的减少。跑完网络流最后输出答案再加上一即可。
代码：
|
|
E - Pie(二分)
题意：
若干蛋糕分给若干人，要求每个人分到的蛋糕是完整的且大小相同，问最大是多少？
分析：
每个人得到的蛋糕越大，得到蛋糕的人数就越少，满足一定单调性，明显二分。
代码：
|
|
F - K Best(二分)
题意：
给定$v和w$序列，从中选择$k$个数，使得$ \sum_{j=1}^k v_{i_j}\over \sum_{j=1} w_{i_J}$最大。
分析：
最大化平均值问题，我们采用二分答案的方法。
设$s ={ \sum_{j=1}^k v_i\over \sum_{j=1} w_i}$，二分$s$，移项整理得$ \sum_{j=1}^k w_i = s * \sum_{j=1}^k v_i$，每次判断能否得到平均值大于等于$s$的$k$个序列的时候，对$v_i - w_i$从大到小排序，贪心的选择最大的$k$个看是否大于等于$0$即可。有点巧妙。
代码：
|
|
G - Median(二分)
题意：
给定序列，求序列所有元素差值的绝对值的中位数。
分析：
利用中位数的位置特点，枚举中位数，找大于等于这个中位数的差值的个数，肯定是中位数越大，个数就越小，利用这个单调性，二分中位数，然后对于每个元素看加上这个差值之后序列中大于这个数的元素个数即可。(这里的处理方法很经典)，此处用$lower_ bound$实现。
代码：
|
|
H - Showstopper(二分)
题意：
一堆偶数中有一个奇数，求这个奇数。
分析：
这道题很无聊啊，不给数据范围，输入又那么恶心。
思想很基本，利用数奇偶的特点及性质即，偶数+奇数=奇数
我们可以把所有数按一定顺序求个前缀和，之前一直是偶数，一旦遇到奇数，加上奇数，后面所有得到的前缀和就都为奇数。利用这个单调性进行二分。
利用$gets$从输入流读取，使用$sscanf$
gets()函数从流中读取字符串，直到出现换行符或读到文件尾为止。最后加上NULL作为字符串结束。所读取的字符串暂存在给定的参数string中。
读入后，处理这种输入有两种方法很巧妙：
- `while(gets(s)){
sscanf(s, "%lld%lld%lld", &t, &y[id], &z[id]);}`读入换行符视为啥也没读入 - 123456789bool read(){int eof = 0;id = 0;while((eof = (gets(s) != NULL)) && strlen(s) > 2){sscanf(s, "%lld%lld%lld", &x[id], &y[id], &z[id]);id++;}return eof||id;}
代码：
|
|
I - Censored!(AC自动机+DP+大数)
题意：
给定若干字符串，求不含这些字符串的长度固定的字符串种类、
分析：
比较模板的一道题，AC自动机经典问题，题目数目会爆$long long$，套个大数模板即可【大数模板蒯自jibancanyang。
代码：
|
|
K - Palindromes
题意：
判断一个字符串是回文的还是镜面的。
分析：
超级水题，map的时候别写错了就行。
代码：
|
|
L - Tiling Dominoes(轮廓线dp)
题意：
给定$n\times m \le 100$的矩阵，让你用$1\times 2$的方块填满，可以横着放也可以竖着放，问你有多少种放法。
分析：
通过这题学习轮廓线dp。大白书上讲解的轮廓线dp很清晰，注意$memset$会超时，数组开到$10+1$即可，或者直接$for$遍历一遍。
代码：
|
|
M - Expedition(贪心)
题意：
给定每个加油站的位置和油量，每走一单元消耗一单元油，问最少需要经过多少加油站到达目的地。
分析：
贪心，原则就是直到走不到下一站，再在这个站加油。
代码：
|
|
N.Package Delivery(贪心)
题意：
从坐标为$0$的地方出发到坐标为$d$的终点，初始油箱是满的，途中有若干加油站，坐标为$xi$，每加一个单位的油收$pi$元，油箱最多装$n$个单位，问到达目的地最少需要多少元。
分析：
贪心，原则就是遇到便宜的就先把油加上，避免走到后面加更贵的油。
那么我们怎么保证遇到的是便宜的呢？可以预处理一遍，倒着推一遍，记录每个加油站的后面的最近的比他便宜的，这样到达该加油站只要加到能走到下一个便宜的就好了，然后到达下一个便宜的再加油。。。依次下去，如果某个加油站后面没有比他更小的，那么直接加满，希望能用便宜的油多走一些路。
代码：
|
|
O. BerDonalds(图绝对中心)
题意：
求图的绝对中心，即在边上或者顶点中选一个点$X$，使得该点到图中顶点的最远距离$f(X)$最小。
分析：
参考非常透彻的讲解 见C题
=== 我是搬运工===
首先$floyd$求出任意两点之间的最短路。
其次，根据题意，对于某一点$X，设其在线段$u-v$上，与点$u$的距离为$x$，对于任意点$w$，我们有f(X)=max{min{d[u][w]+x, d[v][w]+L_{u,v}-x}}$。
下面来分析$f(X)$的性质，对于固定的线段$u-v$，我们可以画出$f(X)关于x$的函数图像，为方便比较，把$w$们放在一个坐标系中，由于我们要求的是到其他点的最大值，所以对于某个$x$，只要保留该$x$对应的最大的$f(x)$值即可，也就是函数图像中最上面的点，如资料中实线所示。
$f(X)$的最小值就是实线中的最低点，观察图可知，这个最小值必然在交叉点上，即$L_1，L_2，L_3…$。
根据函数图像，存在交叉点的前提是$d[u][w_j] > d[u][w_k] 并且 d[v][w_j] < d[v][w_k]$，且有$d[u][w_j] + L_{u,v} - x = d[v][w_k] + x$，而此时的$f(X)= \frac{d[u][w_j] + L_{u,v} - x + d[v][w_k]+ x}{2} = \frac{d[u][w_j] + L_{u,v} + d[v][w_k]}{2}$
这样我们枚举每一条边，然后对于$d[u][w]$从大到小排个序，扫一遍，按照上述式子答案就出来了。
代码：
|
|
P - Hack it!(构造)
题意：
给定$a$，求区间，使得区间内所有数的数字和是$a$的倍数。
分析：
好吧，看起来很数位dp呀。。完全没头绪的想数位d好久。
其实是个找规律题。
首先有序列
$x, x + 1, x + 2…x + 10^k-1$
$x + 1, x + 2…x + 10^k-1,x+10^k$
我们发现$x$的出现的次数一样，而由于$10^k$的各位之和为$1$，所以下面的序列比上面的正好多一，而这与$x$大小无关，所以对于$10^k>x$，每次将序列右移一位，和就增加一！
那么我们最初可以找一个序列，为了保证$10^k大于x$，我们直接取到最大值即$10^18$，先求出$[1,10^{18}]$模$a$的余数，然后将序列右移$a-t$即可保证现在的区间模$a$余数为0。
那么怎么求$[1,10^{x}]$，这里有一个规律，写几位就能发现答案为$45x10^{x-1}$，
然后求模的时候拆起来边模边乘防止爆掉。
代码：
|
|
Q - Runaway to a Shadow【计算几何】
题意：
给定小强初始位置，以及若干圆的圆心和半径。已知小强以均等概率选择前进方向，给定速度和时间，做匀速直线运动。问小强在给定时间内走进圆的概率。
分析：
建立坐标系，以小强初始位置为原点，只要求出以原点为圆心，半径为$T\times V$的圆$O$与其他每个圆相交的部分构成的弧度，再取个并集，那么概率即为$并集大小/2\pi$。
如何求弧度并集？利用余弦定理求出相交部分的弧度，注意弧度存在范围，当原点与交点的连线$L$与圆相切的时候，弧度到达最大，那么在计算的时候只要将$L$跟切线长取个最小值即可~
【沙茶如我以为这样就结束了。
注意！角弧度范围为$[0,2\pi]$，不要忘记对于$a-b \lt 0 和 a+b \gt 2\pi$的情况进行一下处理！orz
代码：
|
|
R - yy math problem(数学)
题意：
求$1/n$小数部分的循环节和非循环节长度。
分析：
挺有意思的题，我是直接模拟除法的过程，那么余数相等即为循环，我们只要找到最先发生余数相同的两个位置，之间的距离即为循环节的长度。注意不要每次都$memset$，会爆，直接$for$遍历一遍。
代码：
|
|