mhlwsk的博客

题目链接：http://codeforces.com/problemset/problem/540/D

概率DP，dp[i][j][k]表示还剩i个石头，j个剪刀，k个布的概率。

以石头减少为例，dp[i][j][k]转移到dp[i-1][j][k]的概率为i*k/(i*j+j*k+i*k)
这样就有dp[i-1][j][k]+=dp[i][j][k]*(1.0*i*k)/(i*j+j*k+i*k)

题目链接：http://codeforces.com/problemset/problem/274/B

题目大意：给定一颗以1为根结点的树，每个结点有一个权值，每次选择包含根结点的子树（注意：这里的子树与一般意义的子树定义不同，这里的子树是只要包含根结点的连通树就行，不一定非要包含所有孩子结点）并把这棵子树上的所有结点权值加一或减一，问至少多少次操作能让这棵树权值为零。

这题题意理解了半天。。

可以看到一个结点的孩子结点一定比它先处理完成（否则即使处理完了这个结点，在处理这个结点的孩子结点时，这个结点仍然会受到影响）。这满足无后效性原则，可以考虑树型DP。对于每个结点维护一个up值代表它至少需要被加一多少次，和一个down值代表它至少需要被减一多少次。每次状态转移时分两步：第一步up[u]=max{up[v]}, down[u]=max{down[v]}，第二步合并up[u], down[v], c[u]并将当前结点需要改变的值统计如up[u]或down[u]中。最终的结果就是up[1]+down[1]。
状态转移第一步的原理：每次修改孩子结点，一定是按照需要修改次数最多的叶子结点来，因为那些需要修改次数较少的节点的修改过程可以并入前者的修改过程中。

题目链接：http://poj.org/problem?id=2891

这题是中国剩余定理模板题（余数不保证互素的情况）。这里直接贴上模板。

题目链接：http://codeforces.com/problemset/problem/687/B

这题是中国剩余定理解的性质。令M=lcm(c1,c2,…,cn)，则对x mod ci=ri用中国剩余定理求得的解在模M意义下是同余的，也即求得的解加上p*M可以得到通解。因而判断M%k==0是否成立，如果成立则x mod k的值是唯一的。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2837

指数循环节对应公式：a^(b%phi(p)+phi(p))≡a^b (mod p) (b>=phi(p))
递归求解每个n即可，需要注意的是公式对应条件b>=phi(p)，如果不满足条件，则不能套公式（即不用多加一个phi(p)），这里在pow_pow里特殊处理了。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5130

首先考虑下干扰的关系，设A(x1,y1),B(x2,y2),P(x,y)，可以列出式子：
sqrt((x-x2)^2 + (y-y2)^2) = k * sqrt((x-x1)^2 + (y-y1)^2)
化简后可以得到一个圆的方程，然后就转化为圆交多边形模板题了

题目链接：http://codeforces.com/problemset/problem/934/E

题目大意：给定平面内n个圆，问这些圆把平面分成了多少个区域。
这题是欧拉定理，但和欧拉定理一般式(V+F-E=2)不太一样..

求圆拆分平面有多少个区域怎么能离得开平面图的欧拉公式呢？
一般平面图欧拉公式：f=e−v+c+1
其中 e 代表边的数量，v 代表点的数量，c 代表连通块的数量，f 代表平面区域的个数
我们把圆弧看作边，交点看作顶点，于是很容易便可以算出 e,v,c 啦~
对于 e ，它相当于每个圆上交点的数量和（因为这些交点把圆拆分成了这么多的弧）
对于 v ，枚举求出交点去重即可
对于 c ，我们已经有了无向图的边，那连通块的数量可以直接 dfs/bfs 或者并查集算出来啦~
然后套用公式就是结果了，注意精度问题。
引用自https://blog.csdn.net/qq_28954601/article/details/79329961

注意圆的欧拉公式中各值的定义也不太一样，E是不会算上单独的圆边的。具体确定方法见上面引用。

题目链接：http://poj.org/problem?id=2187

首先，距离最大的点对一定都在凸包上。
若凸包上两个顶点能落在一对平行切线上，则称他们为对踵点。
显然，答案一定取在一组对踵点对。
如何做？
类似双指针
枚举凸包上的边，找出距离此边最远的点，因为凸包上点到边距离为单峰函数，也就是说点到边构成的三角形面积是单峰函数，因此可以利用叉积比较面积。
注意：不能枚举凸包上的点（而不是枚举边），用上述做法找出距离此固定点最远的点。因为不满足最重要的单峰性
引用自HIT_Tom课件

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6325

注意观察每次移动的花费xi yj - xj yi，这是一个叉积。题目希望花费的负值最大，也就是所有的叉积和尽可能小。贪心考虑，我们需要让移动路线尽可能「上凸」，这样可以向顺时针转动的角度也会尽可能的大。于是维护一个上凸包即可。注意字典序的处理方式，拓展凸包时，如果在一个方向上遇到字典序较大的点，则不要弹出栈里的当前点。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1705

题目大意：有一个在格纸上的三角形，给定三个顶点的坐标，求在三角形内部的格点数。

皮克定理：对于一个所有顶点都为整点的简单多边形，其面积为S，内部格点数为n，边上格点数为s， 则有：S = n + s/2 – 1

这题求边上格点数时可以发现如果边不是水平或竖直的，那么边上的格点数为GCD(a,b)+1，a和b分别为边的水平和竖直方向上的长度。
求面积时要用叉积，直接套海伦公式会因为浮点数误差无法通过。