THUSC 2018

时隔若干个星期后的再一次爆零记（这两天根本没有状态。。。）

June 1st (and before) - Day $-O(1)$

居然 THU 怎么快就把 Ubuntu 升级到了 18.04。。。

反观 NOI Linux 。。。

18.04 应该还稳定的吧。。。（flag）

June 2nd - Day 0

以从上次同样的方式来到 PEK。（只是坐的地铁不同）

宾馆好简陋呀。。。（不是西郊）听说以前来 PKU/THU 都住这，听说饭很好。

放完行李去试机。到那里的时候试机赛马上就要结束了。于是 T1 puts("0"), T2 无草稿纸手算（还少打了负号）+ 全部退化成点。。。 （手机上的 GeoGreba 真难用）

北京好热呀。。。

June 3rd - Day 1

先吐槽时间再次不统一（OJ 时间，本机时间，手表时间不一样。。。），在最后 20min 的时候甚至 OJ 上还显示 4h。。。

根据（一点都不靠谱的）经验，先做 T1。

结果 1h 没有思路。。。

感觉情况不妙，后面好像提答要来不及，赶紧把 T1,T2 的暴力写了（ T1 $O(n ^ 2 \log n)$ 预处理， T2 暴力枚举串）。

还有 3h，开始搞提答。

之前已经在看题的时候顺手 A 了 Subtask1（限制真多）。

一个个看下来：

Subtask2 什么东西，输入个函数，若干个二元组，输出实数。一直以为是点（实际是区间求定积分），凑出来 4 分。

Subtask3 就是根据与输入点的距离找点。本来想数学方法求，结果卡精度。。。先交了 1 分。

Subtask4 输入 01 矩阵，输出整数？（自动认为是 xor 矩阵），凑出 1 走人。（实际上是普通加意义的行列式）

Subtask5 开始是图论题。“The shortest paths from 1 to i is: x” 好迷惑人。。。实际是最短路数。手玩 4 分。

Subtask6 自动脑补成有向图。求无向图 1 号点出发长度为 $i$ 的路径数。手玩 1 分。

Subtask7 什么 “Pair …”，不知道，凑出 1 分。（实际上是每次加边新连通的点对数）

Subtask8 汇编语言，只有 A = B + C 和 if (A == B) goto x，构造 0 和 1 都花了好久。 写完第一部分 $a ^ b$ 告诉我第二部分爆 int 不得分？ 写了 4 行的 if (A > B) ...，每次加一行都要把下面的行号都改一遍。。。

Subtask9 什么东西？（galgame）终于走完一遍，得了 4 分，告诉我不把我的输入存下来？以为要记录所有的键盘操作，于是随机 rand 了个回答然后中间加了无数个回车（也是 4 分），然后得到了个 announcement：“各位选手注意，T3 第九个点不需要输出回车”

Subtask10 又是汇编，多了个 toss 函数，看不懂（好像跟概率有关）。1 分。

回头看 Subtask5，好像要分层连边。写了不知道多久后 A 了。

然后手动三分出 Subtask3 的第二个点，爆搜了 Subtask9 的答案，结果只有 7 分（听说需要在某个两个选项的题目中选 3 ？）。10 + 4 + 4 + 1 + 10 + 1 + 1 + 4 + 7 + 1 = 43。

还有 15 分钟。回去补打了 T1 $O(nq \log n)$ 的暴力，T 了，存了算过的答案（还发现少开 long long），居然过了 17 个点。。。

(30 + ?) + 6 (9 分已经 FST，因为没有考虑把串复制两次 ) + 43，看起来药丸。

好像 T1 又是换一种状态表示方式，然后在线段树上维护。 T2 $k = 0$ 在 AC 机上跑 DP，可以减少许多状态。

希望 T1 数据水一点，希望 Day2 翻盘。

下午开营仪式。居然有小学生来参赛（完了，要被小学生虐爆了。。。），wys 同学回顾了自己出毒瘤题的经历。。。（好像机房里确实有一本《编译原理》，但是现在不知道去哪里了。。。）

June 4th - Day 2

昨天晚上奶了一口 Day1 已经出过提答题了，Day2 应该不出了，可能他们把 Day1 Day2 swap 了一下。

今天早上考前又和隔壁选手说（中国的） OI 比赛好像没有一次连出两道提答的事情。

题面发下来之后， exm ？怎么又有一道提答题，感觉不对。（是不是破纪录了？）

然而 T1 看完题感觉好神奇，然后突然想到了今年 World Final 的那道题，但是发现这道题目并没有那么好的性质。

然后也想到了标算的边权化点权，但依然在考虑打差分标记的事情（没法打差分标记），也没有去想这样能否构造出正确解。

然后感觉 T2 可做就去看 T2。

第一眼以为猫锟题，能启发式合并，然而发现并不能。

然后想了想链的情况，先发现组合数，然后发现是个生成函数，于是愉快的写了个分治 FFT。

想想看能够推广到树上。试图树剖，把每个轻儿子的贡献合并后然后对整条重链做分治 FFT。感觉可行，没算清复杂度（感觉像是 2 个 $\log$ 的），写了一发，调了好久（因为狂用 new 导致各种 RE，到了最后才想起来能用 std::vector），然后 A 了。

T1 依然没有思路，看 T3。按照题目中的提示式子进行合并就是 Subtask1 的正解。

然后看到 Subtask3 好多 1。统计了一下，发现只有 4 种矩形，于是爆枚方案，结果没有，然后发现有个 $1 \times 2$ 的可以横放，然后就出解了。

Subtask4 矩形种类变多了，但是发现随便贪心一下就过了。

以为 Subtask5 也能贪过去，换了 $O(1)$ 种贪心策略都没用。

然后回去看 T1，结果毫无进展。于是干坐到比赛结束。0 + 100 + 30 = 130。

下午讲题。

D1T1 就是改变 DP 状态以便维护。

D1T2 猫锟题，是放在 AC 机上的 DP，将前后的串两个状态同时拿来跑（完了，最优划分永远想的都是 DP）。

D2T1 的构造是将每个点拆成点权为 1 的点，然后将对角的两个点相连，确定每个点的点权是差分约束（做完 出纳员的雇佣 后似乎一直没有做过差分约束了。。。）。得分情况感人：10 人

D2T2 重链剖分实际上是 $O(n \log ^ 3 n)$ 的 ( 每条链被合并 $O(\log n)$ 次， 合并时要做 $O(n \log ^ 2 n)$ 的分治 FFT)，而变成长链剖分（选最大延伸深度的儿子作为重儿子）是 $O(n \log ^ 2 n)$ 的（每条链被合并后，不长于主链，不影响后续合并复杂度，所以实际上相当于 1 次合并）。

两道提答也有些好玩的地方。

第一道类似以上做，（Subtask8-2 是 $a \text{ and } b$, Subtask10 是量子编程，其它的图论题也以搜为主）。

第二道是 3,4,5 特殊性质，其它只要用高明一点的随机，跑很久就能得高分。

面试名单 XJ 全部入围。希望明天面试时不要尴尬。

似乎题目不公开，那来补一下题面：

D1T1: 给出长度为 $n$ 的序列，$q$ 次询问区间 $[l, r]$ 的 LIS 长度，强制在线。$n \le 10 ^ 5, q \le 10 ^ 7, a_i \le 1000$，10s，询问给出随机函数，hash 输出。

D1T2：给出 $m$ 个模板串 $T$，求有多少个长度为 $n$ 的字符串 $S$，使得串 $SS$ 不存在划分方案，使得有多于 $k$ 个划分出的子串为模板串。$n \le 100, m \le 300, |T| \le 5, k \le 3$（实际 $k$ 的限制并不重要）

D1T3：提答，给出一个程序（有多种功能）和输出，要求构造输入数据。

D2T1：在圆环上有 $2 \times n$ 个点，其中在奇数点上有 $m$ 条带边权的连边，要求在偶数点上连边，使得每条奇数点上的边的与之相交的偶数边的边权和大于它自己的权值，最小化偶数边权值和，输出方案。$n \times m \le 5 \times 10 ^ 6$

D2T2：给出一个树，每个结点有两种物品若干（同种物品间两两互不相同），要求对于求出所有从 1 号点到叶子结点的路径上，每个结点取一个物品，取 $k$ 种 1 号物品的方案数，对 $k \in [0, n]$ 求出答案，模 $998244353$ 输出。$n \le 10 ^ 5$，5s

D2T3：提答，给出 $n$ 张纸片，要求找出一张矩形的纸以及裁剪方案，使得能够裁出这 $n$ 张纸片。最小化纸片面积的同时，使得一边的长度落在 $[L, R]$ 之间。

June 5th - Day 3

面试。

再次 1 分钟讲完自我介绍。。。

然后问一些个人相关。

然后问了：

“你认为计算机哪个领域有什么发展前景？”
“有 1000 瓶酒，1 瓶是有毒的，毒性要 1 周才能发作，你需要在 1 周时间内找出这瓶毒酒，至少需要几只小白鼠？”（只知道 999 这个思博上界，有更优解吗？）

英语还是老规矩，这次的文章是 Bellman-Ford。

感觉不行呀。。。

下午几位大佬轮番介绍计算机系的各种活动和机构。（弹幕被【清香鱼汉堡】刷屏了。。。求【双层吉士汉堡】的心里阴影面积）

然后就是发签。

按照（类型，字典序）排序，过了前 100 降 60 之后就感觉稳了，最后搞了一个一本。

最后讨论一下，关键（拉分）还是在 D1T1 的乱搞上。

Good Ending.

晚上似乎 xy 很高兴，请了各路 XJ 神仙（松松松，鏼爷，吉老师，自信，以及更早的周子凯学长）来吃饭。

松松松晚上上课要迟到了，我们：卡一卡常就不迟到了。

讲到省选，气氛突然尴尬了起来。。。

---- 一条手动分割线 ----

刚刚我说这是一个 Good Ending。

那么(supposed) True Ending 是什么呢？D1T1 用标算 A 掉。（这句话的意思是用正确算法得到 T1 的这么多的分，才能说明水平的进步）（但是感觉去写 T1 标算的话 T3 来不及搞，所以。。。考场上也不一定是个明智的选择）

个人感觉这一次的四道传统题都非常不错，虽然出现了两道提答题，但是第一道是弃疗后非常好的娱乐（+得分）手段，第二道也成为随机化算法大师的 gain 分题。

这一场比赛，以前被乱搞的出题人终于不再被乱搞了（倒换了个出题人被乱搞）。而且比赛也没有什么大锅。

最后来 summary 一下：

似乎自从 NOIP 之后，我的成绩（几乎）完全取决于乱搞水平：THUWC 不会乱搞，滚粗。ZJOI 没有乱搞，滚粗。CTSC 有乱搞，Au。（APIO 得感谢猫锟的圆方树。）THUSC 又乱搞，Win。

而且 APIO 和 THUSC 的数据结构都陷入有思路没解法的僵局。（同时也受到了另外题可做程度的影响）

D1T2 和 D2T1 是思维好题，当然，从大众的情况（THUSC 的受众应该是不包含第一梯队的，因为 dalao 冬令营都签了），也发现了整体（自然包括我）对观察性质能力，和基础算法（差分约束，AC 自动机等）的不重视。一方面，出题人出好题不如搬题/出套路题高效；另一方面，做题人接触多了套路和新科技（这两年多项式很火呀），自然就这样。当然，我是套路都没接触多少的人，还要多锻炼。

---- 又一条手动分割线 ----

被强行留在北京参加 NOI 训练，感觉学考凉凉。