2020-2021:teams:i_dont_know_png:ntuwftrial-2016
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:i_dont_know_png:ntuwftrial-2016 [2020/08/07 18:39] qxforever |
2020-2021:teams:i_dont_know_png:ntuwftrial-2016 [2020/08/07 20:17] (当前版本) nikkukun add C & D, add a reference of G. |
||
|---|---|---|---|
| 行 22: | 行 22: | ||
| ===== C - Crazy Dreamoon ===== | ===== C - Crazy Dreamoon ===== | ||
| - | Solved by . | + | Solved by nikkukun. |
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| + | 在坐标 $[0, 2000] \times [0, 2000]$ 上给 $n \leq 2000$ 条线段，问有多少大小为 $1$ 的格子被至少一条线段穿过。 | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | 枚举 $x \in [0, 2000)$，在 $O(n)$ 时间可以计算出每个线段在 $[x, x + 1]$ 的 $y$ 的范围，用前缀和标记一下即可知道覆盖的 $y$ 的个数。 | ||
| + | 总时间复杂度 $O(Ln)$，$L = 2000$。 | ||
| 行 38: | 行 40: | ||
| ===== D - Forest Game ===== | ===== D - Forest Game ===== | ||
| - | Solved by . | + | Solved by nikkukun & Potassium. |
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| + | 给一个 $n \leq 10^5$ 个结点的树，每次随机选一个点删去，获得连通块大小的分数，问所有删除方案的总得分模 $10^9 + 7$。 | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | 考虑删除 $u$ 时，结点 $v$ 做的贡献。$v$ 能对 $u$ 做贡献，当且仅当 $u$ 是 $(u, v)$ 路径上第一个被删除的点。令 $d(u, v)$ 表示 $(u, v)$ 的距离，由于删除是随机的，因此 $u$ 被第一个删掉的概率是 $\dfrac 1{d(u, v) + 1}$，于是问题变成统计树上点对距离个数。 | ||
| + | 统计点对距离可以用树分治，将所有到根的距离 FFT 卷一下，减去各自子树重复计算的贡献，即可做到总时间复杂度 $O(n \log ^2 n)$。比赛的时候做傻了，抄了拆系数 FFT 的板子，但由于多项式系数之和不超过 $n$，卷出来的结果不超过 $n^2$，因此直接 FFT 精度也是足够的。 | ||
| 行 75: | 行 78: | ||
| 二分答案 $x$ 。我们只需要找到 $k$ 个权值和 $\le x$ 的子集即可，或者找不到这么多子集，直接搜索的复杂度是 $O(k)$ 的。总时间复杂度 $O(k\log V)$ 。 | 二分答案 $x$ 。我们只需要找到 $k$ 个权值和 $\le x$ 的子集即可，或者找不到这么多子集，直接搜索的复杂度是 $O(k)$ 的。总时间复杂度 $O(k\log V)$ 。 | ||
| + | |||
| + | 这题是 Dreamoon 在 [[https://zhuanlan.zhihu.com/p/56269536 | 从枚举到 K 短路]] 中提到的一个例题，里面提到的其他用二分 + 搜索 + 剪枝的题目也蛮巧妙的。 | ||
| 行 104: | 行 109: | ||
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| - | 给一棵树，初始每个边都是白色，每次选择两个路径全白的叶节点将其中路径的边全变成黑色，问最少操作步数使得无法继续操作。 | + | 给一棵树，初始每个边都是白色，每次选择两个路径全白的叶结点将其中路径的边全变成黑色，问最少操作步数使得无法继续操作。 |
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
2020-2021/teams/i_dont_know_png/ntuwftrial-2016.1596796771.txt.gz · 最后更改: 2020/08/07 18:39 由 qxforever
