2020-2021:teams:i_dont_know_png:ntuwftrial-2016
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:ntuwftrial-2016 [2020/08/07 17:55] potassium A |
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 精度也是足够的。 | ||
| 行 53: | 行 56: | ||
| ===== F - Lonely Dreamoon 2 ===== | ===== F - Lonely Dreamoon 2 ===== | ||
| - | Solved by . | + | Solved by Potassium. |
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| + | 给一个序列，要打乱顺序，最大化相邻两项差的最小值。 | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | 先排序，分奇偶讨论，如果是偶数则直接匹配（如，3142，51627384），然后发现奇数的时候 $[i,i+\frac n2]$ 区间仅会有一个可以不被选到，于是枚举这个最小值然后匹配即可。 | ||
| ===== G - Dreamoon and NightMarket ===== | ===== G - Dreamoon and NightMarket ===== | ||
| - | Solved by . | + | Solved by qxforever. |
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| + | 给 $n$ 个数，求所有非空子集的权值和第 $k$ 小。$n\le 2\times 10^5,k\le \min(2^ n-1,10^6)$ | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | 二分答案 $x$ 。我们只需要找到 $k$ 个权值和 $\le x$ 的子集即可，或者找不到这么多子集，直接搜索的复杂度是 $O(k)$ 的。总时间复杂度 $O(k\log V)$ 。 | ||
| - | + | 这题是 Dreamoon 在 [[https://zhuanlan.zhihu.com/p/56269536 | 从枚举到 K 短路]] 中提到的一个例题，里面提到的其他用二分 + 搜索 + 剪枝的题目也蛮巧妙的。 | |
| 行 82: | 行 85: | ||
| ===== H - Split Game ===== | ===== H - Split Game ===== | ||
| - | Solved by . | + | Solved by qxforever. |
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| + | 给在第一象限 $n$ 个顶点的简单多边形，问过原点的一条直线最多能把多边形分为几部分。 | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | |||
| + | 只有在经过顶点时才会改变答案。极角排序后扫描，根据被扫的点和其相邻两个点的位置关系分为 $8$ 种情况进行讨论。取最大值作为答案。 | ||
| + | |||
| + | 看了下其他队的，似乎只用分 $4$ 种情况。 | ||
| 行 98: | 行 105: | ||
| ===== I - Tree Game ===== | ===== I - Tree Game ===== | ||
| - | Solved by . | + | Solved by Potassium. |
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| + | 给一棵树，初始每个边都是白色，每次选择两个路径全白的叶结点将其中路径的边全变成黑色，问最少操作步数使得无法继续操作。 | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | 可以转化成二叉树的问题，因为如果三个则必然子树内匹配一对。向上传当前子树贡献二叉、枝条或空树，分类讨论一下即可。 | ||
| 行 114: | 行 121: | ||
| ===== J - Zero Game ===== | ===== J - Zero Game ===== | ||
| - | Solved by . | + | Solved by Potassium & nikkukun. |
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| + | 给一个长度为 $n$ 的 $01$ 序列，一次操作是将某个元素取出并插入到任意位置。$q$ 次询问 $k_i$ 次操作后最长的连续 $0$ 长度。 | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | |||
| + | 对 $1$ 的操作相当于删掉 $1$ 也即合并两段连续 $0$，对 $0$ 的操作相当于向最长连续 $0$ 段添加 $0$。 | ||
| + | |||
| + | 考虑求出答案区间 $[l,r]$ 。设 $0,1$ 的前缀和分别为 $s_0,s_1$，则区间满足 $s_{0,r}-s_{0,l-1}\le k$ 条件，且 $(s_{0,r}-s_{0,l-1})+(k-(s_{1,r}-s_{1,l-1}))$ 最大。式子化为求 $(s_{0,r}-s_{1,r})-(s_{0,l-1}-s_{1,l-1})$ 最大的合法区间。设 $f_i=s_{0,i}-s_{1,i}$ ，维护一个递增的单调队列即可求出答案。 | ||
2020-2021/teams/i_dont_know_png/ntuwftrial-2016.1596794150.txt.gz · 最后更改: 2020/08/07 17:55 由 potassium
