NOIWC 2026 游记

· · 生活·游记

2026.2.7

晚上在报告厅打 ABC 并尝试进入前 20，但还没调完 F 论文分享就提前结束了，遗憾离场。

2026.2.8

因为宿舍条件过于唐氏症已经一些室友原因，申请并获得了独立房间，早睡早起。

2026.2.9 Day 1

开场先看了 T1，感觉是简单题，但是由于肚子不舒服还没看数据范围就去了趟厕所，想到枚举较小的数进行多少次 \times 2 操作。

回来以后开写缺省源，然后写了个不知道什么做法过了样例但是用 self eval 测只获得了 20 分。此时已经过去了 \tt 0.5h，有点急，发现思维比较混乱，于是整理思路。考虑记 k_1,k_2 为最大的满足 2^{k_1}\le x,2^{k_2}\le y 的整数，分别考虑 x 乘上 2^{k_2-k_1-1},2^{k_2-k_1},2^{k_2-k_1+1} 的情况（场上没想到可以少考虑一种）。记 f(x,y,k) 表示对 x 进行 k 次 \times 2 操作，得到的 x,y 还需要进行多少次操作。

发现若此时 x\ge y，则操作次数为 x-y，否则一次加操作可以视为在集合 \{2^c\mid 0\le c\le k\} 中任选一个数 v 并令 x\leftarrow x+v，代价为 1。考虑令 z=y-x，容易发现操作次数即为 k+\lfloor \frac{z}{2^k}\rfloor+\operatorname{g}(z\bmod 2^k)（其中 g(x) 为 x 二进制下 1 的个数）。于是写了一个单次询问 \mathcal O(\log V) 的做法，上 self eval 测，还是 20 分。接着便发现对 y 进行若干次 +1 操作可能可以减小总操作次数。发现这个 +1 的次数一定 <60。于是每次将 z 加上其 \tt lowerbit 即可。

在开头进行一些预处理便得到了一个单次 \mathcal O(\log\log V) 的做法，于是 T1 获得了 96 分，尝试卡常但是没能通过（赛后发现随便优化一下就 \mathcal O(1) 了），中间有两次评测同一份代码，运行时间差异很大（最大的点差了 \tt 500ms），不知道为啥。此时已经过去了 \tt 1.5h，有点急。

读 T2&T3 题面，感觉都不是简单题。

思考 T2，发现可以将问题放到二维平面上，x 轴范围为 [0,m]，y 轴向下表示时间的相反数，范围为 (-\infty, 0]，每个机器猫便可以视为一条斜线。此时移动轨迹便可以视为一条从 y=0,x\in [0,m] 开始不断向下移动且时刻斜率在一定范围内的线。问题便转化为了选取 k 组斜线，满足对于每个组，任何轨迹必与其中一个斜线相交（包括碰到端点）。

于是想到了将平面旋转 45^{\circ}，可以将斜线转化为与坐标轴平行的线。此时想到了某场月赛的一个题，考虑完一个组合法的条件以后直接写了个较为暴力的最短路，通过了 k=1\land n\le 10^3 的数据。接着拼了个 \tt D 性质便开始想 C 题。

观察 C 题，发现数据是随机生成的，前两个测试点不用管 k 的大小。于是直接想到了不断修复叶子节点并删除，写完获得了 44 分，进行一些优化以后还是 44。花了较长一段时间写 n=50 的部分，结果不知道为啥 WA 了。此时发现自己还没有 \tt 200 但是感觉送的分比较多，已经急哭。

放弃 C，继续搞 B。发现这是一个费用流问题，但是对费用流怎么写的印象已经没多少了。于是先写了一个 dinic 通过了 k=1 的 B 性质（不知道为啥场上判了 k=1，实际上 k\neq 1 也可做），接着凭印象写出了 dinic 费用流（赛后发现标记部分写错了，复杂度大了很多），过了 n\le 1000 的部分，获得了 64 分，修改了一些部分分的判定获得 68。

继续优化，但最终还是没能获得更多的分数，用完 25 次 self eval 测试机会（感觉 25 次完全不够用）。手在抖着，但是一切已成定局，比赛结束。

刚结束感觉金牌先跟去年差不多，但是经过一些交流后发现大部分人都没能通过 T1（都获得了 96），大手子 pmd 通过了 T3（/bx），有若干人会 T2 的 96 分，不过大家的分好像都不是很高。

查分，发现 T3 的优化帮我多获得了一份，最终得分为 96+68+45=209。经过交流发现有 Au 了，激动。

晚上将房间让给了 Kevin（Kevin CTT 第一天成功翻盘，成为了 \tt rank\ 1），回到原来的宿舍。此时打呼人走了晚上睡不着问题也得到了解决。

2026.2.12

上午看集训队论文答辩，dzd 依旧稳定发挥。恭喜 Kevin 进入国家队。

下午颁奖，发现自己是 \tt rank\ 19，第一次坐在了前排。节目没啥可说的，全程在水群。感觉 dzd 上台讲话时掌声巨响。

趣事：我的座位为所在排从左到右第二个，但是领完奖回座位时不知道为啥是从右边进去的。

晚上跟同学一起上高铁，不知道为啥位置旁边是教练[紧张]。

省选加油。