🤡

· · 生活·游记

~11.28

停课集训。【数据删除】比较无聊所以不写了。

前一天【】被【】了，只好开启野题日。

哦哦这个家长会怎么这么不牛，怎么还要被迫明天早起去这个荒郊野岭的【】考场。九点半睡了。

11.29

6：30 起来了，7：30 到了。幸好周六早上没什么车。

到达礼堂，依旧面到零个人。启动阿克奈次，啊我【】怎么什么关都打不过，这就是玩了四个月只有七个六星的实力吗。彻底怒了。

8：10 进考场。

8：27 解压，怎么密码是【醒醒吧，这不是 noip】，这么哈人。

8：40 建好文件夹，打好缺省源，开 T1。怎么又是神秘贪心。

想了一会发现取至少两个的那种糖果必定 a_i + b_i 最小，然后剩下的取一个前缀。欸我怎么过不了大样例。然后发现把两个的顺序对调一下做对了。8 个大样例直接自信抛，相信 ccf 111

9：20 开 T2。

数数？？？？？/jk

怎么题面这么长？？？

怎么这么难？？？

这我哪会做啊，我连去年 noip T2 和 CSP2024 T3 都不会。

有点慌。先冷静一下，手玩一下 m 小的情况。欸好像有一个 G 了的条件就是 a' + a < b < 2a（a' 和 a 是 w = 1 的最后两个，b 是 w = 2 的最后一个）。再观察一下发现好像是充要的。

那我还是不会做啊？？？怎么办？？？

【观察数据范围：n \le 5000】

那考虑直接暴力枚举所有 a 和 b 的位置！左边的 a' 直接双指针搞一搞，然后贡献是 2 的若干次幂。那右边呢？写一写，好像是要满足 \operatorname{popcount} 的差是一个定值，算一算发现右边的贡献是类似于 \sum\limits_{i = 1}^n \binom{a}{i} \binom{b}{k - i} 的东西。

等一下，这个玩意怎么有点眼熟？好像是...范...范...什么玩意，可是我不会怎么办。

思索再三，直接考虑大力找规律，还好 5min 就找到了！把这坨东西变成了单个组合数，然后两边的贡献一乘就行了，复杂度是 \mathcal{O}(n^2) 的。

这么难？？？这是 NOIP T2？？？

算了不管这么多了，直接开写。写了 10min 就一遍过了所有大样例。

现在还有 2h 左右。T3 是 mex，什么【】，直接跳过。T4 一看就是一个可爱的 ds，直接开做。

（温馨提示：下文的那个【】可能【千早爱音.jpg】的引人不适（把关键语句标粗了））

考虑离线然后干点什么，比如说历史最值线段树，发现早就忘了这玩意怎么写，怎么办！哦哦好像本来就做不了。

考虑分块！然后你跨块的贡献随便搞一搞，然后...然后复杂度就是 \mathcal{O}(nq \sqrt n)。做牛魔。

然后就不会了，玉玉。

打部分分吧，看一眼数据范围。欸这个特殊性质 DE 怎么这么奇怪。

考虑分治！每次只考虑跨块的区间，那分治就是 \mathcal{O}(n) 的！总复杂度是 \mathcal{O}(nq)！ 哦耶开写。【我当时到底在想什么？？？】

然后就发现了一个问题：不带修区间前缀和 max 怎么做？考虑 st 表！直接记录 [i, i + 2^j - 1] 的区间的前缀和 max，一次询问是 \mathcal{O}(\log n) 的。【我当时到底在想什么？？？*2】

好像过不太了，算了先写完再说。写完直接一边过大样例了。但是为什么最后一个大样例要跑 8s！一看就是那个 log 的问题！那怎么优化上面的问题呢？

已深度睡眠（用时 600s）：考虑分块预处理。直接把所有的小块和大块预处理出来存到两个数组里，然后单次合并复杂度就是 \mathcal{O}(1) 的。 怎么这么难写？【我当时到底在想什么？？？*3】

还剩半个小时，算了还是写一写。写完只剩 15min 了，有点急。疑似前面这么多一遍过，rp 已经消失殆尽了，测一下样例发现没过。急急急急急！！111111

然后没调出来。【】【】只能改回原来的代码了。欸我原来的代码怎么没备份？？【】【】【】幸好两分钟就一遍写对了，救我一命。

只好祈祷这份 \large{\mathcal{O}(nq \log n)} 代码可以多过几个点了。

检查一下 freopen。

欸怎么比赛结束了。别搞。又待了几分钟才出考场。

出考场哀嚎一片。怎么你们都这么会打部分分！

可怜的 xfd 被 T2 爆了。wjc 死磕 T3 失败了。有一些同学被 T1 爆了。传奇 wcz 切掉 T1 直接开 T4，失败了。看手机开机看 qq，lzy 和 zhy 350，太强了。好像有几个学长被送走了，默哀。

水 LA 群，发现很多人都在骂。有人在骂 T4 单 log 跟暴力一个分，于是我也跟了几句。

发现 T4 有单次询问的原题，看看那个题的题解。

。

。。

。。。

原来不带修区间前缀和 max 直接 st 表维护前缀和的 max 就行了啊！！！我是【】

那这个题不是一眼题吗！建议评紫。看到洛谷好像有人写了题解，瞅一眼。

。。

。。。。

。。。。。。

分治的复杂度原来是 \mathcal{O}(n \log n) 的啊！

疑似成为 T4 全世界唯一一个写了 \mathcal{O}(nq \log^2 n) 的人类。

我靠！！！！！！T4 双 log 65！！！！！！！！

！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！