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}$ 。

提示

Hint 1

修改后的序列仍然满足非升的条件。

Hint 2

每次 $\text{2}$ 操作，最多分成 $\log n$ 个不连续的段。

分析

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

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

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