Contest Info

date: 2019.03.12 18:30-23:30

practice link

Solutions

A. Baggage

题目大意：给你一个长度为 \(4n\) 的序列，编号为 \(-2n+1\sim 2n\)，其中 \(-2n+1\sim 0\) 的格子开始时是空的，而 \(1\sim 2n\) 的格子中依次填入了 BABA...。每次操作你可以选取两个连续的非空格子，把它们移动到两个连续的空格子中。要求你给出一个最短的操作序列，使得序列中连续出现 \(n\) 个 A 接 \(n\) 个 B，但是起始位置不做要求。

题解：首先证明至少要移动 \(n\) 步。我们枚举结束时 A 的起始位置，例如位置和开始时对齐：

BABA...BABA
AAAA...BBBB

我们可以发现，前 \(\lceil\frac{n}{2}\rceil\) 个 B 及后 \(\lceil\frac{n}{2}\rceil\) 个 A 必须要移动，那么显然至少要移动 \(n\) 次才能达到要求。其它结束位置都类似可证。

接下来我们构造一个长度为 \(n\) 的解。设 \(n\ge8\)，我们做如下操作：

__BABABA...BABABA
ABBABABA...BAB__A
ABBA__BA...BABBAA
对中间的BA...BA递归处理，注意至多利用左边2个空余格子（如下划线所示），得到
ABBAAA...BB__BBAA
A__AAA...BBBBBBAA
AAAAAA...BBBBBB__

显然每次递归 \(n\) 减小了 \(4\)，又多用了 \(4\) 步操作。

对于 \(n=3\) 的情况，我们需要利用左边的 \(4\) 个空余格子，因此需要特判；\(4\le n\le7\) 时都有满足要求的解，直接暴搜即可。

B. Buffed Buffet

题目大意：有 \(d\le250\) 种食物，离散的食物只能吃非负整数个，吃 \(n\) 个的价值为 \(\sum_{i=1}^{n}t-i\Delta t\)，每个离散食物有固定的质量；连续的食物只能吃非负整数克，吃 \(w\) 克的价值为 \(\int_{0}^{w}t-x\Delta t\mathbb{d}x\)。其中 \(\Delta t\ge 0\)。现在要吃恰好 \(w\le10^{4}\) 克食物，求最大价值。

题解：离散的部分背包，注意到每种食物可以拆成单个的物品，因为我们背包时一定是优先选价值高的，所以不会违反吃的顺序。质量为 \(i\) 的食物显然只会要前 \(\lfloor\frac{w}{i}\rfloor\) 个，因此这部分的时间复杂度为 \(\mathcal{O}(w^{2}\log d)\)。

对于连续的部分，我们的策略显然是一直吃价值最大的，每次只吃一个极小的 \(\mathbb{d}w\)，若有多个最大值，随便吃一个即可。在实现时如果有多个最大的，我们会把它们吃到价值减小相同的大小。在离散部分背包完后，从大到小枚举离散的质量即可。这部分的时间复杂度为 \(\mathcal{O}(wd)\)。

需要注意价值可能为负。

C. Crane Balancing

题目大意：给你一个位于 \(xOz\) 平面的，放置在 \(x\) 轴上的一个多边形，单位面积的质量为 \(1\)。在某一点上挂一个质量为 \(m\) 的质点，问 \(m\) 取值范围多少时该物体不会倾覆。

题解：不会倾覆的充要条件是该物体的重心在多边形与 \(x\) 轴接触的最左及最右两端之间。求多边形的重心可以三角剖分，加上质点后可以得到重心的位置是关于 \(m\) 的一个反比例函数，解不等式即可。

需要注意 case 分析。

E. Maze Reduction

题目大意：有一个迷宫中有\(n\le100\)个房间，第\(i\)间房间中有\(k_i\le100\)扇门，按逆时针顺序给出每扇门通往的房间。每间房间只能以门的数量来区分，同样个数的房间内部看起来没有区别，但是进入房间时的这一扇门是可以被记住的。在已知所有房间中门的信息的情况下，如果起点在房间\(A\)和起点在房间\(B\)两种情况在可以获得的信息中不可区分，就认为\(A\)和\(B\)是等价的。求所有等价类的集合。

题解：令\(f(i,u,v)\)为走了边\((u,v)\)后再走\(i\)步可以获得的信息的hash值，则\(f(0,u,v)=degree_v\)，\(f(i,u,v)=\sum f(i-1,u_i,v)\cdot base^i \pmod{mod}\)，其中\(i\)为以\(u\)结尾的逆时针顺序的房间\(v\)的出边。对于房间\(a\)和\(b\)，首先如果度数不同，一定是不等价的，否则枚举一个偏移量\(i\in[0,n)\)，如果\(degree_u = \sum [f(n,a,u_j)=f(v,b,v_{i+j})]\)，其中\(u_j\)和\(v_j\)分别是\(a\)和\(b\)按逆时针顺序给出的门通往的房间，则是等价的。可以选择两对\((mod,base)\)来减小出错的概率。时间复杂度\(O(n^4)\).

G. Metal Processing Plant

题目大意：给出\(n\le200\)个点的无向完全图，定义集合\(S\)的直径为集合中最大的两点间边权。将这\(n\)个点划分到两个集合\(A\)和\(B\)（可以为空），最小化这两个集合的直径之和。

题解：不妨设\(A\)的直径不大于\(s_1\)，\(B\)的直径不大于\(s_2\)，\(s_1\ge s_2\).

假如给定了\(s_1\)与\(s_2\)，则转化为一个2-sat判定问题：

• \(x_i\)为\(1\)表示\(i\)属于集合\(A\)，\(x_i\)为\(0\)表示\(i\)属于集合\(B\)；
• 若\(w(u,v)>s_1\)，则\(x_u\)和\(x_v\)不可以同时为\(1\)；
• 若\(w(u,v)>s_2\)，则\(x_u\)和\(x_v\)不可以同时为\(0​\)；

枚举\(s_1\)，然后二分最小的可行的\(s_2\)，每次check时做一遍tarjan求scc，用\(s_1+s_2\)更新答案。

这样的时间复杂度是\(O(n^4\log{n})​\)，会TLE，加上一些剪枝，虽然最坏情况复杂度不变，但是可以202ms通过全部数据.

H. Pachinko

题目大意：给你一个高 \(h\le10^{4}\)，宽 \(w\le20\) 的网格。每个格子可能是弹簧，障碍或者终点。球碰到弹簧时会随机往上下左右跳，每个方向的概率给定。但是如果随机到边界或者障碍，那么它不会跳动，会重新随机一次。现在把球等概率随机放在第一行的某个弹簧上（保证第一行没有终点，且至少有一个弹簧）。对每个终点问停在它上面的概率。

题解：和之前的某道题类似，我们用高消求每个点访问次数的期望，对于终点来说，这就是它们被访问的概率。

利用这种黑科技即可做到 \(\mathcal{O}(w^{3}h)\)。

K. Surveillance

题目大意：给出一个长度为\(n\le10^6\)的环和环上的\(k\le10^6\)个线段，求覆盖整个环的需要的最少线段数。

题解：先把环拉成\(2n\)，然后每个点的父亲为覆盖它的线段中最大的右端点加一，如果没有则作为根。枚举点\(i\)，倍增找到第一个小于等于\(i+n\)的祖先，用深度差更新答案即可。时间复杂度\(O(n\log{n})\).