「2025 暑假校内训」第二周

「精选模拟赛」#6

P4141

首先是跑出【所有物品都在时】的方案数。

然后，由于计数背包具有可删性，我们可以直接对 dp 数组分别执行一遍【删除某个元素】的操作（就是把加入元素的循环顺序，符号换一下）。

abc362_e

首先，按照点序列，我们计算出每个边被经过了几次。

计算方法可以使用树上差分，对于每条边，我们钦定那条边连着的更深的那个点为 “代表点”。

对于任意 $i < n$ ，我们设 $u$ 为 $a_{i}$ 和 $a_{i + 1}$ 的 LCA，那么我们给 $a_{i}$ 和 $a_{i + 1}$ 的差分分别加 1，对于 $u$ 的差分减 2，最后将差分通过一遍 dfs 复原成每条边的经过次数。

原理建议自己画图理解，这里不赘述。

我们可以得出点序列经过了多少次边（重复的要重复算）。设其数量为 $h$ 。

设经过的红色边数量为 $R$ ，蓝色边数量为 $B$ ，那么由于 $R - B = k, R + B = h$ ，所以可以得出 $R = \frac{k + h}{2}$ 。对一条边染成红色，若这条边被经过 $d$ 次，会有 $d$ 的贡献，我们要做的就是凑到 $R$ 的贡献，不难发现，这就是一个经典的背包问题，因此把每个经过路径点的 $d_{i}$ 丢进去跑背包即可。

跑完背包后还要注意那些没有被经过过的边，这些边可以随便染色，设数量为 $c$ ，那么答案还要乘上一个 $2^{c}$ 。

abc220_e

对于一条 $(u, v)$ 路径，可以把它拆成两部分： $(u, LCA)$ 和 $(LCA, v)$ 。

问题就变成了对每个点，统计这两部分路径长度的和为 $d$ 的合法方案。

由于是满二叉树，同一层的所有节点的子树结构都相同，所以我们可以对每一层的点考虑其子树结构计算答案，再乘上层中点数量。

对于一个二叉树，统计这个路径长度是不难的，下面我们固定一个深度为 $i$ 的点 $t$ （根节点深度为 $1$ ）。

为了方便，这里对于每一对节点只统计一次（按照无序数对的方式），最后把答案乘 $2$ 。

首先考虑一种简单情况：直接从该点走往它的儿子，长度为 $d$ ，这需要满足 $i + d \leq n$ ，其方案数为 $2^{d}$ 。

然后考虑一般情况。考虑在左子树中抉择一个路径端点 $u$ ，看它与 $t$ 距离的取值范围。显然不能大于 $min (n - i, d - 1)$ （不能太长导致 $d$ 内够不到或者变成上述简单情况，也不能超过树的深度），不能小于 $max (1, d - (n - i))$ （在右边取最长的情况下，左边最短是多少）。

不妨设取值范围内共有 $g$ 个整数。设左子树端点距离 $t$ 为 $x$ ，那么右子树端点距离 $t$ 就是 $d - x$ ，左边共有 $2^{x - 1}$ 种方案，右边共有 $2^{d - x - 1}$ 种方案，乘起来就是 $2^{d - 2}$ ，不难发现它不受左边右边深度具体是多少的影响，于是该点这种情况的答案就是 $g \times 2^{d - 2}$ 。

对每个深度的点都如此计算，然后乘上该深度的点的数量即可。

最后别忘了乘 $2$ ，因为我们对每一对节点只统计了一次，而题目中所求的 $(A, B)$ 和 $(B, A)$ 一类的会贡献两次。

P2391

我们倒序考虑每个操作，给没有染过色的染色。这是一个经典技巧。

然后你就会发现，我们现在的任务是如何快速找到每个没染色的，如果能让复杂度依赖于每次染色的个数就可以了。

伎俩（trick）： 使用并查集维护。并查集父亲指向下一个可以染色的，初始时指向自己，当它 $i$ 被染色后就指向 $i + 1$ 。其实这可以算一个跳跃指针，不过它使用了和并查集一样的路径压缩来优化。

设并查集复杂度为 $O (k)$ ，每个点只会被访问 $O (1)$ 次，复杂度为 $O (n + k)$ 。

P10282

考虑设 $F_{i, j}$ 为第一个数组的前 $i$ 个元素与第二个数组的前 $j$ 个元素可以划分成相等的满足题目条件的段的方案数。

F_{i, j} = \sum_{x, y, valid (x + 1, i), valid (y + 1, j)} F_{x, y}

直接转移是 $O (n^{4})$ 的。考虑优化。

我们可以使用双指针与排序进行优化。方法如下。

考虑先枚举 $i$ ，再枚举第二个数组的转移点 $y$ 。

再搞两个数组：

一个存储对于 $i$ ，可行的“从”转移点 $x \in [1, i - 1]$ 。再将其按照 $x + 1 \sim i$ 区间的平均数升序排序。
一个存储对于 $y$ ，可行的“到”转移点 $j \in [y + 1, n]$ 。再将其按照 $y + 1 \sim j$ 区间的平均数升序排序。

维护一个变量 sum，表示所有目前可行的“从”转移点的 dp 和。

在第二个数组中枚举每个“到”转移点，并且维护一个指针在第一个数组中，每次新枚举一个“到”转移点时就移动指针，把那些满足条件（平均数比当前的“到”转移点小于等于的）的“从”转移点的 dp 值加入 sum 中。

更新完指针之后，就可以将 sum 计入 $d p_{i, j}$ 中了， $j$ 就是我们枚举的“到”转移点。

总复杂度 $O (n^{3} \log n)$ 。

另外，这样的 dp 为什么是正确的？

它能覆盖所有情况。
它能保证有序性。（在 $F_{i, j}$ 中加入 $F_{x, y} (x < i, y < j)$ 时 $F_{x, y}$ 已完成计算。）（习题：请你思考一下并尝试说明。）

P3447

首先第三个条件就是最后答案减去全0的意思。

你先考虑一个特殊情况，就是你会发现如果一个数 $a_{x}$ 可以取到的值域是 $2^{32} - 1$ 的话，无论其它数怎么选，最后我们都可以靠这个数把异或和圆回来，所以答案就是 $(\prod_{i = 1}^{n} (a_{i} [i \neq x] + 1)) - 1$ 。

然后这对我们有启发性了，假设现在枚举到第 $b$ 位，前面几位都是把规矩顶死的，然后现在突然有一个没把规矩顶死，那么这个数字后面就可以任意选，效果就和上面一样，就皆大欢喜了。

于是我们就可以考虑对每一个位计算以下东西：如果这个位以上的位全都顶到上界，可是这一位没有，会对答案造成的贡献。

然后你设 $d p_{i, j, k}$ 表示当前到了数组中第 $i$ 个元素，异或和是 $j$ ，是否（ $k$ ）有没顶到上界的。

然后转移的话，考虑每个点对答案有什么贡献，因为我们最后要统计此位后面的都随意，那么当我们遍历到 $i$ 时，对答案的贡献系数就是 $a_{i}$ 中的此位后面的位（不要忘记 0 的贡献，也就是 +1）。

当然如果你首次把某个位钦定成不满上界的话，这个的系数就是 $1$ ，因为它需要去迎合别的。如果是第二次的话，那么这个数后面的位都能选了，系数就是 $2^{b}$ 。

然后每一位计算完答案加起来即可。当然你会发现有一些位在计算的时候，前面锁死的那些位异或起来不是 0，这样子显然是无法锁死的，所以此类答案不应该被计算进去，直接跳掉。

然后你计算到最后一个位时也要把没有不满上界的方数进去。

「精选模拟赛」#7

arc098_b

问题等价于区间 And 为 0。直接使用双指针即可。

2042D

可以分开计算左右端点，使用 set 即可。

abc159_f

考虑 dp，设 $d p_{i, j, 0 / 1 / 2}$ 表示当前在下标 $i$ ，背包已经放进重量为 $j$ ，尚未进入区间、已经进入区间、已经离开区间三种状态下的方案数。转移是简单的。

arc101_b

遇到中位数，考虑二分这个中位数 $x$ 。令 $a_{i} > x$ 的 $b_{i} = 1$ ， $a_{i} \leq x$ 的 $b_{i} = - 1$ ，问题转化为计算和小于 0 的区间个数是否小于 $⌊ \frac{n (n + 1)}{4} ⌋ + 1$ 。利用树状数组计算即可。

2042E

待补

「精选模拟赛」#8

2026C

考虑每次至多选两个，这是显然的。

然后从大到小，将有机会成为被减免的加入优先队列中，遍历到没机会的就和一个减免者配对。

队列中可能还会剩下 $k$ 个元素，其中前 $⌊ \frac{k}{2} ⌋$ 个可以被减免。

2075D

考虑动态规划预处理出使 $x$ 右移 $a$ 位并使 $y$ 右移 $b$ 位所需的代价。

每次询问直接枚举每个右移的位数判断剩下的数是否相等并取 min 即可。预处理是 $O (\log^{3} x)$ 的，回答是 $O (\log^{2} x)$ 的。

abc197_f

考虑以二元组形式进行广搜， $(x, y) \to (a, b)$ 当且仅当存在边 $x \to a, y \to b$ ，且两条边的 $c_{i}$ 相同。我们从 $(1, n)$ 开搜，搜到 $(x, x)$ （偶数回文串）或者 $(x, y)$ 满足 $x, y$ 有连边（奇数回文串）即可计算答案。

abc356_f

2064F

「精选模拟赛」#9

P9050

P8900

P9904

abc360_g

考虑枚举中心点，计算【左右能拼接在一起的上升子序列长度最大值】。

考虑优化。对于两个子序列，中间可能有多个中心点可以将其计算到，我们不妨钦定每个左侧子序列只有在该子序列结束下标 $x$ 的下一个下标 $x + 1$ 能作为它的中心点。

这样子左侧就转化为了“以某个点为结束点的子序列的最大值”，直接做。

然后我们从大往小枚举，维护一个树状数组，不断把右侧节点加入，树状数组维护每个点 $x$ ：“以值 $x$ 开头的上升子序列的最大值”，然后每次对 $a_{i}$ 进行更新。注意这时查询区间是 $[a_{i} + 1, N]$ ，而 max 是不可差分的，所以要转成负数下标加偏移量变成查询前缀 max。

然后对每个中心点计算即可。注意离散化的时候，如果有类似于 $x, x + k$ 两种数字且中间没有其它数字，那么离散化的时候要将 $x + 1$ 也一同加入，否则会导致 $x, x + k$ 被离散化为 $t, t + 1$ ，原本存在的中心点无法正确计算。

「精选模拟赛」#10

「暑假复健赛」#5

NOI 2025 选做

D1T1

这也是题？

D2T1

考虑挖掘题目的性质。容易发现：

当序列中出现 110 时，设其中 0 的下标为 $k$ ，答案就是所有 110 的 $n - k + 1$ 的最大值。特别地，如果序列中没有 110，但是出现了 101，那么答案为 1。

又因为要支持区间取反，于是我们可以搞一棵线段树，维护：

区间左右端点与长度
区间 110 出现位置
区间 001 出现位置
区间是否出现 101
区间是否出现 010
区间取反 tag
区间首两个元素和末两个元素

然后相邻两个区间信息合并就是把原来的算上，再考虑两个区间相邻的边界会不会出现新的某特定串。

inline node merge(node L,node R){
    node ret;
    //Part 1
    ret.len = L.len+R.len;
    ret.st1 = L.st1;
    if(L.len>1)ret.st2=L.st2;else ret.st2=R.st1;
    ret.ed2 = R.ed2;
    if(R.len>1)ret.ed1=R.ed1;else ret.ed1=L.ed2;
    ret.l=L.l; ret.r=R.r;
    //Part 1.5
    ret.app101 = L.app101 || R.app101;
    ret.app010 = L.app010 || R.app010;
    ret.pos110 = min(L.pos110,R.pos110);
    ret.pos001 = min(L.pos001,R.pos001);
    //Part 2
    static int tmp[6],pos[6];
    int v=0;
    if(L.len>1)tmp[v++]=(L.ed1),pos[v-1]=(L.r-1);
    tmp[v++]=(L.ed2),pos[v-1]=(L.r);
    tmp[v++]=(R.st1),pos[v-1]=(R.l);
    if(R.len>1)tmp[v++]=(R.st2),pos[v-1]=(R.l+1);
    
    if(v<=2)return ret;
    
    auto chk = [&](int st,int x,int y,int z){
        return tmp[st]==x && tmp[st+1]==y && tmp[st+2]==z;
    };
    ret.app101 |= chk(0,1,0,1); ret.app010 |= chk(0,0,1,0);
    if(chk(0,1,1,0))chkMin(ret.pos110,pos[2]);
    if(chk(0,0,0,1))chkMin(ret.pos001,pos[2]);
    if(v<=3)return ret;
    
    ret.app101 |= chk(1,1,0,1); ret.app010 |= chk(1,0,1,0);
    if(chk(1,1,1,0))chkMin(ret.pos110,pos[3]);
    if(chk(1,0,0,1))chkMin(ret.pos001,pos[3]);
    return ret;
}

然后修改某个节点就是把记录的相对应的东西交换一下，并对记录的首尾四个元素取反。

D1T2

考虑操作的方式。我们不妨把每次操作中较小的那个元素向较大的元素连边，易得每个节点至多只有一条出边，且不会形成环。（请不要对相邻的 0 和 0 做无谓的操作！）

于是可以想象，操作完成后，一个序列由若干个形如下图的东西组成：

\dots \to x - 3 \to x - 2 \to x - 1 \to x \leftarrow x + 1 \leftarrow x + 2 \leftarrow x + 3 \leftarrow \dots

以下将形如此状的 $x$ 称为 top。

接下来讨论第一问。

我们考虑可以把序列划分成段，每段按照上述形状计算出段内最大值。设 $f_{i}$ 为以 $i$ 结尾，前面部分的最大值。有转移方程：

f_{i} = max_{0 \leq j < i} {f_{j} + calc (j + 1, i)}

然后考虑在 $O (n^{2})$ 的复杂度内预处理出 $calc$ 。

对于每个左端点，我们预处理出他能贡献到的最远的 top $R m a x_{l}$ ，右端点同理预处理出 $L m i n_{r}$ 。

这样子对于每个询问，端点只会在区间 $[max (l, L m i n_{r}), min (r, R m a x_{l})]$ 之中。

考虑什么样的点能成为 top。

对于一段区间，我们考虑每个数对 top 的贡献。容易发现与 top 距离为偶数的点有正贡献，否则有负贡献。

那么我们计算区间 $s = \sum_{i \in [l, r]} (- 1)^{i + 1} a_{i}$ 的值。

当 $s = 0$ 时，显然任意位置上的数都可以作为 top。
当 $s > 0$ 时，这意味着最后有数残余，且残余那一位系数为正，因为只有残余的那一位可以作为 top，所以 top 一定在 $(- 1)^{i + 1} = 1$ 的点位上，即奇数下标点位。
当 $s < 0$ 时，这意味着最后有数残余，且残余那一位系数为负，top 一定在 $(- 1)^{i + 1} = - 1$ 的点位上，即偶数下标点位。

当 $s = 0$ 时，无论 top 怎么选最后整段区间都会变成 $0$ ，于是这段区间的 $calc (l, r)$ 就是区间 $b_{i}$ 的和。

否则，top 位置无法造成贡献，这段区间的 $calc (l, r)$ 就是区间 $b_{i}$ 的和减去 top 处的 $b_{i}$ 。我们想最大化贡献，就得最小化 top 处贡献，于是在 top 可取区间内找到满足下标限制的 $b_{i}$ 最小值即可。注意 top 是有奇数下标或偶数下标限制的，因此要对两种下标分别预处理区间 min，这个可以直接暴力 $O (n^{2})$ 处理。

另外，【某数没有被进行操作】可以通过 $l = r$ 的情况转移（以下第二问也是如此）。

以上我们做完了第一问，到了第二问，我们沿用第一问的思路，但是你会发现形似 ${1, 1, 1, 1}$ 的区间会有 ${1, 1, 1, 1}$ 或 ${1, 1}, {1, 1}$ 等多种表现方式，我们不妨规定：在计算之前的【最远左右端点】时对于能消为 0 的不再扩展。

如此便处理完了大多数情况，避免算重，但是你会发现对于 $r = l + 1$ 且 $a_{l} = a_{r}$ 的区间上述做法不会统计下来，但是这恰恰是我们需要统计的最小单元，于是特判一下即可。

剩下的就和以前的做法差不多了：我们设 $g_{i}$ 为截止下标 $i$ ，题目所求式子的值。有转移方程：

g_{i} = \sum_{0 \leq j < i} g_{j} \times Bcalc (j + 1, i)

其中 $g_{0} = 1$ 。

然后对于 $Bcalc$ 的计算，我们考虑先处理出区间 $[l, r]$ 中 $c$ 的乘积（设为 $p$ ）。

沿用第一问时的 $s$ 。

当 $s = 0$ 时，无论怎么选 top 最终都是 0，答案即为 $p$ 。
当 $s > 0$ 时，top 在奇数下标。
当 $s < 0$ 时，top 在偶数下标。

对于一个 top 下标为 $t$ ，其答案即为 $p \times {invC}_{t}$ 。

那么我们对每个点位的 $c$ 的逆元进行前缀和（同样也要分两种下标进行）。

然后设 top 可行区间中满足下标条件的点位的逆元之和为 $v$ ，那么 $Bcalc (l, r)$ 就是 $p \times v$ 。

如此，我们做完了这道题目。