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 I

Upsolved by ultmaster.

赛场上想了个数位 DP，结果发现可能完全不是这么回事。

题意：给 $A,B,C,D,E,F$ 六个数，求 $\displaystyle \sum_{a=0}^A \sum_{b=0}^B \sum_{c=0}^C \sum_{d=0}^D \sum_{e=0}^E \sum_{f=0}^F \max \{ |a-b|, |c-d|, |e-f| \} \oplus a \oplus b \oplus c \oplus d \oplus e \oplus f$。

题解：本题关键在于按位考虑对答案的贡献。如果我们能知道最大差为 $d$，$a \oplus b \oplus c \oplus d \oplus e \oplus f$ 的第 $j$ 位上是 1 或者 0 的 $a,b,c,d,e,f$ 有 $x$ 对，我们就可以给答案加上 $2^j \cdot x$ 了。

考虑如何用预处理的方法一次性算出我们需要的方案数。比如以 $a,b$ 为一组，就要考虑所有满足 $0 \le a \le A, 0 \le b \le B$ 的 $(a,b)$，将这些 $(a,b)$ 按照 $|b-a|$ 和 $a \oplus b$ 在第 $i$ 位上是 0 还是 1 分组，就可以得到三维状态 f(i,j,0/1) 表示差是 i，第 j 位上是 0 还是 1 有多少种方案。对这个状态求前缀和 s(i,j,0/1) 就可以得到差不超过 i，第 j 位上是 0 还是 1 有多少种方案。对三组分别进行预处理之后，所求的方案数就是三个 s 在 $d$ 上的乘积，减去三个 s 在 $d-1$ 上的乘积。

Problem J

Solved by kblack. 00:16 (+)

温暖的签到题。

Problem K

Unsolved. (-4)

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

Problem L

Solved by kblack. 01:29 (+3)

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

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

Problem M

Upsolved by kblack.

题意：一系列有若干物品的商店，求一段商店内买不超过 $c$ 的物品的方案数，强制在线。

题解：每个商店相当于 $\sum_{i=0}^{a_i}x^{b_i}$，这个东西有逆，我们求出前缀积和前缀逆积，对于每个询问两边跑一下就能求出求出目标生产函数的前若干项系数和了。

kblack: 明明挺简单的题，没人开，题面又臭又长，就鸽了。。。