zhangxixi的博客

质因子拆贡献+朴素容斥：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 （置换环性质） 我们考虑置换环任意一次操作，会划分成两个小置换环，且他们都是连续段 考虑把环拉成一条链，两个...

对于复杂二进制数位dp问题考虑朴素思想：agc015d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133643686 https://atcoder.jp/contests/agc015/tasks/agc015_d 我一开始考虑的是直接上二进制数位dp，但发现这很难做 然后其实可以从最朴素的二进制+分类讨论角度考虑 同样是那么几个套路，考虑最高位

充分理清限制与条件+构造二分图+最小割：ARC142E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133623334 https://www.luogu.com.cn/problem/AT_arc142_e 他的充要条件是是什么： ai,aj≥min(bi,bj)a_i,a_j\ge min(b_i,b_j)ai​,aj​≥min(bi​,bj​) 存在 ai≥max(bi,bj)a_i\ge max(b_i,b_j)ai​≥max(bi​,b...

树上游走最优策略问题：Cf1725J 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133622359 https://codeforces.com/contest/1725/problem/J 首先要转化题目 发现题目本质是什么 不用回去 = 少走一条路径 传送 = 少走另一条路径 一开始猜的结论是这样 但这并不完整 传送本质是让我们把某些路径少走一遍 考虑这种情况，交于1点 12345678910111213141516171819202122232...

次方计数的拆贡献法（考虑组合意义）+限定类问题善用值域与位置进行ds：1006T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133621275 对于多次方的计数问题可以考虑拆贡献。 题目问 ∣S∣3|S|^3∣S∣3 ， ∣S∣|S|∣S∣ 表示选的点数。相当于在 ∣S∣|S|∣S∣ 中选了3次，也就是选了3个可相同的点。 先考虑3个不相同点的贡献，对应任意3个点，必然会对所有包含其矩形产生贡献。所以只需要统计对应的矩形数目。但是必须乘上全排列6，因为...