Page 1 of 3123

ACM-ICPC World Finals Ekaterinburg 2014

挖坑。

https://gist.github.com/lychees/6b77182120f681429f8f
http://blog.brucemerry.org.za/

Problem B. Buffed Buffet

Brief description:

多重背包、凸背包。

有两类物品可供选择,离散和连续。
对于连续的物品,初始单位容量的价值为 t、单位容量价值损失的速率为 dt。
对于离散的物品,每份物品的容量是 w、初始每份物品的价值为 t、每选择一个物品,下一个件物品价值损失的速率为 dt

问恰好装满 m 容量时的最大价值。

Analysis:

 \begin{aligned}g'(i) &= \max_{0 \le j \le i}\big\{ g(j) + \sum_{n=1}^{i-j}(t - (n-1)d\big\}\\&= \max_{0 \le j \le i}\big\{ g(j) + (i-j)t - \frac{(i-j-1)(i-j)}{2}\cdot d\big\}\\&= \max_{0 \le j \le i}\big\{ g(j) + (i-j)t - \frac{i(i-1)+j(j+1)-2ij}{2}\cdot d\big\}\\&= it - \frac{i(i-1)d}{2} + \max_{0 \le j \le i}\big\{ g(j)-\frac{j(j+1)d}{2} - jt + ijd\big\}\\&= it - \frac{i(i-1)d}{2} + \max_{0 \le j \le i}\big\{ h(j) + ijd \big\}\end{aligned}

Problem D. Game Strategy

Problem K. Surveillance

2014 ACM/ICPC Asia Regional Xi'an Online

Problem 1010. Mart Master II

Brief description:

给定一个边权树,初始时,一些结点上已经建立了市场。每个结点会被距离自己最近的市场所支配(距离相同时,被标号最小的市场支配)。
。。。现在你可以新建一个市场,问新建的市场最多可以支配多少结点。

Analysis:

树分治。

。。。考虑每一个分治中心 c。。。
我们需要求出它对每个所有子树中的结点 u 的贡献(也就是有多少结点,在树中,经过 c,被 u 结点支配)

首先需要枚举新建市场的结点。对于所有结点。。求出距离其最近的市场的距离。。d[u]。。
(这一步把所有 mart 都扔到起始点的集合里。。用 Dijkstra 搞搞就行了。。
注意到距离相同的时候要取标号最小的。。所以这里的 d[u] 需要开 pair。。)

。。树分治的部分。。。需要三遍 dfs()。。
我们先 dfs0() 整棵子树...求出每个结点 uc 的距离 dd,与 d[u] 比较。。
如果 d[u] < dd 那么舍弃。。否则加入平衡树。记做 all。。

.. 再 dfs1() 一个分支。。类似的。。得到 sub。。。
。。再 dfs2() 一个分支。。此时可以通过 all - sub。。。统计这个分支中所有结点的贡献。。。

(上面的平衡树也可以直接用 vector 排序后二分、、)。

http://vjudge.net/vjudge/problem/viewSource.action?id=2763104

Page 1 of 3123