NOIP 2023 游记

开坑咯！！！

第一次参加 NOIP，启动，启动，启动！

Day -?

收到官网账号，获得考场，重庆八中，111 还是这，就是打的士会晕车啊啊啊。

Day -2

得知明天上午高二全体去外面溜达还教练请吃饭，羡慕羡慕~~ 。不过我们下午也就开始放假了，也爽！！！就是希望教练帮忙打一下准考证啊啊啊

Day -1

和同学在家打游戏，飞了些纸飞机但总是飞不直。

Day 1

打算就冲着220打。

NOIP 启动！！！

T1 签到，写了个 stirng 的sort 就走路了，明白常数可能会导致我90，有时间再来写,30 min,90pts。

T2 看着可能是图论之类的但为了时间分配均匀，先写了40分的暴力，60分感觉有点麻烦，跑路,40 min,40pts。

T3 应该是个抽象的dp，我写了个 n^2 就跑路了，30min,35pts。

T4 的思路历程可能就是出题人一步一步帮我设计好了的。

首先能够把题面转化成选择一个点会有 d 的代价，如果一个区间全选了会有一定的贡献，连续的段不能超过 k。

首先简单的 dp，枚举连续的段。设 dp_i 表示前 i 个的答案，对于每个 i 枚举左端点并暴力计算贡献就能 O(n^2m)。

把区间扫描线，复杂度 O(n^2\log m)。

把 n 离散化，复杂度 O(m^2\log m)。

对 k 取min,复杂度 O(m\min(n,k)\log m)。

注意到 dp 式子是 dp 的值加一个常数，扫描线时只会修改一个区间的常数，复杂度 O(m\log m)，110min,100pts。

回来写了 T1 的正解，O(26) 的比大小，复杂度 O(nm+26n\log n)，34min,10pts

期望 100+40+35+100=275

出来大家都会 T2 完蛋人均 335，嘎了。

云斗没挂分，小图灵没挂分，洛谷没挂分。

冲击 C 类。

晚上 ABC E 题无脑题我都WA 6发，嘎了。

难受。