zhangxixi的博客

二分套二分+贪心：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。那么就钦定主元为必选，这样一定更优） 高消的...

ST表倒序释放：1019T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133926195 http://cplusoj.com/d/senior/p/SS231019A 发现只有修改，最后查询，且区间取max，可以考虑维护类似ST表的过程 把 [l,r][l,r][l,r] 拆成前后两个区间，分别在ST表修改 最后ST表从上往下释放即可 复杂度 O(nlogn+m)O(nlogn +m)O(nlogn+m)

set维护连续段+线段树：1018T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133914164 http://cplusoj.com/d/senior/p/386?tid=652f5fe6c1fe41bc229c18fb 线段树维护01，和，支持翻转操作 用类似珂朵莉树的方法维护连续段，连续段之间分别统计，取max 1234567891011121314151617181920212223242526272829303132333435363738...

杨辉三角按列求和 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133906909 假设求杨辉三角这一列 我们考虑这个格子： 然后对其不断展开 综上： ∑i=0n(ik)=(n+1k+1)\sum_{i=0}^n\binom i k=\binom {n+1}{k+1} i=0∑n​(ki​)=(k+1n+1​) ∑i=lr(ik)=(r+1k+1)−(lk+1)\sum_{i=l}^r\binom i k=\binom{r+1}{k+1}-\binom...

dp转自动机：1017T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133894734 http://cplusoj.com/d/senior/p/SS231017D 求本质不同子序列个数见 https://blog.csdn.net/zhangtingxiqwq/article/details/133885358 发现这就是交换 ggg 和 fif_ifi​ 的奇偶性。 我们发现本质不同的 fff 状态只有4种，我们可以基于这个建一个自动机 这样子我...