zhangxixi的博客

异或前后 1 的个数的奇偶性 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132915268 一个常见套路 考虑异或操作，其前后1的个数奇偶性不会发生改变 因为每位要么没1，要么保留1个1，要么同时消掉2个1 这个结论可以方便我们构造fwt的转移系数

可能的模拟网络流部分思路整理（CF1408H） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093428 https://www.luogu.com.cn/problem/CF1408H 先转换 模拟网络流，所以要么割最上面一层，要么割最下面一层。 对于最上一层，肯定是左边连续+右边连续。 考虑枚举左边连续，对应到某些颜色节点，又对应到某些右边节点。 对右边节点建棵线段树，由于左边的点已经确定，先假设下面的和右边的点全部割掉。 右边的点全部割掉，所以...

哈夫曼树/合并果子中具有的单调性：牛客65157/F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132912243 正常哈夫曼树实现是用优先队列的 但是我们发现新建的节点大小满足单调性 那么我们就可以直接拿个队列来维护 但是一开始的节点和新的节点会混在一起 那就拿两个队列维护呗

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​...