文章

题目分析 一条边将多边形分成了 “面对 $n$点” 的一侧和 “背对 $n$点” 的一侧。“背对 $n$点的一侧” 构成了一个点区间，这就是这条边管理的区间。因为不存在相交的边，所以每条边管理的区间之间存在嵌套关系，可以写成树结构。又发现因为整个多边形被严格分成了 $n-3$个三角形，所以形成的东西 阅读更多…

传送门 题解 一个优化建图的例题 首先题目明示跑网络流，然而操作 $2,3,4$因为涉及到一段连续的点，连边会爆炸，所以我们考虑用线段树优化建图 优化建图实际上就是利用线段树的特性，将连续的一段点变成一个点，这种东西脑补一下就明白了，但是还是画个图吧 $qwq$ 如果你想连 $1-3$号点的话你只需 阅读更多…

传送门 题解 这道题比较特别的地方就在于求的是合法数的平方和 其实也不是太难维护 当我们做完第 $u$位的时候此位为 $i$，假设我们还有 $cnt$个合法的数 $p_1…p_{cnt}$，那么它们的贡献就是 $(10^ui+p_1)^2+…+(10^ui+p_{cnt})^ 阅读更多…

传送喵 这两天复习 $splay$真的太痛苦了 $qwq$ 题解 首先我们考虑一下如何维护 $Query$的信息 改变几个括号让括号序列合法？注意到一个合法的括号序列我们是可以将配对括号不断消去直到消没的，如果括号序列不合法我们消括号的时候最后会剩下类似 $)))((($的情况，记 $(=1$，$) 阅读更多…

愉快的推式子吧 (ﾉ≧∀≦)ﾉ！ 设 $f_i$ 表示前 $i$ 根柱子完工后的最小代价。枚举一个小于 $i$ 的 $j$ ，表示为从 $j$ 向 $i$ 连了一座桥，中间的柱子当然全部推掉，计算一下就好： $$f_i=\min{f_j+(s_{i-1}-s_j)+(h_i-h_j)^2& 阅读更多…

KM 算法求解二分图最小权完美匹配 问题描述 给定一个二分图，其左侧有 $X$个节点，右侧有 $Y$个节点，左侧第 $i$个和右侧第 $j$个节点之间有一条权值为 $w_{ij}$的边。 现求这个二分图权值和最大的一个完美匹配。 算法复杂度 最优为 $O(n^3)$ 先决条件 了解增广路有关定理、性 阅读更多…

qwq 机房快关门了突然想起来上午做的这题还算有点新颖所以记录一下吧 题意 求 $\mathbf{S}=N^* – \{z|z=[ \frac{x}{2}]+y+xy,x,y\in N^*\}$的前 $40$个元素 题解 看着这个数据范围和样例我就猜了好几个结论，不过没有 阅读更多…

传送门 因为好久没打可持久化的东西了所以拿这个来练练手 思路很简单。 对于子树的操作就是在 $dfs$序上的一个区间操作，在那个区间建立可持久化 $Trie$即可。 对于路径的操作，你可以在树上建 $Trie$，类似树上差分的思想。你首先需要写一个 $lca=(u,v)$，然后就是查询 $(u,lc 阅读更多…

传送门 一道套路题 首先这个全局异或值最大的信息显然可以用线性基来维护 但是线性基不滋磁删除怎么办啊？ 以时间建立线段树，算出每个数出现的时间区间，并在线段树的每个节点存个 $vector$来记录所有向量，然后每次询问就跑到线段树的叶子节点，然后合并路径上的向量即可。这样就避免了删除操作。 还有一个 阅读更多…

传送门 吐槽 $k\leq 5$(法术伤害+5) 题解 因为答案保证了范围，考虑线性基 当 $k\geq 3$的时候，显然值域范围 $\leq 2^{22}$因此我们可以直接把所有数插入线性基，然后枚举算即可 (tip: 易知每个数的出现次数相同) 当 $k=1$的时候，也容易想到按二进制位讨论贡献 阅读更多…