xixike

# 前言 说是学习笔记，其实窝并没有打算写太多（太麻烦了，而且我的理解还不是特别深，可能也写不清楚），所以打算大概写两句，然后贴个板子。 # 前置知识 Miller−RabinMiller-RabinMiller−Rabin 素性测试。 倍增基础应用。 # Miller−RabinMiller-RabinMiller−Rabin 素性测试 我们知道有费马小定理： ap−1≡1(modp)a^{p - 1} \equiv 1\pmod pap−1≡1(modp)，ppp 是质数且 aaa 是小于 ppp...

虽然很久之前学过一遍，但是又忘了 QwQ，于是重新复习了一遍。 CDQ 分治是一个离线算法，也只能用于离线问题的处理上。 # 主要思想 把当前区间分成两半，向下递归处理。 左边和右边独立的贡献计算出来之后，再计算左边对右边的贡献。 通常会套上一些树状数组之类的数据结构（不然和暴力有啥区别QwQ） # 例题 板子题：P3810 【模板】三维偏序（陌上花开） # Solution 先按第一维从小到大排序，对于区间 (l,r)(l, r)(l,r)，递归处理 (l,mid)(l, mid)(l,mid) 和 (mid+1,r)(mid + 1, r)(mid+1,r)。 由于已经按照 aaa...

# 问题引入 给一些操作，只在 l∼rl \sim rl∼r 时间段内有效。 给一些询问，查询在某一时间内所有操作的贡献。 # 主要思想 我们可以把操作和询问都离线下来，然后对于时间轴建一棵线段树。 对于操作，相当于是在线段树上进行区间修改；对于查询，不停地向下递归，统计答案，回溯时撤销掉操作。 这样的思想被称之为线段树分治。 # 例题 P5787 二分图 /【模板】线段树分治 # Solution 出现二分图的条件是不存在奇环，可以使用扩展域并查集维护。 再来看如何建树，我们先按照时间轴分区间，然后对于每个点开一个 vector，对于每个操作所在的区间，往线段树上对应的节点的...

主席树的最基础的操作就是查询历史版本区间第 kkk 大，带修。 这个问题的基础解决思路：对于每次修改都建一棵权值线段树，显然空间开不下。 这时可持久化线段树的思路就应运而生了。 主要思想： 不难发现，每次修改只会有一条链上的值发生改变，所以我们不需要建出整棵新树，只需要把新建那条链上的点即可。 所以空间就是 nlog⁡nn\log nnlogn...

# 点双，边双 （掌握较为熟练） # 点双： 定义：删去一个点之后，图仍然联通，则称这个图是点双联通的。一个无向图里最大的点双联通子图称为点双连通分量。 算法：跑 Tarjan，回溯过程中若 lowy≥dfnxlow_y \geq dfn_xlowy​≥dfnx​ 就出栈直到目标节点出栈，弹出的点为一个点双。 # 边双： 定义：类似于点双，只不过条件都改为边。 算法：同样和点双很像，如果有 lowy>dfnxlow_y > dfn_xlowy​>dfnx​ 那么存在点双，弹栈加点即可。 # kmp &...

树状数组，dp + 矩阵乘法

dp，树形dp + 换根，背包

线段树分治 + 可撤销并查集动态维护直径，dp + 分块，贪心，dp + 树状数组

# UVA1292 Strategic game 树形 dp\text{dp}dp 板子题。 直接设 fx,0/1f_{x, 0/1}fx,0/1​ 表示 xxx 子树内所有的边都被看守到，且 xxx 不放 或者 放 士兵的最少士兵数。 xxx 如果不放士兵，它的所有儿子节点都必须放士兵，即： dpx,0+=dpy,1dp_{x, 0} += dp_{y, 1} dpx,0​+=dpy,1​ xxx 如果放士兵，那么它的儿子可放可不放，即： dpx,1+=min⁡{dpy,0,dpy,1}dp_{x, 1} += \min\{dp_{y, 0}, dp_{y, 1}...

早就想搭一个自己的博客了，然而本人水平有限，一直没有弄好 QwQ。最近到二南集训，在 yyt 神仙的帮助下耗时一晚上搭建完毕（主要是用了个假的梯子）。 在此感谢 yyt 神仙的大力帮助，以及 rbs 神仙两秒钟搞定 markdownmarkdownmarkdown 渲染问题, baoshuo yyds! 这个博客会不定期更新 OI 相关内容，以及游记等。 之前的博客就不往这里放了，想看更多请到 xixike-cnblogs