本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-25 21:59:53

开始将同学对号入座进题面了。

A. Comparing Two Long Integers：

考察：高精度。
题目简述：
小 I 收到了两个很大的非负整数 $a,b$，由于他很糖（指高血糖，不信你看他名字）他需要判断 $a$ 和 $b$ 的大小关系。$a$ 和 $b$ 可以有前导 $0$。
数据范围：

• 令 $|a|,|b|$ 分别代表 $a,b$ 的位数，则 $1\le|a|,|b|\le 10^6$

在小 I 的小学时学过，比较两个数大小一共分两步：

• 比较两个数的位数。
• 从高位开始逐位比较。

但他发现这一切都建立在两个数不含前导零之上，所以若包含前导零他可以先将数位少的数用前导 $0$ 补满数位，使他们位数相同，再直接进行第二步即可。
时间复杂度为 $\Theta(|a|+|b|)$，空间复杂度为 $\Theta(|a|+|b|)$。

B. Dinner with Emma：

考察：模拟，贪心。
题目简述：
给你一个 $n\times m$ 的矩阵 $c$，现在现由小 X 选择一个 $i\in[1,n]\cap\mathbb Z$，再由小 K 选择一个 $j\in[1,m]\cap\mathbb Z$，得到一个数 $c_{i,j}$，小 X 想让这个数更大，小 K 想让这个数更小，为了防止初一生吵架，你需要给出最后会得到的 $c_{i,j}$ 值为多少。
数据范围：

• $1\le n,m\le 100$
• $\forall i\in[1,n]\cap\mathbb Z,j\in[1,m]\cap\mathbb Z,1\le c_{i,j}\le 10^9$

如果小 X 选好了 $i$，那么小 K 一定会选择最小的一个，即 $\displaystyle\min_{j=1}^mc_{i,j}$。
那么小 X 选的时候肯定想最后值最大，所以最后答案为 $\displaystyle\max_{i=1}^n\min_{j=1}^mc_{i,j}$。
时间复杂度为 $\Theta(nm)$，空间复杂度可为 $\Theta(1)$。

C. The Labyrinth：

考察：dfs。
题目简述：
小 A 收到了一个 $n\times m$ 的网格图，它由 . 和 * 组成，* 指有人阻挡他，. 反之。. 组成的四连通块是小 A 的活动区域，但是小 A 有一个足球，它可以击中一个人的脸并将相应位置的 * 变为 .，现在被击中的人相应位置的四连通块就变成了自己的活动区域，这样可以扩大自己的活动区域。
小 A 还不确定要击中谁，所以希望你求出击中任意一个人后活动区域的大小，同时为了排版整齐，他会让你给出一个表格，若该格本来就为 . 则还输出 .，反之输出该格答案对 $10$ 取模的值。
数据范围：

• $1\le n,m\le 1000$

很明显，我们可以先跑一遍 dfs，求出每个网格所属连通块以及每个连通块的大小，然后对于每个 *，找到它的四联通格，对他们所属的连通块进行去重，累加答案即可。
时间复杂度为 $\Theta(nm)$，空间复杂度为 $\Theta(nm)$。

D. Longest k-Good Segment：

考察：双指针，桶。
题目简述：
小 Z 收到了一个序列 $\{a_n\}$ 和一个整数 $k$，喜欢玩 Genshin 牌的他一下就来了兴趣，想要知道如果一个连续子序列的整数种类不超过 $k$ 种，那么当连续子序列长度最大时，这个连续子序列的左右端点可以是多少（给出一种即可）。
数据范围：

• $1\le k\le n\le 5\times 10^5$
• $\forall i\in[1,n]\cap\mathbb Z,0\le a_i\le 10^6$

为了统计序列整数种类，小 Z 开了一堆桶，实时存储整数个数，当被清零时整数种类减 $1$，从零变到一时种类加 $1$。
然后带进双指针板子即可。
时间复杂度为 $\Theta(n)$，空间复杂度为 $\Theta(n+V)$。

E. Sum of Remainders：

考察：整除分块。
题目简述：
小 L 收到了两个整数 $n,m$，比小 Z 还爱玩原神的他，想求：
$$(\sum_{i=1}^mn\bmod i)\bmod(10^9+7)$$ 数据范围：

• $1\le n,m\le 10^{13}$

整除分块板子题，给原式变个形：
$$\begin{aligned}(\sum_{i=1}^mn\bmod i)\bmod(10^9+7)&=(\sum_{i=1}^mn-i\lfloor\frac{n}{i}\rfloor)\bmod(10^9+7)\&=(nm-\sum_{i=1}^mi\lfloor\frac{n}{i}\rfloor)\bmod(10^9+7)\end{aligned}$$ 后半部分上整除分块就行了。
时间复杂度为 $\Theta(\sqrt m)$，空间复杂度为 $\Theta(1)$。