NOI2024F队游记

（（没进队就自行创造个队进

为了显得内容充足决定拿NOIP灌点水（（

NOIP

（（实际上等于省选了

NOIP 这周周一早上开始发烧，体温一度高到 40 甚至 41，晚上喝了口贝多芬后去也只降到了 38。稍微有点力气后去医院，检查出甲流，吃了一周的药，每天都睡不醒，头很疼，感觉要寄。

又是一个人来考点，到的时候天还是黑的。一个人没看见但是时间又好像快到了，进考场发现人都来完了是我太晚。好像全员戴口罩，十分安全（（伏笔

坐左上角第一排，旁边坐的 hpy，再右边是 tqx，后面一排有 yzx，好家伙全都在啊。好像 hpy 也在发烧，希望他没事。

其实到写的时候（2024-07-26）已经记不太清当时的细节了。T1 分别对每个字符串从小到大和从大到小排序记录两遍之后统计最大串和最小串后暴力比对就可以，应该是直接写了。T2 读着像二分图染色但是身体不太舒服没法仔细思考于是还是只写了部分分。T3感觉是一个很难的 dp 于是只写了 1、2 点（论信心的重要性）。T4 更没信心但还是硬搞了。感觉好像被旁边的 hpy 又传染了，中间连着咳了很久，吸不上气感觉要被迫重开了。最终还是没能思考出 T4，早知道磕一下 T2 了想一会应该就能想到。

离开前被 lyc 叫住了，说实话我至今不知道他如何在没见过我的情况下认出我。愣了亿下才反应过来他伸出的手，于是进行了一个友好的握手。（（嗯嗯...如果 lyc 看到这里的话...我真的对您没有任何意见啊啊单纯是我当时发烧烧蒙了反应了好几秒才反应过来，回来后因此自闭了很久。

最终基本没怎么挂分，但是本身就没写多少。从考场出来后就想着考省选翻盘了。回来后又烧了一周，咳的快去世了。

NOIWC

NOI-WC2024游记

冬令营最后得知了我省没有独立省选，按NOIP成绩选省队。

某天晚上一个人拿着个水瓶接满开水暖手站在育才行知楼楼顶，遂玉玉，欲一跃解千愁。

后来考虑攒钱买 D，但是因为学校老师错吧邮件发给了特派员（因为之前报名全是发给特派员的而这次是直接发给 CCF），而我 APIO 后一直没有接到通知感觉不对问了下才得知此事，于是我 NOI 没了。

NOI 没了？不不不！没有条件就创造条件！手动给自己创造个加差旅费 0 元的 F 队出来！

NOI Day1

大概 40 分钟读完 T1 ，对于每个询问暴力枚举排列 p 看是否可行。时间复杂度 O(n \times m! \times q)。

又花了 40 分钟读完 T2，怎么 WC/APIO 味儿这么浓，感觉见过原题但是加强了请求数。前 15 分考虑一次请求 \frac{n\times(n-1)}{2} 个查询即可，感觉不妙又很妙但是先去看T3。

T3 1~3 点可以 01 搜索，感觉满足性质 A 又同时满足 m=(n-1)\times(n-2) 意味着也可以近似看作满足性质 B。对于性质 B，首先处理向点 1 有方向要求的点；之后如果一个点不能到点 1 那么从这个点出发的要求忽略，到达这个点的要求确保出发点到不了点 1 即可；而如果可以到达点 1 则忽略到达这个点的要求，从这个点出发的要求确保到达的点无法从点 1 到达即可。感觉启示我们用 dp，但是 dp 我是不可能会的，预期得分 36。

决定还是处理 T2，因为题目保证数不会重复，每个查询都可以淘汰一个数，于是感觉可以每次淘汰一半的数，直到剩余的数的数量足够小可以用 15 分的做法问时再做一遍即可，模了一下 13 次请求加 105 万左右的询问是最优的，预期得分 15+37=52。

回忆思考 T2 的过程，这样的做法可以用一次请求和一次询问淘汰一个数，可以省下很多询问数。但如果数的数量比较少，剩余询问数虽然有富裕但又无法 n^2 做时，这样的做法显然是不优的。之前用两个数做对比时一次请求一次询问就可以确定唯一结果淘汰一个数，那么如果考虑改成队三个数作比较就是一次请求三次询问就可以确定唯一结果淘汰两个数。又模了下发现先二分 4 次再三分 5 次再暴力的方法似乎是最优的，总共 10 次请求 109.7 万左右询问，预期得分 15+54=69。

认为 T3 即使真 dp 也不是我能想出来的，决定再想下 T1。感觉似乎可以对每个询问 O(n) 暴力匹配确认排列 p 看是否有冲突，这样时间复杂度直接降至 O(n \times q)，写了下只有三十几行感觉不太对，跑了下样例果然出错，排查了下发现忽略了集合内的数没有顺序这一性质，依旧只有 40。

由于没有数据所以只有预期得分 40+69+36=145。

NOI Day2

（（因为腾不出连续的时间所以没计时，想了很久很久

T1 试图推性质就退了很久，但好像并没有推出什么特别有用的性质。考虑 dfs n^2 的 50 分。

去读 T2 样例没看懂，[5,2,4,5,1] 是什么奇奇怪怪的走法，感觉这样走下去会无限，遂跳过。

T3 首先 01 搜索暴力删边可以水过测试点 1，之后考虑特殊性质。感觉 B 性质很友好，暴力 O(n^2) 判断每个点是否是一类点即可，预期 15 分。依旧感觉像个 dp，遂放弃。

回来继续看 T1，草稿纸上试图分析对于每一个分母有多少个分子是可行的，但是发现找不出什么性质。思考了很久想到的唯一有用的性质是完美正分数的分子和分母中至少有一个是偶数。想到类似质数筛的做法，但好像更像递推（是一个只有自己理解但不知道怎么描述的做法，遂不写在游记中），但是由于是累加而不是标记为 1 就行于是还是无法 O(n)（（怎么会有弱省的 F 队人在想 A 题））。去实现了一下，样例一正确，但是样例二错误，写了下 dfs 对这分析，发现实现细节有误，重新该了两遍后就正确了，样例三四都顺利通过，但是本地测发现样例四时间要六秒多，n,m=10^6 更是要七秒，而时限只有六秒。遂常数优化了一下，大概卡掉六百多毫秒。想起正赛会给开 O2 遂手动开了下，四秒多顺利通过，由于本地机器很巧是 NOI 同款处理器，可信度很大，于是预期 85。

由于依旧没有数据所以只有预期得分 85+0+15=100。

对了下分数线，如果默认笔试满分 100+145+100=345 可以铜。但是考虑时间和心态影响感觉 F 队也挺好最起码没在重庆丢人，要真去了可能我省就要变成一铜八铁了（若算上冬令营和 APIO 我省今年一共一铜十三铁）。去看了同学的游记，发现我省唯一铜牌好像也没了（？？？）。D2T1好像拿到了大众分。（（可喜可贺...（（贺什么啊这么菜QAQ

其实还是很想去的，从游记的只言片语中能感受到和之前冬令营以及APIO的不同。可能是这次的大家会更熟悉一点吧，毕竟冬令营时我们四个都是第一次见面，而这次的他们不是。倒也是当时去冬令营的五个一个进队的都没有。感觉我们当时好像是瞬间适应时差，晚上即使聊天也没有很晚，也没有一起打游戏，中午有次甚至在一起写寒假作业，大家都很乖巧（什？）。大家去NOI的这几天我也一直静不下心做其它事，总在回忆着冬令营的时候，毕竟那是我等了五年的机会啊！

（（所以我省什么时候才能拿金牌啊QAQ