lghjl

摘要： 接下来所有的都是基于一张联通的图\(G\)来讨论的，其点集为\(V\)，边集为\(E\)。 欧拉路径：从一个顶点开始能经过所有边恰好一次的路径；欧拉回路：能够恰好回到起始点的欧拉路径；欧拉图：存在欧拉回路的图，存在欧拉路径但不存在欧拉回路的图也叫做半欧拉图。 欧拉图的性质： 存在欧拉路径 每个点的度 阅读全文

摘要： 一种不同于重链剖分的剖分方法，就是选子树里链最长的作为重儿子。性质1：长链总和为\(n\)。性质2:从一个节点到根节点的轻边个数不超过\(\sqrt{n}\)。原因，因为是长链，所以从轻边跳上去所在的长链的长度一定比现在这个大，\(1+2+3+4\dots\)，所以是\(\sqrt{n}\)个。 应 阅读全文

摘要： 考虑一般的\(01\)背包。就是体积\(w_i\)，\(f_{j}\)表示体积为\(j\)的方案数。不撤销就是\(f_{j}+=f_{j-w_i}\)了，当然倒序。接下来考虑撤销，\(g_{j}\)表示去掉\(i\)后体积和为\(j\)的方案数。那我们使用\(w_i\)时，其他的体积和一定为\(j- 阅读全文

摘要： 考虑这样的一个情景,需要进行的操作是对每一个节点求\(f_{v,i}\times f_{u,j}\)其中\(u=fa(v)\)，\(i\in[1,siz_v],j\in[1,siz_u-siz_v]\)。那么对每一个进行操作就是\(\sum_{siz_v\times (siz_u-siz_v)}=\ 阅读全文

摘要： 问题是这样的，一个序列，每个序列的元素是一条线段，给定做右端点\(l_i,r_i\)，然后询问\(L,R\)中\(\cup [l_i, r_i]\)的大小。加强版 介绍这个问题之前先说珂朵莉树。 我认为珂朵莉树的操作就是在区间上，把连续的，权值相同的点当作一个结点，然后不断的拆线段，合线段的过程（注 阅读全文

摘要： 问题是：一张网格图，存在一些障碍，每次上下左右走。问是否存在路径能从\((1,1)\to (N,M)\)。 对偶？名字是这个，就是图的四联通可以转化成不存在障碍八连通。注意障碍的联通是说第一行最后一列的障碍和第一列最后一行的障碍不连通。当要删障碍使存在四联通时，就是找最少删多少障碍使不存在障碍的八连 阅读全文

摘要： P2704 [NOI2001] 炮兵阵地 古早的题目。注意到\(m\)很小，并且只关心上面两层的状态，所以可以直接压入状态。\(f_{i,S,S'}\)表示考虑到第\(i\)行，前两行中的第一行为\(S\),第二行是\(S'\)。然后枚举当前行转移就行了。会爆。剪枝，把不合法状态判掉。然后枚举第\( 阅读全文

摘要： 10.24 P5658 [CSP-S2019] 括号树 这个实际上就是给定一个括号序列\(a\)，然后对于每一个\(i\)，来说，求出\([1,i]\)的所有合法括号子串（发现这个其实只需要求以\(i\)为结尾的合法括号后缀然后做前缀和就行了）那么只需要找出以\(i\)为结尾最短合法括号后缀就行，（ 阅读全文

该文被密码保护。 阅读全文

摘要： marp: true math: mathjax 根号分治 CF797E Array Queries 我们考虑，按 \(k > \sqrt{n}\) 和 \(k \leq \sqrt{n}\) 分类讨论。 如果 \(k > \sqrt{n}\) , 那么暴力就可以了。 如果 \(k \leq \sq 阅读全文