ICPC 深圳旅游记？

· · 生活·游记

前言

这个 ICPC 全国邀请赛（深圳）是啥，怎么我们学校还有邀请函的？怎么没人要，那我要了。

凑到两个校队高一，我把队长让给了我们队中无疑最强的。

队名就叫嘻嘻佛嗯哦哎了。英文名叫啥？CCF NOI？Smile Monk？（最终决定取了一个比较冗长 Maitreya Buddha en oh alas）

听说我们队不用缴费，那不得不去了。

Day 0

下午三点不到到了萧山机场，四点左右开始登机，晚上七点不到到了深圳。

深圳地方好大，坐了一个半小时地铁总共 55km 才到酒店附近。不管了先睡觉。

Day 1

早上八点多到了港中深，领到了一些小礼品但懒得换衣服，我声称校服是对的。虽然女装更对但没带上。

热身赛，磨洋工磨了大半个小时才 AK，我写了个最水的 D 还吃一发罚时，我是区。小手机真好玩。五子棋真好玩。打块真好玩。

在港中深随机游走了一段时间。队友怎么没把小手机带出来？

正式赛怎么就隔了一个小时，吓哭了。

A 怎么是签到？严肃写掉。

队友写掉了 I，但有解没输出 Yes 吃了一发罚时。

L 怎么也是签到？严肃写掉。

午饭还是经典麦当劳神秘小套餐，不急慢慢吃。

看了一下 G、H、J、K，感觉 H 比较可做，先看 H。

接下来三个小时内队友过掉了 D、F、G，这几个小时我一点贡献也没有。

E 怎么是分讨，交给队友写去。

H 好难，但是好像会了。

注意到，当 n 是奇数，且 k=\frac{n-1}2，此时必须将大小为 k 的集合和大小为 k+1 的集合一一对应，因为显然一样多。分讨是否选了 1，要么本来就选了，要么新选了，要么始终没选。注意到大小为 k 包含 1 的集合有 \binom{2k}{k-1} 个，大小为 k+1 包含 1 的集合有 \binom{2k}k 个，其中 n=2k+1。做差得 \frac1{k+1}\binom{2k}k，这不是 Catalan 数列通项公式吗？虽然仍然没有直接得到什么很肯定是确定的头猪，但和 Catalan 数列的常见应用比对了几下，得到了以下奇异搞笑的做法：

设 a_i=[i\in S]，其中 S 表示给定的集合。从第一位开始往后做，若做到第 x 位：

  1. 若 a_x=1，继续看下一位。
  2. 若存在一段 x 开始的前缀满足 cnt_0\le cnt_1，继续看下一位。
  3. 否则，将该位改为 1，结束该过程。

后来发现前两种情况本质相同，唐完了。

考场上没证出来这是对的，但感觉好像是对的。手玩发现逆操作即位找到第一处 cnt_1-cnt_0 最大的位置。

然后就过了？

队友继续调 E，吃了四发罚时之后过了。Corner case 好多。

午饭吃完了。

队友写 M，但半个小时写不完一点。

估计能混个 Au，下播。

港中深怎么把 ZJ、FJ 的中学生单独拉去进行招生宣传了？

听完回来看滚榜，怎么 28 个正式队的 Au 线排到 rk68 去了，中学生太可怕，但不包括我。

怎么 rk19 了？爽。

后记

本来想 Day 2 结束再继续写，然后赶时间忘了，算了不想写了，反正也没啥好写的。为什么积了足足两个月灰？