AC. 梦想

frank_c1

Codeforces Round #356 (Div. 2)

发布于2016年06月09日 | 暂无评论 | 848阅读 | 比赛经历,生涯框架

昨天晚上有一场Round,又是ABC和DE形成鲜明对比。前三道题近千人过,后两道题两位数过。大概出题人觉得Div. 1 A题应该稍微简单一点,B题开始要难一点。Div. 2?随便扔几道水模拟吧……

凭借手速和ABC的1A强行挤到139,D题好几次出不来怎么办啊QAQ

A. Bear and Five Cards

给定5个不大于100的正整数,要求删除两个相同的数,或删除三个相同的数。求剩下数之和的最小值。

按照题意模拟~

B. Bear and Finding Criminals

给定长度为n的01序列和位置p。你可以知道到p的距离是i的所有位置上的数之和。求可以确定多少个位置上是1。

1 \le n \le 10 ^ 5

按照题意模拟~

C. Bear and Prime 100

交互题。有一个[2,100]的正整数x,有20次询问机会,可以询问一个[2,100]的正整数a,交互程序会回答a是否是x的约数。你需要回答x是质数还是合数。

考虑如果n以内的整数x是合数,必有一个不大于\sqrt{n}的质因子。我们枚举2,3,5,7,如果回答均为no,说明x是质数。

如果在质因子p上回答为yes,那么有两种可能:x就等于p,或者x还含有其它的质因子。不过我们可以确定x一定含有质因子p

于是我们可以枚举[2,50]的质因子q,询问pq,如果有回答为yes,则x是合数,否则x是质数。

D. Bear and Tower of Cubes

我们对一个正整数x作如下操作:(1)找到最大的a,满足a ^ 3 \le x。(2)将x减去a ^ 3cnt自增1。(3)重复步骤(1)(2),直到x = 0

求所有不大于m的正整数能得到cnt的最大值,并求出最大的满足cnt值最大的正整数。

1 \le m \le 10 ^ {15}

感觉这道题的结论好神啊……比赛时硬刚90min没想出来。

a为满足a ^ 3 \le m的最大的a,有

1.选择a作为第一个选定的值,那么x只需满足x \le m,本轮结束后最多剩下m - a

2.选择a-1作为第一个选定的值,那么x需要满足x \le a ^ 3 - 1,本轮结束后最多剩下a ^ 3 - 1 - (a - 1) ^ 3

3.选择a - 2作为第一个选定的值,那么x需要满足x \le (a - 1) ^ 3 - 1,本轮结束最多剩下(a - 1) ^ 3 - 1 - (a - 2) ^ 3

由于(a ^ 3 - 1 - (a-1) ^ 3) - ((a - 1) ^ 3 - 1 - (a -2) ^ 3) = 6a - 6 \gt 0,可以发现情况3一定不会比情况2更优。

于是对于m,我们只需考虑第一轮取aa - 1,直接搜索即可。时间复杂度不是很会证……

E. Bear and Square Grid

给定n \times n的方格,部分格子有障碍。你可以选择一个k \times k的子方格将其中的障碍全部移除。求能图中的最大连通块最大是多少。

1 \le k \le n \le 500

当时一心去想D了,怎么没去看看这么水的题……

我们只需考虑图的最大连通块一定是与k \times k网格连通的情况。

那么如果我们选定了一个k \times k的网格,我们可以用O(k)的复杂度求出它四边共与多少个格子连通。

我们可以先DFS预处理一下连通块,可以用类似并查集的方式维护连通块大小。用滑动窗口的思想,k \times k的网格在滑动时,网格内部的所有格子不应计入四周的连通块大小,在滑动时加减一下即可。

时间复杂度O(n^2 k)

[UPD] Rating 1892怎么还差8呀。求下一次紫名啊啊啊……我要紫名QAQ