xixike

# 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

# P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT/FWT) 先放一个模板后面写题直接复制就可以了。 FWTFWTFWT 原理就不解释了，大家自己去看题解吧 QwQ 这里直接放代码。 CodeCodeCode #include <bits/stdc++.h>#define ll long longusing namespace std;namespace IO{ inline int read(){ int x = 0; char ch = getchar(); while(!isdigit(ch)) ch =...

# Description Luogu 传送门 # Solution 首先我们计算出整棵树的 dfs\text{dfs}dfs 序，然后一个点的祖先的 dfs\text{dfs}dfs 序一定小于当前点的 dfs\text{dfs}dfs 序。 我们把输入的关键点按照 dfs\text{dfs}dfs 序从小到大排序，对于一个关键点 pip_ipi​，所有不能和它放到同一组的点一定在它前面。 考虑依次加入每个关键点，假设 g(x)g(x)g(x) 为 xxx 到根路径上的关键点个数，f(i,j)f(i, j)f(i,j) 表示把前 iii 个关键点分成 jjj...

# Description Luogu 传送门 # Solution 题目让我们求 kkk 个串 LCP\text{LCP}LCP 之和最大，所以考虑建 trie\text{trie}trie 树，然后我们就可以跑树形 dp\text{dp}dp。 设 dpu,idp_{u, i}dpu,i​ 表示在以 uuu 为根的子树中，选取 iii 个结束节点，两两 LCP\text{LCP}LCP 之和最大是多少。 转移的时候为了避免重复转移，我们只加上 xxx 点到其父亲的贡献，即： dpx,i=max⁡{dpx,i−j+dpy,j+(n2)}dp_{x, i} = \max\{dp_{x, i -...