Contest Info

date: 2017.11.02 15:50-20:50

practice link - 10374

Solutions

D. Clones and Treasures

签到题

E. Space Tourists

题目大意 ：在外太空有 \(K^2\) 个站点，每个站点的编号是一个 \(2\) 位 \(K\) 进制数。每个旅行者有一个唯一的 ID（一个 \(N\) 位 \(K\) 进制数），一个旅行者可以被安排到一个站点，当且仅当该站点的编号是旅行者 ID 的子序列。现在问最少保留多少个站点，可以使得每个旅行者都可以被安排到至少一个站点。

题解 ：如果 \(N > K\) ，那么答案显然为 \(K\) 。我们只需要选形如 \(00,11,...,(K-1)(K-1)\) 的站点，由鸽巢原理可以知道，\(N\) 位 \(K\) 进制数中一定有两个相同的位，于是一定存在一个站点可以分配过去。

如果 \(N\leq K\) ，那么我们应当将 \(K\) 种数字，尽可能平均地分为 \(N-1\) 块。那么同样由鸽巢原理，旅行者的 ID 中至少有两位会处于同一块中。我们只需要将每块内部的任意两两数字的排列选出，再加上 \(K\) 个 \(00,11,...,(K-1)(K-1)\) 的站点，就可以满足题目要求了。

J. Terminal

题目大意 ：来自 \(m\) 个队伍的 \(n\) 名程序员在等候乘车。现在只有两辆车，每辆车可以乘坐至多 \(K\) 个人。现在你要给每个人指定一辆车乘坐，满足如下要求：

• \(n\) 名程序员已经形成了一个队列，他们的顺序不可以交换。
• 每一秒钟队首的程序员会前往他被指定的车，当一辆车指定的程序员都上车之后，该车会立即出发。
• 同一个队伍的程序员必须上同一辆车。

问你是否此问题是否有解，如果有解，给出最少的每人等待时间之和。每个人的等待时间定义为从初始时刻，到他被指定的那一辆车出发的时刻。

题解 ：显然被指定到最后一个人所在车的程序员的等待时间是确定的，也即序列长度 \(n\)。 我们考虑枚举另一辆车的出发时间，我们需要尽可能地往这辆车里面塞人。考虑到同一个队伍的程序员必须上同一辆车，所以我们将每个队伍按照最后一个人的出现位置排序，然后做一个背包。每次做完背包之后，找到在区间 \([n-K,K]\) 中最大的装载人数，然后更新答案。

背包可以用 bitset 优化，复杂度为 \(\mathcal{O}(\frac{mK}{32}+mK)\) ，第二部分的常数比较小，可以通过。