zhangxixi的博客

O(n)RMQ四毛子 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132906644 有一种ST表，叫做±1ST表 这种ST表可以在 O(n)O(n)O(n) 的时刻内完成建树 其本质就是分块，大块为整除的ST表，小块的差分数组种类不多，完全可以预处理 现在考虑推广到普通的ST表里 我们发现我们真正关心的是数之间的大小关系。但又要使相邻数之间差恰好为±1 考虑什么东西的差为1。树的欧拉环游序点之间的深度差！ 现在需要数之间的大小关系，也需要树，那么，我们建...

±1 RMQ 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132906556 考虑分块 令 b=log⁡2n2b=\frac{\log_2 n}2b=2log2​n​ ，按 bbb 分块 使用ST表处理大块间的 RMQ 问题 对于一个块内的 RMQ 问题，由于差分数组 2b−12^{b−1}2b−1 种，可以预处理出所有情况下的最值位置 12345678910111213141516171819202122232425262728293031323334v...

笛卡尔树建树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132906457 拿个单调队列维护 最后pop出来的就是它的左儿子 现在还在的，它是他的右儿子 1234567891011int build() { int S[N]; for(int i=1; i<=n; ++i) { while(top && T[S[top]].val < T[i].val) T[i].son[0]=S[top], -...

根号分治与多项式的巧妙结合：GYM-104386G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132866002 使用范围：序列上对于 每种 数的计数问题 考虑对每种数的出现次数进行根号分治 如果出现次数很少，直接平方暴力即可 如果很大考虑任意 (i,j)(i,j)(i,j) ，我们拆一下，再移一下，然后就变成了卷积形式

范德蒙德卷积选数相同的合并 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132863313 对于 ： ∑i(ni)(mi)\sum_{i}\binom{n}{i}\binom{m}{i} i∑​(in​)(im​) 可以通过下面方法变形： ∑i(ni)(mm−i)=(n+mm)=(n+mn)\sum_{i}\binom{n}{i}\binom{m}{m-i}\\=\binom{n+m}{m}=\binom{n+m}{n} i∑​(in​)(m−im​)=(...

善于运用期望可加性+维护增量+DAG上dp：0912T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132857701 CP0912T4 首先看到无环，也就是DAG，显然拓扑 然后看到题目求类似期望和砍边的东西，就要考虑dp 然后有两个Trick 期望具有可加性 对于只有一次的操作，考虑增量 好了，现在我们考虑增量，假设已经知道不操作的答案，现在求恰好操作一次的增量 然后可以手玩一下，发现哪些边对哪些点会有哪些影响。 然后加起来就行了 ...

二进制、数位dp：0912T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132840291 考虑题目转化，二进制下满足 i⊆j,(i+x)⊆(j+y)i\subseteq j,(i+x)\subseteq (j+y)i⊆j,(i+x)⊆(j+y) 这显然是个数位dp形式 考虑枚举每一位与进位， dpk,p1,p2dp_{k,p_1,p_2}dpk,p1​,p2​​ 表示第 k−1k-1k−1 位向第 kkk 位，分别进位 p1,p2p_1,p_2p1​...

判定转状态+序列问题上树形dp：0909T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132796834 考虑没有括号怎么做。 对于这类+*表达式求值问题，正常思考的dp是状态 O(n)O(n)O(n) ，总共为 O(n2)O(n^2)O(n2) 的 但其实可以对于每个dp记录两个值，分别为答案dp，和后面的乘积和g 如果接乘号，就是 [j](dp,g)→[j](dp+g(i−1),gi)[j](dp,g)\to[j](dp+g(i-1),gi)[j]...

生成树、Prufer序列的计数问题：0912T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132839073 看到生成树计数，很容易想到生成树计数 然后发现每个点有度数限制，我们可以先考虑枚举每个点的度数（也可以是Prufer 序列中的出现次数） 假设出现次数为 aaa ，可以得出其生成树方案为 n!∏(ai−1)!\frac{n!}{\prod {(a_i-1)!}}∏(ai​−1)!n!​ 然后后面是个组合数的形式，然后需要推一堆式子 巧拆阶乘...

Cayley 公式 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132832172 nnn 个点的完全图生成树个数为 nn−2n^{n-2}nn−2 如何理解 一个生成树和其prufer序列是唯一对应的 所有生成树和所有Prufer序列形成一个双射关系 而Prufer序列长度为 n−2n-2n−2 ，值域为 nnn ，所以方案为 nn−2n^{n-2}nn−2