1972
SOJ1972 题解
题意 设 \(S\) 为一个可重数集,满足所有元素均为非负整数。你可以对 \(S\) 进行若干次(可以为 \(0\) 次)如下操作:选择一个非负整数 \(x\) 满足 \(x\) 至少在 \(S\) 中出现了 \(2\) 次,在 \(S\) 中删除一个 \(x\),并将 \((x-1)\) 或 \( ......
luogu1972题解
还是先写被卡的做法吧。 节点的区间用了现用现计算卡常过了。 被卡了一上午,难过。 话说有人说我码风有点抽象。 思路 主席树做法。 a[i] 是贝壳序列。 先求出 nxt,即与 a[i] 相同的下一个 a[j] 的下标 j。 用 p114514[i] 记了值为 \(i\) 的数的下标,循环到序列第 \ ......
P1972 [SDOI2009] HH的项链
P1972 [SDOI2009] HH的项链 我们考虑将所有询问按照右端点归类。 然后从左往右扫描每个位置,如果前面有位置和它重复,就把前面的位置删掉(这样做是对的,因为右端点只可能在之后了,那么要访问到前面的位置,就必须要到达这个位置,相当于把重复的贡献减掉)。 初始时假设所有位置都不重复,都是 ......
题解 - CF1972E - Divisors and Table
这题正解是虚树,本解法卡常,仅适合不会虚树的。(例如本人) 注意:下文中根节点深度定义为 1 . 第一步: 转化问题 我们把 $ g(x,y,z) $ 拆开,考虑每个质数是哪些点的因子。 包含这个质数的点构成一个点集,我们只需求这个点集 S 的 $ \sum\limits_{x,y,z\in S } ......
「解题报告」P1972 HH的项链
题目链接:[HH的项链](https://www.luogu.com.cn/problem/P1972) 这道题做法很多,看到有用线段树,主席树和莫队做的,但我不太会用树状数组,所以讲解一下树状数组的解法。 题干告诉我们要求区间内的贝壳的种类数,那么用树状数组怎么维护呢?我们通过一个简单的例子来理解 ......