差分约束学习笔记
给定 $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$ 从最大值开始向前枚举，这种算法可以得到较高的分数，…