2018 ACM-ICPC Shenyang Regional Onsite

Replay

ultmaster:

• 热身赛阻碍了个 kblack 的 AK 进程。暗示了正赛的剧情。
• 听说比多校还难。
• 强制穿衣服的操作有点傻逼。而且衣服还没有去年好看，甚至是中老年保暖衣。:(
• 比赛还没开始就发了题目和密码条。题目没有信封。计算机没有锁屏。有点牛逼。
• 好在也没什么题能做，并不影响结局。
• 按惯例从 A 开始，读一题不会做一题，剧情真的跟多校一模一样。
• kblack 签完到之后很快无题可上。同时 kblack 发现了第二个签到（事实上证明可能是个中期题），用花一样的手速 WA 了。
• 同时场上的气球还是多了起来，C 过的队伍越来越多。跟 zerol 推着推着发现事情并不简单，笑容渐渐消失。
• kblack 占机调试，C 通过的队伍越来越多。
• kblack 拿下了 L 的一血。C 慢慢逼真的，赶 zerol 上去写。写完 WA 了。
• 试图手工打表，发现好像没有任何问题。半个小时后终于重新阅读了数据范围，终于过了。（但是已经完全没有用了）
• kblack 觉得 E 能做，就去写 E。我觉得 G 可能还行，跃跃欲试。
• E 过了以后写了 G，很快 WA 回来了。发现了若干傻逼错误，修一下 WA 一下，不知不觉增加了大量的罚时。
• 然后比赛就结束啦。后面是一个我完全不会做的约瑟夫问题。I 想了个数位 DP，不过完全没有尝试的机会啊？
• 这么惨的罚时居然还是 5 题罚时第一。（？？？
• 前期崩得有点惨。感觉只有 kblack 在线，我和 zerol 都在吃大便啊？
• 总结一下：写了两个简单题，然后全程摸鱼。
• 第一块区域赛金啊，运气好一点的话可能还能更进一步。不过运气看起来早已经透支了呢？（笑）

zerol: 没来

kblack:

• 这机场离市区距离好评啊，来回打车一点也不心疼。
• 这酒店虽然便宜但是外观还算正常。。。
• 热身赛起手签了个到，读错了一个 C，写 **WRONGANSER** 演了自己，与队友一起奠定了互相演的比赛基调。
• 正赛起手签了个 J，因为怂缓了一下，重新确认了一遍数据范围，然后，然后一血就™没了。
• 想下来吃个饭什么的，然后发现 L 也能做，就开了，情况少考虑了一大堆，然后这次没怂，交上去喜提 WA 一枚。
• 修了个小 bug 还是 WA 了，被写 C 的 zerol 赶了下来，然后发现圆的情况少考虑了一大堆。
• C 也自闭了，终于又能上去修了，修得假了一发，终于获得 FB。
• 下来看看题，发现 E 挺套路的，C 过了没题了就上了，线段树写了大半天，总算是 1A 了。
• 之后就自闭 K 去了，会把 $m$ 缩小，归约成 $m$ 小的时候（然后甩锅给 zerol），但不知道 / 没推出递推式，$m$ 小的时候写的 $m\log{m}$ 的，T 得欲仙欲死。
• 出线是不可能出线的，这辈子不可能出线的。
• qls、tls、cls 辛苦了，心疼咖啡🏆。

Problem C

Solved by zerol & ultmaster. 02:09 (+1)

题意：求有多少 $1$ 到 $n$ 的排列满足：将前 $k$ 个的数排列以后，最长上升子序列长度为 $n-1$ 以上。

题解：分四种情况讨论：

1. 排序之后整个就有序了：$k!$

2. 排序之后前面是 $1$ 到 $k$，后面最长上升子序列的长度是 $n-k-1$：$(n-k-1)^2 k!$

3. 前 $k$ 个数里有一个被换成了 $k+1$，被换的那个数可以插到后面里面去：$k! \cdot k(n-k)$。

4. 前 $k$ 个数里有一个（只能是 $k$）被换成了 $k+2$ 以上的数，后面 $n-k$ 个数必须有序：$k! (n-k-1)$。

综上，答案就是 $k!(1+(n-k-1)^2+k(n-k)+(n-k-1))$。

另解：

$n$ 个数的排列上升子序列的长度恰好为 $n-1$ 的方案数是 $f(n)=(n-1)^2$。

讨论：

1. 整个有序 $k!$

2. $(f(n)-f(k))k!$，但是多算了一些，是后面插到前面的部分（应该只能算一次却算了 $k$ 次） $k!(n-k)(k-1)$

最后答案是 $k! (1 + (n - 1)^2 - (k - 1)^2 - (n - k) (k - 1))$

Problem E

Solved by kblack. 02:27 (+)

题意：平面上有 $N$ 个有颜色点，求第 $l$ 到 $r$ 的不同颜色点间的最远曼哈顿距离，修改位置和颜色。

题解：曼哈顿距离最远，肯定先转切比雪夫距离啦，然后用线段树维护区间内不同颜色的两个维度的最大次大就好了。

Problem G

Solved by ultmaster. 03:08 (+2)

题意：有四种操作：增加点、删除点、修改和一个点距离为 $\sqrt{k}$ 的所有点的点权，询问和一个点距离为 $\sqrt{k}$ 的所有点的点权。

题解：距离为 $\sqrt{k}$ 的所有点是不多的。直接暴力即可。注意判断差为正负或为 0 的情况。

Problem J

Solved by kblack. 00:16 (+)

温暖的签到题。

Problem K

Unsolved. (-4)

原本以为 $m$ 小的时候好做，结果发现始终带 log。自闭了。

Problem L

Solved by kblack. 01:29 (+3)

题意：一个大圆，被几个圆咬几口，问剩下的直径。

题解：大讨论，整个圆被吃掉的时候答案是 $0$，其他情况直径来自于两个地方：原本圆的直径和交点之间的距离，把角度扔一起，扫描线一下就好了。