NOI WC 2024 游记

· · 生活·游记

太菜了没去成 PKUWC。

\text{Day }-2

晚上十点到 CQ 了。成功住进了酒店并与在 911（房号）的 wj&myd 汇合。

\text{Day }-1

去人民解放纪念碑和洪崖洞逛了一圈。

去洪崖洞之前在美食街转了两圈，然后买到了两份黑暗料理，亏了。

晚上打 Graphomata。

\text{Day }0

打 Graphomata。

10:40 离开酒店去报道了。

在报道大厅看 Fire in the hole（

首先饭还是很好吃的！然后发现下午没事做了就跑去宿舍看了一下。

我们在 A102，A104 是cjh，A106 是zlt，A124（应该）是 ckj。

后来教练走了，我们整个下午没事干就开始颓废。

首先我们发现房间里没有可以充电的插座！整层楼只有宿管室旁边不到十个插座可以用！

然后我们忽然发现我们宿舍旁边有一个插座，本来要买个插板结果宿管不让用。

最离谱的是宿舍里是没网的。

然后 gjy 想睡觉了，结果他说被子有股奇怪的味道 myd 说像是化粪池。

坐牢\kk

不过电脑还有电，就把 F1 和 F2 过了。

一直坐到晚上五点，然后就跑到教室里去了。

还是没网，不得不 Graphomata 了（

晚上把 F3 过了。

然后就是 WC 启动大会。

首先来点艺术表演，然后就是领导致辞。感觉比听政治老师讲课还难受。感觉不如 dzd。

最后一群领导上台然后 “WC，启动！”

集体上厕所是吧（

回来之后又颓了一会冰与火，发现手感稀烂不如 Gender And a Metal Bat 就睡觉了。

\text{Day }1

上午 lxl 讲持久化数据结构。

持久化平衡树还好，从堆感觉就开始掉线了，后面开摆了（

中午在教室开摆。

下午感觉是个没什么用的讲座，不知道为什么要把额外空间压到亚线性级别。不过题看起来还挺有趣，实际做法听不了一点。唯一注意到的点是 \mathrm O(\log^{100}n) 个数分一块。

然后还有近似最短路。还有 O(n^{2.37}) 的矩阵乘法？还有近似最短路时间复杂度从 \mathrm O(n^{2.33}) 优化到 \mathrm O(n^{2.28})?

这就是 TCS 吗，果然 Theoretical。Not practical at all.

晚上把 Graphomata F4 过了。教学楼一直有只猫在教室间转，看着挺可爱的就拍了两张照。

回到宿舍讨论怎么颓废，于是叫 myd 第二天去买了两副牌。

\text{Day }2

上午题目选讲。没带笔记本，非常生气。

第一题 Wish I Knew How to Sort。

后面是个最短路，再后面就开摆了。

看到下午是个量子通讯，直接溜了。为什么要给 OIer 听量子通讯。

中午和下午一直在开摆，然后发现自己任务计划好久没做，重写了自己的 Miller-Rabin 然后写了个 Pollard-Rho。接着过了 FACT1。然后晚上本来想着卡 FACT2 的常结果把 FACT1 的代码在 SPOJ 上交三遍就过了？然后又在洛谷上交了八发才过。然后 PTC 样例一过直接交了，然后过了。

然后就是摆烂时间。

myd 终于开始 Graphomata 了。我一般是在机房颓废所以笔记本上啥都没有。

然后突然发现我的笔记本上有个三年前从少年宫的 WinXP 电脑上拷下来的 3D Pinball？？

三年之期已到了属于是，wj 玩了都说好。然后就和 wj 一起玩，然后我打出来一个 4\times 10^6 分。

晚上 wj&gjy 在打 MC，但是我没有 MC\kk 就算有我还没鼠标\kk

然后试机。去的时候和同学走散了，不知道哪里拿密码条非常慌，好在他们回来了顺便把我的密码条也带回来了。

试机。发现我不知道密码。试了五分钟最后 myd 告诉我密码是friend。首先开了一下 VSCode 觉得挺好，试机题目是 NOIP 2021。

突然发现我还是不会那年 T3，已经开始害怕了。明天等着打三个暴力吧。

晚上回到宿舍打牌。忽然发现 myd 桌子上全是食堂发的橘子。

\text{Day }3

早上七点起了床。然后进场。发现忘带身份证，最后两分钟拿回来入了场。

首先这个 VSCode 不能运行那我要你有什么用？？但是用 VSCode 习惯了就用 VSCode 写代码用 Sublime 编译。当年 CSP 为了不用 Dev 我也是 Sublime 写代码 Dev 编译。

发了个自测程序是好的，但是只能测样例没什么用。

然后三题看了一遍。

\text{T1}

一场长为 t(1\leq t\leq 3\times 10^5) 分钟的比赛有 n(1\leq n\leq 200) 道题，第 i 道题有三个属性：a_i\in\{0,1\},1\leq c_i\leq t,1\leq v_i\leq 3\times10^5，代表做这道题需要 c_i 分钟，可以获得 v_i 分。

小 A 会从前往后先做完所有 a_i=0 的题，再从前往后做完 a_i=1 的题。如果他做完这题的时间不超过 t 他就可以得到这题的分数。

\text{T2}

给定序列 a(1\leq |a|\leq 5\times 10^5,1\leq a_i\leq 10^{12})。有多少个长度大于 1 的子区间 [l,r] 满足：

存在长为 r-l+1 的序列 b 与正实数 c，满足 b_{i-l+1}\in\{a_i,2c-a_i\} 且 b 严格递增。

原题的物理解释是，一排高为 a_i 的石柱在高度为 c 的水面中会形成 2c-a_i（可能大于 a_i）的倒影。每次你可以从一个柱子或柱子倒影的端点移动到比当前位置高的，在右边与你相邻的柱子（倒影）的端点。有多少对石柱 i,j 使得可以从 i 移动到 j？

\text {T3}

给定一棵形态任意的维护区间和的线段树，它的根节点代表 [0,n)(1\leq n\leq 2\times 10^5)。给定 m(m\leq 2\times 10^5) 个区间和询问，有多少种选择节点的方案使得我们只要知道这些节点的值就可以回答全部 m 个询问？

T1 直接考虑每种做题方案的贡献，也就是说我们直接枚举最后做了那些题。发现不一定每种方案都能算进贡献，具体来说，有些方案是时间还足够再完成一道题的，由于我们只算最终结果的贡献因此这是不合法的。

考虑如何判定能否贡献至答案，发现我们只关心以前做完的题的总用时与下一道要做的题的用时。枚举还没做完的题与它的类型，就可以通过两次背包算出所有最后在做但没做完这题的方案的总贡献。

注意特判所有题都可以做完的情况。因为太菜了，一个人均场切的绿给我整了两个小时。

然后看 T2。发现可以将合法条件转化为柱子到水面距离（即两者高度差的绝对值）是单谷的，并且除了最小值相邻的两个数不能相等且最小值最多两个。继续转化得不存在 a_i 使得 a_{i-1}\leq a_i 且 a_{i}\geq a_{i+1}。

此时还可以发现，如果方案合法必定有一种方案使得某根柱子与水面的距离很小（可以认为等于 0.25），于是我们实际上只需要检查 c=a_i\pm 0.25。

同时注意到一个左端点对应的合法右端点是从左端点开始连续的区间，于是只要快速求出每个左端点对应最大的合法右端点即可。

同时我们发现可以将数列分为几个极长合法段，此时不跨段的区间均合法，于是一个段内的所有数的最大合法右端点至少是这一段的右端点，可以将它们的最大右端点与这段的右端点取 \max。

可以打出 \Theta(n^2) 暴力。

考虑优化，首先将最大右端点取 \max 的是一段区间显然可以线段树。考虑如何维护极长合法区间，发现 c 在越来越大的同时，相邻两个数的大小关系最多改变一次。只有相邻两数的大小关系改变时合法区间的划分才会改变，于是可以算出所有改变的时间排序并在线的用set维护极长合法段的端点，是 \Theta(n\log n)。

打的时候感觉思路挺混乱的，好像细节没想清楚，最后突然发现打完了还剩半个小时。然后一发大样例全过？？

最后摆烂了。T3 n\leq 3 特殊性质手玩打算拿个五分。

出场了发现 200 真的人均分。要垫底了\kk

下午出分。不是 T1 怎么给我挂了五分？T3 手玩算错痛失五分。总共挂了十分。95+100+0=195。

隔壁老哥 245。感觉真垫底了。

原来我 T1 暴力是这样的：

//....
goto TLE;
//....
answer%=mod;
TLE:;
//....

然后没取到模炸了。正解没挂暴力挂了。

出来让 AJ 给我们买了三双拖鞋。

讲评。T1 T2 我都是正解。T3 是个图论转化然后神秘 DP。

吃完饭回教室开始摆烂。发现怎么大家都在写游记，然后我就把这篇游记补了。

晚上有个文艺汇演，没去。有点遗憾。希望以后还有机会吧。

\text{Day }4

早上 Elegia 讲组合计数。

首先讲了一下生成函数的运算与 n 王问题的线性解法、生成函数解法。然后讲 \mathrm O(n\log n\log\log n)\to O(n\log n) 大数乘法和 \mathrm O(\frac{n\log^2n}{\log \log n})\to\mathrm O(n\log^{\log_2 3}n) 半在线卷积，还有 \mathrm O(n\log^2 n) HalfGCD。

从 Hermite-Pade 逼近开始就掉线了，然后突然听到了有 10^{11} 项系数的最小多项式。

中午颓废。

下午颓废。本来两点要去听课结果上了个厕所被关外面了。

然后看了选讲的 8 道题全是黑的，两道 CF 都是 {}^* 3000，一道神仙斜优，一道要从暴力 DP 建出自动机然后优化自动机形态，再在优化后的自动机上跑矩阵快速幂路径计数。太菜了所以被震撼到了。

晚上颓废。以前没打过 tetr 决定尝试一下。

\text{Day }5

早上 csy 讲随机化。然后讲了两道 IOI2023。讲完好像和随机沾不上边啊，这时 csy 说现在我们进入正题（

然后就真开始随机化了，讲了经典随机化和随机打乱和随机排列这两种经典用途。然后就是经典例题 CF1198F（

然后是两道研究题，一道稀疏背包，一道卡字符串哈希。

稀疏背包要用到线性代数的正交基，然后要用什么 LLL 算法。摆了。

结果没想到这玩意是个伏笔，可以把卡字符串哈希转成稀疏背包，十个模数都能卡。然后还能用稀疏背包过 P6634 和一个奇怪题。

中午摆烂，写了 SP12009。下午讲座没去，怎么每次都把最有意思的漏掉了。

晚上 ABC。

旁边两个外校的对着 F 讨论这题 FFT 能不能过，我一看这不典中典中典哈希。怎么出出来的。然后去打 P3013。

打了一会突然想看一下 ABC 其它的题了，然后去看 G 发现一眼主席树板子，E 线段树优化 DP 板子。

不会出 ABC 可以别出。

\text{Day }6

早上答辩，首先 zky 上场来了一个积性函数求和，还有 \mathrm O(\sqrt n\log^2n) 块筛卷积。

然后就是线性拟阵奇偶 \mathrm O(n^3) 做一般图最大匹配。

然后 hlt 的英文自我介绍可能因为紧张而不是很流利。后面他讲完论文，提问环节 dzd：“想问一下你平时的英语是怎么学的。”然后 hlt 说可能是他的问题，dzd：“你的英语是要提高一些。”

难蚌，果然是 dzd，非常的简单直白（

后面还有一位同学提问，“你这个 Treap 分裂是两只 \log 吧，我也只会两只 \log（”

然后第四位的时候有同学问：“你这个论文讲的是 Ynoi 啊，那是不是你这个在 OI 里面不太常见（”

懂了，下次 CSP 让 lxl 出，看你还敢说不常见（

第五位是 realskc！然后在 dzd 面前自豪的说出了“我组织了几天前的文艺汇演”（

然后第六位有同学问对 CTT 和 CTS 题目看法，然后就是典中典 CTT Day4 下发 std（

中午摆了一会开始写题。

下午首先是个精彩瞬间，然后尺子姐姐（

然后颁奖仪式，还在铜牌的时候过了 CF1282E。195 银锭了。

过了一会上台领了奖，不是牌子吗怎么是纸呢（

下台开摆。

过了一会到 Au。

/bx ckj wxw Au

然后看到有个人戴着个 WC 牌（，过了一秒塞衣服里了（

WC 结束了！

下午就在自习室里开摆（

总结一下，来 WC 不仅菜没有人均分还把每个好玩的东西都错过了\kk

希望明年还有机会来 WC 玩！ :D

诶不是我怎么金钩了？