The 2017 ACM-ICPC Latin America Regional Contest
Contest Info
date: 2018.08.30 12:00-17:00
Solutions
A. Arranging tiles
题目大意：给你 \(n\le14\) 个凸包，每个凸包的高度都是 \(h\)。要求你将它们从左到右排成一排，两两之间不能相交，求该图形左侧到右侧的最短长度。
题解：状压 \(dp\)。设 \(dp[S][i]\) 表示当前已经使用了 \(S\) 代表的凸包，且最右边的凸包是 \(i\)。转移时我们只需要知道将凸包 \(j\) 放在凸包 \(i\) 右边至少要增加多少长度即可。容易发现，两个凸包相交当且仅当存在某个凸包的一个点在另一个凸包中。因此我们可以枚举 \(i\) 右凸壳的每一个点恰好在 \(j\) 上，以及 \(j\) 左凸壳的每一个点恰好在 \(i\) 上，这些所有情况下的长度增量取 \(\max\) 就是答案。具体求交点时，可以二分找出凸包的哪条线段与枚举的点所在的与 \(x\) 轴平行的直线相交，然后 \(\mathcal{O}(1)\) 计算即可。
C. Complete Naebbirac’s sequence
签到题。计算出每个数应该有多少个即可。
D. Daunting device
题目大意：
有一个长度为\(n\le10^5\)的数列，一开始所有位置都是\(1\).
\(m\le10^5\)次操作，每次询问数列中等于\(x\)的数字有多少个，并把一个区间内的数字都改成\(y\).
最后输出出现次数最多的数字的出现次数。
题解：
分块之后暴力，\(O(n\sqrt{n})\).
E. Enigma
签到题。数位 \(dp\)。
F. Fundraising
题目大意：
合并相同点之后，求最大权值和的二维严格偏序上升子序列。
题解：
排序一维树状数组一维\(O(n\log{n})\).
G. Gates of uncertainty
签到题。树 \(dp\)。
I. Imperial roads
题目大意：
给出一个\(n\)个点\(m\)条边的无向连通图，\(q\)次询问必须包含某条边的最小生成树权值和。
题解：
建出最小生成树，树边答案就是它，非树边就询问一条链上的最大边，把它换下来，点分治一下，\(O(n\log{n})\).
J. Jumping Frog
签到题。暴力枚举循环节。
L. Linearville
题目大意：有一个网格状的城市，每条边的距离是 \(1\) 或 \(5\)，现在要从 \((x_{1},y_{1})\) 走到 \((x_{2},y_{2})\)，且每走一步一定要向左或向右转 \(90^{\circ}\)，求最短距离。
题解：设在 \(x\) 轴方向走了 \(x\) 步，在 \(y\) 轴方向走了 \(y\) 步。观察这一行走的形式，它等价于 \(|x-y|=1\)。不妨设 \(x_{1}\le x_{2},y_{1}\le y_{2},x_{2}-x_{1}\le y_{2}-y_{1}\)。容易证明，最优情况下必须满足 \(y=y_{2}-y_{1},x=y-[2\nmid x_{1}+x_{2}+y_{1}+y_{2}]\)。这样一来，\(y\) 轴的代价就已经确定了。而对 \(x\) 轴来说，\(x_{1}\to x_{2}\) 的这些步是一定要走的，因此问题就变成了，额外的 \(x-(x_{2}-x_{1})\) 步应当怎么走才能使代价最小。这里就非常简单了，我们要尽可能多走距离为 \(1\) 的边。如果 \([x_{1},x_{2}]\) 中有这样的边，反复走它就可以了。如果没有，我们就先走到离 \(x_{1}\) 最近或离 \(x_{2}\) 最近的距离为 \(1\) 的边，然后反复走它。当然这里需要注意所有 \(1\) 都很远，会使得总步数超过 \(x\) 的情况。
M. Marblecoin
题目大意：
有\(k\)个栈，栈里的数字在\([1,300]\)中，每次可以从某一个栈取出栈顶，第\(i\)次取出的数字代价为它的数值乘上\(365^{T-i+1}\)，\(T\)为栈里数字的总个数。
最小化代价和。
题解：
后缀排序之后通过比较后缀大小来贪心取最小的栈顶，需要在栈之间插入\(301\)来后缀排序。
\(O(n\log{n})\).
