官方英文题解：http://codeforces.com/blog/entry/19237
Problem A：
题目大意：
给出内角和均为120°的六边形的六条边长(均为正整数),求最多能划分成多少个边长为1的正三角形。
题解：
把六边形补全变成一个正三角形,然后减去三个角的正三角形即可。
Problem B：
题目大意：
给出长度相等的两个串AB，定义两个串相等 当且仅当 A=B 或者 当长度为偶数时,A[1...n/2]=B[1...n/2] && A[n/2+1...n]=B[n/2+1...n] 或者
当长度为偶数时,A[1...n/2]=B[n/2+1...n] && A[n/2+1...n]=B[1...n/2]
题解：
1.比赛的时候我想都没想直接根据定义来判断。 复杂度我感觉和快排差不多。。 结果被hack了。 赛后想想其实复杂度还是高了。。 F(n)=4*F(n/2)+O(n). F（n）=O(n2)
由于后面两个条件需要长度为偶数,所以随机数据很容易就过了。。 下面这组数据可以把暴力卡掉。想卡别人还真是不容易。。
2.正解：题目中”相等“的定义是具有传递性的。所以可以分别求出和AB”相等“的且字典序最小的字符串，然后判断是否相等。
String smallest(String s) {
if (s.length() % 2 == 1) return s;
String s1 = smallest(s.substring(0, s.length()/2));
String s2 = smallest(s.substring(s.length()/2), s.length());
if (s1 < s2) return s1 + s2;
else return s2 + s1;
}
Problem C：
题目大意：
给出N*M的棋盘和K个黑色格子的坐标,求从左上角到右下角不经过黑色格子的方案数。 每次只能向右或者向下1格。 K<=3000 N,M<=100000.
题解：
1.这题以前做到过...所以很快就回忆起来了。。可以总方案减去不合法的方案。F[i]表示从左上角不经过黑色格子到第i个黑色格子的方案数。把黑色格子排序，然后
F[i]=左上角到i的方案数-F[j]*(j到i的方案数). 第j个格子在第i个格子左上方。 然后Ans=总方案-F[i]*(i到右下角的方案数)。
2.从(x1,y1)到(x2,y2)的方案数是C(x2-x1+y2-y1,x2-x1). 预处理逆元搞一搞就好了。
Problem D:
题目大意：给出N个点的凸包,求子多边形内整点个数的期望。 N<=100000. 精确到1e-9.
题解：
1.皮克定理肯定是要用的,但我觉得这个题目最巧的还是把多边形转化成线段. 由皮克定理 内部整点数=面积-边界整点数+1. 所以只要处理出期望面积 和 期望边界整点数。
2.期望面积：利用叉积和求多边形面积的方法,把一个多边形面积转化为多条线段的贡献。 期望边界整点数也是同样的道理。 所以我们只要考虑每条线段的对面积和边界整点数的贡献。 假设这条线段为PiPi+k,我们要考虑i+k在i逆时针方向第一个点 的多边形. 因为计算多边形面积的时候是要按顺序的。 这样的多边形有2n-k-1-1个。
总共有2n-1-n*(n-1)个多边形。 除一下就是选这条线段的概率。