NOIP2023游记

Day0

试机看到do_while_trueand yyh, MLE, LgxTpre, modinte

win7, 但有安了C++插件的vscode

但是1e8 rand 跑1. 5s的机子, 想起报数lcez机子线性过不去的故事.

打了ntt和sam

Day1

Before Contest

看样例, 哟, 有字母? , 剩下三个看不出来是啥, tribool啥词不认识

During Contest

吸取经验, 上来先喝咖啡.

先看T1, 这直接对字符串排序, 比最小次小就能过吧

看T2, 看起来模拟每个位置最后是一开始的什么, 然后并查集扩展域处理相等不等限制就行了

看T3, 没懂, 看起来让求若 $a_i>b_i$ 连边, 选出不相交的若干条每个点度数至少是 $1$, 一会再说.

看T4, $n\le 10^9$ 大概是离散化坐标, 像个dp.

开始写T1, 直接sort吧卡常了再搞桶, 0. 5s大样例, 相信lcez的机子, 开T2.

写T2, 开始脑子不对劲, ($a$ 数组是维护每个变量最后的值是哪个变量的初值)赋值 $a_x=y$, 没初始化, 多测不清空, 9: 30过大样例.

开始想C, 发现尽量短的前缀匹配它不是最优, 想了个奇怪 $n^2$, 用vector维护 $a$ 一个前缀的所有能匹配 $b$ 的位置, 但 $3\times 10^7$ 应该是线性吧感觉正解应该不是优化二维dp, 大概30min后发现不会, 开始想D.

诶这个D, 直接dp不就做完了吗, 怎么还不如CSPT4了, 遂又想10minC, 还是不会, 开始冲D.

Wa on test2, 不会DP假了吧, 又写了 $n^2$ 暴力对了, 于是写 $n^2$ 替代线段树还是不对, 最后是 $f_0$ 没放到线段树里. 大概11: 00调出来, 大样例 $4$ 跑 $2. 4s$, 把离散化排序后二分的部分替换成排序后指针扫变成 $2. 2s$, 选择相信lcez的机子.

开始想T3, 又想了1h.

怎么只有1h了, 写T3暴力, 写了个T3特殊性质的假做法(贪心用最短的 $f$ 前缀匹配 $g$)发现过不去样例, 删了, 发现 $n^2$ 暴力跑 $4\times 10^4$ 样例才一点几秒, 选择相信lcez的机子. 大概还剩30min.

四个代码都拖进noi linux下测一遍, 发现diff的结果有些啥也不输出有些输出一个大于号, 不太懂, 肉眼比对过了.

After Contest

去dwt考场堵他, 说是335+了/bx, 出来第一句先骂区分度怎么这么低/fn, 碰见nrd, lgxPre, 大家一对发现谁也没过T3, 看起来人均335+了

然后碰见whc, 大神切了T3, 大概是每个点向左向右找最近匹配, 判断不能交叉, 没有很懂, 证明是他构造出来了一定可以的方案/kt

T1怎么还 $n=1$ 啊急了, 小丑竟是我自己.

云斗估分90+100+40+100=330吧, T1挂10分真是太唐了, 看CCF的了.

出来有看到了yyh, 但dwt怎么不冲上去