9.9 比赛总结

P~S。

A

改成 kruskal 重构树或直接并查集合并，跑一个树上背包。

C

贪心 1

容易发现，从 \(k\) 到 \(k+1\)，最多有 \(4\) 种情况：

• 增加一个 A 类。
• 增加一个 B 类。
• 减少一个 A 类，并增加组。
• 减少一个 B 类，并增加组。

如果不是这些，那 \(k\) 的方案不是最优的。

用 \(5\) 个可删堆维护这些情况即可，注意判空。

贪心 2

实际上，从 \(k\) 到 \(k+2\) 会简单一些，只有 \(2\) 种情况：

• 增加两个单个（A 或 B）。
• 增加一组。

只需要 \(2\) 个可删堆维护。

贪心 3

对于一组物品，分为两类：

• B 类小于 A 类，这时必定先选 A 再选 B，所以可以直接拆成两个物品。
• B 类大于 A 类，这时把两个物品组合考虑，排序的权值为两个物品平均值。

按权值从大到小排序，从前往后考虑，对于一个物品：

• 单个的，直接得到 \(k+1\) 答案。
• 两个的，直接得到 \(k+2\) 答案。对于 \(k+1\) 答案，两种情况：
  • 选择这一组物品，并减去前面一个可以减的物品。
  • 不选择这一组物品，并加上后面一个可以加的物品。

决策单调性

类似贪心 3 的方法对物品分类，对每一类分别求取 \(k\) 个物品的答案（类似上方法）。

设 \(f_k\) 表示答案，\(g_k,h_k\) 分别表示只考虑第一类和第二类的答案，则 \(f_k=\max_{j=0}^kh_k+g_{k-j}\)。容易发现，\(g_{k-j}\) 满足四边形不等式，具有决策单调性。

贪心在考试时可以感性理解，不济就写一个对拍，最好弄一个数据点分治（不然你写对拍干什么）。

B

找到第一个为 \(1\) 的位置 \(p\)，再把 \(p\) 与其它的 \(1\) 的位置交换，然后对 \(p\) 的其它位置冒泡排序，这时分两种情况：

• 交换后 \(p\) 是 \(0\)，如果没有完成排序，则往左边找正确位置。
• 交换后 \(p\) 是 \(1\)，说明新串的 \(1\) 的个数大于原串 \(1\) 的个数，于是如果没有完成排序，正确位置在 \([p+1,n-c-1]\)。

综上，只需在 \([1,n-c-1]\) 中找 \(p\) 的正确位置即可。

总次数为 \(c-1+n-c-2+\dfrac{(n-1)(n-2)}{2}=n-3+\dfrac{(n-1)(n-2)}{2}\leq 120\)。

记得写 SPJ。

D

对于 \(k=0\)，所有的合法格子一定是类似倒金字塔的结构，且能够分为两部分。转化为：一个网格，第 \(i\) 列有 \(i\) 个格子，格子 \((i,j)\) 可以被选择当且仅当 \((i-1,j)\) 和 \((i,j-1)\) 被选择，直接 DP。