题目链接：http://poj.org/problem?id=1696
这题比较容易想到贪心策略：每次只找当前结点需要向逆时针转最小角度能到达的点即可。每次拓展一个点之后以当前结点为基准对其它点进行极角排序，并找到第一个从当前结点旋转方向为逆时针并没被访问过的点拓展即可。
但有一个坑点：极角排序时如果当前基准点位于许多点中间而非它们的边界上，那么极角序并不是唯一的（极角序转过360度依次减小形成了一个环），此时排序的结果是不可用的，因此要在排序前去掉所有在当前结点（准确地说是当前边）顺时针方向的点。
题目链接：http://poj.org/problem?id=3304
题目大意：二维平面上n个线段，问是否存在一条直线，使得所有线段垂直投射到该直线上的投影，都两两有公共点？
所有投影都两两有公共点，那么投影直线一定有一条法线穿过所有的线段，问题转化为是否存在一条直线穿过所有的线段。
通过旋转平移的方式我们一定可以让这条直线经过所有线段中的至少两个端点（想象如果没有经过，那么我们把它向外移直到「撞到」一个端点，再通过旋转的方式使它再「撞」到另一个端点）。
因此枚举两个端点，并判断经过两端点的直线是否经过所有的线段即可。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5726
第一问很好做，一个数与它自己的GCD仍是自己，所以区间GCD可以直接用ST表维护。
第二问就比较麻烦了。要做出第二问需要用到几个性质：
第一个性质使得二分区间边界成为可能，而有了第二个性质我们就可以枚举每一个左边界，并在这个左边界的前提下尽量向右「扩展」，找到GCD相同的最大的右边界，并把这个GCD下的区间数用map维护；接下来更改GCD（这里GCD是减小了）并继续向右拓展右边界，直到拓展到区间尽头，然后枚举下一个左边界并重复上述步骤。可以证明对于每个左边界，GCD相同的右边界有最多log(n)个（第二个性质）。这样整个初始化过程时间复杂度为O(n * log(n))
这样就统计完了每个GCD对应的区间数。
题目链接：http://codeforces.com/gym/101808/problem/K
这题第一眼看上去是树上最短路，但麻烦的是它有n条边不是树。这张图仅有一个环，我们尝试讨论特殊情况把它转化为树上最短路来做。
我们忽略环强行建树，设环上的两个点为X和Y，两点之间的边权为Z，任何两个点经过数根的路径的距离为f(a,b)，那么a和b之间的最短路一定等于min{f(a,b),f(a,X)+f(b,X),f(a,Y)+f(b,Y),f(a,X)+f(b,Y)+Z,f(a,Y)+f(b,x)+Z}
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6214
题目要求求出最小割的最少割边数。
可以理解为双关键字网络流，把每条边容量变成cap*(E+1)+1，E为边集大小（当然E+1也可以是任一个大于边集+1的数），跑一遍最大流。
最小割即为maxflow/(E+1)
最小割边数为maxflow%(E+1) （可以这样理解，一条边是割边当且仅当它被取满，此时这条边容量中新加入的那个1也会被取走）
这题是区间DP，状态转移方程d[l][r]=d[l-1][r-1]+2, s[l]与s[r]可以匹配, d[l][r]=max{d[l][k-1]+d[k][r]}, l<k<=r
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3516
这题是区间DP，类比于线性石子合并。
每次合并的w函数为dp[l][k-1]+dp[k][r]+node[k].x-node[l].x+node[k-1].y-node[r].y;
需要运用四边形不等式优化。
可以类比线性石子合并的做法。
题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1022
线性石子合并，改成了环形并且n达到了1000。环形比较好解决，把n堆石子复制一遍放到原来的石子后边，长度仍然枚举到n，区间右边界枚举到2*n，答案就是所有长度为n的区间的解的最大值。
麻烦的是数据范围比较大，O(n^3)的算法无法解决，这里需要用到四边形不等式优化。
优化本身的数学证明比较麻烦，直接记条件和结论了。
四边形不等式优化条件
在动态规划中，经常遇到形如下式的转台转移方程：
m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(i≤k≤j)（min也可以改为max）
上述的m(i,j)表示区间[i,j]上的某个最优值。w(i,j)表示在转移时需要额外付出的代价。该方程的时间复杂度为O(N^3)。
下面我们通过四边形不等式来优化上述方程，首先介绍什么是”区间包含的单调性“和”四边形不等式“
（1）区间包含的单调性：如果对于i≤i'<j≤j'，有w(i',j)≤w(i,j')，那么说明w具有区间包含的单调性。（可以形象理解为如果小区间包含于大区间中，那么小区间的w值不超过大区间的w值）
（2）四边形不等式：如果对于i≤i'<j≤j'，有w(i,j)+w(i',j')≤w(i',j)+w(i,j')，我们称函数w满足四边形不等式。（可以形象理解为两个交错区间的w的和不超过小区间与大区间的w的和）
下面给出两个定理
定理一：如果上述的w函数同时满足区间包含单调性和四边形不等式性质，那么函数m也满足四边形不等式性质。
我们再定义s(i,j)表示m(i,j)取得最优值时对应的下标（即i≤k≤j时，k处的w值最大，则s(i,j)=k）。此时有如下定理
定理二：假如m(i,j)满足四边形不等式，那么s(i,j)单调，即s(i,j)≤s(i,j+1)≤s(i+1,j+1)。
好了，有了上述的两个定理后，我们发现如果w函数满足区间包含单调性和四边形不等式性质，那么有
s(i,j-1)≤s(i,j)≤s(i+1,j)。即原来的状态转移方程可以改写为下式：m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(s(i,j-1)≤k≤s(i+1,j))（min也可以改为max）注：具体代码实现中k取满足条件的最大值或最小值，下文代码取的最大值。
由于这个状态转移方程枚举的是区间长度L=j-i，而s(i,j-1)和s(i+1,j)的长度为L-1，是之间已经计算过的，可以直接调用。不仅如此，区间的长度最多有n个，对于固定的长度L，不同的状态也有n个，故时间复杂度为O(N^2)，而原来的时间复杂度为O(N^3)，实现了优化！今后只需要根据方程的形式以及w函数是否满足两条性质即可考虑使用四边形不等式来优化了。
题目链接：http://codeforces.com/problemset/problem/768/E
仍然枚举前几个sg[x]，找规律
sg[0] = 0、sg[1] = 1;
sg[2] = mex{sg[0], sg[1]’} = mex{0,0} = 1;
—— 这里的sg[1]’表示已经取了一个石子还剩一个石子的状态，很显然不能取！sg[1]’==0
sg[3] = mex{sg[0], sg[1]’, sg[2]’} = mex{0,1,1} = 2;
—— 同上，很好证明sg[2]’==1，sg[1]’==1，不过注意这里的sg[1]’表示已经取了两个石子还剩一个石子的状态，很显然是可以取的，这和上面的sg[1]’不一样，这里sg[1]’==1
sg[4] = mex{sg[0], sg[1]’, sg[2]’, sg[3]’} = mex{0,1,1,mex{0,sg[1]’}} = 2
—— 很显然这里的sg[1]’表示已经取过一个石子也取过两个石子还剩一个石子的状态，很显然不能取，sg[1]’==0
……
最后可得出sg[x] = {0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5……}中秩为x的元素
引用自https://blog.csdn.net/Jaihk662/article/details/56484066
这里复习了下每个结点的SG值是只由它的后继决定的。