2020-2021:teams:hotpot:200530-200605
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200530-200605 [2020/06/05 14:25] 喝西北风 |
2020-2021:teams:hotpot:200530-200605 [2020/06/05 16:38] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| =====本周推荐===== | =====本周推荐===== | ||
| - | 林星涵： | + | 林星涵：Codeforces Round #647 (Div. 1) - A |
| - | 陶吟翔： | + | 题目大意：给定$n$个点$m$条边，每个点有一个希望染的颜色，这个颜色是一个正整数。现在如果选择一个点染色，那么这个点会被染上最小的且不与和这个点相连的已染色的点的颜色相同的颜色，问是否能够成功染色，能输出方案，不能输出-1。 |
| + | |||
| + | 数据范围：$n,m \le 5 \times 10^5$ | ||
| + | |||
| + | 解题思路：显然应该从颜色小的开始染，我们对每个点的期望颜色进行排序，然后从小往大染，每次染的时候看这个点与哪些点相连，并检查是否能够成功染色，如果途中不能成功染色直接输出-1。这样的算法看似十分暴力，但是由于边数与点数同阶，所以实际上算法的复杂度就是$O(n)$，由于还需要排序，所以总复杂度为$O(n \log n)$。 | ||
| + | |||
| + | 陶吟翔：[[dualgraph|对偶图]] | ||
| 郭衍培： | 郭衍培： | ||
2020-2021/teams/hotpot/200530-200605.1591338321.txt.gz · 最后更改: 2020/06/05 14:25 由 喝西北风
