Contest Info

date: 2019.03.29 14:33-19:33

practice link

Solutions

A. Takeover

题目大意：初始有一个点 \((0,0)\)，和一个包含他的矩形，矩形左下角 \((0,0)\)，右上角 \((1,1)\)。平面上还有 \(n\)（\(1\le n\le 3\cdot 10^5\)）个点 \((x_i,y_i)\)（\(1\le x_i,y_i\le 10^9\)）。让你定一个加点的顺序，使得相邻两次的矩形周长增量的最大值最小。

题解：设现在的矩形右上角为 \((a,b)\)，我们将第一象限由 \(x=a\) 和 \(y=b\) 分成三部分。每一部分对周长的增量是同一个式子，我们维护最小值。每次贪心的找到最小增量即可。正确性证明：加一个点之后，每个点对周长的增量只会减少，假设有一个最小的最大增量，那么如果一个点在这次修改之前是可取的，那么修改不会改变“可取”这个性质（显然二分答案是没必要的）。

B. Unfair Card Deck

题目大意：有 \(n\) 种牌，每种牌有 \(1\sim2\) 张，共 \(30\) 张。每种牌有一个给定的权值 \(X_{i}\)（不告诉你）。每局游戏按下面规则抽牌：设当前第 \(i\) 种牌还剩 \(c_{i}\) 张，那么选择这种牌的概率为 \(\displaystyle{\frac{c_{i}X_{i}}{\sum_{j=1}^{n}c_{j}X_{j}}}\)。选出牌之后把它从牌堆中移除。现在给了你 \(10^{5}\) 局游戏的局面，要求你“猜出”\(X_{i}\) 的值，精度要求不是很高。

题解：考虑一局游戏中第一个 \(i\) 在第一个 \(j\) 之前出现的概率，显然是 \(\displaystyle{\frac{c_{i}X_{i}}{c_{i}X_{i}+c_{j}X_{j}}}\)。但是用这种方法求出的 \(X_{i}\) 只有在 \(c_{i}X_{i}\) 较大的时候才比较准确。因此我们最好按照从大到小的概率求 \(c_{i}X_{i}\)。开始时，我们选取第一列中出现次数最多的牌做为 \(c_{i}X_{i}\) 最大的牌。然后我们计算剩下的牌中 \(c_{j}X_{j}\) 最大的那个，如果它相比 \(c_{i}X_{i}\) 没有小很多，那么我们就以它为次大的牌继续计算。否则，我们认为剩下的牌的 \(c_{j}X_{j}\) 都显著小于 \(c_{i}X_{i}\)，我实现的时候将它们相对于 \(c_{i}X_{i}\) 乘上了 \(10^{-7}\) 的常数。根据题面中的 check 方法，这个做法在题目要求的精度下不会有问题。然后我们先把计算过的牌都删去，再找第一列中出现次数最多的牌作为次大的牌，依次做下去。

C. Diverse Singing

题目大意：有 \(n\) 个歌手和 \(m\) 首歌，还有 \(k\) 个节目。每个节目是 \(p_i,s_i,l_i\) 表示歌手 \(p_i\)，歌曲 \(s_i\)，语言 \(l_i\)。让你从 \(k\) 个节目中找一些子集，每位歌手都出演，每首歌也被唱过。每种语言最多被每首歌唱一次，也最多被每位歌手唱一次。

题解：上下界网络流。第一层 \(n\) 位歌手，第二层 \((p_i,l_i)\) 的 pair，第三层 \((s_i,l_i)\) 的 pair，第四层 \(m\) 首歌。源向第一层连下界为 \(1\) 的边，第四层向汇连下界为 \(1\) 的边。第一层连第二层上界为 \(1\) 的边，第三层连第四层上界为 \(1\) 的边。第二层到第三层没限制。

D. Pick Your Own Nim

题目大意：有 \(n\) 个给定的数，以及另外 \(m\) 组数，要求你在每组中恰选一个数，使得这 \(n+m\) 个数线性无关，或者判断无解。

题解：拟阵交。这些数构成一组基是一个拟阵（当然删除掉给定的 \(n\) 个数，即收缩后仍然是一个拟阵），\(m\) 个数两两不在同一组中也是一个拟阵。证明略。

G. Battle Royale

题目大意：有一个区间 \([L,R]\)，开始时整个区间都是安全的。现在有 \(n\) 个人，每个人在 \(x_{i}\in(L,R)\) 的位置上（互不相同），离开安全区后能生存 \(a_{i}\) 秒。

安全区会不断收缩，具体规则是，有一个 \(M\sim U(L,R)\)，区间以 \(1s^{-1}\) 的速度收缩，且时刻保持 \(\frac{R'-M}{M-L'}=\frac{R-M}{M-L}\)。

对每个人问他生存最久的概率。

题解：首先为了方便计算，把区间平移到使 \(L=0\) 的位置。

在 \(M\) 左边的人，生存时间为 \(\frac{-a_{i}M+(R-x_{i}+a_{i})R}{R-M}\)；在 \(M\) 右边的人，生存时间为 \(\frac{a_{i}M+x_{i}R}{M}\)。由于分母对所有人都是相同的（指左右分开处理），比较时可以约去，因此生存时间对于左右分别都是线性的。所以我们可以对左右分别用平衡树维护下凸壳，左右的最大值相互比较时解一个二次不等式即可。

H. Jeopardy

题目大意：给出一个 \(n\times n\) 的方阵，先手每次删一行，后手每次删一列。先手希望剩下的一个元素最大，后手希望最小。问最后剩下什么。

题解：我们考虑这样一个问题：最后剩下的元素可以大于等于 \(x\) 吗？

这样我们可以把大于等于 \(x\) 的元素看做 \(1\)，小于 \(x\) 的元素看做 \(0\)，考虑最后剩下的是 \(1\) 还是 \(0\) 即可。如果有一行全是 \(1\)，显然最后剩下的会是 \(1\)，我们证明其余情况一定剩下 \(0\)。考虑先手删完后的 \(n-1\) 行每一行的第一个 \(0\)，由抽屉原理很容易知道，至少有一列不含有这 \(n-1\) 个 \(0\)，把这列删除后，剩下的每行仍然至少有一个 \(0\)。

最后找出最大的 \(x\) 即可。

I. Slippers

题目大意：在一个 \(n\times m\)（\(1\le n, m\le 100\)）的棋盘中，每个位置是一只拖鞋，拖鞋的第一个属性是 LR，第二个属性是 ^>v<。每次操作可以选择相邻的两只拖鞋，一只逆时针转 \(90^{\circ}\)，另一只顺时针转 \(90^{\circ}\)。让你做若干次操作，使得棋盘中成对的拖鞋（每只拖鞋只能用一次）总数最多。成对的拖鞋意味着，相邻的两个位置分别是 L 和 R，并且朝向均为左 L 右 R 时的前方。

题解：设 ^>v< 分别为 \(0,1,2,3\)，那么操作不改变棋盘和（\(\bmod 4\)）。我们对 L 和 R 求二分图匹配，如果没有匹配完所有的棋盘（有剩余的位置），那么我们一定能利用这个剩余的位置来对别的位置进行操作，使得匹配都能贡献答案。这个时候答案就是匹配数。

如果匹配完了所有的棋盘，我们猜想如果棋盘和（\(\bmod 4\)）满足条件，那么答案也是匹配数。否则我们一定要拆开一对拖鞋，答案是匹配数减去 \(1\)。

证明：（1）棋盘和（\(\bmod 4\)）相同的局面是可以互相到达的，我们考虑将棋盘的点按照到左上角的曼哈顿距离分组，那么就是若干条形如 / 的对角线，我们可以用上一层的点来任意改变下一层的点，最后只剩下左上角。（2）不同完备匹配的棋盘和（\(\bmod 4\)）是一样的。考虑一个完备匹配的交错路，它只能是一个环（否则就有未盖点，矛盾）。那么对应到棋盘中，也就是走 L 和 R 的交错环。考虑每一个 R，它每转 \(90^{\circ}\)，那么贡献加 \(1\)，对 L 同理，所以交错环上的匹配交换的时候，总的棋盘和不变。\(\Box\)

J. The Good, the Bad and the Ugly

题目大意：有一个人，初始在数轴上 \(x=p\) 的地方，每步操作你可以给他发 + 或 - 的两种命令。如果是 +，他的位置会加 \(d_{+}\)；如果是 -，他的位置会加 \(d_{-}\)。现在你不知道 \(p,d_{+},d_{-}\) 的值，但是它们都是常数，取决于这个人是一个什么样的人：

• 好人：\(p=m,d_{+}=2,d_{-}=-1\)
• 坏人：\(p=-m,d_{+}=1,d_{-}=-2\)
• 丑人：\(p=m\) 或 \(p=-m\)，\(d_{+}=1,d_{-}=-1\) 或 \(d_{+}=-1,d_{-}=1\)

其中 \(m\) 是一个正整数常数，但是也不会告诉你。现在要求你在不超过 \(30m\) 次询问内判断这个人是一个怎样的人，每次询问后，这个人会告诉你他是否在 \(x=0\) 这个点上。

题解：只要我们走到了 \(0\)，就能够排除好/坏中的一种情况，然后再走三步即可判断是不是丑的。所以关键在于在 \(30m\) 步内走到 \(x=0\)。

我们采取 - 若干次，+ 若干次，- 若干次 \(\cdots\) 的策略。设当前 + 用了 \(x\) 次，- 用了 \(y\) 次，如果是好人，\(m\) 至少为 \(g\)，如果是坏人，\(m\) 至少为 \(b\)。初始时 \(x=y=0,g=b=1\)。假设当前要 -，我们尽可能地多 -，只要让 \(m=b\) 时的坏人还能在 \(30b\) 步内 + 回来即可。设 \(u\) 为 - 的次数，那么我们有 \(-(-b+x-2y-2u)+x+y+u+3\le30b\)，即 \(u\le\lfloor\frac{29b-3-3y}{3}\rfloor\)，之后 \(g\) 更新为 \(y-2x+1\)。对于 + 类似处理即可。