好久没更了。

Problem

给定一个 0/1 序列 \(S\) ，执行 \(S \leftarrow S + inv(S)\) 无数次后，证明小数 \(0.S\) 一定是无理数。 \(inv(S)\) 表示将 \(S\) 中的每个 0 变 1 1 变 0 ，例如 \(inv(0111) = 1000\) 。

呼啦啦啦终于回来了。这几天借着腾讯马拉松去深圳玩了一趟，马拉松后顺便在深圳玩了半天。

4-19

早上从长沙出发，大概在下午三点的时候到了深圳。腾讯有人在接送。由于长沙有高铁还是比较方便的，于是我就坐高铁了。CSU 还有几个人也是同一辆车，可是我不知道他们在哪个车厢囧。由于还有人没来，我们就在深圳北站等。等的时候无聊，于是工作人员就要我举着哪个啥腾讯马拉松的牌子摇啊摇，还录了像囧，居然还保留进了最后的视频里面大囧。

接下来就去酒店。我去的时候室友已经来了，中山一中 wzm。由于两人习惯的语言问题，导致语言交流有一定的困难……不过普通话说慢一点还是可以的。吐槽酒店有一个 wifi 叫做 MapleLeafHotel ，但是连不上……于是还要建立一个 wifi 热点。

晚上有个啥破冰活动。我居然看到了 cqx ……重点是他居然认识我，我和他基本上没有交集的……当时我就蹭在 cqx 旁边。我感觉我、wzm、cqx 三个人真就是当时的业界毒瘤，cqx 应该就是毒王了。一开始自我介绍的时候 cqx 基本上是主持人提个问题就回答一个，而且回答的都非常囧。我和 cqx 大概是“被”自我介绍地最多的两个人了。

想起一件事：主持人在上面讲，我和 cqx 在下面聊天，于是主持人对 cqx 吐槽：你怎么就只看着他不看我呢？你们两个是不是有什么秘密？cqx 回应：那是因为你魅力不够。

有个活动是把一首歌的各句歌词拆开，给每人一句，要求根据歌词把组分好，每组内的歌词是同一首歌的。于是看到这些歌我的眼睛彻底瞎了。有些啥啊，《春天在哪里》《卖报歌》《读书郎》《小燕子》。要不是我 xx 我还真就组不上来呢。拜托都是大学生了你还要别人唱这东西。求求你换首歌吧。

还记得 cqx 没有交某个表格，上面要填一个 idea 。于是我就随口说了句一键卸载 360 ，然后 cqx 还真就写上去了，我的三观……

cqx 说他没有带衣服过来换洗，于是向工作人员申请多拿了件衣服，于是我也跟着蹭了件衣服 2333 （其实是给某某带的一件）。话说最后 AC 说他那件衣服穿不下问我要不要，于是我又获得衣服一件真是开心。本来就是去蹭衣服的嘛……

晚上有场 CF#180 。看了前两题后没啥好的想法，于是就没交了。后来看到成绩真是惨不忍睹。完全是靠 AB 两题的手速来混的，CDE 基本上没人出啊。

4-20

于是昨天晚上莫名其妙和别人聊天聊到凌晨两点。然后又喜闻乐见失眠了，然后 6 点就醒了，好囧 →_→

一开始由于 wzm 看错时间以为餐馆在 7 点钟以前开，所以我们 6 点多就起来了……

早上还有些精力。到了腾讯公司后每个人要将自己的创意是吧，于是我随手又 YY 了个创意，希望不要坑队友呢。前面是一堆 ACMer，后面是一堆设计师。ACMer 各种没创意，设计师各种 TLE →_→ 然后每个人要投票，选出几个最喜欢的项目以及自己最想要的人。我只能期望不坑队友了。

吃完中饭后就开始干活了。不得不说这里的便当还真不错，起码比学校食堂的好 →_→ 由于腾讯精心选择时间导致这天下午是 MS 的复赛，于是我就蛋疼了。看了题目后本来想做一做的，但是无奈开始犯困毫无状态做不下去，于是在两点半的时候把账号给了 XLk ，请他帮我做做，XLk 令人感动地帮我进了 onsite （XLk 你真是太好了）……我一直在看看题目没啥好想法，我们组内有人到外面去逛了一圈，发现旁边一个房间的两个组全体做 MS 真是让人感动。

一开始我负责的是 Gale-Shapley Algorithm 的实现，这个很快就搞好了，但是我们队没前端很不给力。每个队有 3 * ACMer + 1 * 设计师，我们队有两个坑爹的家伙（我和 wzm ），还剩一个人根本就没写过网页 →_→ 于是一开始还准备用 WordPress 。前一段时间在写 OJ 的时候接触过 Bootstrap ，感觉一个简单的 HTML 够了，于是写完 Gale-Shapley Algorithm 后转型前端开始鼓捣 HTML 。然后原来的前端师变后台了……

cqx 和我吐槽 MS 。他一开始想写 20 + 20 的，结果 B 的 20 没写出来，怎么交怎么 WA ，于是就……爆零了……事实证明只要 20 + 8 就可以了……

晚上还有场 TCO 的。我这个渣状态居然也想去参加 TCO ？怒爆一零人民群众喜闻乐见，刚刚红起来的小号又黄了。XLk 也混了件 T-shirt 吧。然后莫名奇妙又聊天聊到两点，设计师无奈表示果然我是天坑。

4-21

果然封闭开发不是好受的，简直是在用生命在码代码啊……TCO 后聊了下天然后又开始码 HTML 。其实我很大一部分是在等设计师的图。我们在讨论的时候各种囧，都是尽量简单地想，啥东西不好实现了，就放一张图片算了，反正是 demo 嘛……于是我就只好慢慢等设计师的图片了。

设计师要各种效果，没办法啥都不会只好问问腾讯的 NPC 。CSS 不会啊！！HTML 不会啊！！Bootstrap 不会啊！！由于笔记本上没有 IDE 只好用 Emacs 充上去了。于是怒学 CSS →_→ 由于设计师给我的全是图片，我完全不会定位，于是 HTML 里满天的绝对定位真心丑爆了。

看到设计师还要一段时间才能给出图片，于是我就小憩了一会……小朋友在 HN 省选呢。PYX 打电话过来时真心困死了，随口应了几句他发现了就没说啥了。

下午是产品演示，我就不好吐槽啥了。首先我们的服务器是架构在台式机上的，要演示的话得接到大屏幕上去，于是很囧的那个显示器很久没用了导致我们鼓捣了半天还是没结果，收获了评委的一致吐槽：你们就不能准备充分点吗？然后我在演示的时候，一不小心按过头了把浏览器关了于是搞到一半又要重新来过。接着是 wzm 的繁体中文导致我不得不用 gbk 编码然后在 Chrome 里面还得手动设置编码，屏幕上显示的是一堆乱码囧爆了。还有在提交前的一个小时后台决定改改一个网页结果发现更丑了……于是要产品没产品要创意没创意得到了评委的一致吐槽：其实收养制度和中国的社会体制相关 balabala 于是被轰下台了囧。

晚上有个晚宴，在某个湘菜馆吃的，我表示毫无压力，旁边 wzm 和 AC 表示亚历山大，不得不说这辣味还是够可以的，只可惜饭量太小吃不了多少囧。想起了一件搞笑的事：我们坐车的时候 AC 坐在前面，我和 cqx 坐在后面，cqx 喊 AC 但是 AC 似乎听见了以为是错觉继续听歌。于是 cqx 很蛋疼的打开手机给 AC 打电话：喂是 AC 大神吗？我是 cqx ，你可不可以坐到后面来啊……

晚上就是各自搞各自的事了，不过不得不说腾讯的服务还是挺周到的。

4-22

其实早上就可以走了，但是好不容易来次深圳当然不能啥都没干就走是不，于是托老爸找熟人，找了个地方去玩玩。我去的地方是锦绣中华，等我在一边逛了几个小时后发现还有一半没逛，真是太大了……相机电源表示亚历山大。于是我就只好很囧的半路掏出笔记本给相机充电。抱着个笔记本走路真是奇葩 →_→

晚上有场 CROC R2 。我就不说 onsite 要求 #50 我就是 #51 23333 不过不得不说状态还是回来了，起码还睡了个懒觉的呢，调一个题还半路下了个几何画板一个一个数格子呢。GuyUpLion 都可以涨我就不说啥了。主要是外接键盘手感好吧。

4-23

我勒个去回来的时候被人称作“叔叔”，老了啊 →_→

居然自己做出来了所以说还是很简单的 23333

Problem

定义布尔的乘运算为 AND ，加运算为 OR 。定义一个 DNF （析取范式）为一个布尔函数，返回值为若干个若干个变量的积的和，例如 \(f(x_1, x_2, x_3) = x_1 x_2 + x_2 x_3\) 即为一 DNF 。注意这里定义的 DNF 没有 NOT 。

定义一个对称函数为：接受若干个布尔量，返回一个布尔量，且参数的顺序与返回值是无关的。例如 \(f(x_1, x_2) = x_1 x_2\) 即为一对称函数。

我们说一个函数 A 能用另一个函数 B 表达，当且仅当存在一组参数列表之间的对应关系 \(y_1 = x_{a_1}, y_2 = x_{a_2}, \dots, y_m = x_{a_m}\) ，使得 \(A(x_1, x_2, \dots, x_n) = B(y_1, y_2, \dots, y_m)\) 。例如函数 \(A(x_1, x_2, x_3)\) 表示求 \(x_1, x_2, x_3\) 的众数，可以得到 \(A(x_1, x_2, x_3) = x_1 x_2 + x_2 x_3 + x_3 x_1\) ，令 \(B(x_1, x_2, x_3, x_4, x_5, x_6) = x_1 x_2 + x_3 x_4 + x_5 x_6\) ，可以知道 A 能被 B 表达。

现在有两个问题：

1. 对于所有的 DNF ，都可以找到一个对称函数使得其能表达这个 DNF ？
2. 对于所有的对称函数，都可以找到一个 DNF 使得其能表达这个对称函数？

题目似乎很绕……→_→

有点线性代数的味道。

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\) 个参数相关？