Codeforces-179

这个坑有望被消掉。

XLk 出现了！沉寂多年的 XLk 终于出现了！XLk 你要重出江湖了吗……

状态终于有回来的迹象了。

Solution

A

两次点事件。第一次点事件把每次操作最后会被执行多少次搞出来，第二次就直接求答案了。

B

离线变成每次加点维护最短路。

首先我们求出新加的点 x 到其余点的最短路，这部分可以通过 2 个 for 来解决：假设我们要求 x 到 z 的最短路，先 for x 首先通过一条边到 y ，然后 y 到 z 的最短路已知，更新答案即可。

接着用 x 到其余点的最短路更新其余点对之间的最短路。

复杂度 \(O(n^3)\) 。

C

dp 。令 \(f_{i, a, b}\) 表示我们划了 \(i\) 次船，现在我们这一边还有 \(a\) 个 50kg 的， \(b\) 个 100kg 的。然后枚举有多少个 50kg 的过去以及有多少个 100kg 的过去。当 \(i\) 是偶数并且能够全部过去的时候就找到答案了。预处理一下组合数就好。

注意答案的上界是 \(4n\) 而不是 \(3n\) 。

复杂度 \(O(n^5)\) 。

## D

没看懂题。先坑着吧。

## E

裸数据结构题。没啥好讲的。

注意到那个啥代价的，显然满足区间可加性，于是平衡树/动态线段树/离线离散化线段树都可以。

situatation

无意中看了一下 Registered participants ，大吃一惊居然有 xlk ……

先写 A 。想着为了避免溢出所有数组全部定为 int64 吧，于是手残 typedef int arr64 挂了一次。交了之后马上就反应过来了囧。于是挂的很惨 T_T

接着看 B 。由于以前做过这个题，所以写起来还是很顺手的。但是数组套数组写的我很不爽，后面突然想到 range-based for 完破啊。只可惜写完了 →_→

看完 C 稍微一想想到一个 dp ，以为只要把左边有多少个 50kg 多少个 100kg 的记下来就好，但是总觉得没拓扑序，于是决定加一维步数。我一开始以为回程至多只有 1 个，于是 WA 了 pretest 。后来想到，回程也要枚举，于是似乎又要枚举去程的两个量又要枚举归程的两个量复杂度会不会太高了。一想觉得自己脑残了，直接最暴力的一次一次的 dp 不就好了吗，一次只考虑一程。然后就过了。

然后看 D 没仔细看题。但觉得 E 是可做的，因为有若干人过了。看了题目后觉得是大水，决定写 treap 。写完 treap 后过不了样例，以为是我想错了这个题不能用 treap 做。于是扔掉重新写动态线段树写完就过了好爽。

只剩一点点时间了，等着慢慢度过，结果发现我的 C 被 hack 了……大囧。还是在离比赛还剩 90s 的时候被 hack 的。我想着应该是上界不够吧，但是觉得不能给他再送一个 hack 了……

于是考后把上界从 * 3 改成 * 4 就过了 →_→

最后是 #55 ，被 xlk 怒踩一名。

others

我在想有谁能把说了 AFK 的 xlk 拉回来。于是果然是 XLkAcp 。

CLJ #8 ，重回 IGM

liouzhou_101 #24 ，成为中国区里除 CLJ rating 最高的。

wjmsbmr #48 C 没过。

xlk 和我一样 C 上限没开够。#54

lydrainbowcat 只出了 ABC ，#114 怒跌。rating 2204 好悬。

cp12321 的 D FST 了。于是 #128 回黄。

有人用小朋友的 ID 打比赛……什么心态 →_→

kAc 的 CD 都 FST 了，E 没能交上去，momo。

nonsense

不知道要到啥时候，我才会重新开启沉寂已久的大号呢…… 及尔偕老，老使我怨。淇则有岸，隰则有泮。总角之宴，言笑晏晏。反是不思，亦已焉哉。——不知道我想说啥的就忽略这句话吧。——我没有语文没学好