晚练计划总结2

26-9-1

P17307。

先把 1 号点设为白点。

考虑跳跃过程的实质，是从 1 号点出发，经过若干白点，最后到达重点。

跳跃过程中，我们转化一下代价，从白点跳到白点的代价为。

然后发现，我们在跳跃过程中，是从离某个祖先最近的白点跳过来的。

即要么从祖先白点过来，要么先跳到一个白点再跳下来，由于我们操作时，只有往下跳和先跳另一个子树内的白点再跳到终点所在子树两种策略，从离某个祖先最近的白点跳过来就包含了这两种策略。

设表示从 1 号点到离号点最近的白点的最小代价。

记表示离号点最近的白点，表示离号点最近的白点与的距离，不存在时设为。

转移为 $是的祖先$ 。

是独立的，可以提出来使用形如前缀 min 东西优化，然后转移就是的。

号点的答案为 $是的祖先是黑点$ ，是艾佛森括号。

26-9-2

P10071。

若所有木棍个数均为偶数，答案为。

任取三组木棍不妨设显然和是合法的。

最后可能剩形如或者，后者也可以搞出一个，显然仍是符合条件的，而且已经完全利用了（就剩 1/2 个显然不可能再拼了）。

26-9-3

U725151。

Solution by hyc：

首先需要特判掉的情况，此时无法进行任何操作，答案为。

容易发现，为了通过操作获得一个，最优的操作是选择，因为如果有多余的元素显然可以去掉。

发现直接贪心没有正确性或难以实现。注意到答案（在时）有单调性，因此考虑二分。考虑怎么判定，发现想要凑出，我们需要到各一个；于是我们又可以考虑怎么凑出一个；依次类推，发现最后的限制是至少需要多少个，于是我们只需要在过程中统计的数量即可。

设表示的数量。具体地，设当前考虑了，有个，需要到各个。

初始时；对的每个数操作一次变为，因此有个；需要到各一个，因此。
从到依次枚举。
- 若，那么可以将多余的个各操作一次变为，因此令。
- 若，那么还需要额外的个，将这一部分转化为到各个，因此令。

最终，若那么答案合法，否则不合法。注意过程中是的，所以当时可以直接判定为不合法。注意到答案的上界是，因此可以将的数直接变为。

时间复杂度。

26-9-4

CF2255B。

发现操作事实上可以看做任意修改 0/1 连续段的长度，保证长度和不变，且不改变 0/1 连续段的相对顺序。

然后就是简单题了，两个插板，再乘一起即可。

P16822。

设表示前缀的期望连续零段长度，表示后缀的期望连续零段长度。

有转移

答案就是。

拆一下式子，把做一个后缀和即可计算。

26-9-6

大神题啊。

为了让尽量少的数形成尽量多的相邻，令两两不同的方案一定是最优的。设我们最终使用的不同数的个数为，将这些数两两连边。

相邻两个的不同，等价于在这张完全图（含自环）中找一条路径，使得每条边最多经过一次。这等同于求欧拉路径，路径长如下：

为奇数，此时每个点的度数为偶数，存在欧拉回路，路径长度即为边数。
为偶数，此时每个点的度数为奇数，需要删一些边使得个点的度数为偶数。删即可，留点和点的度数为奇数。路径长度为。

是好求的，枚举即可。

然后就是构造个互不相同的数了。

构造 gcd 两两不同的点，此时不重复。

但是对于，最大到，会大于！

发现我们使用作为底数，相当于给出了一维的信息。

我们可以考虑用两维表示，再加一组底数表示另一维，这样每一维的范围就可以降到。

现在有，但是出现了问题：，需要区分。

发现，所以再加区分即可，但是注意到太大了，所以改成，把放在前面区分即可。

结果就是，这样终于不会超过了。

26-9-7

To do.

26-9-27

To do.

26-10-5

To do.

26-10-6

To do.

26-10-8

To do.

26-10-9

To do.

26-10-12

To do.

26-10-13

To do.

26-10-15

P5280。

神秘，由于操作完全对半，我们可以反向使用等概率事件期望转计数的 Trick，把计数转成期望。

设分别表示自己有 tag 和及其祖先中有 tag 的概率。

考虑一次操作，拆成个线段树区间后，对于这些被完全包含的区间，祖先全部被 pushdown 清空，但是这个节点一定会被标记，所以，。

对于不完全包含的节点（递归过程中经过的节点），祖先也被 pushdown，自身也被 pushdown，且没有标记，所以，。

对于祖先被 pushdown 但是自己完全不被包含的节点，。

这就是修改了，但是注意对的修改需要下传，因为我们的修改是 lazy 的，下面节点未经修改。

26-10-16

P7219。

诡异。

反贪正确性证明什么的还是看题解为妙。

26-10-20

P8868。

第一步很简单，显然离线下来，然后从到扫，两个单调栈显然容易维护和的所有后缀，但是注意到我们不能接受的查询次数，所以必须要做乘积历史和~~但是乘积历史和 tag 极为难搞~~。

考虑我们线段树 info 要维护什么，有区间历史和 ans，区间后缀之和 sumA，sumB。

根据板板 Trick，带修维护历史和，tag 需要维护所有原来项对 ans 的贡献。

再加上本来就有的对和的后缀，tag 就有如下 6 个部分。

prodtoans 表示乘积对 ans 的贡献系数；
sumAtoans 表示 sumA 对 ans 的贡献系数；
sumAtoans 表示 sumB 对 ans 的贡献系数；
lentoans 表示 len 对 ans 的贡献系数；
setA 表示区间修改的后缀；
setB 表示区间修改的后缀。

注意 tag 运算优先级是先做 toans 再 set。

tag 合并难以手推，直接放代码。

tag operator+(const tag &x) const // x 为新 tag
{
    tag ret = *this; // 原 tag
    if (setA) // 如果原来就有 setA，那么 info 与 tag 合并时，info 的 sumA 是不能和 x 合并做贡献的。
    {
        ret.lentoans += setA * x.sumAtoans; // 新 sumA 是 setA * len，因此可确定的转到 lentoans
        if (setB) // sumA, sumB 均不可与 x 合并，转到 lentoans
            ret.lentoans += setA * setB * x.prodtoans;
        else // sumA 不可与 x 合并，sumB 可与 x 合并，转到 sumBtoans
            ret.sumBtoans += setA * x.prodtoans;
    }
    else
    {
        ret.sumAtoans += x.sumAtoans; // sumA 可与 x 合并，转到 sumAtoans
        if (setB) // sumA 可与 x 合并，sumB 不可与 x 合并，转到 sumAtoans
            ret.sumAtoans += setB * x.prodtoans;
        else // sumA 可与 x 合并，sumB 可与 x 合并，乘积就可与 x 合并，转到 prodtoans
            ret.prodtoans += x.prodtoans;
    }
    if (setB) // 同上
        ret.lentoans += setB * x.sumBtoans;
    else
        ret.sumBtoans += x.sumBtoans;
    ret.lentoans += x.lentoans; // len 是定值，直接合并
    // setA, setB 直接覆盖
    if (x.setA) 
        ret.setA = x.setA;
    if (x.setB)
        ret.setB = x.setB;
    return ret;
}

info 与 tag 的合并就简单许多，按照 tag 字面意思合并即可。

info operator*(const info &a, const tag &x)
{
    return {
        /* sumA */ x.setA ? x.setA * a.len : a.sumA,
        /* sumB */ x.setB ? x.setB * a.len : a.sumB,
        /* prod */ x.setA ? (x.setB ? x.setA * x.setB * a.len : x.setA * a.sumB) : (x.setB ? a.sumA * x.setB : a.prod),
        /* ans */ a.ans + x.sumAtoans * a.sumA + x.sumBtoans * a.sumB + x.prodtoans * a.prod + x.lentoans * a.len,
        /* len */ a.len};
}

26-10-26

P9340。

根据结论，将点集按 dfn 排为后，边数等于，点数则等于边数加一。

注意到序列有重复，因此很麻烦，于是直接上莫队。

但是由于需要进行插入和删除，使用 set 维护的话复杂度无法通过。

可以改为链表，通过记录一定的信息可以做到的删除，但是插入复杂度无法保证。

于是请出回滚莫队，由于我们建立一次链表是的，建表次，每个查询删除及回滚次，时间复杂度，取可得时间复杂度。

26-10-27

To do.

26-10-28

To do.

26-11-5

2026 年暑假梦熊省选模拟赛做过的。

~~但是我现在不会了。~~

目标是对计数，要求是交换出来的合法。

按照和的关系，我们可以转化出一些更为容易处理的限制。

记表示交换的次序，越小越先，并且是个的排列。

对于的元素，她们需要刚好被交换到这个位置上，因此，否则，上的元素就会被换到左边去，并且再也换不到右边了。

而对于的位置，需要依次交换被换到，因此。

最后，我们要防止已经到达目的地的元素还被换过，所以有。

同理对于的元素，有，对于，，最后还有。

什么？会不会有，显然是不可能的，因为此时显然无解，而题目保证有解。

现在所有限制都转化成了的限制此时我们只需要对计数即可。

设表示考虑的前缀，且的方案数。

根据限制直接转移即可，这是的，转移是一个形如的形式，容易前缀和优化到。

26-11-6

P14343。

萌萌 DS 题。

的限制可以拆成，这样可以限制分别放到和上。

从左往右枚举扫描线，处理过程如下。

将加入编号为的桶中，等待加入。
枚举号桶中的元素，在线段树中激活。
更新区间，使得区间中的答案对 $区间激活元素的值的$ 和 $区间激活元素的值的$ 取 max。
枚举右端点为的询问，查询询问区间中的最大。
若当前线段树中有的激活的，则取消激活。

1 略，唐诗。

2，5 操作是线段树单点修改，共执行次，时间复杂度正确，需要维护全局及最大值位置来正确进行操作 5。

3 操作可以维护 lazy tag，维护和即可，info 和 tag，tag 和 tag 的合并都是容易的

4 略，正常查询。

就做完了，注意恰当的初值设定，方便判定无解。