2024-01-25
和 wcx、xy 和 lzq 坐火车去重庆。在火车上非常无聊，我们先一起玩了（复古的）水果忍者，然后又玩了会儿 Hypixel 和 Reaching Darkness，但网络实在难受，便放弃了。最后只好玩些单机的，玩了 pvz 和 Getaway Shootout。惊喜地发现 Getaway Shootout 出了新的速通模式。
来到重庆，确实地感受到重庆地形崎岖，坐出租车去酒店，一会儿上一会儿下，到处都是天桥、地下信道，非常混乱，跟着导航也不容易找到路。可能是天气原因，看起来灰蒙蒙的。
中午去吃了羊肉。
发现忘带机械键盘要用的 type-c to usb 接口，也没带耳机，愤怒。
晚上去 Library Checker 上打了打板子，虽然明知道大概率没用（
2024-01-26 (Day 1)
地点是在重庆市育才中学。重庆育才中学环境非常好，风景很美观，教学楼甚至有电梯。
上午先放了进一个小时育才的宣传片（征得我好像会去这个中学一样），然后又有北大的陆院长讲话，不过陆院长讲话脱稿好评。介绍北大的时候，陆院长放了一张 CSRankings 的图片，是北大 rank 1，结果我们下头自己查发现是清华第一（
然后就是合影和试机。试机的时候试机题是 PKUSC2021 的 Day1 T1 Sum Transformation，结果做了一个小时没做出来。还发现装得那个 vim 没有 +clipboard，不能粘到系统剪贴板，交代码又不能提交文档，很难受。而且试机早知道应该打一个 static_modint 之类实用一点的东西，经验太缺乏了。
午餐非常丰盛！有八个菜随便选，还有草莓、橘子和饮料。
然后就是正赛了。
题目：
- 给定一个长度为 n 的 LR 串行 S，Alice 和 Bob 轮流在这个串行上操作，每次选择一个下标 i，如果 Si=L，则保留 i 左侧的，否则保留 i 右侧的。当 S 为空的时候失败，问 Alice 和 Bob 谁必胜。
- 有一个长度为 n-1 的数组 f，令 f’i 表示所有左/右端点是 i 的区间的最小值之和，给定 f’，构造一个对应的 f（不保证有解）。
- 给定一个大根二叉堆，每次操作选定一个位置变成 0，然后将这个位置向下交换使得堆的性质仍然满足。令 f(S) 表示将这个二叉堆进行若干次上面操作后，S 内的所有位置不为 0，且二叉堆和最小的堆（是唯一的）。多次询问，有两个集合 S1,S2，问有多少 S1 ⊆ S ⊆ S1 ∪ S2，满足 f(S) 的 x 位置的值是 z。
第一个问题比较简单，我 20 多分钟就过了，感觉非常自信。然后想 T2，一开始往高斯消元那边想，但是冲了好久也没啥进展。于是去看 T3，发现完全不可做，猜了一个结论然后试着去写了一下，结果是对的，于是拿到了 40 暴力，果断放弃 T3。继续冲 T2，先做了一个 11 的最低档暴力，然后尝试 15 分的 n <= 8，在最后半个多小时的时候发现了一个非常有用的性质，结果写完没调出来。最后 100+11+40，大众分。
ssz 考了 100+26+40，把 T2 的那个 n <= 8 做出来了，orz。但是 hfy 只考了 111。
晚餐去吃烤鸭和火锅。
晚上和 lzq 一起玩去南京集训时玩的 Random Royale，可惜 xy 没下好 Minecraft，要不然还能多一个人。
2024-01-27 (Day 2)
早上看到了 cyb 发来的鼓励视频，陈老居然还记得我们，感动。
上午听了北大王迪教授的讲座，讲编程语言，感觉很牛的样子。
附上 Day 2 午餐的图片，Day 1 忘记拍照了：
下午比赛，题目：
- 给定一个包含若干实数的可重集 S，每次操作可以让一个元素四舍五入，或将两个元素相加，问最后集合的和最大是多少。
- 问有多少个排列，进行 shell sort，可以让交换次数最大。求出最大交换次数和排列数量。
- 有 n 个栈，需要支持一下三个操作：(1) 区间 [l, r] 的所有栈压入 x 个 y；(2) 区间 [l, r] 的所有栈弹出 x 个元素；(3) 查找第 k 个栈 [p, q] 的元素和。
感觉 T1 就相当困难啊，首先想到小数部分 ≥ .5 的可以直接四舍五入，为 0 的可以直接忽略，只剩下小数部分为 .1, .2, .3 和 .4 的。然后就想了半个多小时，没有什么进展，于是准备先打点部分分。先写了 T1 O(n^4) 暴力，结果 TLE 了两个很小的 subtask，然后又卡了卡常数过了。接下来先看 T2 T3，感觉都巨大困难，于是打个暴力就跑路了。
继续来看 T1，有看到有个都是 .2 倍数的部分分，感觉没什么头绪，直到我尝试写了一个这样的东西：
def calc24(i, j):
return [k + (i - k) // 3 + (j - k) // 2 for i in range(min(i, j) + 1)]即枚举 .2+.4 一组的数量，然后剩下的单独组。这个东西不是单调的，但是好像最后最后一个元素是最大值？然后就写了一个进程就过了那个部分分？！
继续冲 T1，想到可以通过调整使得尽量多组 .1+.4 和 .2+.3，这样最多剩下两个数。通过类似上面的方法，发现如果剩下 (.3,.4), (.2,.4), (.1,.3) 都有这样的性质，可以直接 O(1) 做。但是 (.1,.2) 却没有这样的性质，而且有 .1*5, .1*3 + .2, .1 + .2*2, .2*3 四种组合，非常不好处理。最后我决定枚举 .1 * 3 + .2 的数量，然后有倒着枚举 100 个 .1 + .2 * 2 的数量（因为有向下取整，这个和余数有关），结果就过了。此时还有 1h。
然后发现 T2 可以状压，又多了 27 分，再看剩下的没啥时间做了，就开始玩耍 emacs 上的贪吃蛇。
最后出来，大家 Day 2 分都差不多，但是 hfy Day 2 270，直接翻盘，orz。