2020-2021:teams:hotpot:200530-200605

差别

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

到此差别页面的链接

--- 2020-2021:teams:hotpot:200530-200605 [2020/06/05 14:23]
喝西北风
+++ 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|对偶图]]
 郭衍培：
-[[http://codeforces.com/contest/1361/problem/B|题目链接]]
-给定n个数，将这些数分为两个集合，使得这两个集合的数总和之差最小。n个数的给出方式是给定一个p和$a_1,...,a_n$，这n个数是$p^{a_1},p^{a_2},...,p^{a_n}$。结果模$10^9+7$
+给定n个数，将这些数分为两个集合，使得这两个集合的数总和之差最小。n个数的给出方式是给定一个p和$a_1,...,a_n$，这n个数是$p^{a_1},p^{a_2},...,p^{a_n}$。结果模$10^9+7$[[http://codeforces.com/contest/1361/problem/B|题目链接]]

2020-2021/teams/hotpot/200530-200605.1591338238.txt.gz · 最后更改: 2020/06/05 14:23 由喝西北风