2025 CCPC Online 补题

Locklink

2025-10-21

A 整点正方形计数2

statement

有一个边长为 $(n+1,m+1)$ 的矩形区域，对其中每一个整点 $(i,j)$ ，求以其为顶点，在矩形区域内能作出几个整点正方形。

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

solution

枚举正方形边长向量 $(x,y)$ ，能以这条边为边长形成符合要求的正方形的点构成一个矩形，使用二维差分进行修改即可，之后就可以 $\text{O}(1)$ 地计算出任意一个点的正方形数量。 submission

关于二维差分

若要给左上角为 $(x1,y1)$ ，右上角为 $(x2,y2)$ 的矩形区域 $+1$ ，要对差分数组进行如下修改：

diff[x1][y1] += v
diff[x1][y2+1] -= v
diff[x2+1][y1] -= v
diff[x2+1][y2+1] += v

还原数组时：a[i][j] = diff[i][j] + diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]

C 造桥与砍树

statement

求稠密图的最小生成树，点有点权 $a_i$ ，边 $(u,v)$ 的边权定义为 $(a_u+a_v) \mod k$ 。

$n \le 10^5 , k \le 10^9$ 。

solution

求最小生成树的 Ford 算法

将节点分为已加入生成树的和未加入生成树的两类，对于未加入生成树的节点 $u$ ，定义 $dis_u$ 为其到已经加入生成树的节点的最小距离。类似 dijkstra 的思想
每次要选择 $dis_u$ 最小的结点 $u$ 加入生成树，以及用新加入生成树的边更新其他结点的距离。

回到本题

首先将所有 $a_i \mod k$ ，显然不会对答案产生任何影响。

本题中的图为稠密图，边的最大数量达到 $(n-1)^2$ 。克鲁斯卡尔的思路显然无法使用，所以沿着 prim 算法的思路，只需要关心以生成树的点所能连接到的权值最小的点，每次最小生成树的边 $(u,v)$ 连接到一个新点，就给 $v$ 找一条边，并再次给 $u$ 找出一条可以延伸的边。

未加入生成树的点可以用 std::set 维护，并使用 lower_bound() 进行二分查找。注意当没有元素大于等于要查找的值时， lower_bound() 返回 end() 。

为什么使用 set ？可以证明，权值相同的点可以只留下一个，其余的直接批量计算贡献，不会对答案产生影响。
submission

D 通配符匹配

statement

给定一个含有可以匹配任何字符串（可以为空）的通配符 * 的字符串 $S$ 和另一个字符串 $T$ ，求 $T$ 可以与 $S$ 匹配的子串数量。 $n \le 5 \times 10^5$ 。* 的数量不超过 $10$ 。

solution

这题细节比较多。

首先将 $S$ 以 * 为分隔符分割成若干个子串。显然连续的 * 只需要考虑一个即可。

首先考虑首尾都没有 * 的情况，只需要贪心地对于每个开头的串找最先出现的结尾的串，由于我们要找的是 $T$ 的子串而不是匹配的方法数，这之后每一个结尾的串的出现都可以算进贡献。

由于 * 的数量不超过 $10$ ，可以对每个分割出的串先 KMP 找出其在 $T$ 中出现的所有位置，再计算一个 nxt[i][j] ：对于第 $i$ 个子串的第 $j$ 次出现，下一个出现的第 $i+1$ 个子串。

然后考虑 $S$ 首尾是 * 的情况。对于开头是 * 的，如果第一个子串是 a ，答案就要乘以（这个 a 的位置减去前面 a 的位置），这样不会出现重复计算的问题。
如果结尾是 *，结尾可以无限延伸，设最后一个子串为 c ，结尾的乘数就变成了（最后一个 c 的位置到字符串结尾）。

另外需要对全是 * 以及没有 * 的情况做特判。

submission