zhangxixi的博客

二分套网络流：ABC320G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132927159 首先肯定先枚举数字 然后考虑二分答案 每个字符串向它合法的位置连边 然后易发现每个点出度最多为 nnn ，不然没意义 所以最多 O(n2)O(n^2)O(n2) 条边 然后跑网络流，看能不能流完，也就是能不能匹配成功即可 123456789101112131415161718192021222324252627282930313233343536373839404...

atcoder库中的网络流用法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132643984 头文件： 12#include<atcoder/all>using namespace atcoder; 定义： 1mf_graph<int>G(N); //N为边数 连边： 1G.add_edge(u,v,w); //u->v容量为w 最大流： 1int maxflow = G.flow(S,T,1e9); //从S流向T，初始...

FWT小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132922605 核心思想：把 a,ba,ba,b 化成 fwt(a),fwt(b)fwt(a),fwt(b)fwt(a),fwt(b) ，相乘后再化为 aaa 化的过程用的是分治 所以和FFT其实一模一样 OR / AND 卷积 不需要什么技巧，暴力分治转移即可 每次分治下去，相当于位数减一 注意合并过程中我们是计算对应位的贡献 因为其它位的贡献我们在分治下去时已经计算了 后面区间其他数贡献到前面...

FWT笔记存档 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132922560

异或前后 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], -...