NEUACM 2025 Winter Training 6 题解

D 和平委员会 & E Riddle

第一次接触 2-SAT 问题，感觉网上的很多博客讲的都不是很清楚，搞了半天没搞懂，好在最后搞懂了。

SAT 问题是指有若干个变元，和一个谓词，要求找出一个指派使得谓词为真，或者说明无解。

2-SAT 问题指的是把这个谓词写成合取范式后，每个大项中最多有两个变元情形。只有 2-SAT 可以在多项式时间复杂度内求解。

求解的具体方法就是把每个的变元的真与假看作点，大项改写为蕴含式，然后将前见代表的点连一条指向后见的边。若某个变元的真与假在同一强连通分量中，那么无解。反之，如果不存在这样情况，对于我们取缩点后编号较小的点作为该变元的指派，就可以构造出一种解。

这样做的道理在于，当这样构造图后，在图上的移动相当于假定前见为真来进行推理。如果某个变元的真与假在同一强连通分量中，说明无论我们对这个变元进行何种指派，都会推出矛盾。而取缩点后编号较小的点是因为编号较小的点在缩点过程中是后访问的，对编号较大的点没有影响。

题意

根据宪法，Byteland 民主共和国的公众和平委员会应该在国会中通过立法程序来创立。 不幸的是，由于某些党派代表之间的不和睦而使得这件事存在障碍。 此委员会必须满足下列条件：

• 每个党派都在委员会中恰有 $1$ 个代表。
• 如果 $2$ 个代表彼此厌恶，则他们不能都属于委员会。

每个党在议会中有 $2$ 个代表。代表从 $1$ 编号到 $2n$。 编号为 $2i-1$ 和 $2i$ 的代表属于第 $i$ 个党派。

任务：写一程序读入党派的数量和关系不友好的代表对，计算决定建立和平委员会是否可能，若行，则列出委员会的成员表。

分析

在第 $i$ 个党派中钦定一个成员是否去看作变元 $X_i$，那么另一个成员是否去就是 $\neg X_i$。

若 $i$ 和 $j$ 中我们钦定的人厌恶，那么谓词就是 $\neg X_i \vee \neg X_j$，写成蕴含式就是 $X_i \rightarrow \neg X_j$ 和 $X_j \rightarrow \neg X_i$。

感觉理解了 2-SAT 后还是比较好写的。

F Colorful Tree

题意

有一个 $N$ 个节点的树，每条边有颜色、边权。 您需要处理 $Q$ 个询问，每个询问给出 $x_i, y_i, u_i, v_i$，您需要求出假定所有颜色为 $x_i$​ 的边边权全部变成 $y_i$ 后，$u_i$ 和 $v_i$ 之间的距离。询问之间互相独立。

分析

问题转化后就是要求询问的链上指定颜色的个数和边权和。当然可以用主席树解决。

但是莫队也是一种方法。受到之前一道题目启发，一个数上的链可以看作欧拉序中的一段括号序列，那我们可以把要求的链对应到欧拉序上，初始括号序列为空，不断扩展。若没有匹配，则加上这条边的贡献，若有匹配，表明要现有括号序列要弹出，也就是减掉这条边的贡献。

括号序列扩展容易，不好删除，所以可以用不回滚莫队解决。

G Rabbit Exercise

题意

有 $n$ 只兔子在一个数轴上，兔子为了方便起见从 $1$ 到 $n$ 标号，第 $i$ 只兔子的初始坐标为 $x_i$。兔子会以以下的方式在数轴上锻炼：一轮包含 $m$ 个跳跃，第 $j$ 次跳跃是兔子 $a_j (2 \le a_j \le N−1)$ 跳一下，这一下从兔子 $a_{j−1}$ 和兔子 $a_{j+1}$ 中等概率的选一个。假设选了 $x$，那么 $a_j$ 号兔子会跳到它当前坐标关于 $x$ 的坐标的对称点。 注意，即使兔子的位置顺序变化了，但是编号仍保持不变，这里按兔子编号算。兔子会进行 $k$ 轮跳跃，对每个兔子，请你求出它最后坐标的期望值。

分析

兔子跳跃后的期望 $\displaystyle E(x_i’) = \frac{1}{2}(2x_{i - 1} - x_i) + \frac{1}{2}(2x_{i - 1} - x_i) = x_{i-1} + x_{i+1} - x_i$。根据期望的线性性可以计算。但是轮数很多，$n$ 也很大，甚至无法用矩阵快速幂解决。

但是有个惊人的注意到：$x_i’ - x_{i-1} = x_{i+1} - x_i$ 以及 $x_i - x_{i-1} = x_{i+1} - x_i’$，也就是每次跳跃只会交换差分。那我们可以把交换写成置换的形式，然后用快速幂就好了！

H Sky Full of Stars

题意

有一个 $n\times n(n \le 10^6)$ 的正方形网格，用红色，绿色，蓝色三种颜色染色，求有多少种染色方案使得至少一行或一列是同一种颜色。结果对 $998244353$ 取模。

分析

设 $A_i$ 为所有着色的集合，其中第 $i$ 行仅包含一种颜色，$B_i$ 为所有着色的集合，其中第 $i$ 列仅包含一种颜色。

因此，需要计算 $|A_1 \cup A_2 \cup \dots \cup A_n \cup B_1 \cup B_2 \cup \dots \cup B_n|$。

这个就可以用容斥原理计算了。

其中 $f(i,j)$ 是满指定 $i$ 行和前 $j$ 列是同种颜色的的着色数。

$f(0,k) = 3^k \cdot 3^{n(n-k)}$。
如果 $i, j$ 都大于零，那么我们可以注意到，所有选定的行和列实际上是同一种颜色。

因此，$f(i,j) = 3 \cdot 3^{(n-i)(n-j)}$。我们先 $\mathcal{O}(n)$ 计算 $i, j$ 有一个是 $0$ 的部分，剩下的就是：

又可以 $\mathcal{O}(n)$ 计算了！

NEUACM 2025 Winter Training 5 题解

D 丝之割

题意

形式化题意：有 $m$ 条弦，一条弦可以抽象为一个二元组 $(u,v)$，你可以进行任意次切割操作，一次切割操作你将选择两个下标 $i$ 和 $j$ 满足 $i,j \in [1,n]$，然后所有满足 $u>i,v<j$ 的弦 $(u,v)$ 都将被破坏，同时你将付出 $a_i \times b_j​$ 的代价。求破坏所有弦的最小代价和。

分析

首先观察到若存在两个弦 $(x, y), (u, v)$ 满足 $x \le u$ 且 $y \ge v$。那么我们在删去 $(x, y)$ 的时候就一定会删去 $(u, v)$。而我们的目标是删除所有的弦，那么就可以忽略 $(u, v)$。

我们假设现在有了 $m$ 个不相交的弦，那就可以定义状态 $f_i$ 表示删除所有小于等于 $i$ 的弦的代价。

我们发现 $\displaystyle \min_{k \in [u_j, u_{j + 1})} a_k$ 只与 $j$ 有关，$\displaystyle \min_{k > b_i}a_k$ 只与 $i$ 有关。不妨用 $p_j$ 表示前者，$q_i$ 表示后者。

变形后 $f_j = -q_i \times p_j + f_i$，把 $(p_j, f_j)$ 看作点，$-q_i$ 看作斜率，就是经典的斜率优化求最小截距。

而且从左向右的过程中 $q_i$ 和 $f_j$ 单调不下降，直接用最基本的单调队列求下凸壳即可。

F 简单题 加强版

题意

P6222 「P6156 简单题」加强版

求

要求是 $\mathcal{O}(n)$ 的复杂度。

分析

先来点喜闻乐见的莫反套路。

以上都是莫反的常规操作，下面进入本题的核心。

令 $T = dt$，有

。

这里还需要用一个技巧就是自然数幂次可以用线筛在 $\mathcal{O}(n)$ 时间处理。其实做法也比较显然，因为这是一个完全积性函数，所以只需要用快速幂算质数的幂次，剩下的用完全积性函数的性质算。

$\displaystyle \sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor} (i+j)^K$ 这部分显然可以预处理出来。

我们用 $\mathrm{id}^{K}_i$ 表示我们刚才算出来的自然数幂。求前缀和得到 $f_i$。用 $F_i$ 表示 $\displaystyle \sum_{j=1}^{i}\sum_{k=1}^{i} (j + k)^K$。

我们稍微在纸上写一写，容斥一下有

。

现在剩下 $\displaystyle \sum_{d|T}d\mu^2(d)\mu(\frac{T}{d})$。

我们发现这实际上就是一个积性函数的迪利克雷卷积，而积性函数的迪利克雷卷积也是积性函数。根据积性函数的性质，我们只需要求出质数的幂次处的值就能用欧拉筛在线性时间算完整个函数。我们令 $\displaystyle g_i = \sum_{d|i}d\mu^2(d)\mu(\frac{i}{d})$。下面我们讨论这个函数在质数的幂次处的值。

• 当 $k=0$ 时，$g(p^k) = g(1) = 1$。
• 当 $k=1$ 时，$g(p^k) = g(p) = \mu^2(1)\mu(p) + p\mu^2(p)\mu(1) = -1 + p$。
• 当 $k=2$ 时，$g(p^k) = g(p^2) = \mu^2(1)\mu(p^2) + p\mu^2(p)\mu(p) + p^2\mu^2(p^2)\mu(1) = -p$。
• 当 $k>2$ 时，无论怎么选 $d$，$\mu^2(d)$ 和 $\mu(\frac{i}{d})$ 中至少有一个有高次幂，所以 $g(p^k)=0$。

现在，原式就变成了

就可以用经典的数论分块求解了！

H String Problem

题意

给定一个字符串，求出每个前缀当中字典序最大的子串。

分析

稍加分析我们就可以得出一个比较显然的结论，一个字符串当中字典序最大的子串一定是它的一个后缀。现在我们只需要求每个前缀当中字典序最大的后缀。

如果要进一步解决问题就需要进一步观察，这里我列一个我认为对我启发比较大的观察。

如果我们已经求出当前前缀中字典序最大的后缀，现在尾部再加入一个字符，新的答案要么不变，要么就是新加入的字母，要么是 原答案的最小 border 加上这个字符。这里 border 指的是当前答案的与其相同前缀的后缀。

我们知道 border 与循环节有着密不可分的关系。如果我们知道一个字符串的循环节，就能直接找到它的最小 border。

我们假设已经求出了长度为 $i$ 的前缀的答案为 $p$ 开始的后缀，且它的循环节长度为 $k$，考虑新加入字符 $s_{i+1}$ 对答案的影响。

若 $s_{i+1} > s_p$，那么新答案就是 $i + 1$，因为其他字符一定都小于 $s_{i+1}$。

若 $s_{i+1} > s_{p + ((i + 1 - p) \bmod k)}$，也就是新字符比循环节中对应的字符大，那么新答案就是 $i + 1 - ((i + 1 - p) \bmod k)$。稍微写一写就能看出，就不证明了。

若 $s_{i+1} < s_{p + ((i + 1 - p) \bmod k)}$，也就是新字符比循环节中对应的字符小，那么答案不变，但是要重新求循环节。

若 $s_{i+1} < s_{p + ((i + 1 - p) \bmod k)}$，也就是新字符就是循环节中对应的字符，那么答案不变，循环节也不变。

至于怎么求循环节，我采用了 $\mathrm{Z}$ 函数的方法。循环节的长度就是第一个相同前缀是自己本身的后缀与整个字符串的差。我们找到第一个就不用再求了，因为我们只需要求循环节。然后整个更新过程中求 $\mathrm{Z}$ 函数都是不断往右的，复杂度也是线性的。

L Pastoral Oddities

题意

给定一张 $n$ 个点的无向图，初始没有边。

依次加入 $m$ 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。

若存在，则还需要最小化边集中的最大边权。

分析

本题最重要的观察就是原命题等价于存在一个边集使得只存在大小为偶数的连通块。

必要性：若存在大小为奇数的连通块，每个点度数又是奇数，那边数就是 $\displaystyle \frac{\sum \mathrm{deg}_i}{2}$，无法除尽，矛盾。

充分性：对于任意的大小为偶数的连通块，取一个它的生成树，对于每个非根节点，若它儿子给它的度数为偶，则连父亲，否则不连父亲。这样可以保证除根以外都满足度数为奇数。再用刚才的方法，边数等于 $\displaystyle \frac{\sum_{i \ne \mathrm{root}} \mathrm{deg}_i + \mathrm{deg}_\mathrm{root}}{2}$。分子中前一项为奇数，后一项一定也是奇数。

在有了这个结论后，原问题就转化为要最小化边集中的最大边权使得子图中连通块大小都为偶数。如果是静态的问题，可以按边权排序，用并查集维护每个连通块大小，不断加边知道满足条件。

动态的情况下，一般与连通块并查集相关的问题都可以尝试用线段树分治解决。

我们给边排序，考虑在全部边都可用的情况下算出答案就是最后一次加入边的答案。我们考虑倒序删边，已加入的边在被删掉前一定都在答案中。

我们考虑线段树分治，先递归右子树，再递归左子树，到叶子节点时，不断加边知道满足条件，期间加入的边在由于时间而删掉前会一直存在，所以可以边加入，边修改线段树，将这条边一定在答案中的区间中都加上这条边。

NEUACM 2025 Winter Training 4 题解

D 运输计划

题意

一个 $n$ 个点的树，每条边的边权，给出 $m$ 条路径。要求只改变一条边的边权，使得所有路径中长度最大的路径的长度最小。

$n, m \le 3 \times 10^5$。

分析

“最大值最小”提示我们要二分答案。假设我们当前要求最大路径长度不能超过 $d$。那么所有长度大于 $d$ 的路径中都要包含操作的边，且操作的边的边权应当大于等于该路径的原长与 $d$ 的差。
更进一步，这条边的边权应当大于等于所有路径长度最大值与 $d$ 的差。所以，我们可以树上差分来给超过 $d$ 的路径打标记，然后去遍历每一条边，查看是否存在一条边被所有的标记覆盖且边权大于等于路径长度最大值与 $d$ 的差。

E 通配符匹配

题意

几乎所有操作系统的命令行界面（CLI）中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号（*），可以匹配 0 个及以上的任意字符：另一个是问号（?），可以匹配恰好一个任意字符。现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。

对于 $100 \%$ 的数据

• 字符串长度不超过 $100000$
• $1 \le n \le 100$
• 通配符个数不超过 $10$

分析

注意到通配符个数不超过 $10$，所以我们尝试从这里入手。首先我们可以把模式串用通配符分割成 $h$ 段，其中每一段为确定的字符串或第一个字符为通配符剩下的字符为字符串。例如 a*b?c 会被分割为 a、*b 和 ?c 三部分。

定义状态 $f_{k, i}$ 表示待匹配串在第 $i$ 个字符处能否匹配到第 $k$ 段结尾。

接着考虑如何转移。我们用 $\mathrm{str}$ 表示模式串， $s$ 表示待匹配串，$\mathrm{pos}_k$ 表示第 $k$ 段结尾位置，$\mathrm{len}_k$ 表示第 $k$ 段长度。

若第 $k$ 段为确定的字符串，那么直接匹配再从前一段转移即可，即 $f_{k, i} = [f_{k - 1, i - \mathrm{len}_k} \wedge \mathrm{str}_{\mathrm{pos}_k - \mathrm{len}_k + 1, \mathrm{pos}_k} = s_{i - \mathrm{len}_k + 1, i}]$。

若第 $k$ 段为开头为 ? 的字符串，那么直接匹配确定的部分，再跳过前一个字符转移即可，即 $f_{k, i} = [f_{k - 1, i - \mathrm{len}_k} \wedge \mathrm{str}_{\mathrm{pos}_k - \mathrm{len}_k + 2, \mathrm{pos}_k} = s_{i - \mathrm{len}_k + 2, i}]$。

若第 $k$ 段为开头为 * 的字符串，那么直接匹配确定的部分，再跳过若干字符转移即可，即 $f_{k, i} = [\exists(j \le i - \mathrm{len}_k + 1 \wedge f_{k - 1, j}) \wedge \mathrm{str}_{\mathrm{pos}_k - \mathrm{len}_k + 2, \mathrm{pos}_k} = s_{i - \mathrm{len}_k + 2, i}]$。

匹配用字符串哈希即可。

I Mex Game

题意

给定一个长度为 $n+1(1 \le n \le 2 \times 10^5)$ 的字符串 $s$。共 $n$ 轮游戏，第 $i$ 轮进行 $i$ 次操作，每轮均由 Alice 先，与 Bob 交替往集合 $X$ 中加入非负整数（一次加入即一次操作）。对于每一轮，记 $x=\mathrm{mex}(X)$，若 $s_x$ 为 $\texttt{A}$ 则 Alice 胜，反之 Bob 胜。对于每一轮，输出谁胜。

分析

集合 $A$ 中的数不可能成为 $x$，所以两人的策略都是不断加入下一个另一个人的字母出现的位置。又因为操作 $i$ 次后，$x$ 可能出现的范围为 $[0, i]$。所以我们只需要统计 $[0, i]$ 中 $\texttt{A}$ 和 $\texttt{B}$ 出现的次数。如果对方字母出现的次数比自己能操作的次数多则输。

K Tree Edges XOR

题意

$n$ 个点，$m$个询问。

给你一棵树的括号序列，输出它的直径。

有 $m$ 次询问，每次询问表示交换两个括号，输出交换两个括号后的直径（保证每次操作后都为一棵树）

输出共 $m+1$ 行。

$3 \le n \le 100000, 1 \le q \le 100000$

分析

括号序列相当于表示了一次 $\text{DFS}$ 遍历树，($ 表示进入子树，) 表示回到父亲。那么一条路径的长度就是一段形如 )))))((( 的字符串的长度。

考虑用线段树维护这个序列。假设答案由两个区间合并而来，左边由 $a$ 个 (，$b$ 个 ) 组成，右边由 $c$ 个 (，$d$ 个 ) 组成。那么合并后的答案就是 $a + |b - c| + d$。这里用了一个重要的技巧，用 $\max$ 来去绝对值。$a + |b - c| + d = \max(a + b - c + d, a - b + c + d)$。我们令 $x = a + b$，$y = a - b$，$p = d + c$，$q = d - c$。那么答案就是 $\max(x + q, y + p)$。也就是说，

• $x$ 表示一段区间后缀括号合并后 ) 与 ( 和的最大值
• $y$ 表示一段区间后缀括号合并后 ) 与 ( 差的最大值，
• $p$ 表示一段区间前缀括号合并后 ( 与 ) 和的最大值
• $y$ 表示一段区间前缀括号合并后 ( 与 ) 差的最大值

再考虑如何维护 $x, y, p, q$。

这里以 $x$ 为例。对于线段树上一个节点，$x_p$ 可以直接从右儿子拿来，即 $x_p = x_{rs}$，也可以跨越区间 $x_p = a_l + |b_l + l_r| + r_r$，其中 $l, r$ 表示一个区间合并后 ) 和 ( 的数量。我们用相同的手法去掉绝对值 $a_l + |b_l + l_r| + r_r = \max(a + b - l_r + r_r, a - b + l_r + r_r) = \max(x_l - l_r + r_r, y_l + l_r + r_r)$。这样我们就维护出了 $x$。剩下的同理，我们就用 $x, y, p, q, l, r$ 不断向上合并求出树的直径。

NEUACM 2025 Winter Training 3 题解

B「TAOI-3」终有一天，飞向水平线的彼方

题意

原题链接：https://oier.team/problems/X8C。

Mio 有一个长度为 $n$ 的正整数数列 $a_1, \ldots, a_n$。她会对这个序列进行若干次操作，每次她会选择一对正整数 $l,r$，满足 $1 \le l \le r \le n$，且 $(r-l+1)$ 为偶数，然后进行以下两种操作中的一种：

• 对于所有整数 $i \in [l,r]$，令 $a_i \gets a_i+\left(|i-\frac{r+l}{2}|+\frac{1}{2}\right)$。
• 对于所有整数 $i \in [l,r]$，令 $a_i \gets a_i-\left(|i-\frac{r+l}{2}|+\frac{1}{2}\right)$。

形象化地，你可以把这理解为，选择某区间内最中间的数作为中轴，然后把区间内的所有数加上或减去它与中轴的距离。例如，如果选择 $l=1$，$r=8$，效果就是把数列的前 $8$ 个数分别加上或减去 $4,3,2,1,1,2,3,4$。

在 Mio 的操作中，她希望任意时刻数列里的所有数都是正整数。

现在，Mio 想要知道，能否用这样的操作把数列 $a_1, \ldots, a_n$ 变成目标正整数数列 $b_1, \ldots, b_n$。

对于所有数据，保证 $1 \le T \le 5$，$1 \le n \le 10^5$，$1 \le a_i,b_i \le 10^9$。

分析

首先非负是不用考虑的，可以先做完所有的加操作再做减操作。

然后我们注意到所有的 $r - l + 1 > 2$ 的操作都可以分解为一些 $r - l + 1 = 2$ 的操作。因为原先的操作是一个“凹”的形状，可以看作是一整块减去一个“凸”的形状，而“凸”的形状是可以用 $r - l + 1 = 2$ 的操作拼出来的。

那么我们的做法就显然了，只需要从左到右把 $[1, n)$ 范围内的数通过 $r - l + 1 = 2$ 的操作变成我们需要的数再看最后面的数有没有变成我们要的数。

G 超立方体

题意

$D$ 维空间内的超立方图有 $2^D$ 个点，我们把这些点从 $0$ 到 $2^D-1$ 依次编号。

有一个有趣而重要的充要结论是：一定存在一种编号的方式，使得图中任意两个有边相连的顶点的编号的 $2$ 进制码中，恰好有一位不同。

在2维和3维空间内这个结论可以这样形象的理解：对于 $2$ 维空间，我们只要把这个正方形放到第一象限内，使得 $4$ 个顶点的坐标按逆时针顺序依次为 $(0,0),(1,0),(1,1),(0,1)$，然后再把坐标看成 2 位 2 进制数，依次将这 4 个点编号为 $0,1,3,2$ 即可。

对于 $3$ 维空间，同样我们可以将立方体的一个顶点与原点重合，并使得所有棱均平行于坐标轴，然后分别确定这 $8$ 个点的坐标，最后把 $3$ 维空间内的坐标看成一个 $3$ 位 $2$ 进制数即可。对于 $D$ 维空间，以此类推。

现在对于一个 $N$ 个点 $M$ 条边的无向图（每个点从 $0$ 到 $N-1$ 编号），Will 希望知道这个图是否同构于一个超立方图。

$Q~\leq~3,~N~\leq~32768,~M~\leq~1000000$

分析

对于一个 $D$ 维的超立方体，点数 $n = 2 ^ D$，边数 $\displaystyle m = \frac{nD}{2} = \frac{D 2^D}{2}$。我们可以先用以上公式简单判断。

具体如何判断，我们可以发现原点的选取是任意的，维度的顺序也是任意的。所以，我们可以尝试把某一维度的边全部删去，将超立方体划分成两个不连通的 $D - 1$ 维超立方体，然后递归判断。

具体来说，任选一条边断开，将两个点分别放入 $A$ 和 $B$ 两个集合。我们从 $B$ 中选择未配对的点 $p$ 与 $A$ 集合中的点配对，即看点 $p$ 是否有边与 $A$ 中的点相连，若有且仅有一条，那么这一对点就配对了。假设配对的点为 $q$，根据超立方体的性质，一个点有且仅有一个配对点，那么剩下的相连的点就是属于各自集合的了。也就是把与 $p$ 相连的其他点放入 $B$，与 $q$ 相连的其他点放入 $A$。如果不存在这样的点或者存在不止一个，那么说明这个图不是超立方体。这样不断重复就将整个超立方体分成了两个规模较小的超立方体，递归判断。

J Erasing Vertices

题意

给定一个点数为 $n$ $(1 \le n \le 100)$ 的有向图。

等概率随机选定一个还未删除的点 $x$，删除 $x$ 以及图中 $x$ 能通过某些路径到达的点（指向这些点的边也会被删除）。如果图中没有任何未被删除的点，则结束操作，否则重复此操作。
求期望做多少次操作（与标准答案的误差不超过 $10^{−9}$）。

分析

假设随机变量 $X_i$ 表示操作完后点 $i$ 是否被选中过。那么，我们所求的就是 $\displaystyle E (\sum X_i)$。

难点在于如何求 $P(X_i)$。

首先我们可以发现如果一个点 $j$ 无法到达 $i$，那么 $j$ 是否选取与 $i$ 无关。也就是说 $P_i$ 只与能够到达 $i$ 点有关。这个问题可以看作 $n$ 个球，其中有一个球 $i$，$m$ 个 “重要” 的球，剩下的是无关的球。每次从中抽取一个，若是无关的球则接着抽取。求最后抽到 $i$ 的概率。这里 “重要的球” 就相当于可以到达 $i$ 的点。我们稍加分析就能够得出 $P(X_i) = \displaystyle \frac{1}{m + 1}$，其中 $m$ 是可以除开 $i$ 自己外可以到达 $i$ 的点的数量。

知道了这个结论剩下的就是求可以到达 $i$ 的点的数量，可以 $\text{BFS}$ 或者传递闭包解决。

K Tree Edges XOR

题意

给定一棵 $n$ 个结点的树，保证 $n$ 是奇数，边有边权 $w_{i,1}$。现在你可以任意次把与一个边相连的其他边的权值异或上这条边的权值，求是否可以让每条边的边权变为 $w_{i,2}$。

$n \le 10^5$，$w \le 2^{30}$。

分析

本题突破口：化边权为点权，使得某条边的边权为连接的点的点权异或。

我们发现这样转化后，操作相当于交换两个点的点权。

我们令根点权为 $0$，算出其他点的点权，然后就是要判断能否转化。由于我们的根的点权钦定为 $0$，所以不能直接比较两个集合是否相同。我们发现，如果此时我们改变根的点权为 $x$，那么其他点的变化就是异或上 $x$。假设此时点权为 $a_i$，期望是 $b_i$，我们就是要判断是否存在一个 $x$，使得集合 $\{a_i \oplus x\} = \{b_i\}$

由于 $n$ 为奇数，所以我们可以通过 $\oplus_{i \le n} (a_i \oplus x) = x \oplus_{i \le n} a_i = \oplus_{i \le n} b_i$ 来解出 $x$。然后带入回去判断集合是否相等。

L Bitwise Slides

题意

给定一个长度为 $n$ $(n \le 10^5)$ 序列 $a_i$，三个初始为 $0$ 变量 $P$、$Q$ 和 $R$，从左到右遍历序列，每一要选一个变量异或当前的数，要求任意时刻三个变量不可以两两不同。问合法方案数。

分析

定义异或前缀和 $\text{pre}_i = \oplus_{j \le i} a_j$。那么任意时刻有 $P \oplus Q \oplus R = \text{pre}_i$。并且由于任意时刻三个变量不可以两两不同，那么至少有两个变量相同，而相同的变量异或为 $0$，说明至少有一个变量为 $\text{pre}_i$ 且剩下两个变量相同。

定义状态 $f_{i, x}$ 表示操作完前 $i$ 个数，另外两个数为 $x$ 的方案数。

我们不妨设这三个数为 $(x, x, y)$，说明 $y = \text{pre}_i$，那么这三个数只有可能从 $(x, x, z)$ 或 $(x, y, y)$ 转变而来。对于前者 $z = \text{pre}_{i - 1}$，有转移 $f_{i,x} = f_{i - 1, x}$。对于后者，说明 $x = \text{pre}_{i - 1}$，有转移 $f_{i, x} = 2 \times f_{i - 1, y}$。此外，还有一个细节是 $z = x$ 时，也就是 $x = \text{pre}_{i - 1}$，第一个转移应该是 $f_{i,x} = 3 \times f_{i - 1, x}$

综上我们发现，只有在 $x = \text{pre}_{i - 1}$ 时，转移比较特殊，其他情况下，都是复制上一状态。所以我们可以用 $\text{std::map}$ 来存储状态，每次只更更新 $x = \text{pre}_{i - 1}$ 的状态。

答案就是 $\text{std::map}$ 中元素的和。

NEUACM 2025 Winter Training 2 题解

D 松鼠聚会

题意

二维平面上 $n$ 个点。求其中一个点使得其他点到该点的切比雪夫距离之和最小。

$0 \le n \le 10^5$。

分析

切比雪夫距离含有 $\max$，难以维护。考虑通过坐标变换

将切比雪夫距离转化为曼哈顿距离求解。

对于点 $(x_i, y_i)$，其他点到该点的距离和为：

将坐标排序后计算即可。

E ABB

题意

求使给定小写字母字符串成为回文串需在字符串末尾加入字母的最少数量。

字符串长度 $\text{len} \le 4 \times 10 ^ 5$。

分析

当然可以用马拉车解决。但是没必要。

题意转化后其实就是找字符串中最长的回文后缀，后缀不够明了，可以反转后转化为找前缀。根据回文串的性质，回文串反转后不变。所以我们就是在反转后的串中寻找最长的前缀使得它等于反转前的后缀。这启发我们用 $\text{KMP}$ 算法求解，我们将反转后的字符串拼接到原字符串前，我们要找的就是 $\text{next}_{2n}$。但是有可能此时 $\text{next}_{2n} > n$，为了避免这种情况，我们在中间添加一个特殊字符即可。

H 图腾

题意

给定一个 $1 \sim N$ 的排列。

求满足

的四元组个数与满足

或

的四元组个数的差。

对于 $100\%$ 的数据，$N ≤ 200000$。

以下是两种四元组的图形。

分析

每个四元组都难以单独计算，而问题要求我们算它们的差，所以，我们尝试用容斥把式子变形，消去不好算的部分。

定义 $[abcd]$ 表示符合相对大小关系四元组的数量。例如 $[1234]$ 表示单调递增的四元组的个数。

这个式子的推到还是很有技巧性的。我们发现通过两位去凑，总能消除一个共同的四元组。
比如如果你想要消去 $[1234]$，那么 $[1324] - [1243]$ 可以变形为 $([1xx4] - [1234]) - ([12xx] - [1234])$ 来消去。
多试几次消去不同的项就能凑出来。

到这里问题解决的一半，剩下难点在于如何计算每一项。

对于 $[1xxx]$ 和 $[1234]$ 还是很好计算的，这里不再赘述。

对于 $[1x2x]$，我们可以枚举 $2$ 出现的位置。

对于 $2$ 右边的 $x$ 容易处理，只需要乘上右边大于 $a_i$ 的个数。
左边相当于要求 $[132]$。并且此时我们只能枚举最右边 $2$ 的位置。

我们再次尝试容斥原理计算。我们发现，我们可以算出满足左边两个数至少存在一个小于 $a_i$ 的三元组个数为 $\tbinom{i - 1}{2} - \tbinom{G_i}{2}$，其中 $G_i$ 为左边大于 $a_i$ 的元素个数。
满足这样的三元组的和为 $[123] + [132] + [213] + [312]$。
其中 $[123]$ 很好算， $[213]$ 和 $[312]$ 可以就是求左边有多少个右端小于 $a_i$ 的“下降”，可以通过树状数组计算。

对于 $[13xx]$，我们发现将这个排列求逆后正好是 $[1x2x]$！我们只需要把原排列求逆再用 $[1x2x]$ 的方法计算即可。

I Triangle

题意

给出一个正整数 $S$ $( 1 \le S \le 10^{18} )$，你需要找出三个 $[0,10^9]$ 范围内的点。
使得构成的三角形面积是 $\displaystyle \frac{S}{2}$。

分析

可以固定一个一个点为 $(0, 0)$。剩下两个坐标为 $(x_1, y_2)$、$(x_2, y_2)$。

我们让 $x1$、$y2$为 $\left\lceil\sqrt{S}\right\rceil$，调整 $x2$、$y1$，即可完成。

J Shift and Flip

给你两个 $\text{01}$ 串 $A$ 和 $B$，你可以进行以下 $3$ 种操作：

1. 将 $A$ 左移一位（如 $\texttt{0011} \rightarrow \texttt{0110}$）。
2. 将 $A$ 右移一位（如 $\texttt{0011} \rightarrow \texttt{1001}$）。
3. 选择一个满足 $B_i = 1$ 的位置 $i$，令 $A_i = 1 - A_i$。

问要使 $A$ 和 $B$ 相等至少要进行几次操作。

$\text{len}_A, \text{len}_B \le 2000$。

分析

显然如果 $A$ 中有 $1$，而 $B$ 中没有 $1$，问题无解。

显然如果 $A$ 和 $B$ 中都没有 $1$，答案为 $0$。

下面我们只需要解决 $B$ 中至少有一个 $1$ 的情况。
通过简单分析，我们可以将整个过程总结为以下三步。1. 去往第一个小修改的位置；2. 沿着一个方向不断修改；3. 将 $A$ 和 $B$ 对齐。

我们可以想象有一个初始为 $0$ 计数器，当左移时计数器减 $1$，右移时计数器加 $1$。
我们定义整个过程中计数器的最小值为 $l$，最大值为 $r$，最后的值为 $d$。
根据我们刚才的分析，整个过程要么是“左右左”，要么是“右左右”，那么整个移动的距离就是 $2 \times (R - L) - \left|d\right|$。

下面我们不妨设过程为“左右左”来解决，对于“右左右”我们可以将 $A$ 和 $B$ 反转后用相同的方法解决。

我们先预处理出 $\text{pre}_i$ 和 $\text{suf}_i$ 分别表示 $B$ 中 $i$ 左边和右边第一个 $1$ 与 $i$ 的距离。
然后我们可以枚举 $d$，来确定 $l$ 和 $r$。
我们扫描 $A$ 串，若 $A_i \ne B_{(i + d) \bmod n}$ 则说明该位置要反转。
若 $\text{pre}_{(i + d) \bmod n} \le d$，则说明我们可以在右移的过程中某个位置将这一位修改。
否则，说明我们需要在一开始多左移或右移几位来修改这一位。

如果要通过左移修改，那么要满足 $\displaystyle -l \ge \text{pre}_i$；

如果要通过右移修改，那么要满足 $\displaystyle r \ge d + \text{pre}_{(i + d) \bmod n}$。

这样我们就有了若干个约束条件，优化的目标是让 $r - l$ 尽可能小。
我们通过图像来解决这个最优化问题。我们将所有的条件画在坐标系中，发现是若干 $\displaystyle \frac{3}{4}$ 平面交。
我们可以排序后用单调栈保留相交后最外边的 $\displaystyle \frac{3}{4}$ 平面，在交点处求解。

复杂度 $\mathcal{O}(n^2 \log n)$。如果用桶排可以优化到 $\mathcal{O}(n^2)$。

NEUACM 2025 Winter Training 1 题解

F 炸弹

题意

在一条直线上有 $n$ 个炸弹，每个炸弹的坐标是 $x_i$，爆炸半径是 $r_i$，当一个炸弹爆炸时，如果另一个炸弹所在位置 $x_j$ 满足：
$|x_j-x_i| \le r_i$，那么，该炸弹也会被引爆。

现在，请你帮忙计算一下，先把第 $i$ 个炸弹引爆，将引爆多少个炸弹呢？

答案对 $10^9 + 7$ 取模。

分析

注意到一个炸弹爆炸后引发的爆炸区域是连续的。如果我们可以求出每个炸弹爆炸后引发的爆炸区域的做右端点，则引爆的炸弹数为区域中炸弹的个数。

定义 $l_i$ 和 $r_i$ 分别表示第 $i$ 个炸弹爆炸后引发的爆炸区域的左端点和右端点。

那么有 $l_i = \min \left(x_i - r_i, l_j \right)$ 其中 $|x_j - x_i| \le r_i$。

这个式子我们可以借用 $\text{dijkstra}$ 算法的思想，先计算 $x_i - r_i$ 最小的炸弹 $l_i$，也就是 $x_i - r_i$。然后再用它去更新其他可以引发它的炸弹的 $l_i$，然后再取 $l_i$ 最小的去更新可以引发它的……

还有一个问题是能够引发某个炸弹的炸弹很多，如果每个都去更新则复杂度很高。实际上，我们只需要去更新某个炸弹左边的第一个能够引发这个炸弹的炸弹，以及右边的第一个能够引发这个炸弹的炸弹。这样更新是可以不断延续下去而不影响正确性的。

每个炸弹会更新左右两个可以引发它的炸弹，每次更新后的 $l_i$ 加入优先队列。复杂度 $\mathcal{O}\left(n \log n \right)$。

G 病毒

题意

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：

例如如果 $\{011, 11, 00000\}$ 为病毒代码段，那么一个可能的无限长安全代码就是 $010101 \ldots$。如果 $\{01, 11, 000000\}$ 为病毒代码段，那么就不存在一个无限长的安全代码。

现在给出所有的病毒代码段，判断是否存在无限长的安全代码。

$1 \leq n \leq 2000$，所有病毒代码段的总长度不超过 $3 \times 10^4$。

分析

我们把所有的代码段放到 $\text{trie}$ 树上建立 $\text{AC}$ 自动机。对于一个不含病毒的代码，它在 $\text{AC}$ 自动机上的转移不会经过病毒代码的结尾节点。也就是说，我们需要在 $\text{AC}$ 自动机上从根节点出发找一个环。

一个细节是，如果一个节点的 $\text{fail}$ 树上经过病毒节点，则该节点也是病毒节点。

J Adventurers

题意

二维平面上 $n$ 个点，要求把他们用一个十字分为四部分，使得点最少的部分的点数量尽可能大。

数据范围： $n \le 10^5$。

分析

将点按照某一维排序，这里我们都用 $x$ 来排序。将十字的竖线从左往右扫，此时我们以及将点分为两部分，只需要确定横线的值来使得最少部分的点尽可能大。考虑二分答案，对于左右的任意部分，当答案确定后，我们也就可以确定横线可以存在的区间。我们将左右两部分的区间相交，看是否为空。

确定区间可以用平衡树实现，复杂度 $\mathcal{O} \left( \log n \right)$，二分复杂度 $\mathcal{O} \left( \log n \right)$，扫描复杂度 $\mathcal{O} \left( n \right)$，总复杂度 $\mathcal{O} \left( n \log^2 n \right)$。

N - Graph Subset Problem

题意

$T$ 组数据。

给你一个有 $n$ 个顶点和 $m$ 条边的无向图，和一个整数 $k$。

请你找到一个大小为 $k$ 的团（称一个 $k$ 个点的集合为团，当且仅当点集大小为 $k$，并且该子集的每两个顶点之间存在一条边。）或一个非空的顶点子集，使该子集的每个顶点在该子集中至少有 $k$ 个邻居。

输出方案。

对于每个测试用例：

• 如果找到一个合法点集，在第 $1$ 行输出 1 和子集的大小。在第 $2$ 行，以任意顺序输出子集的顶点。
• 如果找到一个大小为 $k$ 的团，那么在第 $1$ 行输出 2。第 $2$ 行中，以任意顺序输出该团的顶点。
• 如果没有所需的子集和集团，请输出 -1。
• 如果存在多个可能的答案，输出其中任意一个。

分析

分析团和合法点集的特点，团要求每个点有 $k - 1$ 条边，点集要求每个点有 $k$ 条边。也就是说，所有度小于 $k - 1$ 的点都可以删去。

按照这个想法，我们先删掉度小于 $k - 1$ 的点。此时图中每个点的度数都大于等于 $k - 1$。若所有点度数都大于等于 $k$ 那么当前的图就是一个合法的点集。否则我们找到一个度为 $k - 1$ 的点，判断这和点和与它相连的所有点是否在一个团中。如果符合则输出，否则删去这个点，重复上述过程。

判断一个点集是否是一个团，我们可以直接暴力判断每个边是否存在。对于某条边，可以在其中一个节点的出边中二分查找另一个节点。所以，对于一个大小为 $k$ 的点集，判断的时间复杂度为 $\mathcal{O}\left( k^2 \log m \right)$。上述算法中每次循环都会至少删掉一个度数为 $k - 1$ 的点，循环次数为 $\displaystyle \frac{m}{k - 1}$。所以总的时间复杂度为 $\displaystyle \frac{m}{k - 1} \times k^2 \log m = \mathcal{O} \left( mk \log m \right)$。看似无法通过，但是，我们注意到团的边数为 $\displaystyle \frac{k(k - 1)}{2}$，当 $m < \displaystyle \frac{k(k - 1)}{2}$ 时，我们并不需要判断是否出现团。所以复杂度为 $\mathcal{O} \left( m \sqrt{m} \log m \right)$。

O Greedy Shopping

题意

给定一个大小为 $n$ 的非升序列 $a$ 。

现在有两类操作，

1 x y ， $\forall i\in[1,x],a_i=\max(a_i,y).$

2 x y ， 从下标 $x$ 开始，从左往右访问序列 $a$ ，如果 $a_i\le y$ ，则 $\text{answer}++,y=y-a_i$ 。

对于每一次操作 $2$ ，输出 $\text{answer}$ 。

提示

分析

根据以上提示可以想到用线段树维护序列区间左端点值，右端点值，区间和。

对于操作 $\text{1}$，如果当前区间最小值大于 $y$，则无需修改，否则递归下去修改，复杂度 $\mathcal{O} \left( \log n \right)$。

对于操作 $\text{2}$，我们可以线段树上二分找到第一个可以统计的元素，然后再线段树上二分找到统计的区间右端点，不断重复上述过程找到所有统计的区间。复杂度 $\mathcal{O} \left( \log^2 n \right)$。

2024 下半年回忆录

前言

又到了半年一度的回忆录总结，2024 下半年对我真是不平凡的半年，但也有可能每个半年对我来说都不是平淡的。人生到处知何似，应似飞鸿踏雪泥。下半年借着打 XCPC 赛事的机会，去了很多之前没有去过的城市，在能力和眼界等方面都有不小提升。

虽说是 2024 年的回忆录，但当我真的开始码字，已经是大年初九，一方面是因为想要把一整个学期和寒假都包括在回忆录中，另一方面也是时间比较有限，没有太多无事可做的空闲来完成这篇回忆录。但是现在因为校队集训需要提前返校，我可以有机会在去往沈阳的动车上有充足的时间完成这篇回忆录。

暑假

整个八月，我都在参加学校的暑假集训。虽然已经搞了六年算法竞赛，但是从来没有如此系统，如此大强度地训练。从每天上午九点开始一直到晚上九点，除去吃饭时间一直都在机房训练。八月的沈阳雨水非常多，记得在一次下大雨把鞋湿了个透之后，就开始穿拖鞋去训练，没想到拖鞋与雨天是如此搭配。

训练的内容虽然大部分早已学过，但是还是收获颇丰。对于字符串这类我以前没有学习动力的东西重新系统性地学习，感觉也没有想象中那么枯燥。

训练期间与队友组队参加了牛客多校，因为参加比较晚，只参加了后半程的六场比赛，但是发挥还不错，在最终的排名出来后也为队伍赢得了下半年比赛的名额。

九月

九月正式开学后，课程十分繁忙，还要抽出时间训练，感觉每天都很累，而且很难说是否有提升，感觉学校的课程可以进一步优化。

九月比较重要的事就是奖学金的评定，我本以为凭借 rk2 的排名和竞赛还是很轻松的，结果发现我从未参加各种活动，志愿时长也少得可怜，与各种奖学金基本无望。这让我十分不满，但是也没什么办法，毕竟“规则就是规则，又不是今天定的”。但是我还是对学校、国家的奖学金评价体系深为不满。在我看来，奖学金应当提升成绩的占比，可以按照保研的占比来。但这也是我的“想象”罢了。

济南站

十月开始了第一场 CCPC 的比赛。我们依然选择了上半年来过的济南站。这次是白天在济南参观，白天济南的大小泉眼更加晶莹剔透，水底的水草清晰可见。

比赛的过程也相对顺利，把该做的题做完正好是银尾。

重庆站

第二次 CCPC 选择了重庆，是为了避开各种考试和对报名人数分析后定的。

但是重庆遇上清华出题，被数学场狠狠薄纱，遗憾打铜。

上海站

第一场 ICPC 选择上海，理由也没什么，主要想到上海玩。结果听学长说年年的上海站竞争都很激烈，感觉似乎有点博弈失败。

去上海的航班由于天气延误起飞，途中也是异常颠簸，给我留下很大心理阴影。

下飞机后坐了磁悬浮到市中心，感觉磁悬浮没有想象中那么好，和高铁似乎没什么乘坐体验上的区别。

由于上海天气，陆家嘴根本看不到什么夜景，就连东方明珠也埋入的雾气当中，只能草草拍照打卡。

在各种 debuff 下，比赛的结果居然还不错，再次守住了银牌，这也是最惊心动魄的一次滚榜。

整个上海站似乎有一种欲扬先抑的感觉。

昆明站

如果是上海站是欲扬先抑的话，昆明站就是欲抑先扬了。

赛前各种博弈选到昆明站，希望在大赛站有所成绩。

到了昆明后，见识到了滇池的海鸥，令人心驰神往。

但是赛场上却十分坐牢，没有人开出来题，遗憾打铁。

西安站

在昆明打铁后的一个月，我狠狠加训，希望在西安站有所发挥。

但是似乎我们还是过于低估 EC-final 的强度，再次被数学题卡住，遗憾打铁。

感觉自身实力还不足以在 EC-final 拿奖，还是要加训。

期末

这次期末周因为之前的比赛复习时间十分有限，但是我似乎已经锻炼出了应付考试的能力。

考试过程十分平静，把该拿的分拿到。

成绩也不错，概率论能满绩出乎我的预料，各种思政课却不堪入目，最后分数对冲，绩点也是 4.3 没什么太大变化。

寒假

寒假被同学拉去打数模，除夕前一直在对着我们那个难蚌的模型调来调去，不止结果如何。

但是我最在乎的还是和高中的“鼠友”们去玩，结果大家时间都不是很充裕，最后在我返校的前一天才能抽出时间出去玩。

2024 上半年回忆录

前言

又到了一年一度的总结时间。话说“回忆录”这一系列不过是源于去年一时兴起想把美好的时光记录下来所写的一点文字，没想到反响不错，从此便成为我的博客的固定栏目。

不过写回忆录也不光是为了读者的反馈和阅读量。若真以此为目的，怕不是博客都没必要写了😂。回忆录更多的是为了让我铭记过去半年的经历，总结过往，规划未来。

现在呢是 2024 年的 8 月 27 日。去年的 8 月 26 日我到东北大学报道，同时也写下了那篇《暑假回忆录》的第一个字。如今，一年过去，再次读来，仍会让人不禁露出微笑，这也是写回忆录的一大乐事。

好了，废话疑似有点过多了。这次的回忆录记录的是今年 2 月至 8 月的一些故事，让我们开始吧！

二月的尾巴

二月底返校前为了应对选修的电子积木课程稍微看了看 arduino 的一些内容。arduino 本身的内容自然是十分简单。之前看有一些显示器有类似于“神光同步”屏幕内容的功能感觉十分震撼，便尝试自己用 arduino 实现一下，就是采样屏幕边缘的颜色再映射到灯带上，没什么技术但是效果还不错。后面又迷上了画板子，用嘉立创做了一个最小系统板。又用免费的打样次数打了样，效果还不错。

之后呢就踏上了返校的列车。

学业

学业部分主要是对这个学期学习的总结，不喜欢建议直接跳过。

攒机

开学后先给自己装了个电脑，靠着上个学期攒的一些钱和父母的资助成功装了一台白色海景房。捡了这么多年洋垃圾总算能用一次正统酷睿了。先马的新视界机箱确实好看。12400f 的 U 也是够用了，捡了一个 6800xt 的久经沙场老兵用的也是十分舒适。

课程

这个学期有三门理学院的课，高数、线代、大物。看起来十分棘手。一开始有点摆，不是很能消化，大物平时的雨课堂测验错了不少。好在期末周狠狠学，成绩还可以。专业课 C++ 就是手到擒来了。课设通过我连着通宵也是拿下。选修只学了 arduino，由于寒假的积淀也是轻松拿下。本来还选了几个选修，但是都是第一次课就给了我极大的震撼，速速退课了。体育课摸摸鱼划划水过去了。英语课自知实力有限，便努力与老师搞好关系，寄希望于老师好好捞。

期末周

不知是哪个人才能想出把大物、高数、线代排在连续的三天进行考试，导致我复习时需要在三门课程之间反复横跳。

第一天大物考试内容不难，唯一一道卡了的题用高斯定理就能算出，而我甚至是积了一个反常积分算了出来。好在有惊无险。

第二天高数考试也是没有很卡的题目，都会做就是怕计算错误，本来快要做不完了，结果一看压轴题是见过的原题，一下秒了，卡点交卷。本来自信满满，结果一对答案发现拉格朗日乘数法的题看错题了，第一步就没了🤡。直接心跌倒了谷底。

第三天线代更是易如反掌，甚至是没有证明题。随便写完检查就交了。

后面考英语就是完全云里雾里了，听力更是无从下手，出来考场以为要挂了。😭

成绩

英语考完发现大物出分了，甚至是期末满分，只有雨课堂扣了分，感觉好亏。

后面又出了线代，满分预料之中。只是慕课有些许扣分。

一日晚上出了高数，甚至是 95，感谢老师狠狠捞。

英语给了我最大的惊喜，给了 90 分，令人忍俊不禁。

最后绩点也是接近 4.3，全院第二。超额完成学期开始订的目标。

本来只是想好好提一下绩点，没想到给了我如此大的惊喜，这下可以期待一下奖学金的事情了。😂

竞赛

上半年打的比赛有天梯赛和邀请赛。

天梯赛被一道字符串题搞到心态爆炸，给学校拖了后腿，现在想起仍是难以平复，唯有努力训练来弥补了。😭

邀请赛打了 CCPC 济南邀请赛。

5 月 24 日，飞往济南，本来想和 rx 面基，结果发现山大有活动不让参观。

本来以为此时就此作罢，没想到第二天出现了转机。我们凭借比赛的邀请函成功进到山大，这里不得不表扬山大的包容。在 rx 带领下成功参观了大名鼎鼎的山大数学系。中午在山大食堂吃了山东特色把子肉，太好吃了。

下午热身赛。会场十分气派，看出来组织者对于比赛的重视。

晚上在学长带领下夜游济南。泉城的夜晚水光相映。济南作为一个北方城市，五步一泉，十步一湖，十分神奇。

第二天正式赛也是十分顺利，我自己做了一道构造，一道 DP。最后顺利拿下银牌。不过是邀请赛，没什么用。

暑假校队集训，基本每天都在训练，也没什么好说的。不过牛客多校打得还行，下半年应该有比赛可以打。

娱乐

京吹3

盼望着，盼望着，四月来了，《吹响吧，上低音号》第三季开播。作为我少数关注的番之一，我本想借最后一季与它告别。结果在第十二集播出后，平稳的告别已再无可能。播出后的那一周整个人都比较懵，没想到现实中的回旋镖从番剧中向我飞来。不过如今想想也就释怀了，我也不想过多评价。当时的热情也随之消散。不过还是买了第三季的 CD，毕竟音乐还是要听的。

OSU

OSU 在一次更新后，PP 计算方式变了，涨了很多。这个学期由于学习压力较大，没怎么打，PP 没什么进步，不过也无所谓了，玩音游自己开心就好。

黑神话

从初中开始期待的黑神话，实际上手还是十分震撼，但是后面游玩的欲望并不强烈。感觉最近对各种娱乐都没有兴趣，不过也挺好的，把时间放在正事上没什么不好。

最后一点感想

这次的回忆录不是很长，感觉上半年的经历不是很多，主要还是学习和竞赛占了大部分，所以也没什么可说的。

过去一年，感觉自己变化还是很大的。许多事情真正了解后反而更加迷茫。根本原因还是学识太少，还是要多学一点才好看清未来的方向。

最后还要说的是，由于暑假集训没有回家，希望国庆可以回家待几天，要是能和“鼠友”见面那就更好了，这算是近期的一个小计划吧。

半年后见!

CCPC2022威海站 B题 Recruitment 题解

题目大意

原题链接

初始有一个由 个正整数组成的形如 的式子, 个操作每次将其中一个加号改为乘号. 现给出初始的式子和每次修改后的式子的值 , 求原来的 个正整数以及每次操作的符号的位置. 输出任意方法即可, 无解输出 .

数据范围： .

提示

解法

如果我们将一次修改理解为将加号两侧的数合并, 合并的数为原来两数的乘积, 就会发现问题实际是求一个可重集使得每次合并后集合中数的和等于 . 显然最后集合中只剩下 . 则最后一次合并前的两个数设为 满足 , 可以解方程求出这两数, 把这两个数放入集合. 考虑倒推, 我们每次枚举集合中的数尝试还原, 若成功则接着去找下一个要还原的数, 直到全部还原. 若当前集合中每个数都不能被还原, 说明我们当前的集合是错误的, 需要回退. 这一过程可以搜索解决. 但是 , 直接搜索复杂度很高. 注意到若 说明原来的两个数至少有一个是 . 我们将 中满足上述条件的剔除, 则剩下的操作前的两个数至少有一个大于等于 , 搜索层数会降到 层. 实际根本没有这么高.

还可以继续剪枝, 若当前用集合中某个数 分解后失败, 则当前层不需要再尝试用别的与 相等的值去分解, 可以用 std::map 记录是否还原过某个数剪枝.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define frep(i,a,b) for(int i=a;i<(b);++i)
#define drep(i,a,b) for(int i=a;i>=(b);--i)
#define ls tree[p].l
#define rs tree[p].r
#define mid ((l + r) >> 1)
typedef long long ll;
typedef unsigned long long ull;
#define Maxq priority_queue<int,vector<int>,greater<int> >
using namespace std;
const int MAXN = 1000010;
ll js(ll m, ll n){ //解方程 a * b = m, a + b = n
	if(n * n - 4 * m < 0) return -1;
	ll ans = (n + sqrt(n * n - 4 * m)) / 2;
	if(ans > 0 && n - ans > 0 && ans * (n - ans) == m) return ans;
	else return -1;
}
int n;
ll q[MAXN];
struct node{
	int w, t, l, r, siz;
}tree[MAXN]; //用二叉树记录每个数的还原
int endd;
int add(int w){
	tree[endd].w = w;
	tree[endd].t = -1;
	tree[endd].l = tree[endd].r = -1;
	++endd;
	return endd - 1;
}
void del(){
	--endd;
}
int sum;
int pre[MAXN]; //下一个要还原的操作位置
int id[MAXN]; //id[x]是x处操作再所有没有1的操作中的位置
int rt;
bool dfs(int p, int pos, map<int, bool> &mp){
	if(p == 1){
		return true;
	}
	if(tree[pos].l == -1){
		if(mp[tree[pos].w]) return false;
		mp[tree[pos].w] = true;
		int a = js(tree[pos].w, q[p - 1] - (sum - tree[pos].w));
		if(a != -1){
			tree[pos].t = id[p];
			tree[pos].l = add(a);
			tree[pos].r = add(tree[pos].w / a);
			int tmp = sum;
			sum -= tree[pos].w;
			sum += a + tree[pos].w / a;
			map<int, bool> mpp;
			if(dfs(pre[p], rt, mpp)) return true;
			else{
				del(); del();
				tree[pos].t = -1;
				tree[pos].l = tree[pos].r = -1;
				sum = tmp;
				return false;
			}
		}
		return false;
	}
	else{
		if(dfs(p, tree[pos].l, mp)) return true;
		else if(dfs(p, tree[pos].r, mp)) return true;
		else return false;
	}
}
void print1(int p){
	if(tree[p].t == -1){
		tree[p].siz = 1;
		cout << tree[p].w << " ";
		return;
	}
	print1(tree[p].l);
	print1(tree[p].r);
	tree[p].siz = tree[tree[p].l].siz + tree[tree[p].r].siz;
	return;
}
int out[MAXN];
void print2(int p, int len){
	if(tree[p].t == -1){
		return;
	}
	out[tree[p].t] = len + tree[tree[p].l].siz;
	print2(tree[p].l, len);
	print2(tree[p].r, len + tree[tree[p].l].siz);
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	rep(i, 1, n) cin >> q[i];
	int p = 1;
	int cnt = 0;
	pre[1] = -1;

    //去掉1
	rep(i, 2, n){
		if(q[i] - q[i - 1] == -1){
			++cnt;
		}
		else{
			pre[i] = p;
			id[i] = id[p] + 1;
			p = i;
		}
	}
	int cnt_ = cnt;
    //剔除1后更新
	rep(i, 2, n){
		q[i - 1] -= cnt_;
		if(pre[i]) continue;
		else cnt_--;
	}
	bool flag = true;
	rep(i, 2, n){
		if(q[i] <= 0){
			cout << -1;
			return 0;
		}
	}
	rt = add(q[p]);
	sum = q[p];
	map<int, bool> mp;
	if(dfs(p, rt, mp)){
		print1(rt);
		rep(i, 1, cnt) cout << 1 << " ";
		cout << endl;
		print2(rt, 0);
		int last = n - 1;
		rep(i, 2, n){
			if(pre[i]){
				cout << out[id[i]] << endl;
			}
			else cout << (last--) << endl;
		}
	}
	else{
		cout << -1;
	}
	
    return 0;
}

CF1970E3 Trails (Hard) 题解

题目

题目大意: 给定 个点. 每个点都和一个共同的中心点有若干条路径. 对于第 个点, 有 条短路径, 条长路径. 一个小人开始在 号点, 每天他要走两条路径到达一个点(可以和出发点相同), 要求每天走过的路径至少有一条长路径. 问走 天后, 所有合法路径的方案数.

思路

一个朴素的想法是递推.

设第 天在 号点的方案数为 .

则有

令 也就是

使用矩阵快速幂可以解决.

但是我们发现 我们甚至连一次矩阵乘法都做不完!

我们发现

这何尝不是一种矩阵乘法?

于是我们构造矩阵

那么

而 是一个二阶矩阵, 可以计算!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define frep(i,a,b) for(int i=a;i<(b);++i)
#define drep(i,a,b) for(int i=a;i>=(b);--i)
#define ls tree[p].l
#define rs tree[p].r
#define mid ((l + r) >> 1)
typedef long long ll;
typedef unsigned long long ull;
#define Maxq priority_queue<int,vector<int>,greater<int> >
using namespace std;
int mylog(int a){
	int ans=0;
	if(a&0xffff0000){
		ans+=16;
		a>>=16;
	}
	if(a&0x0000ff00){
		ans+=8;
		a>>=8;
	}
	if(a&0x000000f0){
		ans+=4;
		a>>=4;
	}
	if(a&0x0000000c){
		ans+=2;
		a>>=2;
	}
	if(a&0x00000002){
		ans+=1;
		a>>=1;
	}
	return ans;
}
inline int read(){
	register int a=0,b=0;
	register char c;
	c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')b=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar();
	}
	return b?-a:a;
}
const int MAXM = 100010;
const int MOD = 1e9 + 7;
struct Matrix{
	int n, m;
	int **data;
	Matrix(int e) : n(e), m(e){
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
		rep(i, 1, n){
			data[i][i] = 1;
		}
	}
	Matrix(int n, int m) : n(n), m(m){
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
	}
	Matrix(const Matrix & other) : n(other.n), m(other.m){
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
		rep(i, 1, n){
			rep(j, 1, m){
				data[i][j] = other.data[i][j];
			}
		}
	}
	~Matrix(){
		rep(i, 0, n){
			delete[] data[i];
		}
		delete[] data;
	}
	Matrix& operator= (const Matrix & other){
		if(&other == this) return *this;
		rep(i, 0, n){
			delete[] data[i];
		}
		delete[] data;
		n = other.n;
		m = other.m;
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
		rep(i, 1, n){
			rep(j, 1, m){
				data[i][j] = other.data[i][j];
			}
		}
		return *this;
	}
	Matrix operator* (const Matrix &other){
		Matrix ans(n, other.m);
//		ans.n = n;
//		ans.m = other.m;
		rep(i, 1, ans.n){
			rep(j, 1, ans.m){
				ans.data[i][j] = 0;
				rep(k, 1, m){
					ans.data[i][j] = ((ll)ans.data[i][j] + (ll)data[i][k] * other.data[k][j] % MOD) % MOD;
					if(ans.data[i][j] < 0){
						cout << 1;
					}
				}
			}
		}
		return ans;
	}
};
Matrix ksm(Matrix a, int k){
	if(k == 0) return Matrix(a.n);
	if(k == 1) return a;
	if(k & 1){
		Matrix tmp = ksm(a, k >> 1);
		return tmp * tmp * a;
	}
	else{
		Matrix tmp = ksm(a, k >> 1);
		return tmp * tmp;
	}
}
int s[MAXM], l[MAXM];
signed main(){
	int m = read(), n = read();
	rep(i, 1, m) s[i] = read();
	rep(i, 1, m) l[i] = read();
	Matrix A(m, 2), B(2, m);
	rep(i, 1, m){
		A.data[i][1] = s[i] + l[i];
		A.data[i][2] = l[i];
	}
	rep(i, 1, m){
		B.data[1][i] = s[i] + l[i];
		B.data[2][i] = MOD - l[i];
	}
	Matrix a0(m, 1);
	rep(i, 2, m) a0.data[i][1] = 0;
	a0.data[1][1] = 1;
	Matrix tmp = ksm(B * A, n - 1) * B * a0;
	Matrix ans = A * tmp;
	ll sum = 0;
	rep(i, 1, m) sum += ans.data[i][1];
	printf("%lld", sum % MOD);
    return 0;
}