Codeforces Round #313 (Div. 1)

官方英文题解：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(n²)

由于后面两个条件需要长度为偶数,所以随机数据很容易就过了。。下面这组数据可以把暴力卡掉。想卡别人还真是不容易。。

ba * 32768

ab * 32768

2.正解：题目中”相等“的定义是具有传递性的。所以可以分别求出和AB”相等“的且字典序最小的字符串，然后判断是否相等。

String smallest(String s) {

    if (s.length() %  == ) return s;

    String s1 = smallest(s.substring(, s.length()/));

    String s2 = smallest(s.substring(s.length()/), 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.期望面积：利用叉积和求多边形面积的方法,把一个多边形面积转化为多条线段的贡献。期望边界整点数也是同样的道理。所以我们只要考虑每条线段的对面积和边界整点数的贡献。假设这条线段为P_iP_i+k,我们要考虑i+k在i逆时针方向第一个点的多边形. 因为计算多边形面积的时候是要按顺序的。这样的多边形有2^n-k-1-1个。

总共有2ⁿ-1-n*(n-1)个多边形。除一下就是选这条线段的概率。

巴特西

Codeforces Round #313 (Div. 1)

最新文章

热门文章