zhangxixi的博客

数据结构中的判定转状态+扫描线：P1502 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133124669 https://www.luogu.com.cn/problem/P1502 发现正常扫描线很难维护恰好大小为 WWW 的区间 反过来，对于每个星星维护合法的左下角下标 把原先的判定转成了和点有关的状态，把点变成矩形后求并即可 12345678910111213141516171819202122232425262728293031323334353...

线段树维护矩阵：0920T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133100771 正解为文艺平衡树维护矩阵，但我打不动，所以打了部分分 首先可以写成dp形式 然后又可以写成矩阵形式 然后矩阵显然支持结合律 所以可以拿线段树维护 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596...

广义线段树上树剖再拿线段树维护：0914T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132891386 cp 一种常见套路（也是广义线段树问题的核心解决方法，UNR1好像也有一题）： 如果在线段树上进行一段区间修改，那么必然是一段右节点+一段左节点 这个过程其实就是zkw的本质 下面都要用zkw来理解 考虑原题，有一棵不规则的线段树 类似zkw，在这类题目中，我们要先把开区间变成闭区间 然后每个点记录其 兄弟节点 的信息 考虑现在区间为 (x,y...

多观察题目性质：0919T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133047414 http://cplusoj.com/d/senior/p/SS230919C 本题难点在于观察题目性质 对于 p=1p=1p=1 ，必然只能放在自己本身 对于 p=2p=2p=2 ，首先必然满足对称性 满足对称性后，在往中间扩散时，必然更劣 所以必然其中以一边为1 然后就可以上树状数组了 1234567891011121314151617181920212223...

颜色扩散类dp及其优化：0919T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133047170 http://cplusoj.com/d/senior/p/330 此题前半部分是AGC058B 这是一个颜色扩散类dp，对于这类dp，存在一个性质。 假如一个区间被 iii 染，一个被 jjj 染，则必然满足 i<ji<ji<j （这是下标） 所以转移可以用前缀和优化至 O(n2)O(n^2)O(n2) 1234567for(i=1;...

拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132994501 https://atcoder.jp/contests/arc163/tasks/arc163_d 首先竞赛图有个性质： 然后有了这个性质，我们就可以考虑计数题的经典套路，拆贡献算总和。 考虑假如我们成功划分成两个集合 A,BA,BA,B ，其中一个可以为空（我们可以令 AAA 可以为空，防止算重），我们就记为算到一个新的...

哈密顿回路 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132992984 哈密顿回路是一个经过所有节点恰好一次的回路。 相当于把欧拉回路定义中的边变成点

简单的反射容斥与多项式快速幂：Loj#6738. 王的象棋世界 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132978606 首先看到不能走出边界，发现是个反射容斥 对于此题，我们可以采用循环卷积来实现反射容斥 也就是说，如果我们走出了边界，相当于就是走到了另一边 而实现这个过程我们可以把卷完后 i+pi+pi+p 的部分直接平移到 iii 就行 加速这个过程可以用多项式快速幂 1234567891011121314151617181920212223...

对于每种情况分别统计概率来计算期望+树上连通块统计：ARC165E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132971902 https://atcoder.jp/contests/arc165/tasks/arc165_e 考虑一个常见套路，我们对每个连通块统计其概率，设为 p(T)p(T)p(T) ，则答案为 ∑∣T∣>kp(T)\sum_{|T|>k} p(T) ∣T∣>k∑​p(T) 可以想成对于每个大小大于 kkk 的连...

数位dp+判定转状态：Loj #6274. 数字 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132950029 https://loj.ac/p/6274 和位运算有关，然后值域范围又非常大，位之间关联不大，显然考虑数位dp 然后有上下界限制，直接来个4维 然后每一位考虑，先满足or的性质，然后考虑and 发现有冲突只会是（1,0）和（0,1） 首先如果发生冲突，则要么无限制，要么上界为1，下界为0 所以某位0的以后不会受上界影响，某位为1以后不会受下界...