zhangxixi的博客

c++accumulate()，partial_sum()，fill()函数 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132264428 accumulate() 求和，传入 begin指针、end指针，首项 12int a[5]={1, 2, 3, 4, 5}, b[5], c[5]; printf("%d\n", accumulate(a, a+5, 100)); 100+1+2+3+4+5=115 pa...

线段树记录系数维护动态信息：ZR2612 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132255084 http://zhengruioi.com/problem/2612 ai+bj≥0a_i+b_j\ge 0ai​+bj​≥0 => ai≥−bja_i\ge -b_jai​≥−bj​ 因此考虑把 bbb 去负， ai≥bja_i\ge b_jai​≥bj​ 也就是一个区间 aaa 最小值大于 bbb 最大值 套路1 （大小关系转不同） 对于此...

对平移类dp用数据结构优化：ZR2617 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132240791 http://zhengruioi.com/problem/2617 对于此类dp式子： dpi,j=∑dpk,j−w(k,i)dp_{i,j}=\sum dp_{k,j-w(k,i)} dpi,j​=∑dpk,j−w(k,i)​ 暴力计算为 O(n3)O(n^3)O(n3) ，但如果 w(j,i)w(j,i)w(j,i) 在 w(j,i−1)w(j,...

颜色类问题与分治：P7215 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132221132 https://www.luogu.com.cn/problem/P7215 化为点分治后，把原问题变成钦定一个点必选的问题 转化这一步是点分治维护颜色类题目的一个性质，如果某种颜色外面有，就会在外面被考虑，不需要在此层 对朴素分治也有启发，对于在大区间统计了的答案，就不需要在小区间统计了 考虑在钦定一个点必选时，怎么做，首先把它定义为根。 把每种颜色丢入一个...

点分治过程中维护李超线段树：CF1303G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132219909 https://www.luogu.com.cn/problem/CF1303G 看到这题，首先很容易想到树形dp，但发现要维护两个值，一个为末项，一个为和，很好分析出这个东西有凸性。 这个时候有两种做法，维护凸包或李超线段树。 之所以用李超线段树，是可以想象出维护末项（k）和和 （b）之后最终的答案其实之和队对面的深度（x）有关，而这个大胆猜测可以...

李超线段树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217504 插入过程中，先询问中点，让 uuu 在上，它必然覆盖其中一个区间。 然后看看左右端点哪里 vvv 比 uuu 大，就在对应区间递归下去

点分治小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217048 https://www.luogu.com.cn/problem/P3806 dfs1：找到当前重心 dfs2：统计当前每个点到重心的距离 dfz：点分治 找重心，处理出 xxx 所有儿子子树和非 xxx 子树的大小最大值，这个最大值最小的点 xxx 就是答案 注意这个过程中统计非 xxx 子树大小需要统计当前分治区间的大小 sumsumsum ，要时刻注意维护这个...

容量很大体积很小的背包问题 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132216843 完全背包 https://www.luogu.com.cn/problem/P9140 多重背包 http://zhengruioi.com/problem/2620 值域大体积小，所以肯定是优先选性价比高的。 但是恰好的条件很难搞，记 mmm 为 max⁡wi\max w_imaxwi​ 的。 然后可以想象最后肯定是拿走一部分，再加入一部分。 然后在...

把约束条件转为不等式：CF1394C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132212342 https://www.luogu.com.cn/problem/CF1394C 当时对于同号和异号的情况进行分类讨论，一个转化为±条件，一个转化为max条件。 由于分类讨论而且约束条件种类不同，导致不能整体判断。 而解题的关键在于把这些约束条件转化为不等式条件，化为不等式后有些时候发现不完整（就是计数里漏的情况），所以只需要写成判断所有约束条件同时满足即...

通过数据结构维护数论分块结果：ZR2609 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132178041 http://zhengruioi.com/problem/2609 对于 这类东西，应该是自然反应，枚举个 aia_iai​ ，然后数论分块，这里是 O(nn)O(n\sqrt n)O(nn​) 然后会在纸上推一大轮（结论忘了）推出 xxx 的合法区间 [l,r][l,r][l,r] ，然后就是判断 aj∈[l,r]a_j\in[l,r]aj​∈...