zhangxixi的博客

可删除背包（计数类）=＞转移数组进行展开：ABC321F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133219375 https://atcoder.jp/contests/abc321/tasks/abc321_f 还真没见过这个套路，呜呜┭┮﹏┭┮ 首先加就正常加，从后往前 但删的话应该是从前往后减 为什么呢？ 先写一下自己的理解，加要从后往前加是为了防止加多次 减的话为了保证每个被删的数只减一次，应该从前往后。 考虑前 iii 个已经被还原了，那...

交错序列——差分：GZOI2023D2T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133247058 单点修改，全局查询交错序列最大值（ max⁡(∑i(−1)ibi)\max(\sum_i (-1)^ib_i)max(∑i​(−1)ibi​) ）， bbb 为 aaa 的子序列 正常做法是线段树，但对于交错序列问题，有一种更好的方法，就是差分 考虑 ai−aja_i-a_jai​−aj​ ，本质就是 [j+1,i][j+1,i][j+1,i] ...

具有部分单调性的区间个数计数问题——考虑分治：GZOI2023Day1T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133218885 询问有多少区间满足 Sum×Len≤Max2Sum\times Len\le Max^2Sum×Len≤Max2 发现在 MaxMaxMax 定的情况下，显然满足单调性 对于此类题目，可以考虑分治处理 对于当前分治区间，我们采用的分治策略是左右独立算+计算跨区间 显然必然是一段后缀加一段前缀。 先枚举左端点，然后根据上...

点分治维护dp+连通块上新型dp思路+乘积方面进行根号dp：0922T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133217931 首先连通块，所以点分治肯定是 Trick1 钦定选根的连通块dp 对于钦定选根的连通块dp，有一种常见思路 先对原树求其dfn序，按dfn序 倒序 求解 具体的，对于当前点 iii （注意这里都是指dfn序），我们可以钦定 iii 是否选 如果 iii 选，就由 i+1i+1i+1 ，也就是 iii 的第一个儿子转移过来...

二进制位运算相关的计数问题——巧用高维前缀和：0922T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133183403 http://cplusoj.com/d/senior/p/SS230922B 在 https://blog.csdn.net/zhangtingxiqwq/article/details/133176573 当中，我们大致对题目进行了转化。 对于询问 kkk ，我们现在要求所有 a(i,j)a(i,j)a(i,j) 的异或和，满足 ...

Lucas在与位运算有关的组合数中的应用 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133176573 求 (nm) mod 2\binom{n}{m}\bmod 2(mn​)mod2 根据 Lucas，有 (n mod 2m mod 2)(n/2m/2)\binom{n\bmod 2}{m\bmod 2}\binom{n/2}{m/2}(mmod2nmod2​)(m/2n/2​) 也就是 (n&1m&1)(n>>1m>...

线段并交问题——抓住包含关系 / 转移贡献用端点加减表示 ： 0922T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133175632 http://cplusoj.com/d/senior/p/SS230922C 首先有个贪心，按长度从大往小选，是错的 然后有个dp，按左端点排完后选连续段，也是错的 但把上面两个结合起来，还是错的 然后此时错的有个共性，就是存在区间包含关系 然后我们把区间包含关系去掉，另外统计贡献，那样是对的 只不过超时而已 然后发...

树哈希与换根dp：CF763D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133148959 采用的树哈希函数是： dpx=wx×∑y∈xdpy2+wx2\Large dp_x=w_x\times \sum_{y\in x}dp_y^2+w_x^2 dpx​=wx​×y∈x∑​dpy2​+wx2​ 发现从 xxx 到 yyy 时只有 xxx 与 yyy 的哈希值会变化，分别维护即可 12345678910111213141516171819202122...

一个适合换根树哈希函数 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133146153 dpx=wx×∑y∈xdpy2+wx2\Large dp_x=w_x\times \sum_{y\in x}dp_y^2+w_x^2 dpx​=wx​×y∈x∑​dpy2​+wx2​ 这个方法适用于对整棵树统计每个节点的哈希值，也适合换根（因为只和他的儿子节点集合有关） 当然，写双哈希是最稳妥的

与树上边权、连通块、二分块相关的问题（抓住各连通块之间的联系，考虑增量）：CF444E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133138502 https://www.luogu.com.cn/problem/CF444E 首先肯定二分 然后是棵树，所以考虑按顺序枚举边权 然后肯定会有连通块和并查集 考虑现在场上有多个连通块，我们只保留大于 midmidmid 的边 则每个连通块都必须往外连边 一个很朴素的思路是判定每个连通块外面是否够 ∑xi&g...