treap 果然是一条好汉。

普通平衡树？treap 基本功能。fanhq 式的写法超级漂亮，基本不会写错（注意大于小于号即可）。原论文中说了 treap 的插入期望旋转两次，也就是说 insert 的时调用的 split 常数会很小。

关于权值的问题，我习惯搞个大根堆，因为懒得给 null 赋初始权值了。

splay 的拿手好戏，序列操作？由于 treap 支持 split/merge ，所以毫无压力。而且由于普通的 insert/erase 都涉及 split/merge 了，所以这是必备的。换句话说，treap 支持序列操作和 splay 一样天然。

另外，treap 还可以原生支持持久化，只需每次修改一个点时新建一个点代替就好了。一个小改动就是动态 weight ，因为 weight 不能持久化。内存占用什么的都是浮云。splay 要想持久化的话感觉比较囧，老教授的方法是多次（ \(O(\log n)\) 次） deep-splay，即把最深的点旋上来。

根据 CLJ 的论文，我们可以知道 treap 还是重量平衡的。fanhq 的写法中 split/merge 需要完完整整重构树，但是复杂度分析类似。（代码量？都是浮云啦……）

目前就 finger search 不支持了？

代码量什么的，感觉和 splay 差不多了。

又是一个 Matrix67 大大翻译过的题。

Problem

\(n\) 个人围成一圈，第 \(i\) 个人手中有一个数 \(a_i\) 。现在重复执行以下两步：

1. 如果 \(a_i\) 是奇数，则把 \(a_i\) 加 1
2. \(a'_i \leftarrow \frac{1}{2}(a_i + a_{i+1})\)

证明：有限步后，所有的数一定相同。

这个坑有望被消掉。

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)\) 。

没看懂题。先坑着吧。

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

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

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

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

今天的题非常漂亮，但是证明实在是不忍直视。这题解写的是有多蛋疼啊 →_→

Problem

有一个 \(n\) 元函数 \(f(x_1, x_2, \dots, x_n)\) ，其中每个参数的定义域以及函数的值域均为 \(\{0, 1, 2\}\) 。且 \(f\) 满足，若 \(x_1 \neq y_1, x_2 \neq y_2, \dots, x_n \neq y_n\) ，则 \(f(x_1, x_2, \dots, x_n) \leq f(y_1, y_2, \dots, y_n)\) 。

是否对于每个满足条件的 \(f\) ，都存在一个 \(j\) ，使得 \(f\) 的函数值只与第 \(j\) 个参数相关？

似乎这个题仍然比较简单。（但我仍然不会 233）

Problem

有一个只包含正整数的多重集 \(S\) ，A 和 B 博弈。每次 A 把 \(S\) 分成两个多重集 \(C_1, C_2\) ，B 可以：

1. 令 \(S\) 为 \(C_1\) ，并把 \(S\) 里的所有元素减一
2. 令 \(S\) 为 \(C_2\) ，并把 \(S\) 里的所有元素减一

若某时刻 \(S\) 为空集，则 \(B\) 胜利，游戏结束。若某时刻 \(S\) 中存在一个 0 ，则 A 获胜。

求两人获胜的条件。

Problem

三只蜘蛛想要在一个立方体上抓住一只虫子。已知虫子的最大速度是蜘蛛的最大速度的三倍，且蜘蛛和虫子都只能在棱上活动。对于任意的初始局面，蜘蛛是否都能抓到虫子？

UyHiP 的题目感觉很杂，相对来说 TOAD 就好玩多了嘛。

Problem

给定一个无向图，点有黑白两种颜色。每次你可以选择一个点，并把这个点以及所有和它相邻的点的颜色取反。初始时所有点的颜色是白色。

是否能在有限步内把所有的点全部变成黑色？

原题链接如下

少了个特判被 cha 好桑心……

1k 原题什么情况！我勒个去。

Solution

250 pts

结论： \(n\) 为奇数是先手必败。若 \(n = 2^k\) 则 \(k\) 奇先手必败 \(k\) 偶先手必胜，否则先手必胜。

证明的话还是归纳吧。不打表我真就不会做。

果然我被坑能力拔群。轻轻松松被 7k+ 坑 →_→

我提问发自真心。

500 pts

显然，对于一个元素来说，如果它不在一开始的位置，则在其他任何位置的概率是相同的。

于是我们可以递推出 \(k\) 次操作后，每个元素在初始位置的概率。不妨设 \(f_i\) 表示 \(i\) 次操作后的概率，可以得到递推式：

\[f_{i+1} = \frac{n-2}{n} f_i + \frac{2}{n} \frac{1}{n-1} (1-f_i)\]

前一半表示一开始就在这个位置的概率，后一半表示交换回来的概率。

如何计算答案？我们计算每个元素对答案的贡献。枚举每个元素，再枚举最后的位置 \(x\) ，则对答案做出的贡献是在这个位置的概率乘上这个数的值再乘上这个位置被子序列包含的概率。

1000 pts

原题什么的，我就只能说自己做题太少了。没坑好神奇

以下是 xiaodao （蒯）的方法，我觉得非常漂亮。

大家见过的构图大部分是 S -> x -> y -> T 这种图吧。这次的构图是 S -> x -> y -> x -> T 好奇葩。

我们把白点按照列数的奇偶分成两种白点。则黑点每次在两种白点中要各取一个。于是前一个 x 表示的是第一种白点，后一个 x 表示的第二种白点，中间的 y 表示黑点。为了保证一个黑点只会被流一次，我们需要将 y 再拆点，流量上限 1 。

这种建图的关键是每一个 L 形被一条增广路所表示，利用白点列数的奇偶性非常巧妙。写起来非常好写～（有 SAP 模板就是爽）

situation

首先看完 250 ，发现不会做。以前见过一个除法的，特水，分解质因数即可。减法的还真就不知道怎么做。

看了一下样例，感觉没啥思路。而且 \(n\) 的范围是 \(10^{18}\) ，普通分解方式还应付不了，所以不会是质因数分解这方面。决定赶紧写程序打表。表倒是好打，发现奇偶性很有规律的样子，于是把必胜/必败与 \(n\) 的奇偶性无关的提出来，发现一定是 2 的幂。然后就好了。

怒开 500 。看完第一段感觉很开心的样子，想到了 CF 某题，那个题是动态维护每个点最后在某个位置的概率。继续看下去发现有个啥还有个期望子段和，感觉就是这样了。再一想发现没具体给定交换，那么动态维护的矩阵一堆相同的数，不同的数只有 2 个 →_→ ……稍微推了下发现是可行的。怒写代码，430+ 分好爽。

然后开了 1000 pts 的，想了一下觉得没啥好做的，于是就坑了 →_→

Challenge 的时候发现 250 pts 的被 Cha 了，原因是忘记判 1 这个特殊条件了 T_T

幸亏过了 500 pts 否则就爆零了。

最后 #136 ，由于是小号还是可以涨的。只涨了 52 。（下次可以涨红吧？） 不要立 flag ！

others

Petr #1 rejudge #2 meret #3

wuzhengkai #15 。250 居然 FST 真是无语。

ChnLich #18 和我一样第一题被 cha 。

xiaodao #20 rating 和我一样了。上次 Seter 给 xiaodao 跌了蛮多的。

tourist #21 因为 1000 pts FST 了。

7k+ 居然用大号！cha 人 cha 的丧心病狂。#23

scottai #71 过前俩题正常节奏。

liouzhou_101 的 500 pts 只有 200+ 分，所以他俩题加起来没我一题多…… #143

秋锅第一题看错题了光荣爆零。

耀爷一开始说他不想做了，于是硬把他拉过来做……不过考到一半没网了好惨 →_→

nonsense

祝大家 CTSC 好运。

不能太颓废了，得开学习模式了呢。

这个题目似乎比较简单。

Problem

某国有 2kw 选民，国王的支持者只占 1% 。现在有一种“民主”的选举方式：我们将全部的选民分为 \(n_1\) 组（每组选民数目相同），每组内的选民再分为 \(n_2\) 组（仍然要求选民数目相同），再这样分下去，直至只剩一个人。每一组的投票结果为这一组分成的若干个小组的投票结果中，出现次数最多的候选人。如果有多个相同的，我们假定国王会输。

是否存在一种分组方式，使得国王通过一定的分配方案使得他获得整个选举的胜利？

似乎 Matrix67 大大已经翻译过了。

Problem

一个长度为 \(n\) 的 0/1 串，A/B 俩人博弈。每次操作如下：

1. 如果当前串首是 1 ，则放一个 0/1 到串尾，由 A 决定
2. 如果当前串首是 0 ，则放一个 0/1 到串尾，由 B 决定
3. 删除串首，重复以上过程

如果有限步内这个串全是 0 ，则 A 获胜，否则 B 获胜。

问什么情况下 A 必胜。