2020-2021:teams:intrepidsword:2020-nowcoder-multi-4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:intrepidsword:2020-nowcoder-multi-4 [2020/07/28 22:54] admin [H. Harder Gcd Problem] |
2020-2021:teams:intrepidsword:2020-nowcoder-multi-4 [2020/07/28 22:56] (当前版本) admin [I. Investigating Legions] |
||
|---|---|---|---|
| 行 60: | 行 60: | ||
| ===== I. Investigating Legions ===== | ===== I. Investigating Legions ===== | ||
| - | **题目大意**： | + | **题目大意**：有 $n$ 个点，$m$ 种类型，现在告诉你两两点对是否属于同一连通块，但是有至多 $5\%$ 的概率反转。让你求出每个点的类型。其中，$30\le n\le300,1\le m\le\lfloor\frac{n}{30}\rfloor$。每个点随机一种类型，出错也是随机的。 |
| - | **题解**： | + | **题解**：对于每个点，考虑剩下的点哪些和它属于一个连通块。对于同一连通块的点，它们共同的邻点应当很多，反之则应当很少。对于同一连通块的，大致计算一下期望应当是 $\frac{n}{m}-\frac{2n}{20m}$，反之则大致是 $\frac{2n}{20m}$。经过本地测试，取最大值的 $\frac{2}{3}$ 为阈值可正确判断，并且 ''%%ac is ok%%''。 |
| ===== J. Jumping on the Graph ===== | ===== J. Jumping on the Graph ===== | ||
2020-2021/teams/intrepidsword/2020-nowcoder-multi-4.1595948063.txt.gz · 最后更改: 2020/07/28 22:54 由 admin
