【10.26】集美大学第九届程序设计竞赛（同步赛）

ALL：13
AC：7
补题：3

题解：集美大学第9届校赛【出题人题解】

---

逛孙厝的贝贝

题意：略。

思路：问题拆为两部分：

1. 在 $m$ 个 有体积上限 的编号为 $1\sim m$ 的盒子里放入 $n$ 个球，问方案数量。
2. 在 $m$ 个 无体积上限 的编号为 $1\sim m$ 的盒子里放入 $n$ 个球，问方案数量。

第二个问题隔板法即可。第一个问题解法：

考虑 DP ，定义 $dp(i,j)$ 表示前 $i$ 个盒子恰好放入 $j$ 个小球的方案数量，转移方程 $dp(i+1,j+dt)+=dp(i,j)$ ，其中 $dt\in [0,w_{i+1}]$ 。这一步可以用前缀和优化。总时间复杂度为 $O(n\cdot m\cdot w)$ 。（赛时脑抽了，一直在想值域上限为 $k=5\cdot 10^6$ 的转移，没有关注到上限其实为 $\sum m\cdot w=9\cdot 10^4$）

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=54362666

---

区间

题意：略。

思路：贪心思维题。从高位开始贪心，我们把 $r_i$ 视作该区间选择的数字。遍历到 $bit$ 位时：

1. 如果 $n$ 个区间这一位都是 $1$ ，说明可以取到 $1$ ，那么上界不需要调整，需要调整下界：（如果下界这一位是 $0$ ，说明下界缩小时必然会经过这一位为 $1$ ，那么直接把下界赋值为 $2^{bit}$ ）。

2. 如果 $n$ 个区间这一位不全为 $1$ ，那么取不到 $1$ ，同样要调整上下界。如果一个区间在这一位上界为 $1$ 且下界为 $0$ ，那么下界缩小时必然存在 $011111\cdots (共bit位)$ 状态，为了使后面的贪心更顺利，全为 $1$ 最好。上下界赋值为 $2^{bit}-1$ 。

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=54368000

---

序列

题意：略。

思路：思考一个数字 $a_i$ ，需要满足左边或右边的数字都小于等于 $a_i$ ，那么需要把左边大于 $a_i$ 的数字调换到右边，右边的也同理。而且可以发现左边 / 右边所有的数字经过调整之后，大于 $a_i$ 的数字刚好是紧邻 $a_i$ 的，因此调换次数为左边 / 右边大于 $a_i$ 的数字个数，取最小即可。

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=54368396