2017 ACM-ICPC World Finals

Contest Info

date: 2019.03.26 16:25-21:25

practice link

Solutions

A. Airport Construction

题目大意:给出一个 \(n\)\(3\le n\le 200\))个点的简单多边形,求出它内部最长的线段(可以与边界重合)。

题解:首先我们证明该线段必然经过两个顶点。对于任意一条线段,我们可以将它往长度增大的方向平移(这里显然线段的长度关于平移的距离是一个一次函数),直到它接触一个顶点。之后我们再以这个顶点为旋转中心旋转线段,可以证明线段的长度的导数关于旋转的角度是单调增的,从而线段的长度是下凸的,因此我们也可以找到一个单调增的旋转方向,直到它再次接触另一个顶点。

接下来,我们枚举两个顶点作为该线段所在的直线,把所有交点的进出情况求出,即可得到这条直线在多边形内部的每一段。下面分析不同的相交方式下的进出情况:

  • 若直线和边不平行

    • 若不相交于端点,则进/出

    • 若相交于端点,如果这个端点的两条边在直线同侧,那么不进不出;如果在直线异侧,那么进/出

  • 若直线和边重合(首先这种情况下,这条边本身一定在直线上)

    • 若该边的两条邻边在直线同侧,那么经过这条边后不进不出

    • 若该边的两条邻边在直线异侧,那么经过这条边后进/出

C. Mission Improbable

题目大意:给出一个俯视图为 \(r\times c\)\(1\le r, c\le 100\))矩形的仓库。每个位置有一个数字表示这个位置的箱子个数。你想偷走尽可能多的箱子,然后随意排列剩下的箱子,使得三视图不变。

题解:显然 \(0\) 还是 \(0\),非 \(0\) 还是非 \(0\),否则俯视图会发生改变。我们求出行的 max 数组 \(mr\),和列的 max 数组 \(mc\)。假设每个非 \(0\) 的位置有一个箱子(保证俯视图不变),然后每一个非 \(0\)\(i\) 加上 \(mr_i-1\) 的贡献,列同理。现在我们尽可能匹配 \(mr_i=mc_j\)\(i,j\),用最小费用可行流即可。

D. Money for Nothing

题目大意:有 \(m\) 个供应商和 \(n\) 个买家(\(1\le m,n \le 500000\))。第 \(j\) 个供应商从第 \(d_j\) 天开始供应货物单价为 \(p_j\);第 \(i\) 个买家一直到第 \(e_i\) 天都以 \(q_i\) 单价收购货物。选择一对供应商和买家,求出最大收益。

题解:答案为 \(\max\limits_{i\in[1,n]}(\max\limits_{d_j\le e_i} (q_i-p_j)\cdot(e_i-d_j))\)。对于两个卖家 \(i​\)\(j​\),如果 \(d_i\le d_j​\)\(p_i\le p_j​\),那么卖家 \(j​\) 一定没有卖家 \(i​\) 更优。对于两个买家 \(i​\)\(j​\),如果 \(e_i\le e_j​\)\(q_i\le q_j​\),那么买家 \(i​\) 一定没有买家 \(j​\) 更优。

只保留有用的买家和卖家,并分别按照 \(d,e\) 从大到小排序,令 \(u(i)\)\(\max\limits_{d_j\le e_i} (q_i-p_j)\cdot(e_i-d_j)\) 取到最值的最大的 \(j\),则 \(u(i)\) 单调不减,直接分治即可,时间复杂度 \(\mathcal{O}(n\log{n})\)

证明:

\(i<j\)\(u(j)<u(i)\),则有 \[ \tag{1} e_i-e_j<0,q_i-q_j>0 \]

\[ \tag{2} d_{u(i)}-d_{u(j)}>0,p_{u(i)}-p_{u(j)}<0 \]

\[ \tag{3}(q_j-p_{u(j)})\cdot(e_j-d_{u(j)})>(q_j-p_{u(i)})\cdot(e_j-d_{u(i)}) \]

\[ \tag{4}(q_i-p_{u(j)})\cdot(e_i-d_{u(j)})\le(q_i-p_{u(i)})\cdot(e_i-d_{u(i)}) \]

由 (3) 和 (4) 分别变形化简得到: \[ \tag{5}(p_{u(i)}-p_{u(j)})\cdot e_j+q_j\cdot(d_{u(i)}-d_{u(j)})-p_{u(i)}\cdot d_{u(i)}+p_{u(j)}\cdot d_{u(j)}>0 \]

\[ \tag{6}(p_{u(i)}-p_{u(j)})\cdot e_i+q_i\cdot(d_{u(i)}-d_{u(j)}) - p_{u(i)}\cdot d_{u(i)} + p_{u(j)}\cdot d_{u(j)}\le 0 \]

由 (5) 和 (6) 可以得到: \[ \tag{7} (p_{u(i)}-p_{u(j)})\cdot (e_i-e_j)+(q_i-q_j)\cdot(d_{u(i)}-d_{u(j)}) < 0 \] 而 (7) 与 (1) (2) 矛盾,因此不可能存在 \(i<j\)\(u(j)<u(i)\)

E. Need for Speed

签到题。

F. Posterize

简单 dp。

G. Replicate Replicate Rfplicbte

题目大意:有一个无限的黑白染色网格,定义一次操作为将所有黑色格子为中心的 \(3\times3\) 网格颜色取反(所有黑色格子同时进行),但是操作完后可能出现错误,有一个格子颜色翻转。现在给出一个若干次操作后的局面,要求你尽可能多地逆操作,直到不能还原。(其实是找到面积最小的初始局面,下面将证明一次操作一定使得面积变小,所以上述描述等价)。

题解:我们证明,每个局面如果能还原,要么只有一个错误且错误位置唯一确定,要么无错误。

考虑还原在进行什么样的操作:它等价于选取一些 \(3\times3\) 的网格,将它们颜色取反,每个 \(3\times3\) 网格中间的格子即组成了还原后的局面,而当前局面中剩余的黑色格子则是“错误”。注意到这个操作是可逆的,因此我们只要证明空白局面和只有一个黑色格子的局面互相不可达(要么错误,要么无错误),以及两个只有一个黑色格子的局面互相不可达(错误位置唯一确定)即可。

考虑对一个空白局面做操作,我们要证明他不能到达只有一个黑格子的局面。对于第 \(1\) 行来说,每次操作就是选取一个 \(1\times3\) 网格取反。可以发现,模 \(3\) 余数相同格子的异或和是相同的。于是第 \(1\) 行要么没有黑色格子,要么至少有两个。\(\Box\)

两个只有一个黑色格子的局面互相不可达,相当于空白局面和有两个黑色格子的局面互相不可达(把一个黑色格子异或即可)。刚才的结论对列也同样成立,所以在列上要么没有黑色格子,要么至少有两个。所以不可能只有两个黑格子,否则第一个黑格子所在的列就只有一个黑格子了。\(\Box\)

最后描述一下实现。与刚刚的证明类似,我们从上往下消,如果当前行模 \(3\) 余数相同格子的异或和不同,那么显然这行必须有一个错误,这种情况我们就从下往上再消一次,如果还有错误,则不能还原。具体消的时候,我们考虑最上(下)一行最左边的黑色格子,那么显然这个格子右下(上)方的格子一定是一个 \(3\times3\) 网格的中心,把它消去后递归地做即可。

I. Secret Chamber at Mount Rushmore

签到题。

L. Visual Python++

题目大意:棋盘中有许多矩形,它们的关系只有相离和内含。不同矩形不能共享边界。现在给出了 \(n\)\(1\le n\le 10^5\))个矩形的左上角和 \(n\) 个矩形的右下角,让你给出一种合法的对应关系。

题解:我们把所有的点按照从上往下,从左往右的顺序枚举,将左上角的 \(c\) 放入 set 中,然后右下角匹配一个左边离它最近的左上角。最后再扫描线 check 一下是否共享了边界,注意要 \(r,c\) 各扫一次。

coldwater’s comment:

比赛的时候判断了 set 不可重来判 \(c\) 上的共享边界,但是 wa 了。因为这样没判断两个矩形的右边界相交。