contest 1

1001 Avian Darts（咕）

不是很懂三维空间角速度怎么合成的，改天问一下隔壁物竞的同学吧，先咕了。

update：问了，他们表示没听懂我在说什么。

1002 Boring Task（咕）

下次一定吧。1007 把我人都搞没了。

1003 Cookies

从后往前处理，第 \(i\) 天第 \(k\) 块以前会有 \(\lfloor\frac{k-1}{p_i-1}\rfloor\) 块被吃掉，加上这个值即可。

考虑怎么求 \(f_n\)，首先 \(divmed(n)\) 的等价定义为 \(\leq \sqrt{n}\) 的最大因子。

It’s difficult to get the value directly in reasonable time.

考虑分段打表，本地跑出 \(f_{2.5\times10^6i}\)（p.s.：hdu 代码限制 64K），跑个十分钟就跑出来了。存差分值好像代码长度要短些。

考虑怎么求 \(divmed(l\dots r)\)，发现用埃氏筛即可。

submission。

1004 Distinct Sub-palindromes

1005 Fibonacci Sum

模 \(10^9 + 9\) 意义下 \(5\) 有二次剩余，斐波那契通项公式 + 等比数列求和。

1006 Finding a MEX

度数 \(>B\) 的用 set 维护；度数 \(\leq B\) 的询问时暴力查。取 \(B=O(\sqrt{n\log n})\) 最优。

【以上是现场莽过去的做法】

大点修改 \(O(\log n)\)，询问 \(O(\log n)\)，考虑平衡一下；使用分块可以做到修改 \(O(1)\)，询问 \(O(\sqrt{n})\)，总时间复杂度 \(O(n\sqrt{n})\)。

由于大块的度数和为 \(O(n)\)，所以可以对所有大点一起分。

1007 Hunting Monsters

考虑固定砍哪些怪物，怎样安排顺序最优。这是个经典贪心问题：所有 \(a_i\leq b_i\) 的排在 \(a_i > b_i\) 的前面；\(a_i \leq b_i\) 的内部按 \(a_i\) 从小到大排；\(a_i > b_i\) 的按 \(b_i\) 从大到小排。

先按这个法则排好序，显然有朴素 dp：\(f_{i,j}\) 表示后 \(i\) 个选 \(j\) 个砍的最小初始体力，转移式：

为了方便优化，我们不妨先把 \(a_i\leq b_i\) 与 \(a_i > b_i\) 分开考虑。

先考虑 \(a_i>b_i\)，显然 \(f_{i,j-1}\leq f_{i,j}\) 且 \(f_{i,j}\leq f_{i-1,j}\)。

考虑 \(\max\{f_{i-1,j-1}+a_i-b_i,a_i\}\) 的取值，它决定于 \(f_{i-1,j-1}\) 与 \(b_i\) 的大小关系。

由于 \(f_{i,j-1}\leq f_{i,j}\)，所以存在 \(j_0\) 满足 \(j\leq j_0\) 时 \(f_{i-1,j-1} \leq b_i\)；\(j > j_0\) 时 \(f_{i-1,j-1} > b_i\)。

注意到 \(f_{i,j}\leq f_{i-1,j}\) 且 \(b_{i} \leq b_{i+1}\)（一开始的贪心性质，注意我们是从后往前 dp），则 \(j_0\) 随 \(i\) 增大而增大。

对于 \(j<j_0\)，有 \(f_{i-1,j-1} \leq b_i\) 且 \(f_{i-1,j}\leq b_i < a_i\)，故 \(f_{i,j}=f_{i-1,j}\)。

对于 \(j = j_0\)，\(f_{i,j}=\min\{f_{i-1,j},a_i\}\)。

对于 \(j>j_0\)，\(f_{i,j}=\min\{f_{i-1,j},f_{i-1,j-1}+a_i-b_i\}\)。它的值取决于 \(f_{i-1,j}-f_{i-1,j-1}\) 与 \(a_i – b_i\) 的大小关系。

考虑加入虚点 \(f\’_{i-1,j_0-1}=b_i\) 来统一 \(j\geq j_0\) 的形式，得到 \(f_{i,j_0}=\min\{f_{i-1,j_0},f\’_{i-1,j_0-1}+a_i-b_i\}\)。

因此不难想到当 \(j \geq j_0\) 时 \(f_i\) 应该是凸的，即 \(f_{i,j}-f_{i,j-1}\leq f_{i,j+1}-f_{i,j}\)。至于怎么证。。。

This convexity can be proved by mathematical induction on