2012-C08-team5
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
B: Kth Sentence
具体做法可以参考 prowindy 那边的题解，但是不知道为什么 prowindy 程序中的 aha 变量没有使用也能 AC 来着（http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=647827）
不管怎样，总之我按自己的理解去写了一遍，发现我的写法中的那个 start 变量（作用同 aha，表示是否能创建新串）必须使用才能 AC
[wiki:2012-C08-team5-problem-B 程序代码]
----
D: Matrix Operation
坐标映射即可，用视角向量 + 行和列的翻转标记 + 行和列的映射数组进行维护，维护值也只要一个 map，不需要线段树什么的
比赛时试图把『视角向量』与『行和列的翻转标记』写在一起，WA 了很多次。后来发现这样是不对的，应该老老实实分开处理
[wiki:2012-C08-team5-problem-D 程序代码]
----
E: Multi Ending Story
～ 召唤 kotori 学长来此处填坑 ～
[wiki:2012-C08-team5-problem-E 程序代码]
----
F: Network Reliability
做法很简单：
{{{
for(int s=0;s<=mask;s++){
dp[s]=1;
for(int r=(s-1)&s;r>(s^r);r=(r-1)&s)
dp[s]-=dp[r]*rate[cnt[s]-cnt[r]-cnt[s^r]];
}
}}}
其中 cnt[s] 为在 s 这个 mask 下有哪些边，rate[x] 为有 x 条边都消失了的概率。预处理复杂度 O(2^n^ * m)，DP 复杂度 O(3^n^)
原理：如果点集 S 不是连通的，则存在一些划分，能够将 S 划分为一个连通的点集 R 和其他的点 S - R，其中 S - R 的那些点是否连通不用考虑（防止重复计算）
于是点集 S 能够连通的概率就是 1 - dp[R] * rate[连接 R 和 S - R 的边的数目]（另外，为了防止重复计算，枚举的 R 不要被之前枚举中出现过的 S - R 包含）
[wiki:2012-C08-team5-problem-F 程序代码]
----
G: Runaway Domino
在二维平面上，有一列折线型的多米诺骨牌，从中间的某个点 (xt, yt) 以速度 vt 开始向两边倒下
有一个人在 (xp, yp)，走路速度为 yp，想去阻拦多米诺骨牌使其尽可能早地停止倒塌（只需要停止时间尽量早，可以置之不理，但是'''不能手动去推倒'''）
有一个关键条件是：人的速度 vp 一定大于骨牌倒下速度 vt
有了上面的条件，就是一道简单的二分题了（做法不必说了吧，已经很简单了，只要根据上面的条件证明二分是对的就可以了），可惜比赛时没有去注意，错过了这题
[wiki:2012-C08-team5-problem-G 程序代码]B: Kth Sentence
具体做法可以参考 prowindy 那边的题解，但是不知道为什么 prowindy 程序中的 aha 变量没有使用也能 AC 来着（http://acm.hust.edu.cn:8080/judge/contest/viewSource.action?id=647827）
不管怎样，总之我按自己的理解去写了一遍，发现我的写法中的那个 start 变量（作用同 aha，表示是否能创建新串）必须使用才能 AC
D: Matrix Operation
坐标映射即可，用视角向量 + 行和列的翻转标记 + 行和列的映射数组进行维护，维护值也只要一个 map，不需要线段树什么的
比赛时试图把『视角向量』与『行和列的翻转标记』写在一起，WA 了很多次。后来发现这样是不对的，应该老老实实分开处理
E: Multi Ending Story
～ 召唤 kotori 学长来此处填坑 ～
F: Network Reliability
做法很简单：
for(int s=0;s<=mask;s++){
dp[s]=1;
for(int r=(s-1)&s;r>(s^r);r=(r-1)&s)
dp[s]-=dp[r]*rate[cnt[s]-cnt[r]-cnt[s^r]];
}
其中 cnt[s] 为在 s 这个 mask 下有哪些边，rate[x] 为有 x 条边都消失了的概率。预处理复杂度 O(2n * m)，DP 复杂度 O(3n)
原理：如果点集 S 不是连通的，则存在一些划分，能够将 S 划分为一个连通的点集 R 和其他的点 S - R，其中 S - R 的那些点是否连通不用考虑（防止重复计算）
于是点集 S 能够连通的概率就是 1 - dp[R] * rate[连接 R 和 S - R 的边的数目]（另外，为了防止重复计算，枚举的 R 不要被之前枚举中出现过的 S - R 包含）
G: Runaway Domino
在二维平面上，有一列折线型的多米诺骨牌，从中间的某个点 (xt, yt) 以速度 vt 开始向两边倒下
有一个人在 (xp, yp)，走路速度为 yp，想去阻拦多米诺骨牌使其尽可能早地停止倒塌（只需要停止时间尽量早，可以置之不理，但是不能手动去推倒）
有一个关键条件是：人的速度 vp 一定大于骨牌倒下速度 vt
有了上面的条件，就是一道简单的二分题了（做法不必说了吧，已经很简单了，只要根据上面的条件证明二分是对的就可以了），可惜比赛时没有去注意，错过了这题
附加文件
- Contest 8 by way to answer.zip by oldjunyi