CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
======2020/05/30——2020/06/05周报======

=====团队训练=====

由于周末事情太多所以没有进行。

=====林星涵=====

====专题====

=====陶吟翔=====

====专题====

[[dualgraph|对偶图]]

=====郭衍培=====

====专题====

本周无

=====本周推荐=====

林星涵：Codeforces Round #647 (Div. 1) - A

题目大意：给定$n$个点$m$条边，每个点有一个希望染的颜色，这个颜色是一个正整数。现在如果选择一个点染色，那么这个点会被染上最小的且不与和这个点相连的已染色的点的颜色相同的颜色，问是否能够成功染色，能输出方案，不能输出-1。

数据范围：$n,m \le 5 \times 10^5$

解题思路：显然应该从颜色小的开始染，我们对每个点的期望颜色进行排序，然后从小往大染，每次染的时候看这个点与哪些点相连，并检查是否能够成功染色，如果途中不能成功染色直接输出-1。这样的算法看似十分暴力，但是由于边数与点数同阶，所以实际上算法的复杂度就是$O(n)$，由于还需要排序，所以总复杂度为$O(n \log n)$。

陶吟翔：[[dualgraph|对偶图]]

郭衍培：

给定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|题目链接]]


结论1：若一个数a大于一个集合A中的所有数，且A中的所有数之和大于a，则存在A的一个子集，该集合所有数之和等于A。且该子集可以由A中前n大的数组成。


结论2：用p个$p^{a_i-1}$替换$p^{a_i}$，结果一定更优


由结论1，最大的数a在两个集合中的出现次数之差不超过1（否则一定不优）。且若差为1，则另一个集合要么包含其余全部小于a的数（其余数之和仍小于a）；要么另一个集合的前n大数之和等于a。若为后者，由结论2，此时最优策略是将小于a的前n大数放进另一个集合。接下来，可以重复上述过程，直到小于a的所有数之和小于a。
实现时，可以通过模一些大的质数（只模一个1e9+7会被卡）判断是否相等。
CVBB ACM Team

用户工具

站点工具

页面工具
