zhangxixi的博客

KD-tree + 二进制分组重构：P4148 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135242661 https://www.luogu.com.cn/problem/P4148 平面数点问题，空间小，可以考虑用kd-tree来解决。 只不过kd-tree是静态的，我们要支持修改，可以使用经典套路二进制分组重构。 12345pre coding at 11:19st coding at 11:43st bugging at 12:05passin...

环异或 + bitset线性基 +线段树分治 ： P3733 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135240352 https://www.luogu.com.cn/problem/P3733 包括首都的环肯定由一个生成树上一堆环并起来，也就是对于一棵生成树，我们把所有非树边对应的环丢入线性基中，然后求最大。 由于初始的图不变，所有生成树就可以不变了。 对于加边、删边、改边操作。改边相当于删+加。每条边有一个存活时间，显然线段树分治即可。 线性基...

转化为ds类 + 移轴不移图：P5324 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135237445 https://www.luogu.com.cn/problem/P5324 首先相当于一堆柱子，放倒后覆盖 [1,n][1,n][1,n] 对于平移操作，我们移起来非常麻烦，我们可以移轴不移图，移动区间 [1,n][1,n][1,n] 即可。 然而，对于一个柱子大于 nnn ，就不能拿它来覆盖，我们要动态维护，因此ds需要支持区间修改。我们维护区间m...

建图+分类讨论+dp：CF704C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135232777 https://vj.imken.moe/contest/599445#problem/C 我们直接建图，由于度数最多为2，要么是环，要么是点，要么是链。（对于操作1直接打tag即可） 对于链，我们直接 f(0/1,0/1)f(0/1,0/1)f(0/1,0/1) 表示上一位是啥，当前异或和为啥的方案数。如果是环，就破环成链，然后记一下第一个是啥。 然后就是...

括号序列匹配利器：贪心匹配 + 折线图：ARC141C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135225808 https://www.luogu.com.cn/problem/AT_arc141_c 首先可以列出一些条件，那是 sss 的必要条件： 若 pi>pi+1p_i>p_{i+1}pi​>pi+1​ ，则 si=( ,si+1=)s_i=(\,,s_{i+1}=)si​=(,si+1​=) 若 qi>qi+...

调整法+单调性分析（贪心）+折半状压：Cf839E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135224828 https://vj.imken.moe/contest/599445#problem/D 有以下结论： 带权子图必为完全图 内部点权值一定相等 点个数越多越好 对于1的证明，我们使用调整法。考虑 (x,y)(x,y)(x,y) 不连通，把 xxx 全加到 yyy 或把 yyy 全加到 xxx ，一定有一个更优。 2显然。...

大小比较之类从大往小进行+离线+ds： P3722 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135215119 https://www.luogu.com.cn/problem/P3722 看到什么排列，还有一堆大小比较，min/max的限制，考虑从大往小的顺序进行枚举，发现贡献如图： 离线后拿个ds维护即可。 12345pre coding at 21:34st coding at 21:40st bugging at 22:05passing a...

网络流+先跑一遍确保正确性：ARC156F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135209595 https://www.luogu.com.cn/problem/AT_arc156_f 可以很显然建一个流： 然而它最大流是对的，但构造方案可能会假，因为存在最左边的边没流，相当于某个数没选。 一定有解是怎样？全选 aia_iai​ ，所以我们可以先全选 aia_iai​ 跑。然后我们再加入 bi,cib_i,c_ibi​,ci​ 来跑，那样反悔...

推结论：Gym - 103371I 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135208880 https://vj.imken.moe/contest/600552#problem/A 对上下做一次，对左右做一次，求出 xix_ixi​ 表示高度为 iii 时宽度最大为 xix_ixi​ ， yjy_jyj​ 表示宽度为 jjj 时高度最大为 yjy_jyj​ ，然后丢坐标系上求交即可： 考虑证明。必要性显然。充分性我们可以对所有矩形在合法位置放，...

猜结论 + bitset优化高斯消元：CF1070L 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135202185 https://www.luogu.com.cn/problem/CF1070L 所有点度数为偶，则答案为1. 此时可以猜结论，猜测答案最多为2. 如果答案为2，看一下充要条件是什么。划分为两个集合（注意可以不连通），其中一个 xi=1x_i=1xi​=1 ，另一个为0. 如果本身度数为偶，则是 ⊕xj=0\oplus x_j=0⊕xj​=...