Difference between revisions of "2018 ACM-ICPC Shenyang Regional Onsite"

From EOJ Wiki
Jump to navigation Jump to search
(No difference)

Revision as of 10:40, 24 October 2018

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$,其他情况直径来自于两个地方:原本圆的直径和交点之间的距离,把角度扔一起,扫描线一下就好了。