Petrozavodsk Winter-2019. Yandex Cup-2019

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\) 分成三部分。每一部分对周长的增量是同一个式子,我们维护最小值。每次贪心的找到最小增量即可。正确性证明:加一个点之后,每个点对周长的增量只会减少,假设有一个最小的最大增量,那么如果一个点在这次修改之前是可取的,那么修改不会改变“可取”这个性质(显然二分答案是没必要的)。

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\) 的边。第二层到第三层没限制。

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}\)。让你做若干次操作,使得棋盘中成对的拖鞋(每只拖鞋只能用一次)总数最多。成对的拖鞋意味着,相邻的两个位置分别是 LR,并且朝向均为左 LR 时的前方。

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

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

证明:(1)棋盘和(\(\bmod 4\))相同的局面是可以互相到达的,我们考虑将棋盘的点按照到左上角的曼哈顿距离分组,那么就是若干条形如 / 的对角线,我们可以用上一层的点来任意改变下一层的点,最后只剩下左上角。(2)不同完备匹配的棋盘和(\(\bmod 4\))是一样的。考虑一个完备匹配的交错路,它只能是一个环(否则就有未盖点,矛盾)。那么对应到棋盘中,也就是走 LR 的交错环。考虑每一个 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\)。对于 + 类似处理即可。