Codeforces Round #456 (Div. 2)

A. Tricky Alchemy

题目描述：要制作三种球：黄、绿、蓝，一个黄球需要两个黄色水晶，一个绿球需要一个黄色水晶和一个蓝色水晶，一个蓝球需要三个蓝色水晶，现有(A)个黄色水晶和(B)个蓝色水晶，要制作(x)个黄球，(y)个绿球和(z)个蓝球，还需要多少个水晶？

solution
(max(0, x*2+y-A)+max(0, z*3+y-B))

时间复杂度：$ O(1) $

B. New Year's Eve

题目描述：在(1)~(n)中选不多于(k)个数，使选出来的数的异或和最大，输出最大值

solution
当(k=1)时，最大值为(n)。当(k>1)时，令LG为大于n的最小的(2)的幂，则一定存在两个数（例如(n)和(LG-1-n),其中(LG-1-n)<(n)）使得它们的异或和为(LG-1)，即最大值为(LG-1)

时间复杂度：(O(1))

C. Perun, Ult!

题目描述：你在玩一个游戏，在游戏中你只有一次攻击的机会，你的攻击值为(damage)，当你攻击时，所有敌人都会受到伤害，假设攻击后有(s)个敌人死亡，那么你的得分为((bounty+increase*t)*2)，其中(t)为你攻击的时刻，(t)为整数，其余值均为给定常数。每个敌人有三个属性：最大生命值(max_health)，初始时的生命值(start_health)，单位时刻恢复的生命值(regen)。当一个敌人的生命值小于等于(0)时，敌人死亡。游戏开始后还有(m)个更新信息，每个更新信息为：在(time)时刻，敌人(enemy)的生命值更改为(health)。问你的得分最大值，当最大值为无穷时，输出(-1)。注意：(increase, regen)可能等于(0)。

solution
每个敌人的生命值与时间的关系可看做一条折线，再作直线(y=damage)，显然得分最高的时刻会在交点处取得。

现先判断最大值为无穷的情况
1、若 (increase=0)，则不可能无穷
1、若 (increase eq 0)，且(damage geq max_health)对所有敌人成立，则最大值为无穷
2、若 (increase eq 0)，且某个敌人的(regen=0)，最后一次更新的生命值(health leq damage)，则最大值为无穷

判断完无穷的情况后，将所有更新信息（将初始生命值看做时刻(0)的更新信息）按敌人为第一关键字，时刻为第二关键字排序。计算交点时刻，同时记录该交点为哪个敌人，若不存在交点，但该敌人可被消灭，则将该段折线的最后时刻((regen=0)时为inf,即一个比较大的数）看做交点。
将交点按时刻排序，更新信息按时刻排序。按交点时刻进行扫描，同时维护该时刻可消灭的敌人数目，更新答案。具体维护操作为：根据更新信息判断在该时刻，某个敌人的可消灭状态是否改变，更新答案后，该交点的敌人视为不可消灭。

时间复杂度：(O(nlogn))

D. Fishes

题目描述：有一个(n*m)的鱼塘分成一个个(1*1)的格子，每个格子最多只能有一条鱼。有一个(r*r)的网，捕鱼时若网的左上角在格子((x, y))，则((x, y))到((x+r-1, y+r-1))的鱼都能捕到，注意：整个网必须在鱼塘内。现要在鱼塘中放(k)条鱼，使得随机撒网时捕到鱼的数目的期望值最大。

solution
如果我们把每个格子能被多少种撒网方式覆盖写成一个函数(f(x, y))，则

[f(x, y)=[min(n-r+1, x)-max(x-r, 0)][min(m-r+1, y)-max(y-r, 0)] ]

期望值

[E=frac{1}{(n-r+1)(m-r+1)} sum f(x_k, y_k) ]

若固定鱼的(x)坐标，则(f(x, y))关于(y)为一个单峰，且在(y=frac{m+1}{2})时有最大值。所以可以用一个优先队列来维护最大值，优先队列初始元素为每一行的(frac{m+1}{2}-1)和(frac{m+1}{2})，即(n*2)个元素，每次取出最大值，然后将它左或右（本来向左的为左，向右的为右）的元素添加到优先队列。

时间复杂度：(O((n+k)log(n+k)))

还有另外一个方法：注意到其实整个二元函数是一个以((frac{n+1}{2}, frac{m+1}{2}))为顶的一个山峰，所以初始元素可以只有一个元素：山顶，然后每次取出最大值后把它邻近的四个格子都添加到优先队列里，但要注意判重。

时间复杂度：(O(klogk))

E. Prime Gift

题目描述：有(n)个不同的质数，求第(k)小的数满足它的所有质因数都属于这(n)个数。(n leq 16), 数据保证答案小于(10^18)

solution
首先可以用二分将问题转化为判断性问题，即求(x)内有多少个数满足条件。
若这(n)个质数为最小的(16)个质数，则(10^18)内有(755,104,793)个数满足条件，但若为(8)个质数(2, 5, 11, 17, 23, 31, 41, 47)，或(3, 7, 13, 19, 29, 37, 43, 53)，则对应个数为(1,119,429)和(500,675)。所以可以将(n)个质数从小到大排序，然后分成偶数位和奇数位两个集合，每一集合搜索出满足对应集合条件的数字，而满足原集合条件的数字可由两个集合的数字相乘得到。根据单调性，可用双指针在线性时间内求出(x)内符合原集合条件的数字个数。

时间复杂度：(O(log(10^{18})*10^6))