NOIP2023 游记
写在前面 意料之外的结局。 已经过了一个多月了啊，本来没想写的，但不写又好像少了点什么，权当记录一下三年的 OI 生活吧。 开始回忆。 Day -? 高三有推荐名额！赶紧去拉人。 CCF 说没交 480 的都不能去，寄。 Day 0 没什么特别的，中午大巴去杭师大仓前，三年 NOIP 都…
CSP 2023 邮寄
半退役卷积 Day -? 心血来潮再裸考一次，初赛75 。 Day -1 杭州两日游，今年竟然在杭师大仓前。 酒店没去年的好(早饭也一样)，但是很便宜就不管了。 Day 1 哈哈，复习是不可能复习的，线段树都不会打了。 上午在看石头门。 进场前撞到了前几届的学长。 进场，睡觉，给密码…
CF 板刷记录
CF1748E (*2300) 经过观察可以发现符合要求的 b 序列的充要条件是和 a 的笛卡尔树相同。 这个笛卡尔树比较特别，单看权值时是一个大根堆不是小根堆，把权值取反即可，差不多的。 想到笛卡尔树就好办了，建出笛卡尔树然后在上面 dp 即可。 Code CF 1737D (*2200…
NOIP 2022 退役记
NOIP 2022 退役记 Day -16 打模拟赛，补题，摆烂，whk 的同学们在期中考。 Day -15 上午模拟赛，三场大 DS ，笑死了，根本调不完。 下午补了一下午题目，whk 的同学们还在期中考。 晚上打了两道题，然后开摆。 Day -14 上午 VP 了一场之前的模拟赛，很…
CF1641D Two Arrays 题解
真神仙题。 做法一 使用 bitset 优化暴力，对权值开 bitset，匹配时直接或起来即可。 注意到空间很大，可以通过根号分治优化，时间复杂度大概在 $O(\sqrt{\frac{n^3m}{\omega}})$。 做法二 这个容斥是真的 NB。 判断两个集合是否重合的一个方法：枚…
公认为信竞天才的“王神”，因热爱而专注，因专注而优秀
公认为信竞天才的“王神”，因热爱而专注，因专注而优秀 竞赛圈获封“王神”的他， 身上有无数闪闪发光的标签： 六年级获 CSP-J/S 竞赛双一等奖 初二获 NOIP 竞赛一等奖 初三获全国青少年信息学奥林匹克竞赛冬令营金牌 高一获全国青少年信息学奥林匹克竞赛冬令营金牌 高一获…
字符串相关
字符串相关 先随便写写，想起来在再补吧。 KMP 这个退役前应该忘不了吧。还是写一下吧。 维护一个 nxt 数组表示最长 border ，匹配的时候直接暴力用 nxt 数组跳到最近的位置。 因为 j 最多往前跳 len 次，算上求 nxt 就是 $O(n+m)$。 失配树 kmp 的 n…
CSP2022-S 游记
Day -? 省流：宇宙射线轰击了出题人的脑子。 蒙了十多分，几乎都错，成小丑了家人们。 膜拜 wyy3332623 。 整了个活： Day -? 出分了，只有82，人均吊打我/kk Day -1 考点在学车，中午提前润去杭州。 宾馆还是可以的，旁边的吃的也挺多，晚饭全机房一…
dp优化小结
决策单调性优化dp 很早之前看李煜东蓝书的时候被吓到了，现在来补一下。 前置芝士 决策单调性前提：最优化dp。通俗地讲就是每个状态只能由一个最优地状态转移而来。 决策单调性：状态的最优转移点单调，形式化地说就是。 四边形不等式：有函数 $w(x,y)$，令 $a\le b \le c \l…
CF200A Cinema 题解
根据题意，若要填的位置已经被占了，那么就按照半径递增的曼哈顿距离圆填入。 我们发现，一个点周围最密集的情况下也只可能有 $k$ 个点，也就是说这个正方形的边长不会超过 $\sqrt k$ 。 所以我们需要找的只有对角线为 $\sqrt{2k}$ 的正方形，用并查集分别维护每一行的联通块的左右边…