NOIP2023 游记
写在前面 意料之外的结局。 已经过了一个多月了啊，本来没想写的，但不写又好像少了点什么，权当记录一下三年的 OI 生活吧。 开始回忆。 Day -? 高三有推荐名额！赶紧去拉人。 CCF 说没交 480 的都不能去，寄。 Day 0 没什么特别的，中午大巴去杭师大仓前，三年 NOIP 都在这里考。 到的时候已经不早了。 接下来海波请吃饭，记得荤菜超多，下血本了。 还有同学过生日，挺好的。 Day 1 睡得很好，早饭不错。 在进考场前什么都没复习。 发密码，开题。 看 T1，就是个字符串比大小，经典 T1 难度。 半小时码完，写的垃圾做法还要记录次大值，本机跑了一秒半，想了想还是扔了。 看 T2，哦哦哦，是不是扩展域并查集，这个我会！ 想了很久，调了很久，大概一个小时之后搞出来一..
CSP 2023 邮寄
半退役卷积 Day -? 心血来潮再裸考一次，初赛75 。 Day -1 杭州两日游，今年竟然在杭师大仓前。 酒店没去年的好(早饭也一样)，但是很便宜就不管了。 Day 1 哈哈，复习是不可能复习的，线段树都不会打了。 上午在看石头门。 进场前撞到了前几届的学长。 进场，睡觉，给密码，启动。 看 T1，秒了，虽然知道码力肯定不能和一年前比，但打半小时也太捞了。 看 T2，我草，很可做的样子，60分不是一眼，赶紧想正解。 两小时后：60pts 跑路。 看 T3：傻逼大模拟，我现在这B码力拿头打，15pts 跑路。 看 T4：好像很眼熟，但是不会，$n \le 20$ 都不会打，性质 A 打了跑路。 睡觉，出场，晚上接着看石头门。 Day ? 好像能估分了，竟然一分没挂，他妈的，去年..
CF 板刷记录
CF1748E (*2300) 经过观察可以发现符合要求的 b 序列的充要条件是和 a 的笛卡尔树相同。 这个笛卡尔树比较特别，单看权值时是一个大根堆不是小根堆，把权值取反即可，差不多的。 想到笛卡尔树就好办了，建出笛卡尔树然后在上面 dp 即可。 Code CF 1737D (*2200) 先说结论：最短路一定是将某一条边变为连接 1 和 n ，然后直接走这条边。容易反证得出。 那么我们现在的问题就是求出对于每一条边，同时经过两个端点和这条边的最短路径，求出来之后乘以边权再取最小值即可。 做法很多，但是既然 n 这么小就还是 Floyed 好了。 总时间复杂度 $O(n^3+nm)$。 Code CF 1726E (*2400) 很厉害的数数题。 首先有一个性质：将 $i$ 与 $p_..
NOIP 2022 退役记
NOIP 2022 退役记 Day -16 打模拟赛，补题，摆烂，whk 的同学们在期中考。 Day -15 上午模拟赛，三场大 DS ，笑死了，根本调不完。 下午补了一下午题目，whk 的同学们还在期中考。 晚上打了两道题，然后开摆。 Day -14 上午 VP 了一场之前的模拟赛，很水啊。 接下来下午就是补一些之前的题，CF 的好多题质量确实非常高。 晚上也补题目啊，whk 的同学们期中考考完了，我高中最后一场能咕咕的考试结束了。 今天中午颓了 generals 和 gartic 。 Day -13 上午打模拟赛，有几道题的套路见过的，感觉这个 D 很有意思。 下午打洛谷月赛啊，交互很可做，自己搞了个做法玩玩，但是调试没删喜提 70 。 晚上放假了晚上。 Day -12 补题，补..
CF1641D Two Arrays 题解
真神仙题。 做法一 使用 bitset 优化暴力，对权值开 bitset，匹配时直接或起来即可。 注意到空间很大，可以通过根号分治优化，时间复杂度大概在 $O(\sqrt{\frac{n^3m}{\omega}})$。 做法二 这个容斥是真的 NB。 判断两个集合是否重合的一个方法：枚举两个集合的子集，长度为奇数的子集相同就加一，为偶数的子集相同就减一，最终若有相等元素，则最终值一定为 $1$。 证明：令 $s$ 为交集大小，则我们所求值为 $\sum\limits_{i=1}^{s}\dbinom{i}{s}(-1)^{i+1}$，由二项式定理可以推导得到。 这个方法看似时间复杂度很劣，但是在这道题中有奇用，我们可以用他来判断若干集合中于一个集合有相同元素的集合个数。 具体的，..
公认为信竞天才的“王神”，因热爱而专注，因专注而优秀
公认为信竞天才的“王神”，因热爱而专注，因专注而优秀 竞赛圈获封“王神”的他， 身上有无数闪闪发光的标签： 六年级获 CSP-J/S 竞赛双一等奖 初二获 NOIP 竞赛一等奖 初三获全国青少年信息学奥林匹克竞赛冬令营金牌 高一获全国青少年信息学奥林匹克竞赛冬令营金牌 高一获亚太地区信息学奥林匹克竞赛金牌 高一获全国青少年信息学奥林匹克竞赛金牌 竞赛天才的背后，是智慧有爱的同学氛围，和专注于梦想的无数汗水。 闪闪发光的王神 从小学开始踏上竞赛道路的王煜阳，是公认的信竞天才，一路披荆斩棘，获奖无数：全国同届信竞第一名，普及组、提高组双一等奖，初一 WC、APIO 夺银，初一清华营优秀获得者， NOI2022 唯一达到金线的初一选手…… 王煜阳在中学生竞赛圈里获封号为“王神”。在学..
字符串相关
字符串相关 先随便写写，想起来在再补吧。 KMP 这个退役前应该忘不了吧。还是写一下吧。 维护一个 nxt 数组表示最长 border ，匹配的时候直接暴力用 nxt 数组跳到最近的位置。 因为 j 最多往前跳 len 次，算上求 nxt 就是 $O(n+m)$。 失配树 kmp 的 nxt 建树罢了，每个位置的 nxt 是它的祖先。 能求两个前缀的最长公共 border ，但是好像没有什么用。 Trie 树 没什么好讲的，0/1 trie 可以讲一下但是并不属于字符串（（（ AC 自动机 简单来说就是 trie 树上跑 kmp，但是有点抽象。 我们先来考虑 AC 自动机的建立，每一层都可以用上一层的失配数组更新，因此我们使用 BFS ，将每一层逐层更新，因为在 trie 树上对..
CSP2022-S 游记
Day -? 省流：宇宙射线轰击了出题人的脑子。 蒙了十多分，几乎都错，成小丑了家人们。 膜拜 wyy3332623 。 整了个活： Day -? 出分了，只有82，人均吊打我/kk Day -1 考点在学车，中午提前润去杭州。 宾馆还是可以的，旁边的吃的也挺多，晚饭全机房一起去旁边吃了家川菜。 晚上打牌，打游戏，反正明天上午又没有比赛，直接通宵。 睡前并没有看板子。 Day 1 早上习惯性地六点钟醒过来，人麻了。 早饭自助餐好评，培根里脊配炒饭炫了两盆，还有现做的拌面，水果也出人意料地不错。 上午接着摆，大家激情讨论普及组今年的难度。 然后十二点半左右就有题目了，十分钟口胡阿克，J组真是一年比一年离谱。 中午睡了一会，就过去学车了，感觉考场比去年杭师大的小了不少。 考..
dp优化小结
决策单调性优化dp 很早之前看李煜东蓝书的时候被吓到了，现在来补一下。 前置芝士 决策单调性前提：最优化dp。通俗地讲就是每个状态只能由一个最优地状态转移而来。 决策单调性：状态的最优转移点单调，形式化地说就是。 四边形不等式：有函数 $w(x,y)$，令 $a\le b \le c \le d$，若其满足 $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$ 则称函数 $w(x,y)$ 满足四边形不等式。 决策单调性与四边形不等式的关系：考虑形如 $dp(i)=\min\left\{dp(j)+w(j,i)\right\}$ 的dp，若 $w(j,i)$ 满足四边形不等式，则此dp满足决策单调性。 那么我们怎么通过决策单调性优化dp呢，这有很多种方式。 分治优化决策单调性dp ..
CF200A Cinema 题解
根据题意，若要填的位置已经被占了，那么就按照半径递增的曼哈顿距离圆填入。 我们发现，一个点周围最密集的情况下也只可能有 $k$ 个点，也就是说这个正方形的边长不会超过 $\sqrt k$ 。 所以我们需要找的只有对角线为 $\sqrt{2k}$ 的正方形，用并查集分别维护每一行的联通块的左右边界就可以在 $O(\sqrt{k})$ 的时间复杂度内实现单次查询。 但是当 $m$ 很小的时候，左右边界被填满了，那么就会导致这时候不是一个正方形，需要遍历的行数增多。 但是这时候我们发现中间的一部分已经填满，不需要再填，那么我们也用并查集维护一下，这样可以保证查询的区间一定是一个正方形。 总时间复杂度 $O(k\sqrt{k})$ 。 aclink