noip2025邮寄

· · 生活·游记

day-11

体测，上午一直在紧张。然后中午练了一下跳远直接导致腹肌酸痛。然后跑 1000m 的时候腿一直是软的，还好最后有望及格。

体测完右膝倒闭了，上厕所都会痛，于是停止打球。

day-2

遭遇感冒，回家 lululu 了 3 天。一直在培养张勤健，但是打不过 alex_liu。

day1

没睡好，但还算精神。

压缩密码很诡异，由于无法分辨；和：解压时吃了一发罚时。

A 不太一眼，但是想了 2min 发现只会选最小的 x+y，其余的 x 只用看选不选，那排个序枚举一下就完了。先不急着写。

B 比想象中的难。观察一会发现是先排序，如果有 i<j<k 满足 2a_j>a_k,a_i+a_j<a_k，且 k 是最大的不选的，j 是最小的选的，就不合法。想的不太清楚，先扔了。

9:00 左右看完了 CD 题面，被吓哭了，先不做。然后 5min 左右写了 A。监考老师说 cmd 坏了，要用虚拟机来 diff？？？那我不会 linux 咋办啊。还好 A 容易肉眼比较。后面想了一下发现 B 枚举 j,k 就好做了，容易 O(n^2)。9:30 左右写完，这个没 cmd 我真没招了，肉眼随机比对了一些行，假装过了。

然后感觉 C 这种题已经不在我的能力范围内了。然后开始想 D。发现部分分很少，考虑特殊性质。发现特殊性质 D 可以对每个点找到以它为左右端点的答案，然后只需要用到这些区间，就是每次询问 O(n) 个区间 checkmax。那没有特殊性质也可以先处理 l=2^i,r=2^j 的答案，然后只要查询 2 个区间即可。那只要解决 O(n) 次区间 checkmax。发现可以只考虑左端点 \in[i-l+1,i] 和右端点 \in[i,i+l-1] 的所有答案就可以了。可以做到 O(n\log^2n+qn)，如果你喜欢的话可以写 n 个 st 表做到 O(n\log n+qn)。

10:30 左右写完，大样例 3.3s，不会卡这个的常，假装能过。2.5h 大战 C，能赢吗。

反正最后是没有赢。每个点可以选择孝敬它的某一个祖先，或者取到子树的较大值。那么是 f_{u,x,y} 表示 u 子树内选了 x 个点孝敬，\text{mex}=y 的答案，转移类似树上背包 O(n^3)。然后随便拼了 m=2，时间就差不多到了。我也不知道我最后写的是不是 O(n^3)，不管了。

最后是 100+100+[40,56]+[65,100]=[305,356]，别挂分。

upd：复现了一下 D 考场代码，民间数据 95pts，倒闭。发现我把其中两个单调队列换成 st 表后快了一万倍，然后就能过了/yun

现在我决定把 CTT 邮寄也放在这里，时间仍以 noip 当天为 day1。

day1

觉得自己膝盖好了，于是下午打了个球，然后又开始疼了。

day2

前往北京。我弟说要送我去机场，但是他疑似感染了诺如病毒，然后在路上/tuu我身上了，导致我舍弃了一条裤子在车上。

飞机餐一如既往地难以下咽，勉强吃了些沙拉和果冻。然后快下飞机的时候感觉很想吐，怕不是被传染了，不好笑。

晚上吃了~老北京~涮羊肉，不知道地不地道，吃完以后就不觉得想吐了。

day3

报到，室友是 9 字母下划线 4 字母。下午进行了试机，被 BC 击败了。本地机子很快，1e8 线性筛仅需 300ms-，但是 oj 疑似慢一些，然后在开营仪式上见到了张勤健。我疑似有点拉肚子。

day4

困昏了。降温严重，走去机房的路上感觉全身都被冷空气打穿了。

一开场就肚子疼，但是在 WC 思考到了 t1 的 O(nq) 做法。回来后迅速地写了。然后考虑上数据结构优化，然后我怎么不会优化啊。周围人都在哐哐写代码，那我咋办。想到自己可是省集 10 场会 0 题的人，好像不会这个题也没啥是吧。

t2 是字符串，t3 看起来是数论。t2 思考了若干假做法，感觉自己一点字符串都不会，很快就决定滚蛋。t3 范围很像根号老哥，部分分则是往根号分治方向启发。于是考虑根号分治，首先会了个 O(n^{\frac 34})，但怎么数据范围只有 10^6 和 10^{13} 啊，完全不给机会。后面仔细思考到了一个 O(n^\frac 23) 做法，看起来比较有前途，至少可以通过所有部分分，冲。

把一个题拆成 3 个题导致写了很久，终于在某个时刻获得了 60 分。然后卡常卡常卡卡时间到了。然后一直卡到了比赛结束。最后本地极限数据已经跑进 3s 了，但是 oj 比较慢，所以无法通过。只能说该给个 10^{12} 的分的。

最后 45+50+60=155，成为拼好分选手（t1 和 t2 甚至各有 10 分没拼），那可能是拼坏分选手。

day5

昨晚睡太晚了，导致起来的时候头晕。

又是不会 ABC，上来想了很久 A 怎么做。先想第一问，过了很久才会 n=1，然后发现 \gcd(n,m)=1 时可以分开算完再合并。\gcd(n,m)>1 想了很久都不会。感觉只有群论大手子能做出来。

然后观察了一下 B，很快会了结论，但怎么又不会维护。暴力好像很多，于是拼好分。

C 长得很像线性代数大手子题，打了 30 跑路。

最后 29.5+70+30=129.5。

出来发现 BC 都被过穿了，C 怎么是诈骗题，我真没救了。

考完听说 noip 出分了，获得 100+100+56+75=331，怎么 CCF 神机没有护送我通过 t4？

day6

睡得早了一些，但是起来还是很困/yun

A 居然是可做题，但是不会 1log，但是 2log 轻松通过了。

然后开始 lululu，经过漫长思考会了 B 单次询问 O(L\sqrt L)，但是空间很爆炸，感觉不应该写这个。于是又进行了漫长思考，但是啥也没研究出来。最后写了个这个东西，居然获得 61 分，那不做了。

然后做 C，部分分不太多，并且我咋都不太会啊。先思考 p=2，发现可以把 or 干掉，然后 popcount 是很少的，可以直接枚举，那么只有 O(d^2) 种值。然后 (A,B,C) 固定的时候就是要搞一些二位数点。此时我认为要做 qd^2 次二位数点，直接做不一定能过，也不太好写。然后又经过漫长思考，发现二元组的顺序好像也只有 O(d^2) 种，那就是对 2^dd^4 个点做 qd^2 次二位数点。咬咬牙不知道能不能过。写了一半发现只用查 q 次，那不是直接平衡到 O(2^dd^4+q\sqrt{n}) 了？高达 73 分，开写。

最后没写完，100+61+0=161。

讲评时发现我 B 其实是单次线性的，然后最后正解是 O(L\sqrt{L}) 的，不知道我这个能不能改过去。然后 C 确实是这么做的，p=3 时也只有 1000 多种顺序，但是 d 比较小所以复杂度差不多。