zhangxixi的博客

杜教筛入门 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142208852 求 fff 的前缀和（不要求 fff 为积） 考虑 h=f∗gh=f*gh=f∗g ，若 h,gh,gh,g 前缀和都好求，那 fff 的前缀和 sss 是好求的 ∑i=1nhi=∑ij≤nfigj\sum_{i=1}^n h_i=\sum_{ij\le n}f_ig_j i=1∑n​hi​=ij≤n∑​fi​gj​ ∑i=1nhi=∑i≤ngi∑d=1⌊ni⌋fd\sum_{i=...

[SDOI2010] 地精部落（简单dp） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142138324 https://www.luogu.com.cn/problem/P2467 一开始想错方向，小丑了 设 f(i,j,0/1)f(i,j,0/1)f(i,j,0/1) 表示还剩 iii 个，上一个在剩余数里面排名为 jjj ，之前是上升/下降的方案数，转移显然 滚一下前缀和就好 123456789101112131415161718192021222...

[SCOI2014] 方伯伯的玉米田（dp+树状数组维护行列） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142137107 https://www.luogu.com.cn/problem/P3287 显然每次操作的区间一定是一个后缀 我们直接令 dp(x,i)dp(x,i)dp(x,i) 表示最后一个数是 xxx （加之后），加了 iii 次的最长长度，转移显然 max⁡dp(y≤x,j≤i)\max dp(y\le x, j\le i)maxdp(...

BZOJ3688. 折线统计（dp+ds） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142096597 https://hydro.ac/d/bzoj/p/3688 一个很显然的dp， f(x,k,0/1)f(x,k,0/1)f(x,k,0/1) 表示现在末尾的数为 xxx ，已经有 kkk 段线段，之前一直在上/下的方案数，转移显然。 然后前面一维我们遍历 iii 时只会修改一个 xxx ，同时查询其他前后缀的和，那直接树状数组即可。 1234567...

P2605 [ZJOI2010] 基站选址（线段树优化dp） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142056966 https://www.luogu.com.cn/problem/P2605 看错题几次，无语了 我们设一个 f(i,j)f(i,j)f(i,j) 表示第 jjj 个基站在 iii ，然后对于一个 [l,r][l,r][l,r] ，如果里面建了基站就搞定，建不了就需要 www 的代价。 [l,r][l,r][l,r] 离散化后按 r...

[NOI1998] 免费的馅饼（三维偏序转二维偏序） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141938125 https://www.luogu.com.cn/problem/P7302 接完 iii 能去接 jjj 的充要条件是什么？ ti≤tjt_i\le t_jti​≤tj​ ∣pi−pj∣≤2(tj−ti)|p_i-p_j|\le 2(t_j-t_i)∣pi​−pj​∣≤2(tj​−ti​) 绝对值的套路就是拆掉 pi+2t...

BZOJ2959 长跑（LCT维护边双后缩点） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141937532 https://www.luogu.com.cn/problem/P10658 显然，一个边双内的点可以全部在一起，也就是可以缩成一个点 此时我们可以用LCT来维护，正常的连边显然，当要缩点时就把这点链提取出来，然后把整棵splay遍历一遍，搞一起即可 要拿个并查集维护实际对应点。 12345678910111213141516171819202...

P4842 城市旅行（拆贡献 + LCT） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141900793 https://www.luogu.com.cn/problem/P4842 发现题目就是要维护一个LCT，然后我们只要把pushup写成功了就行。 那我们现在就不管LCT了，就单纯想用一棵二叉查找树怎么维护。分母是好搞的，分子我们要想点办法。 考虑右子树对左子树的贡献，我们假设处理出一个 L[k]L[k]L[k] 表示左子树中每个值乘以左边界的可选...

P2147 [SDOI2008] 洞穴勘测（LCT） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141825874 https://www.luogu.com.cn/problem/P2147 第一次学LCT，梳理一下。 LCT是基于splay的，所以Splay的两个基本函数都有： Rotate：不同点在于如果 yyy 的父亲是 zzz ，需要判断是否在同一棵平衡树树里在连实边。但是 xxx 的父亲一定为 zzz Splay：注意，要在对 xxx...

[NOI2014] 魔法森林（LCT维护MST） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141868128 https://www.luogu.com.cn/problem/P2387 考虑按 aaa 排序加边，我们只需要维护 1,n1,n1,n 的最短链就行 假如如果一直是森林那么是好做的，直接LCT即可。如果加入一条边后有环，我们可以尝试把环上最大一条边删掉。 实现的时候，我们可以把边换成点，然后把链提取出来，在平衡树内删掉最大点即可 12345...