Codeforces 掉分日常(七):几个过渡小问题

Codeforces 掉分日常之 1242 A/B/C、1257D/E/F

写在前面

这几天毕设、组里和实习三方面的事情都比较忙,写算法题的时间越来越少了。最近填完了 World Final 的坑,也花了不少工夫,前几天在 Polygon 上出了几道题,还挺有意思的。前两天有两场 CF 比赛,时间都比较晚,不想睡得太晚就没有参加。补了一下题,思路都挺简单的,有几道题只是对 coding 要求比较高。这篇博客改一下风格,不做详细分析了,快速地过一下上两场 CF 的所有(对我来说可做的)题。

1242 A. Tile Painting

对 n 个格子进行染色,对于任意 i, j 若有 则这两点必须同色。问至多染成多少种不同的颜色。

稍微模拟一下可以发现,如果 n 有两个不同的质因子,答案一定为 1。否则 n 一定可以表示成 ,则答案为 p+1。

这道题 n 的范围是 ,因此直接暴力枚举 1 到 的数试除即可;如果 n 的范围是 ,可以用 Miller_Rabin 判素数 + 开根判素数平方 + 枚举判素数k(k>3)次方解决。

 

1242 B. 0-1 MST

一个 n 个点的完全图,其中有 m 条边的权值为 1,其余边的权值为 0。求最小权值生成树 Minimum Spanning Tree 的权值。

题目可以等价为:求图中 0-连通块(即只能走 0 边的连通块)的数量。由于 0 边有 条,因此 dfs 的时候不能暴力循环所有相邻的点,而是搞一个 set 装所有未遍历的点,每次遍历 set。可以证明 set 被遍历的次数是 O(m) 的。

 

1242 C. Sum Balance

给定 k () 个集合,每个集合中有 n() 个数,所有集合中的每个数互不相同。现在每个集合中取出一个数,交换顺序后再依次放回,有没有可能让每个集合中所有数的和相等。

首先,由于所有数都是固定的,我们一开始就可以算出所有数的总和,除以 k 就是每个集合目标的和。如果除不尽 k ,那么答案肯定是不可能。

然后可以算出每个集合的和,以及其与目标的差。接下来就遇到瓶颈了,怎么确定每个集合中取出哪个数、放到哪个集合中去呢?虽然 k 比较小,但每个集合中的数很多,看似很难选择。

原题目很长,不细心看可能会不注意到这句话:所有集合中的每个数互不相同,事实上这是这道题的关键。我们改变思路,假设从第 1 个集合中取出了 x,我们暂时先不考虑把它放到哪个集合中去,而是计算第 1 个集合需要放入的数。由于所有数都不同,这个“需要放入的数”要么不存在,要么只存在于一个唯一的集合里,假设是 2 号集合。那么 2 号集合取出的数就确定了,它又有一个“需要放入的数”....

如此递归下去,问题就转化为了(不太直观但仔细想一下是等价的):一个 n*k 个点的图,每个点有 0-1 条出边,形成若干个环。每个点有“颜色”,即其属于的集合 id。问是否存在若干个环,它们恰好不重复地覆盖所有集合。

由于题目数据比较水,化简到这一步之后我看有写代码暴力 dfs 也过了。标程给出了一种 的解法:扫描出所有环,并用位压的方式存储每个环覆盖的 id。然后用 SOS dp(枚举所有集合的所有子集)计算满的 mask 是否能够被覆盖即可。由于题目要求输出方案,因此这里 dp 的过程中还要记录路径,其余细节不再赘述。

参考代码:64696185

 

1257 D. Yet Another Monster Killing Problem

勇者杀恶龙,每个勇者有耐力和攻击力两个数值,恶龙只有攻击力。每次派出一个勇者,他一个个地与恶龙战斗,直到打败等同自己耐力数量的恶龙,或者被恶龙打败(攻击力比它低)。问至少要派出多少个勇者。数据范围:勇者+恶龙数目小于

二分。

 

1257 E. The Contest

三个集合,调整到整体有序(集合 1 的数全都小于集合 2 的数,集合 2 的数全都小于集合 3 的数),至少要移动多少个数。

前缀和扫一下,真的很简单。

 

1257 F. Make Them Similar

定义两个数中二进制 bit 为 1 的数量相等称为两数相似。给定数组 A,问是否存在整数 x ,使数组 B=A xor x(A 中每个元素异或 x)中的数两两相似。

首先用常见手法把 A 中的一个数变成 0,即所有数异或 A[0],最终结果也异或 A[0]。然后剩下的数中如果有人的 popcount 为奇数,则直接答案不存在。否则转化为问题:找到一个 x 使得:每个数的二进制位中的 2k 个 1 恰好有 k 个与 x 重合。

暴力枚举 x 的复杂度是 ,考虑分治,分别枚举 x 的前 位 和后 位。把 x 的前 15 位拿去和每个数异或,算出还差多少个 1,然后再拿后 15 位去异或,看是否正好有这么多的 1。这个过程可以用一个 map<vector<int>, int> 来存储。C++ 标准库中的 vector 是没有哈希函数的,所以不能用 unordered_set<vector<int>>,除非你自己定义其哈希函数。但 vector 是有默认比较函数的(字典序比较,见 less<vector<T>>),因此可以作为 set/map 的键类型(当然,会引起拷贝复制,插入查询等等的复杂度都要乘上一个 O(vector.size()) )。这种用法比较少见,值得学习。