Codeforces Round 781 (Div. 2)
A. GCD vs LCM
题意:
给定数n,找到a,b,c,d四个数满足下列条件:
1.
2.
思路:
取特殊情况,令即可。
即构造
时间复杂度:
所需时间与输入规模无关:
1 |
|
B. Array Cloning Technique
题意:
给定一个长度为n的初始数组副本,你可以进行以下两种操作:
- 选择任意一个数组副本,将其复制出一个新的数组副本。
- 选择两个数组副本,交换它们的两个元素。
询问将其中任意一个数组副本的全部元素变相同的最少操作次数。
思路:
- 首先,我们贪心的选择第一个数组副本作为目标,将这个数组的全部元素变成相同。
- 然后,我们记录下初始数组副本中的最大相同数字出现次数,那么将其他所有元素变成相同的交换(操作1)次数显然是。
- 接着我们计算复制数组副本的次数(操作2),我们不难发现每次复制并交换结束后,相同数的个数都会翻倍,所以我们通过这种方式找到最小复制次数即可。
最后,将操作1和操作2的次数相加即可。
时间复杂度:
统计相同数字的最大出现次数中使用了map来完成,所以时间复杂度为:
1 |
|
C. Tree Infection
题意:
给定一棵树,现在要去感染这棵树的全部节点,我们可以在每个单位时间内执行以下两种操作(同时进行):
- 对于所有的节点,如果他的某个孩子节点被感染,那么可以感染一个其它健康的孩子节点。
2.任意选择一个健康的节点,并感染它。询问将整棵树感染的最少时间。
思路:
首先,我们可以发现,感染传播(操作1)只会在一个个"孩子群体"中进行,实际上感染与树并没有太大的关系,我们完全可以把这一个个"孩子群体"取出来。
还是举个例子(第一个案例):7
1 1 1 2 2 4
很显然,这里的"群体"有这些:
{1},{2,3,4},{5,6},{7}我们可以先把所有的群体找出来,然后采用贪心策略,从数量大的群体开始感染,采用如下判断方法:
- 我们从大到小感染所有"群体"(依次对所有"群体"使用操作1一次,然后让它们内部传播),我们记录下完成上述操作后所有群体还剩下的未感染个数(如果已经全部感染则不用管)。
- 如果此时还有剩余节点未被感染,我们让它们内部传播,并手动感染剩余节点最多的"群体"。
即在贪心后模拟感染的过程(实现上可能还是有点复杂了)。
时间复杂度:
使用了map和优先队列,总时间复杂度:
1 |
|
D. GCD Guess
题意:
交互题:
先要猜测一个整数x的大小,你可以按照以下规则询问最多30次:给出数字和,返回
思路:
30次的询问次数,我们应该尝试从位的角度取解决。
那么我们怎么知道每一位取0还是1呢,按照如下方法:
- 假设我们已知
- 那么的~位应该全是0
- 我们可以用是否等于来判断位取0还是1。
- 若等于,则取1,若不等,则取0。
- 此时询问的,而询问数应该大于0,所以我们询问。
- 若等于,则取0,若不等,则取1。
- (这个转换是为了凑出a和b),所以询问为。
时间复杂度:
我们每次询问可以确定数的某一位:
1 |
|
E. MinimizOR
题意:
给定长度为n的数组,定义花费为,现在给出q个询问:
给出整数和,找出区间内的最小花费。
思路:
本题最重要的是证明一个性质:
如果区间内的最大数(即最大数不超过k位),那么答案一定在个区间最小数内按位或产生。
证明如下:对,只有0和1两个数,显然成立。
现在我们将设结论对成立,我们尝试证明对也成立。
分类讨论:
- 若位全是1,那么答案必然出现在之前已经选择的个数中,而且此时选择的个最小数与之前应该是一致的。
- 若位0的个数大于等于2,那么答案必然出现在之前已经选择的k+1个数中,而且此时选择的个最小数与之前应该是一致的。
- 若位0的个数恰好等于1,应该取1,所以答案还是出现在之前选择的个数中,但是此时选择的个最小数与之前不一定一致,因为最坏情况就是之前个数位全是1,而此时位是0的一个数会取代其中的一个数,所以我们这个时候要多取一个数,取个最小数即可。
通过以上说明,我们证明结论:
如果区间内的最大数(即最大数不超过k位),那么答案一定在个区间最小数内按位或产生
现在的任务就是找到区间最小数,这个可以用线段树完成。
此外,因为的范围并不会很大,所以我们每次并不会真的求出它,我们每次都假定它在边界最大值,所以每次最多找到31个最小数。
时间复杂度:
这题的常数会特别大,因为每次询问都需要查找最多31次。
1 |
|