$\tt 2022-3-31$ 逃了一天模拟赛，自己写题。 话说 $\tt Hater$ 的题好难呀，一天只搞了 $4$ 题。 然后学了一个 bitset 关于字符串匹配的应用 | Legendgod’s Blog。 感觉自己图论和数据结构都不是很行，就已经拖后腿了。 之前写的 $\tt ds$ 浅谈都没有更新了。 哦对了，还有一个 $\tt \large \text{分块}$ 我不会啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。 $\tt 2022-3-30$ 还是考试，别人都 $\tt AK$ 了，就我只会 $\tt T1$。 $\tt T2$ 和正解一样，没有调出来，$\tt T3$ 本质上可以建图之后进行 $\tt Dp$。 提一下 $\tt T3$：# 2727. 「JOI 2015 Final」舞会 发现本质上就是将 $3$ 个数合并成一个数，而且对于最终答案我们显然可以二分变成 $0/1$ 的情况。 之后我们考虑合并的话直接重构树，然后从下到上进行 $\tt Dp$ 设 $f ...

emmm 这里大概会记录一下 $vp$ 的场次和一些想法吧。 Codeforces Round #691 (Div. 2) 反正我是心态崩了，就是 $A, B$ 其中 $A$ 直接猜结论，然后 $B$ 是一个找规律的题目，因为画出来之后可以发现矩阵是规则的。对于 $C$ 题直接秒杀了不多说了。 $D$ 看起来是可撤销贪心实际上是 $\tt Dp$。 E 题解 F 题解 总结一下就是说还是要从多方面进行思考，对于看起来比较复杂的题目是否有简化的方案。同时不要放过任何可能的突破点。 Codeforces Round #769 (Div. 2) 感觉还好前 $4$ 题写得有点慢，然后 $5, 6$ 来不及写了。 感觉上第 $4$ 题可能我的做法比较奇怪。 放一个最后两题的题解 CF1632E2 题解 | Legendgod’s Blog Educational Codeforces Round 123 (Rated for Div. 2) - Codeforces 属于是口胡了。 前面的题目比较简单，最后一题考的东西还是挺多的，需要多思考组合意义。 CF1644F 题解 | ...

加乘原理对于给定的集合 $S$ 对于其中满足某一性质 $P$ 的元素 $x$ 求和 $f(x)$ 即求出： $$\sum_{x \in S} f(x) [P(x)]$$ 将 $S$ 称为组合类，$x$ 称为组合对象，$f$ 称为权值函数。 $\color{blue}\Delta$ 构造双射 不同的两个组合类中的组合对象可以一一对应，这样对于两个组合类进行计数是等价的。 另一种情况是同一组合类中的组合对象可以建立对应关系 ( 或多个为一组 )，我们只需要对于每组中的一个进行计数，再乘上组的大小。 $\color{blue}\Delta$ 加法原理 对 $S$ 中的所有元素求和 $f(x)$ 等价于将 $S$ 划分成若干个集合 $S_i$ 分别求和再相加： $$\sum_{x \in S} f(x) = \sum_{i = 1} ^ m (\sum_{x \in S_i} f(x))$$ $\color{blue}\Delta$ 乘法原理 将 $S$ 拆分成 $S_i$ 的笛卡尔积， $S$ 中元素的权值 $f(x)$ 等于其拆分出的各 $f_i(x_ ...

据说图论我会的东西相对少一点，我们先写图论。 二分图概念和判定定义：对于无向图 $G = (V, E)$ 存在将 $V$ 划分成两个不相交子集 $A, B$ 满足集合内部没有连边，则 $G$ 为二分图。 定理：图 $G = (V, E)$ 是二分图，当且仅当 $G$ 中没有奇环。 推论：二分图 $G = (V, E)$ 的任意子图为二分图。 推论：二分图 $G = (V, E)$ 是二分图，当且仅当其任意连通子图是二分图。 封锁阳光大学 - 洛谷 给定一张图，求是否存在点集 $V$ 满足任意一条边只有一个顶点在 $V$ 中。 本质上就是分成两个集合，使得集合内部没有边，就是二分图。 直接染色之后取点数小的即可。 [NOIP2010 提高组] 关押罪犯 - 洛谷 给定一张无向带权图，将图分成两个集合，使得集合内部边权的最大值最小。 考虑权值大的肯定尽量是两个集合之间的边，考虑二分答案，之后找到不合法的边钦定一定要分为两个集合，设二分的答案为 $X$ 或者说建立图 $G = (V, E), E = { w > X ...

还是接着分块，之前写太多了，$\tt marktext$ 炸了。 Legendgod’s Blog $\color{blue}\Delta$ 带插入全序集维护 题意：维护一个序列，支持（在指定元素后面）插入元素，询问两个元素的先后顺序。 平衡树 可以暴力维护，复杂度是 $O(\log n) - O(\log n)$ 。 或者说对于每个平衡树的每个节点钦定一个权值，每次插入的时候根据这样钦定的顺序每个点就有了一个权值，这样我们可以 $O(1)$ 比较。 但是这样对于深度的要求很高，我们用替罪羊树就行了 $O(\log n) - O(1)$。 块状链表 考虑上面这个 $O(1)$ 很妙能不能加强，我们还是考虑钦定权值，进行分块每块在 $[\log n, 2\log n]$ 的大小之间。 比较元素的时候优先比较块的位置，如果在同一块内在再比较块内的位置。 块内外都用钦定权值维护，但是块的元素数量比较多，如果一直搞链就寄了，所以需要使用平衡树维护，总共有 $\frac{n}{\log n}$ 个块，每次插入复杂度是 $O(\log n)$ 的，所以是 $O(n)$ 的。 考虑钦定块 ...

Legendgod’s Blog 分块 一点都不会，从零开始学习。 区间分块：对于整个序列分成 $ \frac{n} {B} $ 块，每块的大小为 $ B $。 值域分块：同上，只是将值域分块了 询问分块，有的时候修改很少考虑记录修改对于之后每次询问暴力操作。 分块主要是维护信息不能高效合并的情况。 之后参考：command_block 的博客 进行学习。 题意：【模板】线段树 1 - 洛谷 区间加，区间求和。 考虑序列分块。 询问：每块记录和，散块暴力询问。 修改：整块打标记，散块暴力修改。 可以暴力散块的时候清空整个散块的标记，或者直接标记永久化。 题意：教主的魔法 - 洛谷区间加，查询区间 $\ge k$ 的数个数。 首先对于每块内部进行排序。 询问：二分位置，散块暴力。$O(\frac{n}{B}\log B + B)$。 修改：整块打标记，散块暴力归并排序。 $O(\frac{n}{B} + B)$。 取 $B = \sqrt{n \log n}$ 最优。 考虑上面的部分复杂度要大一点，所以考虑让上面部分平衡，可以根据均值不等式 ...

Legendgod’s Blog 树状数组一个函数 $\tt lowbit(x) = x \text{&} (-x)$ 表示 $x$ 的最低二进制位的位置。 可以维护区间加区间和，常数比较小。 $O(n)$ 建树，考虑对于节点 $x$ 向上更新 $x + \tt lowbit(x)$ 即可。 查询第 $K$ 小，就是经典二进制上二分，假设元素 $i$ 出现了 $a_i$ 次。 123456789int Kth(int k) { int cnt = 0, ret = 0; for(int i = log2(n); ~ i; -- i) { ret += (1 << i); if(ret >= n || cnt + t[ret] >= K) ret -= (1 << i); else cnt += ret; } return ret + 1;} 时间戳优化，听起来听高级的，其实就是打标记看当前时刻有没有经过，经过的时候 ...

Legendgod’s Blog 一下子没有什么精神，开一个博客来总结一下，我曾经会过什么东西，同时就当做复习了。 预计会写稍微多一点东西，尽量按照 $\tt oi-wiki$ 的结构和自己的理解来。 如果说当做课件的话可以用下面的部分： ‘ 队列常常就是用 $\tt queue, priority_queue, deque$，分别是普通队列，优先队列，双端队列。 优化 $\tt Dp$，比如说维护一个最大值，就是考虑如果说当前值比之后加入位置的小，显然当前的位置就不用了。每次我们取出队头的最大值即可。 优化斜率 $\tt Dp$，常常说是否要取等的情况，明显这个队列是维护斜率单调的，至于取等的情况，我们考虑斜率相同但是截距不同的情况，所以是需要删除前面的斜率相同的位置。 维护最短路，这个比较显然就不说了。 记住这个东西是先进先出就可以了。 栈就只有一个 $\tt stack$。 维护最值，还是考虑维护最大值，我们对比一下队列的维护方式。队列可以加入当前不是最大值但是之后最大值删掉之后可能产生贡献的情况，但是栈如果发现不能加入之后就不会再加入了，所以说队列是可以维护 ...