A. ArcSoft’s Office Rearrangement
Tag: 贪心
给定一列数，要把它分成K个大小相等的堆，每次可以
- 合并两个相邻的堆
- 将一个堆拆成两个，大小自定
解法
贪心，从第一个开始，如果这堆的大小跟目标的大小相等，则跳过
如果它的大小大于目标大小，则将它拆成两堆
如果它的大小小于目标大小，则将它并到下一堆里
B. Bomb
Tag: 图论
平面上有1000个炸弹，需要被全部引爆，引爆第i个炸弹需要\(c_i\)的代价，同时会引爆半径\(r_i\)以内的所有炸弹。
问引爆所有炸弹需要多少代价
解法
强联通分量缩点后变成DAG，显然此时选择所有入度为0的炸弹最优
C. Car
Tag: 贪心
一条线段上分成了n个区间，通过每个区间的时间为整数，同时通过前面的区间的速度不大于通过后面区间的速度。求通过整个线段的最短时间。
解法
显然，通过最后一个区间的时间为1个单位
通过第\(i\)个区间的最短时间为\(t_i = \lceil\frac{d_it_{i+1}}{d_{i+1}}\rceil\)
其中，\(d_i\)表示第i个区间的长度
D. Difference
Tag: 折半查找
设函数\(f(x, k) = x\)的各位数的\(k\)次方的和，设\(g(x, k) = f(x, k) - x\)，给定\(y, k\)，求满足\(g(x, k) = y\)的x的个数，其中\(y \le 10^9, y \in \{1, 2,\ldots ,9\}\)
解法
注意到\(f(99999999, 9)=3486784401 > 10^9\)，所以猜想x的范围不会超过\(10^9\)，将x拆成两部分，预处理后枚举前面一半就可以确定后面一半
复杂度\(O(\sqrt{x}\log\sqrt{x})\)
E. Equation
Tag: 搜索
给定\(c_i\)个数字\(1\)到\(9\)，和无数的加号与等号，求可以组成的9以内的不同的加减法的个数，加数有序
解法
手头枚举一下，不难发现，答案绝对不会超过36，考虑搜索+剪枝
实际上，搜索+剪枝可以恰好在时限以内通过此题，大约在950毫秒左右，这样的复杂度不超过\(O(2^n)\)，如果是在比赛时，这样没有问题
考虑优化复杂度，我们可以归类，注意到\(a+b=c\)与\(b+a=c\)是不一样的，但是它们用的数字完全相同，所以可以将其合并，复杂度变为\(O(2^m 3^n)\)，其中\(m=8, n=14\)，大概就变成了前者的1/50左右，对于此题是完全没有问题的
本题的作者给出的做法是在此基础上，将\(1+a=(a+1)\)这样的等式再提出来，放在最后贪心处理，这的等式有8个，这样复杂度就变成了\(O(2^m 3^n p)\)，其中\(m=8, n=6, p = 8\)，这样之后，即使全部枚举，也只需要不超过150万次，完全没有问题
在实际测试中，枚举+剪枝比出题人的方法快一些
F. Four Operations
Tag: 贪心
给定一个长度不超过20的，仅包含1-9的字符串，要求在其中按顺序添加+-*/四个符号，使得表达式的结果最大。
解法
考虑到四个符号的优先级，最后的A*B/C的结果是越小越好，那么AB显然是一位数
然后枚举加号、减号和除号的位置就好，这个复杂度是\(20^3\)的，但是常数小，所以没有被卡掉。
正解是在这个基础上，如果最后的表达式为A+B-C*D/E的话，AB必有一个是一位数，E最多是两位数，这样答案就只有4种，复杂度大概在20^2这个数量级上
（待写题解）
G. Game of Eliminate
（待写题解）
H. Hazy String
（待写题解）
I. Inequality
（待写题解）
J. Just a Math Problem
（待写题解）
K. Kingdom of Obsession
给定\(n, s\)，求一个\(\{s+1, s+2, \ldots, s+n\}\)到\(\{1, 2, \ldots, n\}\)的双射\(f: a\rightarrow b\)，且满足\(a \mid f(a)\)，只需要回答该映射是否存在。
解法
首先，一个最显然的结论是，\([s + 1, n]\)直接映射到\([s+1, n]\)就好。
第二个显然的结论是，如果在\([n+1, s + n]\)之间有两个质数，那么显然答案不存在。
因而，注意下面这个式子：
\[\pi(n) \approx \frac{n}{\ln n}\]通过这个式子，推出结论：如果一个连续区间内只有一个质数，那么这个区间不会太长，即\(\min\{n,s\}\)不太大。
综合以上三点，当\(\min\{n, s\}\)比较大的时候，直接输出不可能即可
否则，将\([s + 1, n]\)直接映射到\([s+1, n]\)之后，对剩下的数暴力匹配就好。
本题的关键在于，通过\(\pi(n) \approx \frac{n}{\ln n}\)能够得出“如果一个连续区间内只有一个质数，那么这个区间不会太长，即\(\min\{n,s\}\)不太大”这一重要结论。