zhangxixi的博客

Hall定理证明可行性来贪心 + 模拟断流与增流： CF1009G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135333029 https://www.luogu.com.cn/problem/CF1009G 显然是流，然后贪心，然后要每次流一下证明可行性，这里提供两种解决方法： Hall定理 左边点数只有6，我们直接 262^626 跑Hall定理 模拟断流 用EK实现网络流。我们直接少流当前位置的。显然一条流最多经过14个点，因此复杂度是对的。 H...

随机类问题解法——利用统计学：1229B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135332294 http://47.92.197.167:5283/contest/440/problem/2 结论： nnn 个随机 [0,1][0,1][0,1] 变量的期望最小值为 1n+1\frac 1 {n+1} n+11​ 因此我们以输入的数为随机种子生成随机数。相同的种子生成的数是一样的，所以相当于有 mmm （不同数）个数的随机数。我们取最小值即可...

闵可夫斯基和 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135329408 几何上可以理解为B沿着A一周覆盖的图形。也可以是B偏移和A交的向量。 对两个凸包归并

反向贪心决定博弈+博弈论中条件改变人的决策满足单调性：1229A 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135329131 http://cplusoj.com/d/senior/p/SS231229A 结论： 人们倒着来，每个人去掉当前对自己最不利的 因此我们有了 O(n3)O(n^3)O(n3) 考虑当一个人变了后，每个人的决策必然满足单调性，因此就可以平方了 12start coding at 20:19passing at 21:18 123...

12.29听课笔记 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135297427 A 1，n个0，n个1 B -1 放最小 +1 放最大 C 假如根定，可以直接dp 打表得只要根是叶子，答案取最小 直接暴摊也是对的 D 假如定根， DPuDP_uDPu​ 内部分辨要多少个点。则 DPu=∑DPv−[存在一个儿子为叶子且分支>1]DP_u=\sum DP_v-[存在一个儿子为叶子且分支>1]DPu​=∑DPv​−[存在一个儿子为叶子且分支&...

边分治建虚树优化：P4565暴力写挂 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135272909 https://www.luogu.com.cn/problem/P4565 首先题目的式子很难看，可以变成 ： depx+depy+dis(x,y)−deplca2(x,y)2\frac {dep_x+dep_y+dis(x,y)-dep_{lca_2(x,y)}}2 2depx​+depy​+dis(x,y)−deplca2​(x,y)​​ 然后直接边...

边分治+虚树+直径合并：P4220通道 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135266426 https://www.luogu.com.cn/problem/P4220 第一棵树可以直接边分治，然后黑白染色，弄到第二棵树上建虚树 第三棵树很难搞。需要回到题目本身，发现题目没叫我们求奇奇怪怪的东西，而是求距离，肯定有啥性质，而且还是最大距离，就是一个点集的直径。 直径显然支持合并性，我们直接在虚树上树形dp进行合并即可 123456pre cod...

虚树建树（单调栈法） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135266476 单调栈维护一条链，初始先按dfs序排序，考虑加入一个点 黑色为栈里面的点，红色为当前加入的点，蓝色为LCA点。 黄色部分需要全部pop掉，蓝色和红色要加入单调栈 代码见oi-wiki https://oi-wiki.org/graph/virtual-tree/

边分治、二度化 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135266447 边分治可以使每次分治时恰好只有两边的点，统计贡献起来非常方便 但是朴素边分治时不行的，菊花图可以卡掉，所以要把点二度化，以这个图为例： 二度化后为： 再举个例子： 二度化后是： 绿点是原图点

动态链上第k小——整体二分+ds：P4175 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135253442 https://www.luogu.com.cn/problem/P4175 第k大先转第k小。 考虑离线。离线完后此题采用整体二分，对于当前二分区间是独立的。把所以操作的查询按时间戳排序。 对于修改操作，如果当前点上的值小于等于mid，则可以有贡献。 对于查询操作，要判断当前两点链上有多少个点有权值。可以用树上差分来解决，所以上一步的维护就要支持...