2020-2021:teams:intrepidsword:2015-shanghai-regional
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2015-shanghai-regional [2020/07/05 21:52] toxel add H |
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 ===== | ||
| 行 19: | 行 27: | ||
| * 首先将出现次数为 $1$ 的字符直接算入 $u$ 中，不参与转移，即 $dp[\Sigma+1][0][0][cnt[1]][0]=1$ | * 首先将出现次数为 $1$ 的字符直接算入 $u$ 中，不参与转移，即 $dp[\Sigma+1][0][0][cnt[1]][0]=1$ | ||
| * $dp[i][j+1][k][u+1][v]+=dp[i][j][k][u][v]$ | * $dp[i][j+1][k][u+1][v]+=dp[i][j][k][u][v]$ | ||
| - | * $dp[i][j+2][k][][v+1]+=dp[i][j][k][u][v]*2(cnt[i]-j-1)$ | + | * $dp[i][j+2][k][u][v+1]+=dp[i][j][k][u][v]*2(cnt[i]-j-1)$ |
| * $dp[i][j+1][k+1][u+1][v]+=dp[i][j][k][u][v]*(cnt[i-1]-k)$ | * $dp[i][j+1][k+1][u+1][v]+=dp[i][j][k][u][v]*(cnt[i-1]-k)$ | ||
| * 这些转移都不难。最后当 $i=2$ 时，要注意记录用来包围 $u$ 的字符 | * 这些转移都不难。最后当 $i=2$ 时，要注意记录用来包围 $u$ 的字符 | ||
| 行 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.1593957136.txt.gz · 最后更改: 2020/07/05 21:52 由 toxel
