【cf293X】Croc Champ 2013 – Round 2

2015年6月11日1,6762
A. Weird Game
两个人都应该采取贪心策略
根据规则,先取0而对方不取0则败,所以有1则取1,当然尽量取对方也是1的那些
取0的时候同理,尽量取对方是1的那些
我们模拟游戏进程得出两个人的最终序列比较即可

B. Distinct Paths

容易发现,n+m-1>K时是无解的,那么有解的棋盘就很小了,状压使用的颜色+dfs

然而这样的状态还是太多,我们发现dfs到一个格子的时候,所有未在棋盘上出现的颜色并无差别,所以只要搜其中一种将结果记录下即可

注意模运算速度感人

C. Cube Problem

\[(a+b+c)^3-a^3-b^3-c^3=3(a+b)(b+c)(c+a)\]

求出n/3的所有约数,枚举两个,算出另一个check一下即可

D. Ksusha and Square

大意是在一个凸多边形内(包括边上)随机选俩不同的格点,以它们连线为正方形对角线,求这个正方形的期望面积

正方形面积等于\(((x_1-x_2)^2+(y_1-y_2)^2)/2\)

我们要算出所有正方形面积和除以正方形个数

这个式子行列是独立的,且我们很容易可以得出凸多边形内每个x/y坐标的点的个数

发现问题转换为

求\(\sum_i \sum_j a_i \times a_j(i-j)^2\)

设\[s_0=\sum_i a_i\ ,s_1=\sum_i a_i \times i\ ,s_2=\sum_i a_i \times i^2\]则\[\sum_i \sum_j a_i \times a_j(i-j)^2\]\[=\sum_i a_i\sum_j a_j(i^2-2ij+j^2)\]\[=s_0 \times s_2-\sum_i a_i \times i\sum_j a_j(i-2j)\]\[=s_0 \times s_2-s_1^2\]

On可以得出结果注意一些精度问题

E. Close Vertices

点分治水题

一维排序一维树状数组维护一下

就是麻烦。。

 

  • 蒟蒻2015年6月13日 下午5:27 回复

    请问题目在哪里可以找到= =

    #1  
  • 蒟蒻2016年3月22日 下午7:11 回复

    求题目

    #2