Contest Info

date: 2019.03.26 16:25-21:25

practice link

Solutions

A. Airport Construction

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

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

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

• 若直线和边不平行

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

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

• 若直线和边重合（首先这种情况下，这条边本身一定在直线上）

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

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

B. Get a Clue!

题目大意：略。看题面吧，太长了。

题解：容易想到，枚举每张牌属于哪个人（或开始时被抽走），然后 check 是否不与给定局面矛盾。但是这样的复杂度稍高。

可以发现，每一局对不同人的牌的限制是相互独立的。因此我们可以将剩下 \(3\) 个人的牌分别处理，然后 merge 起来。状态最多为 \({16\choose5,4,4,3}\approx5\times10^{7}\) 种。虽然说合并的时候会有一些重复状态，复杂度会稍微高于这个值，但是每个局面又至少可以去掉一些状态（后面会看到），因此复杂度还是合理的。事实上跑得飞快。

非法状态的规则很简单。如果该人是 -，那么他必然没有初始的三张牌；如果该人是 *，那么他有初始的三张牌之一；如果该人是大写字母，那么他必然有这张牌。注意由于输入保证合法，对自己的操作不需要判断。

感觉其实是个简单题。哭了。

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

签到题。

K. Tarot Sham Boast

题目大意：给你 \(s\) 个长度相同的字符串，\(\Sigma=3\)。现在有一个长度为 \(n\) 的串，每个位置是 \(3\) 种字符中的一种，等概率随机，位置之间相互独立。要求你把给出的字符串按照在这个串中出现的概率排序。

题解：设串长为 \(l\)，字符集为 \(k\ge3\)。对于一个串 \(s\)，定义 \(S=\mathbb{Z}\cap[1,l-1]\cap\{i|s_{1..l-i}=s_{i+1..l}\}\)。定义 \(g_{S}(n)\) 为 \(S\) 下长度为 \(n+l-1\) 的串中，只有 \(1..l\) 为目标串的概率。这又可以理解成只有 \(n..n+l-1\) 为目标串的概率，即为目标串在 \(n\) 处首次出现的概率。因此 \(\sum_{i=1}^{n}g_{S}(i)\) 即为长度 \(n+l-1\) 的串中目标串出现的概率。记为 \(f_{S}(n)\)。

考虑用容斥计算 \(g_{S}(n)\)。枚举目标串第二次出现的位置，我们有 \[ g_{S}(n)=\frac{1}{k^{l}}-\sum_{i=1}^{n-l}\frac{g_{S}(i)}{k^{l}}-\sum_{i\in S}\frac{g_{S}(n-i)}{k^{i}} \] 那么有 \[ \begin{aligned} f_{S}(n)&=\sum_{j=1}^{n}\left(\frac{1}{k^{l}}-\sum_{i=1}^{j-l}\frac{g_{S}(i)}{k^{l}}-\sum_{i\in S}\frac{g_{S}(j-i)}{k^{i}}\right)\\ &=\frac{n}{k^{l}}-\sum_{j=1}^{n}\frac{f_{S}(j-l)}{k^{l}}-\sum_{i\in S}\frac{f_{S}(n-i)}{k^{i}}\\ &=\frac{n}{k^{l}}-\sum_{i=1}^{n-l}\frac{f_{S}(i)}{k^{l}}-\sum_{i\in S}\frac{f_{S}(n-i)}{k^{i}} \end{aligned} \] 这里需要证明一个引理：\(g_{S}(n)\ge\frac{k-1}{k}g_{S}(n-1)\)。因为新加入的字符至少有 \(\frac{k-1}{k}\) 的概率不是目标串的最后一个字符。

考虑两个集合 \(S\) 和 \(T\)，设 \(\min\{T-S\}=r,\min\{S-T\}>r\)。记 \(D(n)=f_{S}(n)-f_{T}(n)\)，则有 \[ \begin{aligned} D(n)&=-\sum_{i=1}^{n-l}\frac{D(i)}{k^{l}}-\sum_{i\in S\cap T}\frac{D(n-i)}{k^{i}}-\sum_{i\in S-T}\frac{f_{S}(n-i)}{k^{i}}+\sum_{i\in T-S}\frac{f_{T}(n-i)}{k^{i}}\\ &=-\sum_{i=1}^{n-l}\frac{D(i)}{k^{l}}-\sum_{i\in S}\frac{D(n-i)}{k^{i}}-\sum_{i\in S-T}\frac{f_{T}(n-i)}{k^{i}}+\sum_{i\in T-S}\frac{f_{T}(n-i)}{k^{i}} \end{aligned} \] 当 \(n\le r\) 时，显然右边各项均为 \(0\)，因此 \(D(n)=0\)，\(n=r+1\) 时，\(\displaystyle{D(n)=\frac{1}{k^{r+l}}}\)。下面我们归纳证明：\(D(n)\ge\frac{k-1}{k}D(n-1)\)，这样我们就有：\(n\le r\) 时，\(f_{S}(n)=f_{T}(n)\)；\(n>r\) 时，\(f_{S}(n)>f_{T}(n)\)。

\(n\le r+1\) 时显然成立。

\(n>r+1\) 时，考虑 \[ \begin{aligned} \Delta D(n)&=-\frac{D(n-l)}{k^{l}}-\sum_{i\in S}\frac{\Delta D(n-i)}{k^{i}}-\sum_{i\in S-T}\frac{g_{T}(n-i)}{k^{i}}+\sum_{i\in T-S}\frac{g_{T}(n-i)}{k^{i}}\\ &\ge-\frac{D(n-l)}{k^{l}}-\sum_{i\in S}\frac{\Delta D(n-i)}{k^{i}}-\sum_{i=r+1}^{+\infty}\frac{g_{T}(n-i)}{k^{i}}+\frac{g_{T}(n-r)}{k^{r}}\\ &\ge-\frac{D(n-l)}{k^{l}}-\sum_{i\in S}\frac{\Delta D(n-i)}{k^{i}}-\sum_{i=1}^{+\infty}\frac{g_{T}(n-r)}{k^{r}(k-1)^{i}}+\frac{g_{T}(n-r)}{k^{r}}\\ &\ge-\frac{D(n-l)}{k^{l}}-\sum_{i\in S}\frac{\Delta D(n-i)}{k^{i}} \end{aligned} \] 由于 \(D(n-i-1)\ge0\)，因此 \(\Delta D(n-i)\le D(n-i)\)，因此 \[ \begin{aligned} \Delta D(n)&\ge-\frac{D(n-l)}{k^{l}}-\sum_{i\in S}\frac{D(n-i)}{k^{i}}\\ &=-\sum_{i\in S\cup\{l\}}\frac{D(n-i)}{k^{i}}\\ &\ge-\sum_{i=\min\{S\}}^{+\infty}\frac{D(n-i)}{k^{i}}\\ \end{aligned} \] 容易发现，\(\forall x\in S,y\in\mathbb{N}^{+},xy\le l-1,xy\in S\)。因此显然 \(\min\{S\}\ge2\)。因此 \[ \begin{aligned} \Delta D(n)&\ge-\sum_{i=2}^{+\infty}\frac{D(n-i)}{k^{i}}\\ &\ge-\sum_{i=1}^{+\infty}\frac{D(n-1)}{k\cdot(k-1)^{i}}\\ &\ge-\frac{D(n-1)}{k} \end{aligned} \] 即 \(D(n)\ge\frac{1}{k}D(n-1)\)。\(\Box\)

\(k=2\) 时测了一些也没有反例，但是也没法用上面的办法证明（\(k=2\) 时上面的等比级数是发散的）。不会证。

L. Visual Python++

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

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

coldwater’s comment：

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