脚本宝典收集整理的这篇文章主要介绍了刷题记录2022.3[2]，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
(Rightarrow rm luogu) 链接
观察减法部分，可以发现可以用笛卡尔树+树形背包完成，每次合并节点 (u) 的两个儿子的时候，假设物品数分别为 (i,j) ，那么合并的答案显然要减去 (2ija_u) （这里乘二是因为每一对询问两次），如果要选上 (u) ，那么还需要减去 (a_u times (2times text{除 } u text{ 以外选择的个数}+1)) 。
(Rightarrow rm luogu) 链接
首先设定 (A>B) 。
观察性质，如果存在 (i(1leq ileq n-2)) ，有 (a_{i+2}-a_i<B) ，这时无论如何分 (i,i+1,i+2) ，都是不满足条件的。因此此时答案为 (0) 。
接下来用 (rm dp) 解决，设 (f(i)) 表示考虑了前 (i) 个元素，其中强制令 (i) 放入集合 (A) 。显然这时候需要枚举上一个放入 (A) 的元素 (j) ，而这个 (j) 需要满足下面的条件：
第一个条件显然限制了 (j) 的最大值，而第二个条件限制了 (j) 的最小值，用前缀和维护一下 (f) 即可。
(Rightarrow rm luogu) 链接
首先将和节点 (1) 相关的边都删掉，这样会有若干个联通块。
如果联通块和 (1) 只有一条边相连，因为路径权值是异或和，对联通块设一个线性基，接下来找到一颗生成树，然后将仅含一条非树边的环加入这个联通块的线性基中，可以认为任何一条从 (1) 到某个点然后再回到 (1) 的人和路径（包括不简单路径）都可以用树上路径配合若干个先前提到的环组成。（这个套路来自(text{CF938G Shortest Path Queries}) ），而因为要回到 (1) ，所以树上路径的权值和为 (0) ，因此只需要看是否存在一些环是线性相关的。如果存在一些线性相关，那么这个联通块显然不能选。
如果联通块和 (1) 有两条边相连，那么实际上有两种情况：
接下来可以选择一些联通块，这个似乎做不了，因为线性基的数量过多？但是很多线性基实际上是一样的，将线性基消成最小的（将若干二进制数拼起来之后字典序最小），发现这时候只有不到 (400) 个不同线性基，那么就可以 (rm dp) 了，要先预处理出两个线性基合并之后得到的线性基作为转移。
(Rightarrow texttt{Code})
(Rightarrow rm luogu) 链接
将每个人的信息 ((a_i,b_i)) 转化一下，就是和他相同分数的区间为 ([a_i+1,n-b_i]) 。
将相同的区间合并一下，合并之后的人数设为这个区间的权值 (w[l,r]) ，问题转化一下：选择不相交的若干区间，令选择的区间的权值和最大，这时候可以将区间按右端点排序，设 (f(i)) 表示考虑了前 (i) 个区间，强制选择第 (i) 个区间的最大权值和，那么有：
特别的，令 (l_0=0,r_0=0) 。
(Rightarrow rm lugou) 链接
首先枚举一个起始点 (T) ，接下来考虑一对数 ((i,j)(i>j)) 对答案的贡献，这实际上是在求 (i) 在 (j) 之前被走到的概率，考虑当 (mathrm{lca}(i,j)) 被走到之后的情况，这时候，除了这两个点到 (rm lca) 的路径之外，其他的点都不用管，因为对答案的概率没有影响，显然有 (frac{1}{2}) 的概率往其中一条路径拓展一次，那么有 (f(i,j)) 表示第一条路径先拓展 (i) 步，然后第二条路径才拓展了 (j) 的概率，可以得到：
那么 ((i,j)) 的答案显然是 (f[mathrm{dep}(i)-mathrm{dep(lca}(i,j)),mathrm{dep}(j)-mathrm{dep(lca}(i,j))]) 。
以上是脚本宝典为你收集整理的刷题记录2022.3[2]全部内容，希望文章能够帮你解决刷题记录2022.3[2]所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。