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
CF VP 记录
刷了蛮久 CF 了，一直忘记写记录，现在想起来就写一下。 CF 1697 (2022.7.28) A,B 无意义水题。 C 把操作等价于 $b$ 的移动，只能在 $a$ 中向左移，在 $c$ 中向右移。 把 $a$，$c$ 提出来之后看对应的两个 $b$ 之间有没有不能跨过得即可。 D 操作 1 的 26 已经提示了每种字母只能用一次操作 1 。 那么一个很 naive 的想法就是对于每种字母求出他们最后的位置，每次扩展的时候暴力询问，但这样是 27000 次的。 然后又发现这东西可以二分，那么就做完了。 E (赛后) dp 还是太菜了 /kk 根据题意，两个点可以同色当且仅当他们互为最近点对。 那么我们可以把图拆成数个联通块，连通块中两两曼哈顿距离相等，连通块中的点要么..
7月26日闲话
上午模拟赛怒切倒数，赚了 wyy 30块。 晚上大家都要狗卷，单排 VP 。 捏妈的，差点 2100 冲不出来了。 多索雷斯复刻了，夏活还会远吗。
7月20日闲话
学习了一些底层。 起因是这道题，使用了 set 中的一些性质。 set::find **参数：**该函数接受一个强制性参数element ，该元素指定要在集合容器中搜索的元素。 **返回值：**该函数返回一个迭代器，该迭代器指向在集合容器中搜索的元素。如果找不到该元素，则迭代器将指向集合中最后一个元素之后的位置 我之前没想过这玩意能求区间的包含关系。 但这道题里面，只需要重定义一下 < ，find 一下就能找到包含的区间。 struct node{ int l,r; bool operator <(const node &x)const{ return r<x.l; } }; 原因是这样的： set 中判断元素是否相等： 当 A<B和 B<A 都为假时..
7月19日闲话
上午打模拟赛，保龄了。什么时候才能不挂分？什么时候才能不挂分？什么时候才能不挂分？ 快进到 NOIP 也保龄 /hx 。 虽然没有大样例，@wyy332623 依旧是阿克神，吊打我。 下午晚上 VP 了两场，调 E 调到崩溃。 晚上扫雷，赌狗不得 house 。
CF407C Curious Array 题解
前言 优秀的高阶差分/前缀和练习题。 Solution 思路 题意很清晰，不加以赘述。 注意到区间修改，但是我们发现修改的不同，因此设法将其转化为相同的值。 经过打表或手膜等一系列方式，我们发现修改值之间存在一些美妙的关系。 考虑差分。 $k=1$ 时 一次差分后的差分序列的值均为 1 ，可以配合数据结构修改。 但更好的方法是二次差分，转化为形如 ${1,0,0,0… ,-1}$ 单点修改的形式。 $k=2$ 时 经过一次差分我们发现其转化为了上述 $k=1$ 的形式。 直接三次差分。 $k = x$ 时 我们从 $k$ 较小的情况推广，容易发现我们修改的应该是 $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$ 大的变种，实现起来并不是特别困难。 时间复杂度 $O(n\log n)$ 。 Code //#pragma GCC optimize(3) #include<bits/stdc++.h> #define N 500005 using namespace std; int read(){ int x=0,w=1; char ch=getchar(); while(ch>'9'||ch<..
组合数学学习笔记
数学还是太菜了 \kk 。 组合数和排列数 定义 高中数学选修三内容。 定义排列数 $A_n^m$ 为从 $n$ 个不重复的元素中选 $m$ 个按一定顺序排列的方案数。 根据乘法原理易得 $$ A_n^m=n\times (n-1)\times … \times(n-m+1)=\frac{n!}{(n-m)!} $$ 定义排列数 $C_n^m$ 为从 $n$ 个不重复的元素中选 $m$ 个的方案数。 由排列数公式易得 $$ C_n^m=\dbinom{n}{m}=\frac{n!}{m!(n-m)!} $$ 也就输排列数除去 $n!$ ，简单易懂。 推广 二项式定理 $$ (x+y)^n=\sum\limits_{i=0}^n \dbinom{n}{i}x^iy^{n-i} $$ ..
P6076 [JSOI2015]染色问题 题解
个人认为是道很好的组合加容斥练习题。 Solution 考虑将行，列，颜色的限制分开处理。 先限制颜色。 令 $f(i)$ 为只使用 $i$ 种颜色，满足行列限制的方案数， $$ ans=\sum\limits_{i=0}^c\dbinom{c}{i}(-1)^{c-i}f(i) $$ 再限制列。 令 $g(i,j)$ 为只是用 $i$ 种颜色，只填 $j$ 列的方案数。 $$ f(i)=\sum\limits_{j=0}^m\dbinom{m}{j}(-1)^{c-j}g(i,j) $$ 最后 $$ g(i,j)=((i+1)^j-1)^n $$ 带入求解即可，时间复杂度 $O(mc\log n)$ 。 Code #include<bits/stdc++.h> #defi..
P7044 「MCOI-03」括号 题解
很有意思的组合计数加容斥。 Solution $K=0$ 就是经典括号匹配问题，开个栈模拟一下即可。 $K=1$ 显然可以 $O(n^2)$ 枚举子串，但这样复杂度太高。 考虑拆开找贡献，对于下标为 $i$ 的左括号，设它匹配的右括号下标为 $j$ (特别的，没有匹配时 $j=n+1$ )。 那么易证，这个左括号对所有 $i\le r＜ j$ 且 $1\le l\le i$ 的区间都有 1 的贡献，总贡献即为 $i\times(j-i)$ 。 右括号同理，因此可以 $O(n)$ 计算。 $K>1$ 套用 $K=1$ 时的计算方法，找贡献。 我们发现对于一个 $K$ 级偏值的字符串，只会对包含它的母串的 $K+1$ 级偏值造成贡献。 还是假设以下一个下标为 $i$ 的左括号，..
P3380 【模板】二逼平衡树（树套树）题解
萌新怒码4k ，搞出来一份不开O2就会T的代码。 只会 fhq-treap ，所以就来了一发 线段树套 fhq-treap。 也就调了一个小时 一些注意点 调用 fhq-treap 时 root 要传址。 寻找排名为 k 的数的时候二分的 check 要 queryrk(k+1) ，因为 queryrk() 找的是小于 k 的数，而 check 的要求是小于等于 k 的数。 Code #include<bits/stdc++.h> #define N 100005 #define orz puts("orzwyy332623");//tiaoshi #define ls(p) p<<1 #define rs(p) p<<1|1 using ..
多项式入门
前言 这个傻狗啥都不会还敢来学多项式。 虽然这好像连入门都不算（（（ 背板！！！背板！！！ 前置的一些定义 点值表示法：将 $n+1$ 个不同的值带入到 $n$ 次多项式中形成 $n+1$ 个点的坐标以代表唯一多项式，支持 $O(n)$ 计算卷积。 单位根：复数意义下 $x^{n}=1$ 即为 $n$ 次单位根。(有 $n$ 个) 本原单位根：$e^{i\frac{2\pi}{n}}$ 称为 $n$ 次单位根的本原单位根，记为 $ω_n$ 。 原根：若 $1\le g\le n-1$ 且 $g$ 模 $n$ 的阶为 $\varphi(n)$ ，则称 $g$ 为 $n$ 的原根。 卷积的一般形式： $$ c_i=\sum\limits_{i=j\oplus k}a_jb_k $$ DFT ..
点分治学习笔记
定义 点分治，顾名思义，就是通过基于点的分治的一种算法。 通常用于处理树上问题，如树上所有路径统计。 我们设一次操作的时间复杂度为 $O(1)$ ，那么一次点分治复杂度为 $O(n \log n)$ 。 具体流程 操作->分治->操作……（不知道怎么讲） 点分治的核心主要在于高效的分治，每一次都可以将所求区间大小缩短至 $\dfrac{1}{k}$ 。 因此 $T(n)=k\times T(n/k)$ ，根据主定理，时间复杂度为 $O(n \log n)$ 。 分治的关键在于从在每一次操作的树上寻找重心，易证以重心为根的每颗子树大小不超过 $\dfrac{n}{2}$ ，从而可以有效缩小操作区间，保证正确的复杂度。(其实感性也很好理解的来着) 例题 P3806 【模板】点分治1 ..
CF1661D Progressions Covering 题解
link 简化题意 给定一个长度为 $n$ 的数组 $A$ ，和一种操作。 每次操作选定长度为 $k$ 的区间 $[L,R]$ , 将 $A_L-1$，$A_{L+1}-2$ …… $A_R-k$ 。 求使 $A$ 中所有元素小于等于0所需的最小操作个数。 Sulution 一个显然的贪心思路： 从后往前枚举，对于每个大于等于1的 $A_i$，将区间 $[i-k+1,k]$ 操作 $\left\lfloor\dfrac{A_i}{k}\right\rfloor$ 次。 证明略。 暴力实现是 $O(n^2)$ 的，我们考虑维护这个操作。 因为需要区间修改，单点查询，考虑线段树，但是每次修改的值不一定，考虑转化。 发现每次修改对于区间的差分数组改变一致，于是将原数组转化为差分数组。 那么我们..
P5289 皮配 题解
（注 ：第一次打这种超出目前能力的 dp ，调了四个晚上。 简化题意： 有四位导师，他们被两两一组分成了红 / 蓝阵营，另外两两一组分成了鸭 / R 派系 有 $n$ 所**学校**，来自 $c$ 个**城市**，第 $i$ 个学校有 $s_i$ 名选手。 同一所学校的选手必须选择同一个导师。同一个城市的选手必须选择同一个阵营。同城对派系的选择没有限制。 有 $k$ 所学校的选手有自己讨厌的老师。 求一共有多少种情况，答案对 $998244353$ 取模。 (注：每个学校可以加入自己讨厌的老师的阵营/派系) 50 pts 做法： 设 dp 状态为 $f_{(0/1,i,j,k)}$，表示 dp 到第 $i$ 个学校，选择 蓝(0)/红(1) 阵营，蓝阵营有 $j..
欧拉函数小结
定义 $\varphi(x)$ 指对于 $\forall i\in [1,x]$ ，满足 $\gcd(i,x)=1$ 的 $i$ 的个数。 也就是小于等于 $x$ 的正整数中与其互质的数的个数。 基本推论 $\varphi(x)=x-1\quad(x\in \mathbb{P})$ $ \begin{aligned} \varphi(p^k)& =p^k-p^{k-1} \quad(p\in \mathbb{P},k\in \Z^*) \\ &= p^k(1-\frac{1}{p})\quad(p\in \mathbb{P},k\in \Z^*)\end{aligned}$ 这是因为只有当一个数不包含质数 $p$ ，才可能与 $x$ 互质。而包含质数 $p$ 的数一共有$ p^{k-1} $个，即 ..
P2572 [SCOI2010]序列操作 题解
线段树全家桶，还是挺考验码力的。 注意点： 三种 tag 的覆盖关系（隔壁调了半年） push_up 和 push_down 的更新细节 query2 的去最值细节（我举得我的方法蛮好的）。 总之坑点还是蛮多的。 code #include<bits/stdc++.h> #define N 200005 #define ls(p) p<<1 #define rs(p) p<<1|1 using namespace std; int read(){ int x=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=get..
模拟退火学习笔记
模拟退火，RP检测器，玄学算法，yyds。 看什么学习笔记，当然是看日报了。 过程 就是模拟冶金学的退火过程，乱搞，具体理论的证明我也不是很懂。 流程图(自己懂就好)： 优化/乱搞 温度T的初始值设置问题。 温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。 退火速度问题。 模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
差分约束学习笔记
给定 $n$ 个形如 $a-b≤c$ 的式子，求一组解或求两个变量间的最值 转化为图论问题跑最短/长路即可。 例：P3275 [SCOI2011]糖果 。 简化题意：给定一串约束条件，求所有元素的最小值。 稍微转换一下，就是使两个元素差值尽可能小。 例如 $x_1+c≤x_2$ 如果用最短路去约束，则会取到最小值，所以应该用最长路去维护。 具体原因我也解释不来屮。 又因为题意对每个元素都有大于等于1的约束，所以从超级源点向每个元素的边边权要设为1。 这题就做完了，但是有些些小细节。 #include<bits/stdc++.h> #define N 200005 #define int long long using namespace std; inline in..
牛客提高第七场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)$ 的期望值，答案对 $998244353$ 取模。 题解 令 $k=n+1-i$ ，枚举 $a_i=j$ ，则前 $i-1$ 个数的可行的方案为: $sum_i=$ $\sum \limits_{j=1}^{i-1}(k+1)^{i-1-j} \times k^j$ 大力观察发现是等比数列。 等比数列求和公式： $\sum \limits _{k=0}^{n-1}(x \times a^{k}) = ..
NOIP 2021 游记
$\mathrm{Day} -9$ 打模拟赛 ： $A$ 题不会啊，dp 真难。 $B$ 题按板子打完部分分之后开始乱搞，想着把每个不同的字串拿出来搞一下再取和。没想到再来一次 dp 很可惜 (话说为什么有两道dp) 。 $C$ 题暴力，啥是数论分块？ $D$ 题暴力，啥是重心？重心咋求？ $20 + 70 + 35 + 50 = 175$ 被 wyy332623 和 rouxQ 巨佬吊打。 打 generals：被全机房吊打。 $\mathrm{Day} -8$ 又打模拟赛： $A$ 题二分+特判乱搞，搞过去了，话说二分怎么打。 $B$ 题傻逼dp ，然而赛时还是没有调出来。对自己dp 式子理解有误，tcl。 $C$ 题欧拉序+大力观察，下午补的时候忘了前向星反向历遍心态调炸了..
FHQ- Treap学习笔记
FHQ-Treap 与Treap都保证在第一关键字有序的情况下，维护第二关键字以达到平衡的目的。 但是Treap用的是旋转，FHQ-Treap 用的是分裂和合并。 FHQ-Treap 与Treap不同的地方： 优美的分裂和合并。 非旋。 支持区间修改 FHQ-Treap 与Treap相同的地方： 都保证在第一关键字有序的情况下，维护第二关键字。 本质上都是BST(二叉搜索树)。 注意点 合并时要保证第一棵树的权值小于第二棵树的权值(因为合并操作只比较随机值)(仅指作为平衡树时的操作)。 排名分裂维护的是书的中序遍历。(例题) Code of P3369 【模板】普通平衡树 #include<bits/stdc++.h> #define N 200005 using na..
乘法逆元小结
什么是乘法逆元 当有 $ a*x ≡ 1 \pmod {p} $ 时，则 $a$是模 $ p$ 意义下的乘法逆元。 费马小定理求逆元 费马小定理 $a ≡ a^{p-1} \pmod {p} $ 所以 $a^{p-2} ≡ 1 \pmod {p} $ 求 $a^{p-2} \bmod p$即可。 当且仅当 $p$ 为质数且 $a,p$ 互质时可用。 int ksm(int x,int k){ int sum=1; while(k){ if(k&1) sum=sum*x%p; x=x*x%p; k>>=1; } return sum; } signed main(){ px=read(),p=read(); ans=ksm(x,p-2); return 0; } 扩展欧几..
CSP-S 2021 游记
2021.10.22 来到杭州，然后打印乱七八糟的东西，吃了兰州拉面 ？？？ 晚上睡不着。 2021.10.23 早上 $5:00$ 就起来划水，上午普及组打铁。 $2h$ 打完四道暴力，然后开始扫雷（ 。 预估得分：$355$ ； 中午吃完饭就快一点半了，很困。 下午更困了屮。 $14:00$ 进场，趴着睡了 $20min$ 。 $14:30$ 开考，还是有点混乱，甚至想上大号。 看 $T1$ ，好像可做，$30min$ 打了个离散化 + 三分的做法，过了大样例，然后莫名自信 (垃圾大样例)。 然后看 $T2$ ,看半天不会打，看 $T3 T4$ 好像也不会。 $16:30$ 硬着头皮打 $T2$ 暴力，然后忽然发现 $T3$ 好像可做。 $17:00$ 发现根本想不出来，然后..
主席树学习笔记
权值线段树 就是指线段树的叶子节点保存的是当前值的个数。 权值线段树一般支持以下三个操作： insert erase/remove query 贴一个alphadalao的题解。 主席树 主席树，也叫做可持久化线段树，准确来说，应该叫做可持久化权值线段树，因为其中的每一颗树都是一颗权值线段树。 经典例题：查询区间第k小。 主席树是静态的。 为了实现可持久化，就要保存树的历史版本。最自然的想法当然是每进行一次修改，就新建一颗线段树，这样的空间复杂度显然是不能够接受的。通过观察不难发现，每次进行单点修改，发生变化的只有从叶子节点到根节点这一条链上的节点，换句话说，只有 $logN$ 个节点发生了变化，而其他的节点都可以重用，没有必要新建。 看图非常好理解。 超棒的讲解 然后就是一些实现上..
P7746 PLAĆE 题解
题目大意 给定一棵初始权值已知的树，每次操作: 对某个节点子树上的所有节点加上 $ x $ 。 查询某个节点的权值。 具体思路 1.暴力(112 pts) 对于每次修改操作，我们把修改值储存下来，然后每次询问操作我们历遍所求点的祖先，计算总和。 这看起来是 $\mathcal{O}( m\log n )$ 的正解，但是这仅限于这棵树是平衡的时候。在退化成链的极限条件下会被卡到 $\mathcal{O}( mn )$ ，在 $ 1 \le n , m , \le 5 \times 10^5 $ 的数据范围下会T掉。 核心代码： int a=read(); int x=tree[a].fa,w=tree[a].num; while(1){ if(x==0) break; w+=tag[x]; ..
树状数组学习笔记
位运算是补码进行运算的 因此可以解释负数进行位运算时的奇妙现象 补码：正数的补码就是其本身 负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1) E:原码：10000001； 补码：01111111. lowbit：lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位1 E:lowbit(10001)=1,lowbit(10010)=10。 lowbit的实现方式： 1. int lowbit(x) { return x - (x & (x - 1)); } 2.(推荐) int lowbit(x) { return x & -x; } E:lowbit(1000011)=100011..
P7635 [COCI2010-2011#5] DVONIZ の 题解
题目 这道题的思路很暴力，通过优化的枚举就可以得到一个很不错的时间复杂度，只是坑点有点多，所有坑点我都会在接下来的文字中叙述。 前置芝士：二分答案(不会的先去学)。 第一种，暴力枚举 (最高54分) 我们可以将每一个数元素所对应的 $K$ 从最大值开始向前枚举，这种算法可以得到较高的分数，但肯定不是正解，但如果思路错了分数甚至没有暴力高。 #include<bits/stdc++.h> using namespace std; long long n,s,x,sum[100005]; bool work(int i,int mid){ if((sum[i+mid-1]-sum[i-1]>s)||(sum[i+mid*2-1]-sum[i+mid-1]>s)) return ..
P7542 [COCI2009-2010#1] MALI 题解
基本思路：贪心，每次将 $A$ 中的数从大到小与 $B$ 中的数从小到大一一对应组合，即 $A$ 中最大的数与 $B$ 中最小的数组合， $A$ 中第二小的数与 $B$ 中第二大的数组和，其中最大的数对即为所求。 像这样: 非常简单易懂的贪心。 但是俗话说得好，贪心不难，但是难的是证明。 非常随意的证明： 设数对 $(A_1,B_1)$ 是最大数对，下一个数对为 $(A_2,B_2)$ 。 根据我们之前的贪心思路，可知 $A_1B_2$ 而要使最大数对的最大值减小，要么将 $A_1$ 与 $B$ 中更小的数组合，要么将 $B_1$ 与 $A$ 中更小的数组合,以前一种方法为例，新的两个数对为 $(A_2,B_1)$ 和 $(A_1,B_2)$ 很容易发现 $A_2+B_1>A_1+B_..
P7541 DOBRA の题解
题意：给定一个只包含下划线和大写字母的字符串，将下划线全部换成大写字母，问有多少种填法能使这个字符串不包含 3 个及以上连续的元音字母、3 个及以上连续的辅音字母，并且至少包含一个大写字母 L。 这道题可以用深搜做的，从左到右进行遍历，遇到一个下划线搜一次并进行讨论，由于最多只有十个下划线，因此并不会TLE。 附代码： #include<bits/stdc++.h> using namespace std; long long dfs(int n); string s; int a[105],lens,l,x; int main(){ cin>>s; lens=s.size();//字符串长度 for(int i=0;i<lens;i++){ if(s[i]=='..
P6607 [Code+#7]蚂蚁 の 题解
蒟蒻第一篇题解 传送门 P6607 [Code+#7]蚂蚁 首先，由于所有蚂蚁始终在运动且不会陷入死循环，因此所有蚂蚁都能爬到终点(也就是说题目的-1是拿来误导的) 接下来考虑穿过的情况,由于相遇会立刻反向，点与点之间的相对位置不变，可以看作存在一种特殊的”传递”(虽然时间不同所对的点也不同) example:(图丑不要在意) 因此两点相遇前后一秒也可以看作两点相互穿过 综合起来可以发现，假如有一点向东(或西)走，且距离东(或西)x个单位，那么x个单位后必有一个点到达东边(或西边)端点。因此各个点的到达时间都可以确定，只需依次对应输出即可。 那么怎么对应呢？以第一个点为例，若向东走，则所需时间即为p[i]。若向西走，没有另一个向东走的点，则为l-p[i]；有点向东走的话，t即为p[向东走的第一个..