专栏文章

why put shushu on B????? || NOIP 2025 游记

llittlebug
生活·游记参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min9swa6
此快照首次捕获于
2025/12/01 22:54
3 个月前
此快照最后确认于
2025/12/01 22:54
3 个月前
查看原文
推荐在 cnblog 阅读。同样地，洛谷不会实时更新qaq
退役喵~（真的qwq
没什么好说的，早就放下了…
祈祷失败……不过也没有完全失败，虽然数数放了 B，但是这是个紫题，大部分人还是做不出来的。

Day -17

祈祷 NOIP 不会把数数放在 AB（1/18）

Day -16

祈祷 NOIP 不会把数数放在 AB（2/18）

Day -15

祈祷 NOIP 不会把数数放在 AB（3/18）

Day -14

祈祷 NOIP 不会把数数放在 AB（4/18）

Day -13

祈祷 NOIP 不会把数数放在 AB（5/18）

Day -12

祈祷 NOIP 不会把数数放在 AB（6/18）

Day -11

祈祷 NOIP 不会把数数放在 AB（7/18）

Day -10

祈祷 NOIP 不会把数数放在 AB（8/18）

Day -9

祈祷 NOIP 不会把数数放在 AB（9/18）

Day -8

祈祷 NOIP 不会把数数放在 AB（10/18）

Day -7

祈祷 NOIP 不会把数数放在 AB（11/18）

Day -6

祈祷 NOIP 不会把数数放在 AB（12/18）

Day -5

祈祷 NOIP 不会把数数放在 AB（13/18）

Day -4

祈祷 NOIP 不会把数数放在 AB（14/18）

Day -3

祈祷 NOIP 不会把数数放在 AB（15/18）

Day -2

祈祷 NOIP 不会把数数放在 AB（16/18）

Day -1

祈祷 NOIP 不会把数数放在 AB（17/18）
上午打点板子，11:58 准时出发喵。
车上睡睡睡。
下午继续打板子，感觉图论和数学的板子都忘完了啊。然后桌子离插座太远导致没法充电，何意味。
约了几个人面积。
去试机，原来 55 考场在 44 号机房吗。喵了一眼发现左边是和我姓名同首字母的 Au✌🏻，看来位置是按照姓名首字母字典序排的。
注意到电脑上啥编译器都有，不过没有 CLion，vs 又不怎么会用，所以还是老老实实地用 devc++ 吧。不过倒是可以拿 vs 写代码的。
唉我去的时候已经开始试机了，所以面积失败…只能等明天赛后了。

Day 0

起床。祈祷。
祈祷 NOIP 不会把数数放在 AB（18/18）
去考场了。
考场外碰到了 _ImposterX_并领到了徽章 /崇拜

正式赛

没在没让动键盘的时候动键盘，几个监考老师一直在那转来着。
密码是什么什么 dream。（!noip@Nov29,2025:dream
读题。
我【】你【】的出题人在 B 放数数。白祈祷了呜呜（
开 A，思考 eps 秒，发现同时选 xi,yix_i,y_i 一定是选那个 xi+yix_i+y_i 最小的，剩下的就选最小的 xix_i 就好了，于是直接这么做。没过 candy3，哦需要考虑选若干个 xix_i 的情况，那从小到大枚举选几个 xix_i，剩下的全选最小 xi+yix_i+y_i，取个 min 就做完了。
于 30min 过掉了所有大样例，感觉不大会有 corner case，直接看 B 了。
在代码开头写下了：
CPP
// why put shushu on B?????
// why put shushu on B?????
// why put shushu on B?????
// why put shushu on B?????
// why put shushu on B?????
B 大概就是一个，统计「贪心的答案 ≠\ne 01 背包的答案」的方案数，思考 20min，真的好无头猪，一点想法都没有 /yun。去看部分分。
先是会一个 O(2nm)O(2^n m) 的暴力，能过掉 n≤10n \le 10 的点。然后按照分值去思考部分分。发现 m=2n−1m = 2n-1 只需要判一下 wiw_i 全为 22 是否合法就可以了；m=2n−2m = 2n-2 是还需要判一个「只存在一个 wi=1w_i = 1」，复杂度是 O(nm)O(nm) 的。然后是性质 A，发现这种情况是全部合法的，直接输出 2n2^n 即可。
然后去研究 m=2m=2，发现需要分讨两种情况：
  • 按照贪心策略，先是考虑只选一个 wi=2w_i = 2 的情况，容易注意到这个 ii 只能是 nn，而为了让贪心选到 ana_n，需要把一个后缀都强制 wi=2w_i = 2，具体地需要找一个最大的 pp 满足 ap≤an/2a_p \le a_n/2，然后 i>pi>p 的部分必须 wi=2w_i = 2，i≤pi \le p 的随便选，于是有 2p2^p 种方案。
  • 然后是选两个 wi=1w_i = 1 的情况，容易发现必须有一个 wi=1w_i = 1 满足 i>pi>p（不然贪心就选不到两个 11），剩下一个随便放。于是枚举 i∈(p,n),j∈[1,i)i \in (p,n) , j \in [1,i) 作为最后一个 11 和倒数第二个 11，方案数即为 2j−12^{j-1}。然后要特判掉 i=ni=n，直接给答案加上一个 2n−12^{n-1} 即可。
凑一凑发现有 52pts 了！剩下的也不会了，开写。
第一件事肯定是写暴力，然后发现 01 背包是 O(nm)O(nm) 的而不是 O(m)O(m) 的！那上面那一坨部分分是不是得假一堆 /jk
回去看了看，哦大部分还是不依赖这个的，那还好。
写写写，发现只有 m=2n−2m = 2n-2 的部分分影响了，观察大样例发现输出都差不多，进而发现都是 2n2^n 或 2n−12^n-1，于是直接判了下 w1=1w_1 = 1 和 wn=1w_n = 1 两个情况，过大样例了。
看时间，发现 B 已经花了 2h 了，不过还剩下 2h 写 CD 的部分分，时间还是比较充分的。
开 C，是 mex 问题，想起来前几天刚和 Synthesize讨论了一个 mex 问题来着（但是并没有任何作用），于是在代码开头的注释中写下了 // tie tie @Synthsize /qq。
思考，但是发现只会一个 O(4nn)O(4^n n) 的暴力状压做法，甚至完全想不到 mm 有什么作用，加点剪枝可以过掉 n≤13n \le 13 共 16pts，或许还能拿退火骗点分。打算先看看 D。
花几分钟重新理解了下题意，便有了一个 O(n2log⁡n)−O(n2q)O(n^2 \log n) - O(n^2 q) 的暴力 + 预处理做法，直接预处理选择每个长度对每个位置产生的贡献，用线段树维护区间 min 即可，有 15pts。然后看特殊性质，发现 Rj≤32R_j \le 32 可以直接上面的做法，不过仅考虑长度 ≤32\le 32 的情况，复杂度是 O(32nlog⁡n)−O(n∑(Rj−Lj))O(32n \log n) - O(n \sum (R_j-L_j)) 的，也有 15pts。
其它部分分都不会了。
虽然注意到这个东西真的很像莫队，但是发现莫队的复杂度完全比暴力更劣啊（
于是先写 D，成功过掉两个部分分的大样例。
还剩 1h 写 C，根本不急，不过中间因为错误地考虑了 fu,Sf_{u,S} 不可达的情况，浪费了点时间，暴力写完就只剩 30min 了。快速去写退火，本来以为计算整棵树的 mex 复杂度是 O(n)O(n) 的，然后发现并不是，似乎可以用 dsu on tree 做到 O(nlog⁡n)O(n \log n) 不过没时间了，于是直接写了 O(n2)O(n^2) 的，毕竟退火也不是很依赖这个东西的复杂度。
经过一番调参，发现根本过不掉 n≤40n \le 40 的大样例，最大只能做到比答案小 [5,20][5,20]，还剩 5min 调不动了，查了查文件就摆了。
估分：100 + 52 + 16 + 30 = 198
出考场，准备面积，几个熟悉的来找了我，但是约好的两个没面过的怎么没来 /kel，我的位置和衣服都和描述的一样啊喵 /wq
最后人快走光了，实在等不到我也走了 w
教练说难度黄紫黑黑，？真 NOI Plus 啊（
高二的年级主任请吃了饭。笑点解析：我高一并且这次来打 NOIP 的高二有 55 个，高一有 1515 个。
然后返程，因为电脑昨天在酒店的时候用没电了，所以没法玩小岛时光了，只好睡睡睡。
回机房，开始复现考场代码。A 过了，B 怎么 m=2m=2 挂没了 /jk，问了问发现是没判 ai=ana_i = a_n，要寄喵 /ll
这下只剩 178 了，幸好测了测 CD 都没有挂分。
以下为在各 OJ 民间数据的测试结果：
洛谷：100 + 32 + 16 + 30 = 178 核桃：100 + 52 + 16 + 30 = 198 云斗：100 + 52 + 16 + 30 = 198
怎么说呢，虽然只有洛谷挂了，但是确实是挂了，数据稍微强一点就能把我卡掉了。。
不过 178pts 在 SD，应该还是有 1= 的吧？
和群 u 聊了会儿天，感觉好像比较弱的打的比较好，反而比较强的打的没那么好了，果然 B 正解是冲不得的。

Day 1

会放不到两天的假期（明天晚上开学）。
所以今天要玩一天喵。
然后游记一直在咕咕咕……
uno 好玩 qwq

Day 2

终于来写游记了 w
回忆录会补的，不过可能需要等一段时间啦qwq，补 whk 的时候会抽空写喵！

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...