zhangxixi的博客

枚举子集式子转二项式定理 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133702110 对于枚举子集的题目，我们可以变成枚举子集大小。转成二项式定理 以 ： ∑y⊊x,y≠1(−1)∣y∣+1\sum_{y\subsetneq x,y\neq 1}(-1)^{|y|+1}∑y⊊x,y=1​(−1)∣y∣+1 为例 我们枚举集合大小，再去大小为0的情况， −∑i=0n(−1)i(ni)−(−1)=(1+(−1))n+1=1-\sum_{i=0}^n(-1...

用min-max容斥实现lcm与gcd互换 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133698576 lcm本质是每个质因子质数取max，gcd是每个质因子质数取min 然后我们就可以直接套min-max容斥：

min-max容斥 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133698526 设 S,TS,TS,T 都是可重序列 maxS=∑S⊊TminT(−1)∣T∣−1maxS=\sum_{S\subsetneq T}minT(-1)^{|T|-1}maxS=∑S⊊T​minT(−1)∣T∣−1 minS=∑S⊊TmaxT(−1)∣T∣=1minS=\sum_{S\subsetneq T}maxT(-1)^{|T|=1}minS=∑S⊊T​maxT(−1)∣...

序列：全序关系 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133698338 一个序列满足全序关系必须满足以下条件： 反对称性：若 a≤ba\le ba≤b ，则 b≥ab\ge ab≥a 传递性：若 a≤ba\le ba≤b 且 b≤cb\le cb≤c ，则 a≤ca\le ca≤c 完全性： a≤ba\le ba≤b 或 b≤ab\le ab≤a

质因子拆贡献+朴素容斥：1007T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133697910 http://cplusoj.com/d/senior/p/SS231007C 考虑枚举gcd，然后容斥，恰好转至少。 ggg 表示gcd恰好为 ddd ， fff 表示至少为 ddd 显然有 f(d)=∑d∣ng(n)f(d)=\sum_{d|n}g(n)f(d)=∑d∣n​g(n) ，可以直接莫反成： g(d)=∑d∣nf(n)μ(nd)g(d)=\s...

差分构造法推广：arc166_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133694378 https://atcoder.jp/contests/arc166/tasks/arc166_d 首先肯定是这样子放： 考虑相邻之间的差，本质就是橙色区间减蓝色区间数量 区间数量越少显然越优，所以我们要么保留橙区间，要么保留紫区间，然后两两匹配 12345678910111213141516171819202122232425262728293031323...

ds套dp——考虑位置转移or值域转移：CF1762F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133691573 https://www.luogu.com.cn/problem/CF1762F 分析性质，就是我们选的数要么递增，要么递减（非严格） 然后很明细是ds套dp， fif_ifi​ 表示以 iii 开头的答案 然后考虑如何转移（ds套dp难点反而在转移而不是状态，因为要考虑如何和ds结合） 转移的话，要么从位置考虑，要么从值...

长链贪心+虚树+类直径合并性+分块建树维护ST表：1008T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133690843 http://47.92.197.167:5283/contest/408/problem/4 两个可以推的经典套路： 我们可以对所有点建序树，然后取前 kkk 大。而取前 kkk 大可以通过以直径端点为根长剖来贪心 直径具有合并性（不仅是连通块，而且是点集）。同理，前 kkk 大的点也具有合并性。 想到这里，我们就已...

分析性质+dp计数：1007T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133659409 http://cplusoj.com/d/senior/p/SS231007D 分析题目性质，有： 按编号顺序最短路必然为连续段 边只会在连续段内和相邻连续段之间连 iii 段 连 i+1i+1i+1 段， i+1i+1i+1 段中每个点恰有1条来自 iii 的边 然后肯定是考虑 f(l,r)f(l,r)f(l,r) 表示最后一段为 [l,r]...

置换环建笛卡尔树：AT_wtf22Day1B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133644610 https://atcoder.jp/contests/wtf22-day1/tasks/wtf22_day1_b?lang=en 置换环是用值连位 首先肯定要分成每个置换环，每个置换环操作次数只能是 size−1size-1size−1 （置换环性质） 我们考虑置换环任意一次操作，会划分成两个小置换环，且他们都是连续段 考虑把环拉成一条链，两个...