有点线性代数的味道。

Problem

有一个 \(n \times n\) 的矩阵，每个格子内有一个数。你每次可以查询一个子矩阵的权值和，求找出主对角线上点的权值和的最少需要多少次查询。

一个经典的博弈论题。

Problem

有 \(n\) 个石子，A B 两人博弈，A 先手。A 首先取若干个石子（至少一个，不能取完），然后 B 和 A 再轮流取石子，每次取的石子不能超过上次取的石子数，且至少取一个，无法操作的人输。求 \(n\) 满足什么条件时先手必胜。

增强一下：如果不能超过上次取的石子数的两倍，求先手必胜的条件？如果不能超过 \(f(x)\) （\(x\) 表示上次取的石子数， \(f\) 是一个非降函数），求先手必胜的条件？

似乎比较简单 →_→

Problem

令 \(x_1, x_2, \dots, x_n\) 为 \(n\) 个随机变量，易知 \(x\) 的和 \(S\) 服从正态分布， \(x^2_i\) 服从 \(n\) 个自由变量的卡方分布。

如果给定 \(S\) ，求 \(x^2_i\) 满足什么分布？

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

Problem

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

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

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

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 差不多了。

这个坑有望被消掉。

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

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

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

原题链接如下