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}$ 的正方形，用并查集分别维护每一行的联通块的左右边…
CF VP 记录
刷了蛮久 CF 了，一直忘记写记录，现在想起来就写一下。 CF 1697 (2022.7.28) A,B 无意义水题。 C 把操作等价于 $b$ 的移动，只能在 $a$ 中向左移，在 $c$ 中向右移。 把 $a$，$c$ 提出来之后看对应的两个 $b$ 之间有没有不能跨过得即可。 D…
7月26日闲话
上午模拟赛怒切倒数，赚了 wyy 30块。 晚上大家都要狗卷，单排 VP 。 捏妈的，差点 2100 冲不出来了。 多索雷斯复刻了，夏活还会远吗。
7月20日闲话
学习了一些底层。 起因是这道题，使用了 set 中的一些性质。 set::find **参数：**该函数接受一个强制性参数element ，该元素指定要在集合容器中搜索的元素。 **返回值：**该函数返回一个迭代器，该迭代器指向在集合容器中搜索的元素。如果找不到该元素，则迭代器将指向集合中…
7月19日闲话
上午打模拟赛，保龄了。什么时候才能不挂分？什么时候才能不挂分？什么时候才能不挂分？ 快进到 NOIP 也保龄 /hx 。 虽然没有大样例，@wyy332623 依旧是阿克神，吊打我。 下午晚上 VP 了两场，调 E 调到崩溃。 晚上扫雷，赌狗不得 house 。
CF407C Curious Array 题解
前言 优秀的高阶差分/前缀和练习题。 Solution 思路 题意很清晰，不加以赘述。 注意到区间修改，但是我们发现修改的不同，因此设法将其转化为相同的值。 经过打表或手膜等一系列方式，我们发现修改值之间存在一些美妙的关系。 考虑差分。 $k=1$ 时 一次差分后的差分序列…
7月15日闲话
一如既往的摆。 今天是星期五，我想吃疯狂星期四，但是绍一方圆四公里没有 KFC 。 但是有金拱门，最近疯狂送福利，4个人去白嫖了 15 个鸡块和三杯雷碧，人均二十出头。 晚上看着长长的题单陷入了沉思，决定开摆。 开了一场 VP ，第一次 div2 场切了 E ，非常兴奋。 赛后一看， …
7月14日闲话
摆烂。 率性哥 ldz 教授率性技巧。 晚上开了一场 div.2 ，差点 1700 的 D 都打不出来了。 差不多退役得了 /lh 。
7月13日闲话
保龄。 upd：蹭了一顿饭。
CF746F Music in Car 题解
无内鬼，来点主席树做法。 其实是因为不会 stl。 Solution 看这个连续区间加上，区间长度不限制，还有 $t$ 的单调性，考虑双指针。 那么复杂度瓶颈就在如何快速计算区间中前 $w$ 大的数的时间的一半。 区间前 $k$ 大，考虑主席树。 其实就是经典区间第 $k$ 大的变种，实…
组合数学学习笔记
数学还是太菜了 \kk 。 组合数和排列数 定义 高中数学选修三内容。 定义排列数 $A_n^m$ 为从 $n$ 个不重复的元素中选 $m$ 个按一定顺序排列的方案数。 根据乘法原理易得 $$ A_n^m=n\times (n-1)\times … \times(n-m+1)=\frac…
P6076 [JSOI2015]染色问题 题解
个人认为是道很好的组合加容斥练习题。 Solution 考虑将行，列，颜色的限制分开处理。 先限制颜色。 令 $f(i)$ 为只使用 $i$ 种颜色，满足行列限制的方案数， $$ ans=\sum\limits_{i=0}^c\dbinom{c}{i}(-1)^{c-i}f(i) $$ …
P7044 「MCOI-03」括号 题解
很有意思的组合计数加容斥。 Solution $K=0$ 就是经典括号匹配问题，开个栈模拟一下即可。 $K=1$ 显然可以 $O(n^2)$ 枚举子串，但这样复杂度太高。 考虑拆开找贡献，对于下标为 $i$ 的左括号，设它匹配的右括号下标为 $j$ (特别的，没有匹配时 $j=…
P3380 【模板】二逼平衡树（树套树）题解
萌新怒码4k ，搞出来一份不开O2就会T的代码。 只会 fhq-treap ，所以就来了一发 线段树套 fhq-treap。 也就调了一个小时 一些注意点 调用 fhq-treap 时 root 要传址。 寻找排名为 k 的数的时候二分的 check 要 queryrk(k+1) ，因为…
多项式入门
前言 这个傻狗啥都不会还敢来学多项式。 虽然这好像连入门都不算（（（ 背板！！！背板！！！ 前置的一些定义 点值表示法：将 $n+1$ 个不同的值带入到 $n$ 次多项式中形成 $n+1$ 个点的坐标以代表唯一多项式，支持 $O(n)$ 计算卷积。 单位根：复数意义下 $x^{n}=1$…
点分治学习笔记
定义 点分治，顾名思义，就是通过基于点的分治的一种算法。 通常用于处理树上问题，如树上所有路径统计。 我们设一次操作的时间复杂度为 $O(1)$ ，那么一次点分治复杂度为 $O(n \log n)$ 。 具体流程 操作->分治->操作……（不知道怎么讲） 点分治的核心主要在于高…
CF1661D Progressions Covering 题解
link 简化题意 给定一个长度为 $n$ 的数组 $A$ ，和一种操作。 每次操作选定长度为 $k$ 的区间 $[L,R]$ , 将 $A_L-1$，$A_{L+1}-2$ …… $A_R-k$ 。 求使 $A$ 中所有元素小于等于0所需的最小操作个数。 Sulution 一个显然的贪心…
P5289 皮配 题解
（注 ：第一次打这种超出目前能力的 dp ，调了四个晚上。 简化题意： 有四位导师，他们被两两一组分成了红 / 蓝阵营，另外两两一组分成了鸭 / R 派系 有 $n$ 所**学校**，来自 $c$ 个**城市**，第 $i$ 个学校有 $s_i$ 名选手。 同一所学校的…
欧拉函数小结
定义 $\varphi(x)$ 指对于 $\forall i\in [1,x]$ ，满足 $\gcd(i,x)=1$ 的 $i$ 的个数。 也就是小于等于 $x$ 的正整数中与其互质的数的个数。 基本推论 $\varphi(x)=x-1\quad(x\in \mathbb{P})$ $ \b…
P2572 [SCOI2010]序列操作 题解
线段树全家桶，还是挺考验码力的。 注意点： 三种 tag 的覆盖关系（隔壁调了半年） push_up 和 push_down 的更新细节 query2 的去最值细节（我举得我的方法蛮好的）。 总之坑点还是蛮多的。 code #include<bits/stdc++.h> …
模拟退火学习笔记
模拟退火，RP检测器，玄学算法，yyds。 看什么学习笔记，当然是看日报了。 过程 就是模拟冶金学的退火过程，乱搞，具体理论的证明我也不是很懂。 流程图(自己懂就好)： 优化/乱搞 温度T的初始值设置问题。 温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温…
差分约束学习笔记
给定 $n$ 个形如 $a-b≤c$ 的式子，求一组解或求两个变量间的最值 转化为图论问题跑最短/长路即可。 例：P3275 [SCOI2011]糖果 。 简化题意：给定一串约束条件，求所有元素的最小值。 稍微转换一下，就是使两个元素差值尽可能小。 例如 $x_1+c≤x_2$…
牛客提高第七场T2 武义寺 题解
题意简述 对于一个排列 ${p= \{ 1,2,...,n\}}p={1,2,...,n}$，记 $\text{val}(p)$ 等于最小的 $i$ 满足 ${i}> a_ii>a$ ，如不存在则 $\text{val}(p)=n+1$ 。求 $\text{val}(p)$ …
NOIP 2021 游记
$\mathrm{Day} -9$ 打模拟赛 ： $A$ 题不会啊，dp 真难。 $B$ 题按板子打完部分分之后开始乱搞，想着把每个不同的字串拿出来搞一下再取和。没想到再来一次 dp 很可惜 (话说为什么有两道dp) 。 $C$ 题暴力，啥是数论分块？ $D$ 题暴力，啥是重心？重心咋…
FHQ- Treap学习笔记
FHQ-Treap 与Treap都保证在第一关键字有序的情况下，维护第二关键字以达到平衡的目的。 但是Treap用的是旋转，FHQ-Treap 用的是分裂和合并。 FHQ-Treap 与Treap不同的地方： 优美的分裂和合并。 非旋。 支持区间修改 FHQ-Treap 与Treap相…
乘法逆元小结
什么是乘法逆元 当有 $ a*x ≡ 1 \pmod {p} $ 时，则 $a$是模 $ p$ 意义下的乘法逆元。 费马小定理求逆元 费马小定理 $a ≡ a^{p-1} \pmod {p} $ 所以 $a^{p-2} ≡ 1 \pmod {p} $ 求 $a^{p-2} \bmod…
CSP-S 2021 游记
2021.10.22 来到杭州，然后打印乱七八糟的东西，吃了兰州拉面 ？？？ 晚上睡不着。 2021.10.23 早上 $5:00$ 就起来划水，上午普及组打铁。 $2h$ 打完四道暴力，然后开始扫雷（ 。 预估得分：$355$ ； 中午吃完饭就快一点半了，很困。 下午更困了屮。 …
主席树学习笔记
权值线段树 就是指线段树的叶子节点保存的是当前值的个数。 权值线段树一般支持以下三个操作： insert erase/remove query 贴一个alphadalao的题解。 主席树 主席树，也叫做可持久化线段树，准确来说，应该叫做可持久化权值线段树，因为其中的每一颗树都是一颗权值…
P7746 PLAĆE 题解
题目大意 给定一棵初始权值已知的树，每次操作: 对某个节点子树上的所有节点加上 $ x $ 。 查询某个节点的权值。 具体思路 1.暴力(112 pts) 对于每次修改操作，我们把修改值储存下来，然后每次询问操作我们历遍所求点的祖先，计算总和。 这看起来是 $\mathcal{O}( …
树状数组学习笔记
位运算是补码进行运算的 因此可以解释负数进行位运算时的奇妙现象 补码：正数的补码就是其本身 负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1) E:原码：10000001； 补码：01111111. lowbit：lowbit这个函数的功能就…
P7635 [COCI2010-2011#5] DVONIZ の 题解
题目 这道题的思路很暴力，通过优化的枚举就可以得到一个很不错的时间复杂度，只是坑点有点多，所有坑点我都会在接下来的文字中叙述。 前置芝士：二分答案(不会的先去学)。 第一种，暴力枚举 (最高54分) 我们可以将每一个数元素所对应的 $K$ 从最大值开始向前枚举，这种算法可以得到较高的分数，…
P7542 [COCI2009-2010#1] MALI 题解
基本思路：贪心，每次将 $A$ 中的数从大到小与 $B$ 中的数从小到大一一对应组合，即 $A$ 中最大的数与 $B$ 中最小的数组合， $A$ 中第二小的数与 $B$ 中第二大的数组和，其中最大的数对即为所求。 像这样: 非常简单易懂的贪心。 但是俗话说得好，贪心不难，但是难的是证明。 …
P7541 DOBRA の题解
题意：给定一个只包含下划线和大写字母的字符串，将下划线全部换成大写字母，问有多少种填法能使这个字符串不包含 3 个及以上连续的元音字母、3 个及以上连续的辅音字母，并且至少包含一个大写字母 L。 这道题可以用深搜做的，从左到右进行遍历，遇到一个下划线搜一次并进行讨论，由于最多只有十个下划线，因此…
P6607 [Code+#7]蚂蚁 の 题解
蒟蒻第一篇题解 传送门 P6607 [Code+#7]蚂蚁 首先，由于所有蚂蚁始终在运动且不会陷入死循环，因此所有蚂蚁都能爬到终点(也就是说题目的-1是拿来误导的) 接下来考虑穿过的情况,由于相遇会立刻反向，点与点之间的相对位置不变，可以看作存在一种特殊的”传递”(虽然时间不同所对的点也不同)…