NOIP 2023 挂分日寄

NOIP 2023 挂分日寄

Day -1 2023.11.17

光速改完前一天的联考 T4，进入板子大赛

感觉前面的各种板子熟练了不少，好！

居然没有忘掉 线 性 求 逆 元 这个神秘东西，一大进步

Inv[i] = 1ll * (p - p / i) * Inv[p % i] % p

线段树也在 10 分钟左右调完，比较顺，信心++

但是最后的什么神秘 Z函数 这种东西还是不会，急

下午好像都开始摆了，四点过下去看了 排球比赛，很有精神！

有一个场子有两个校队的老哥薄纱对手，双方似乎都十分没有体验感

吃完晚饭直接睡，十分的稳健！

Day 0

return (void);

Day 1

前序

06：20 起了个大早。

07：05 抵达盛安街，完全胜利

07：12 找到一家绵阳米粉，遂食

07：30 食毕，排队，考拉和幽灵居然已经到了，这就是住在酒店的力量！

08：10 进场，总算没有出现什么 奇妙的问题 ，但还是有些紧张

08：18 进入考试，并在老师警告之前打开了虚拟机并写完缺省源，赢！

08：25 下发密码，怎么又是随机的东西，这次居然还有两重...

赛时

08：30 启动！

08：32 T1 是什么水题

此时此刻，命运的齿轮已经开始转动

顺便写一下赛时的思路：

题意实际上就是问你当前 单词重新排列后 字典序最小状态 能否 比其他单词各自重新排列后 字典序最大状态的最小值 更小

然后对每个字符串 排序找 最大状态（类型 1）和 最小状态（类型 2）

将新得到的 \(2N\) 个字符串 按字典序从小到大排序

在第一个 类型 1 串前面的所有 类型 2 串 对应的原串 必能成立

即这些串对应答案为 1，其余串为 0

时间复杂度 \(O(N^2 \log N)~~N=3000\) 有点卡

但 字符串比较的小常数 和 CCF i7-9 的 少 年 机 让我们一致坚信它能过

08：48 T2 感觉不可做

后面发现 隔壁的老哥 写了大半场没调出来，似乎真的很难

最后就真的没写，出来才发现输麻了

08：55 T3 似乎是能做的？！

当时瞎胡了个贪心，居然认为是对的，崩

当时以为是能拓展就直接拓展...想想比较纸张

09：08 T4 题意好复杂，但是应该能拿分

09：10 开题顺序定好 \(1 \to 3 \to 4 \to 2\)，厕所启动！

09：15 开始写 T1

09：25 写完 T1（他最好是写完了

09：30 过掉所有样例，自己造了几组似乎 没有问题（这下寄了吧

09：45 发现 T3 假了

10：00 发现 T3 可以真

这时候雀食想到一些真的东西

题意是要求拓展后一个序列的 每一位 都 严格大于 另一个

就说对于两个序列，它的 首位 和 末尾 这两位是一定会对上的

所以可以先判部分 不成立的情况，即 首位 或 末尾对应位差为 0

或者什么 \(A_1 > B_1\) 又 \(A_N < B_M\) 之类的，反之亦然

这个时候也可以直接确定两个序列到底谁更大

不妨 钦定 第一个序列（\(A\)）更大些，反之交换两个序列就行

然后枚举 \(A\) 上的数，在 \(B\) 上放一个指针 \(Pos\)

每次如果 \(A_i > B_{Pos}\) 则右移指针 \(Pos\) 到第一个 \(B_{Pos} >= A_i\)

反之左移指针 \(Pos\)

注意这里和直接找 \(B\) 中第一个大于 \(A_i\) 的数还是有所不同

因为每次右移左移都是基于上一次 \(Pos\) 的位置操作的

这里指针含义就是 \(A\) 序列前 \(i\) 个数在拓展后最多匹配到 \(B\) 的 \(Pos\) 位置

然后遍历完整个 \(A\) 序列，如果中途 \(Pos = 0\) 直接跳出，说明不成立

如果最终的时候 \(Pos = M+1\)（或者在一些写法下是 \(M\)），那么成立

反之也不成立（即 \(A\) 序列最后不能匹配 \(B\) 的 前 \(M\) 个数）

这样理论时间复杂度是 \(O(N^2)\) 的，但事实上跑的飞快

云斗数据怎么卡都没卡掉，甚至在 \(Ver.2\) 数据中直接拿到 \(95~pts\)

非常的好！

10：15 发现复杂度假了

10：30 发现想不出来，准备先拿下 \(55~pts\)，有点慌

这个时候想到 Meatherm 的赛事小技巧，于是又去上了个厕所

11：10 写的差不多，又调了好一会儿，时间不多了

11：20 发现 T4 应该不能拿分

11：30 发现 T4 确实可以拿分

11：40 不是很会在 T4 拿分

12：15 好像胡对了，想拿更高的分

这里赛时直接在 \(N\) 和 \(K\) 两个维度考虑的

状态即设到第 \(i\) 天时已经连续跑了 \(j\) 天

转移方程很显然，这里要把 \(M\) 个任务拉通来看

每次枚举到下一天时 部分回溯，避免重复计算，具体细节看代码

预计得分 \(36~pts\)

12：25 想不出来，失败

这时候时间不多了，又启动了一下虚拟机试了试编译

有些纠结到底去 T3 冲还是继续想 T4，又或者直接冲 T2 暴力

（当时 T3 有一个 $75~pts - 100~pts $ 的做法，但感觉不一定写得出来

纠结了好一会儿，好像完全没有时间了，只能再多次检查代码，罚坐

12：58 开始坐立不安

13：00 结束！

赛时 保守估计 得分 \(100~pts + 0pts + 55~pts + 36pts = 191 pts\)

赛时 脚造数据 得分 \(100~pts + 0~pts + 75~pts + 36~pts = 211~pts\)

当时觉得考的还行，但是 T2 没想是纯纯的纸张

顺便这里记录一下 T3 的 \(O(q \cdot N \log N)\) 做法

在刚刚 \(N^2\) 做法上发现，每次枚举时

实质上是要去找 \(Pos\) 位置前后第一个大于 \(A_i\) 的数

当时想到可以用 ST表 + 二分 优化

就是在每次得到 \(A,B\) 序列时对其建 ST表

若是想找 \(Pos\) 位置之后的值，左右边界分别设为 \(Pos, M\)

\(O(1)\) 查询 从 \(Pos\) 当前二分到的位置 区间内 最大值是否大于 \(A_i\) 即可

相当于遍历到每个 \(A_i\) 时用 \(O(\log N)\) 的时间查询 符合条件的位置 跳

这样 建表 和 遍历 时间复杂度都是 \(O(N \log N)\)，然后 \(q\) 次询问

这个东西预期得分 \(75~pts+\)

赛后

13：05 和 \(zhicheng\) 进行交流，发现 T2 是如如

13：20 前往集体聚餐，好像大家都很会 T2, T4，瓜起喽

似乎 T3 也找到原题了，而且 \(O(q \cdot N \log N)\) 能过...

聚餐的时候 \(Hanghang\) 说他 T1 看错题了（1500 字忏悔）

我们帮他证明了 错误做法的正确性，他觉得很对，这下这下了

当时他把题看成了 每个单词 只能找两个字母做 一次交换

（原题是 任意次 交换，相当于 重新排列）

感觉很怪，但是不得不承认这是对的（这题出了个啥）

可以知道，我们仍然尽量使得选择的这个字符串 字典序尽量小

而其它的字符串 字典序尽量大，最后比较

容易发现，如果只交换一个字母

对于选择的字符串，最好的方式就是找到 最小的字母与首字母交换

对于其他的字符串，最好的方式就是找到 最大的字母与首字母交换

然后这样换完之后同样比较 选择的字符串 向最小变换后

是否比其它字符串 分别 向最大变换后 的最小值 更小

如果比较时首字母都不相同，那么没有争议

因为重排后首字母和这样操作后 首字母是一样的（只有后面不同）

（即只比较首字母效果一样）

如果相同，可以发现选定串 后面的部分每个字母 都 大于等于 首字母

而 其他串 后面的部分每个字母 都 小于等于 首字母

也就是说 其他串后面部分 无论怎么排序 都将 小于等于 选定串后面部分

亦即 只要首字母相同 其他串字典序一定小于选定串，则选定串答案为 0

（不管是 只换首字母 还是 全排）

饭后向 \(Hanghang\) 学习 \(UNO\) 这种 \(8+\) 小 游 戏，一把打完就离场了

16：10 到家睡觉！

18：10 起床，好像代码 和 云斗数据 都出来了，测测我的

云斗速度，你值得信赖！

然后... T1 大挂 \(40~pts\)，这下蛤蛤了！！！

是这样的说，排序当时想的如果 类型 1 和 类型 2 串相等

那么为了保持 严格小于 的性质，这个 类型 2 串对应的原串肯定是不行的

结果其实由于保证了 单词两两不同，这样的情况一般不会发生

唯一发生反而是在如果一个字符串只有一种字符 \(eg:aaaaaaaaaa...\)

这样它生成的 类型 1 串 和 类型 2 串都是一样的

这个时候吧 类型 1 串排到前面，然后就会把这个字符串判为 假

但实际上这个字符串是符合要求的，于是 寄了

（只能希望随机数据力）

已经没有心情看最后两题了...

结果 T3 竟然水了 \(95~pts\)，这数据不好评价

后面把 \(O(q \cdot N \log N)\) 的做法小写了一下，写到 01：30

一交，\(RE\) 了好一部分，只有 \(50~pts\)，实在熬不住了，睡！

回学校再调

T4 又小挂 \(8~pts\)，像是没开够，反正挺傻的...

最终得分 \(60~pts + 0~pts + 95~pts + 28~pts = 183~pts\)

感觉数据再严一点甚至拿不到这个分数，自闭了要

（题解似乎又堆了好多？？？？？

Day2

写总结的日子

总的来说，

​ 这次在 心态和准备 上还是好了一些，没有 忘带某些东西 或之类的奇妙事件发生，赛前 无法专心复习的时间 也有所减少。但是就心态方面仍有提升空间，像是最后接近 \(40~min\) 基本没想出或者写出什么的这种状态也是不行。

​ 而 赛时技巧 还是有待提升，无论是像 对拍 之类的检查技巧还是调试的方法，掌握都不够熟练。就像这个 T1，如果当时可以很快的写出一个 拍子，进行个 几百甚至几千组 对拍，可能就能检查出问题。

​ 知识积累 上也有很多不足，这也导致第一遍看题的时候 胡了很多假做法，导致后面预判失误，摇摆不定，进而也浪费了不少时间。仍然需要加紧补齐知识短板，同时认真改错总结 联考的题，积累做题思路和经验。

根本的原因还是实力不足

​ 开学以来集训，能明显感受到自己的进步。但是成绩不够理想，除了客观上的积累不足以外可能仍然有 没有用尽全力 的努力这种成分在。不可否认上半期会在适应新的学习节奏，但是下半期以及之后应当要有更好的状态。不能再有什么 联考 \(\to\) 罚坐 \(\to\) 睡觉 这种神秘问题，并尽可能在学期结束前过完一边课件，寒假找时间突破 数学方面 内容，争取在后面比赛中有更好的发挥