用户工具

站点工具


2020-2021:teams:intrepidsword:2015-shanghai-regional

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
2020-2021:teams:intrepidsword:2015-shanghai-regional [2020/07/07 11:21]
toxel fix a bug
2020-2021:teams:intrepidsword:2015-shanghai-regional [2020/07/11 22:21] (当前版本)
admin add CH
行 6: 行 6:
  
 ====== Solutions ====== ====== Solutions ======
 +
 +===== C. Colorful Tree =====
 +
 +**题目大意**:给你一棵树,每个结点有一个颜色。要求支持两种操作,一种是将某个结点的子树颜色全改为 $c$,一种是查询某个结点子树中不同颜色的数量。
 +
 +**题解**:修改时,将 $u$ 子树中所有子树中的 label 删除,将 $u$ 的 label 设为 $c$。显然,一个结点的颜色是其祖先中离它最近且有 label 的那个。那么就变成了一道带修莫队。时间复杂度 $\mathcal{O}(n^{\frac{5}{3}})$。
 +
 +标算似乎是 $\mathcal{O}(n\log n)$ 的。
  
 ===== H. Happiness of Frog ===== ===== H. Happiness of Frog =====
行 25: 行 33:
  
 其中 $i,j$ 可滚动。时间复杂度 $O(\Sigma^{4})$。 其中 $i,j$ 可滚动。时间复杂度 $O(\Sigma^{4})$。
 +
 +===== I. Infinity Point Sets =====
 +
 +**题目大意**:给一个点集,不断将其中的点对之间连线段,把交点加入点集。如果最终可有无限的点,称该点集为无限的。给定一个点集,求所有非空有限子集。无重点。
 +
 +**题解**:一个点集有限,当且仅当点数 $\le4$ 或存在一条直线上至少有 $3$ 个点,而该直线两侧分别至多有一个点。然后扫描线即可做。
 +
 +证明自己多画画图即可。
 +
  
2020-2021/teams/intrepidsword/2015-shanghai-regional.1594092105.txt.gz · 最后更改: 2020/07/07 11:21 由 toxel