2016-SE02-team1

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?SID=fabe45f24bca2f90&action=140

jtjl & akalm

== 流水账 ==

== 总结 ==

== 题解 ==

=== B. Tree Coloring [JTJL] ===

自底向上判断，自顶向下填充即可。时间复杂度O(n)。[[BR]]

=== D. Secret Community Card Game [JTJL] ===

二分图匹配[[BR]]

=== E. Partition [JTJL] ===

最坏期望是1/sqrt(pi)*sqrt(n)个格子能切断，所以3/2*sqrt(n)应该比较宽裕。[[BR]]
考虑随机十个斜率，找出正好切成相等两半的截距，然后判断在该直线上的格子数是否满足要求即可。[[BR]]

=== F. Matrix Consistency [JTJL] ===

XOR高斯消元。考虑x每一维变动对xA的影响，是与A的相应行的1有关。而对于固定的xA，除非为0向量，否则均有1/2的y使得xAy=1。[[BR]]
所以只需求出有多少个自由度即可。但是直接高斯消元是O(n^3^)的，加上bitset也过不了，而且很难找主元……[[BR]]
考虑到答案式子对于自由度k, ans = 1/2 - 2^(-k-1)^，可以发现k>=40之后和1/2的误差小于1e-9，所以直接暴力消元，自由度大于40的时候break就好啦。[[BR]]

=== G. MST of Random Points [JTJL] ===

（原问题的理论复杂度也是O(nlogn)，但是比较难写）[[BR]]
考虑到数据的随机性，每个点只可能和附近的点连边。对于比较小的n直接暴力求最小生成树即可，对于比较大的n，我们在坐标范围分成sqrt(30000) * sqrt(30000)个网格，对于每个点，只和它所在的网格，以及以该点为左边界中心的大约8*8的网格中的点连边，这样选中的边大概有n * 64条，然后暴力做MST即可。[[BR]]
~~（大概有各种乱搞姿势吧……，调调参数拧一拧~~

=== I. Statistics [JTJL] ===

考虑到每个物体都是独立的，只需要单独计算。再考虑反面，即1号物品摸第k次的时候，另一个物品还没有被摸过的概率。是P = (p * (1 - p) / (1 - (1 - p)^2^))^k^ [[BR]]
Ans = (n-1) * P + 1[[BR]]
~~(比赛的时候直接看着样例凑凑凑，凑出来的）~~[[BR]]

== 补题 ==

A C ~~G~~ H

=== JTJL ===

 * Unaccepted: G

比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?SID=fabe45f24bca2f90&action=140

jtjl & akalm

流水账

总结

题解

B. Tree Coloring [JTJL]

自底向上判断，自顶向下填充即可。时间复杂度O(n)。

D. Secret Community Card Game [JTJL]

二分图匹配

E. Partition [JTJL]

最坏期望是1/sqrt(pi)*sqrt(n)个格子能切断，所以3/2*sqrt(n)应该比较宽裕。

考虑随机十个斜率，找出正好切成相等两半的截距，然后判断在该直线上的格子数是否满足要求即可。

F. Matrix Consistency [JTJL]

XOR高斯消元。考虑x每一维变动对xA的影响，是与A的相应行的1有关。而对于固定的xA，除非为0向量，否则均有1/2的y使得xAy=1。

所以只需求出有多少个自由度即可。但是直接高斯消元是O(n³)的，加上bitset也过不了，而且很难找主元……

考虑到答案式子对于自由度k, ans = 1/2 - 2^(-k-1)，可以发现k>=40之后和1/2的误差小于1e-9，所以直接暴力消元，自由度大于40的时候break就好啦。

G. MST of Random Points [JTJL]

（原问题的理论复杂度也是O(nlogn)，但是比较难写）

考虑到数据的随机性，每个点只可能和附近的点连边。对于比较小的n直接暴力求最小生成树即可，对于比较大的n，我们在坐标范围分成sqrt(30000) * sqrt(30000)个网格，对于每个点，只和它所在的网格，以及以该点为左边界中心的大约8*8的网格中的点连边，这样选中的边大概有n * 64条，然后暴力做MST即可。

~~（大概有各种乱搞姿势吧……，调调参数拧一拧~~

I. Statistics [JTJL]

考虑到每个物体都是独立的，只需要单独计算。再考虑反面，即1号物品摸第k次的时候，另一个物品还没有被摸过的概率。是P = (p * (1 - p) / (1 - (1 - p)²))^k

Ans = (n-1) * P + 1

~~(比赛的时候直接看着样例凑凑凑，凑出来的）~~

补题

A C G H

JTJL

Unaccepted: G