8.18~8.24

梦里一曲离合，醒时莫记歌。

CF2124E

感觉出来的题目。首先和为奇数肯定不行。

然后感觉过去要将数列分成和差距尽可能小的两端，然后用一次操作将长的那段消掉两段的差。

具体来说设长的段和为 \(S_1 = \sum_{i = 1}^{k} a_i\)，短的为 \(S_2 = \sum_{i = k + 1}^n a_i\)，\(\Delta = S_1 - S_2\)。相当于要证明 \(S_1\) 可以分出两段 \(\frac{\Delta}{2}\)。

根据定义 \(S_1 - a_i < S_2 + a_i\)，则 \(a_i > \frac{\Delta}{2}\)。

所以剩下的约束就是 \(S_1 - a_i \geq \frac{\Delta}{2} = \frac{S_1 - S_2}{2}\)，移项后是 \(S_1 + S_2 \geq 2a_i\)。

所以如果满足这个约束就有解，否则无解。

那这个 \(ans \leq 2\) 啊，题面的 \(\leq 17\) 不是纯诈骗。

CF2126G2

考虑枚举最小值 \(a_v\)，然后可以得到一个 \(a_v\) 是最小值的区间，用 \(1\) 和 \(-1\) 的 trick 转化成区间和 \(\geq 0\) 的判定。考虑选出来的区间一定是 \([l, v)\) 的后缀 \(\max\) 加上 \(a_v\) 加上 \((v, r]\) 的前缀 \(\max\)，可以用线段树维护。同时你会发现如果 \(v \rightarrow v - 1\) 只会单点改几个点，所以使用主席树就可以了。

CF2126G1

直接做的 G2 看题解得到一个更劣的做法。

考虑中位数的限制比较强，所以枚举中位数。然后又是同样地 \(1\) 和 \(-1\) trick，处理出前缀和 \(s\) 后我们处理前缀 \(\min\) 和后缀 \(\max\) 就可以快速判断了。

2025 牛客暑期多校 Round 3 D

弱智题。注意到如果存在 \(a\) 个连续 \(1\) 或 \(a + 1\) 个连续 \(0\) 就可以持续滚雪球然后全变 \(1\)，否则输出 \(1\) 的个数即可。

2025 百度之星初赛 第二场 T喵喵

给定一棵 \(n\) 个点的无根树，你可以进行如下的若干次操作：

1. 若目前的森林为一棵无根树，为这棵树选定一个节点做根；
2. 选定一个正整数 \(k\)，将与森林中每个根节点距离\(^*\)为 \(k\) 的节点打上标记，然后删除它们与父亲之间的连边；
3. 将这一次操作中被标记的节点作为新产生的树的根节点。

\(^*\)树上两点之间的距离定义为两点之间路径上的边数。

我们称一组点对 \((u,v)\) 是完美的，当且仅当 \(u<v\) 并且存在一种操作方案，使得 \(u\) 和 \(v\) 可以在同一次操作中被打上标记。

请计算完美点对 \((u,v)\) 的数量。

\(1 \leq T \leq 10, 2 \leq n \leq 2 \times 10^5\)

画画图会发现只有两个点相邻或者两个距离为 \(3\) 的点同时为叶节点会不合法。统计一下即可。

2025 百度之星初赛 第二场 T喵喵喵

你需要维护一个元素为 \(k\) 位二进制数的集合 \(S\)，支持如下两种操作：

1. 向 \(S\) 中插入一个整数 \(x\)；
2. 给定整数 \(x\)，求 \(\displaystyle\min_{v \in S} \{\text{popcount}(x \oplus v)\}\)。

\(1 \le n \le 2 \times 10^5\)，\(1 \le k \le 20\)，\(1 \le op \le 2\)，\(0 \le x < 2^k\)，执行操作 2 时 \(|S| > 0\)。

套路题。

考虑在插入数的时候维护一个 \(F_i\) 表示数 \(i\) 的最小答案。会发现插入是 \(\Theta(2^k)\)，查询是 \(\Theta(1)\) 的，非常不好。

不妨只维护一半，即令 \(F_{up, i}\) 表示前一半二进制固定为 \(up\)，后一半为 \(i\) 时与当前集合中点异或的最小答案。

插入的时候对于插入数 \(x\) 的前一半 \(up\) 进行更新 \(F_{up, i} = \min(F_{up, i}, \operatorname{popcount}(down \oplus i)\)，查询的时候由于后一半的已经做好了，所以枚举一下前一半即可。

2025 牛客暑期多校 Round 8 H

神秘 DS 题。

发现 \(i\) 要缓存命中的条件是（记 \(f_i\) 为 \([pre_i, i - 1]\) 中出现的不同数字个数）：

• \(l \leq pre_i < i \le r\)
• \(f_i \leq k\)

那么第一个查询就是询问 \([l, r]\) 内 \(f_i \leq k\) 的个数，第二个询问就是求第 \(k\) 小的 \(f_i\)。

注意到 \(f \in [0, n]\)，所以直接值域分块维护这个东西就做完了。

CF2126F

一看就得用类似线段树的东西 \(\log\) 维护吧。

对每个颜色维护一棵线段树，然后将树上的点转化为 BFS 序就可以直接单点修改区间查。

CF105484B

愚蠢的题目。

看到连续两个就应该想到奇偶性，那么删掉两个不会改变下标奇偶性。不妨将偶数位下标对应的取反，那么变成 01 匹配。而 2 就用来消掉一个 0 或 1。

P4064

肯定要二分对吧。想想判定怎么做。

显然我们的目标是把 \(< mid\) 的所有数变大，从左往右枚举所有的数，对于一个数 \(a_i\)，如果左边的所有数都正确了，那就只要管右边的数即可。贪心地想，对于可以覆盖 \(a_i\) 的所有区间要尽量让右端点覆盖的更远，使用大根堆维护这个即可。

\(\Theta(nlog^2n)\)，如果使用线段树组维护区间的数小概率 T。

CF2132

A

模拟

B

注意到答案一定是 \((10^t + 1)x\) 的形式，所以枚举一下 \(t\) 即可。

C1

考虑三进制分解，这样得到的一定是最小次数。

C2

考虑在三进制分解的基础上尽量将高位的往低位移动。

D

将 \(k\) 转化成 \(1 \sim n\) 的范围加上一些散位，数位 DP。

令 \(g_i\) 表示数字 \(i\) 出现的次数，\(f_{i, j}\) 表示 \(i\) 位数中 \(j\) 出现的次数（有前导 \(0\)）。然后直接 DP 即可。

E

贪心，先选出前 \(z\) 大的，然后根据 \(x\) 和 \(y\) 的限制进行调整即可。即把超过 \(x\) 或者超过 \(y\) 的个数给到另一个上。处理下前缀和就可以维护了。

F

思路是很显然的，要求出所有 \(1 \sim n\) 的路径的交集，其实就是求割边。把割边求出来后再 dfs 一遍就好了。

然后这个最小距离显然可以通过 bfs 来解决。

G

狗屎题目描述，根本看不懂在写什么。这一整场都是这样。

2025 年杭电暑期多校 Round 4 T喵

给定一个长度为 \(n\) 的非负整数序列 \(a_1,a_2,a_3,\cdots,a_n\)。

定义函数 \(f(l,r,L,R)\)，其中 \(l,r,L,R\) 均为整数，\(1\le l\le r\le n\)，\(-n\le L\le R\le n\)。其值根据以下方法得到：

1. 将所有满足 \(l\le i\le r\)（\(i\) 是整数）且 \(L\le a_i\le R\) 的 \(a_i\) 依照它们在 \(a_1,a_2,a_3,\cdots,a_n\) 中的顺序取出，组成一个新序列 \(b_1,b_2,b_3,\cdots,b_x\)，其中 \(x\) 为新序列的长度。
2. 若 \(x>0\)，则 \(f(l,r,L,R)\) 的值为 \(b\) 的最大子段和\(^*\)，否则 \(f(l,r,L,R)=-\infty\)。

\(^*\)一个序列的最大子段和定义为：从该序列中选出连续的一段，该连续段的和的最大值。

求出函数 \(f\) 的最大值。同时求出达到这个最大值的不同函数参数的组数对 \(998244353\) 取模后的值。

本题有多组测试。

简单题，注意到最大值一定是所有大于 \(0\) 的数之和，所以找到这一段 \([l, r]\)，那么所有的 \(l' \leq l \leq r \leq r'\) 都是可行的。

然后值域只要包括这一段的 \([min_v, max_v]\) 也都是可行的。

2025 年牛客暑期多校 Round 8 G

一大堆做法，记一下我自己的做法。

注意到若连通块数 \(\geq 3\) 无解，等于 \(2\) 时在两个连通块之间任意连边都可行。

重点考虑一个连通块的情况。考虑在做 \(kruskal\) 的过程中若存在一条连接连通块 \(A\) 和 \(B\) 的边，边权为 \(w\)，那么我们只要在两个块之间任意多连一条边权 \(< w\) 的边就可以替换掉这条 \(w\) 边，于是贡献为 \(sz_A \times sz_B - F(A, B)\)，其中 \(F(A, B)\) 是原图上就有的从块 \(A\) 到块 \(B\) 的边。

所以现在的问题是怎么维护 \(F\)，显然直接在并查集的过程中启发式合并边即可。

2025 年牛客暑期多校 Round 9 G

序列最值可以考虑笛卡尔树。

注意到 \(A\) 末尾的数 \(A_x\) 被加进来那么它在笛卡尔树上非子树内的结点一定要被删掉，同时 \(A\) 中的其它数字一定是是 \(A_x\) 在笛卡尔树上的祖先。

可以根据末尾的数是什么直接暴力 DP，但会发现上述性质相当于限制了 \(A\) 的长度上限为 \(sz_x\)。

记 \(A_x\) 到祖先的数 \(b_1, b_2, ..., b_m\)，其中 \(b_m = A_x\)，它们出现的次数是 \(cnt_i\)。则我们需要求满足以下条件的 \(cnt\) 取法：

• \(cnt_m > 0\)
• \(\sum_{i = 1}^m cnt_i \leq sz_x\)

计数一下就是 \(\sum_{i = 1}^{sz_x}\binom{i + m - 2}{m - 1} = \binom{sz_x + m - 1}{m}\)。

所以总的答案就是 \(\sum_{u = 1}^n \binom{sz_u + dep_u - 1}{dep_u}\)。

P2541

暴力是人都会。类似的题还有 P12459。

考虑直接暴力会重复很多状态，考虑构造一种方式进行去重。令状态为 \(S = (a_1, a_2, ..., a_x, a_{x + 1}, .., a_n)\)。

则有三种转移：

1. \((a_1, a_2, ..., a_x, a_{x + 1}, ..., a_n) \rightarrow (a_1, a_2, ..., a_x + 1, a_{x + 1}, ..., a_n)\)
2. \((a_1, a_2, ..., a_x, a_{x + 1}, ..., a_n) \rightarrow (a_1, a_2, ..., a_x, a_{x + 1} + 1, ..., a_n)\)
3. 当 \(a_x = 2\) 时，\((a_1, a_2, ..., a_x, a_{x + 1}, ..., a_n) \rightarrow (a_1, a_2, ..., a_x - 1, a_{x + 1} + 1, ..., a_n)\)

这个三操作意义在于让类似 \((1, 1, 1, 1, 1)\) 的状态转移到 \((1, 2, 1, 2, 1)\)。这样我们一定可以转移出所有状态。

不妨按照次小值减最小值排序 \(n\) 个序列，那么状态可以简化成 \((x, y, v)\)，表示 \(a_{x + 1 \sim n} = 1, a_x = y\),当前的值为 \(v\)。

那么三种转移就变成了：

1. \((x, y, v) \rightarrow (x, y + 1, v')\)
2. \((x, y, v) \rightarrow (x + 1, y, v')\)
3. 若 \(y = 2\)，\((x, y, v) \rightarrow (x + 1, y + 1, v')\)

于是用优先队列维护一下就全对完了。

ABC420

A、B、C

过

D

显然直接 BFS，记录一下当前机关情况 \(g\)，每次踩到机关 \(g \oplus 1\)。

E

显然并查集直接维护就行了。

注意写并查集的时候如果两个点的根节点相同一定要特判。

WA 了 \(\infty\) 发。

G

MO。

\(n^2 + n + X = Y^2\)，配方有 \((n + \frac{1}{2})^2 + X - \frac{1}{4} = Y^2\)，移项 \((2n + 1)^2 - 4Y^2 = 1 - 4X^2\)。

平方差公式，\((2n + 1 - 2Y)(2n + 1 + 2Y) = 1 - 4X^2\)，令 \(A = 2n + 1 - 2Y, B = 2n + 1 + 2Y\)，则 \(n = \frac{A+B-2}{4}\)。

注意到 \(1 - 4X^2\) 为奇数，且 \(A\) 与 \(B\) 都是奇数。

因为 \(n\) 是整数，所以 \(A + B \equiv 2 \pmod 4\)，又 \(A, B \equiv 1 \pmod 4\) 或者 \(A, B \equiv 3 \pmod 4\)。

所以当且仅当 \(A \equiv B \pmod 4\) 时合法，直接强行枚举一下 \(1 - 4X^2\) 的因数然后判断即可。

\(\Theta(\sqrt N)\)。