zhangxixi的博客

分析性质+排列置换环+最小割：1024T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134022318 http://cplusoj.com/d/senior/p/SS231024D 相当于各选一些置换环进行一次位移 我们考虑只对A进行置换。对于一个大小>1的环，如果对其进行位移，一定可以使这些位完全不同。 因此，如果我们置换B，置换的意义是什么？是把A中自环的位置统计掉，使这些位置不同。 但如果我们再置换B，可能会和之前已经置换的A在某些地方相...

组合计数+容斥：1024T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134013962 http://cplusoj.com/d/senior/p/SS231024B?tid=653748c7611b23c4594b05ab 要么是环，要么是链，都可以有两个方向 链的话可以缩成点一起统计 长为2的链如果成二元环不应该乘2，那么考虑容斥 g(i)g(i)g(i) 表示至少有 iii 个二元环不被算错的方案数， ∑i=0kg(i)(−1)k−i\sum...

线段树维护势能类 / 均摊类问题：CF403E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134002988 https://www.luogu.com.cn/problem/CF403E 场上想对于一棵树的某个子树把所有向外边全部删掉 变成dfn序一个在子树区间，一个不在的问题 易发现这个问题可以用线段树维护 在一个点在其dfn序加入另一个点，维护区间另一个点dfn序的最大和最小值 如果不在询问区间里，直接递归 易证明均摊是 O(nlog⁡n)O(n...

枚举最大值+ds：1887D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133996658 https://codeforces.com/problemset/problem/1887/D 左边区间最大值小于右边区间最小值 肯定要离线 感觉分治？ 枚举左边区间最大值 求出其影响范围，推出左端点可取范围 然后可取右端点就是一段连续大于此值得区间 也就是左端点在一段区间时右端点可以在另一端区间取 差分一下，拿个数据结构维护即可 发现枚举最大值过程从大往小枚...

二分套二分+贪心：CSPS2023T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133991517 二分答案 再二分出每个点最晚什么时候被选 然后按照最晚被选的时间从前往后贪心 暴力跳即可 复杂度 O(nlog⁡2n)O(n\log^2n)O(nlog2n) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535...

wqs二分+斜率优化：1019T4 / P9338 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133955885 https://www.luogu.com.cn/problem/P9338 考虑暴力前 iii 个分 jjj 段 fi,k=fj−1,k−1+gj,if_{i,k}=f_{j-1,k-1}+g_{j,i}fi,k​=fj−1,k−1​+gj,i​ ， O(n3)O(n^3)O(n3) 然后划分段数，段数显然越多越优，那么就上wqs二分， O...

斜率优化dp 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133955843 fi=min⁡(aj−j×i)f_i=\min(a_j - j \times i)fi​=min(aj​−j×i) 考虑变成点对 (j,aj)(j,a_j)(j,aj​) ，则 fi=Yj−Xjif_i=Y_j-X_jifi​=Yj​−Xj​i 令 i=k,fi=bi=k, f_i=bi=k,fi​=b ，得 b=Yj−Xjkb=Y_j-X_jkb=Yj​−Xj​k ，即 Yj=...

计算几何+2sat：1020T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133943270 http://cplusoj.com/d/senior/p/SS231019C 我们进行这样的转化 则0/1必选一个，2/3必选一个 那么就变成一个2sat问题 两三角形有交，则一个选，一个不能选 对角三角形一个选，一个不选。一个不选，一个选 三角形不合法，则选向不选连边，代表必须不选 123456789101112131415161718192021222...

判断两线段是否相交 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133943208 我们做两次 每次把一条线段视为直线，判断另一条线段的两个点是否在直线的两侧 如果两次都符合，说明直线相交 1234567891011121314151617181920212223struct Point { double x, y; Point operator - (const Point &A) const { Point B; B.x...

图论+线性基高斯消元与主元：1019T2 / P4151 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133932506 http://cplusoj.com/d/senior/p/SS231019B 相当于图上选一条链和一堆环 考虑dfs生成树。 则链是两条从根出发的链 环是每条返祖边组成的环 所以环和链的异或和可以求出来 链的放到线性基里 然后线性基通过高斯消元求主元（贪心思想，主元可以令那一位一定为1。那么就钦定主元为必选，这样一定更优） 高消的...