跳转至

枚举优化

求和类

如果多个变量之间存在 数学关系，可以 只枚举其中部分变量， 推导出其它变量，从而 减少循环层数。

常见模式：枚举两个变量后，第三个变量的值唯一确定，无需再枚举！

常见例子

  • 鸡兔同笼：总数已知，鸡 $x$ 枚举后，兔 = 总数 $-x$。
  • 三数求和：若 $a_i + a_j = a_k$，枚举 $i, j$ 后，$a_k$ 唯一。

例题一：卡片问题

有三种卡片，分别为 A、B、C，每张卡片均有 $n$ 张，卡片上对应的数字为 $1,2,3$。

现在想组成一个数字 $d$，问有多少种方案？

朴素做法

  • 三重循环：$i,j,k$ 分别表示 A、B、C 卡片的使用数量。
  • 每种张数从 $0$ 到 $n$ 枚举，判断：
    • if (i + 2 * j + 3 * k == d)
  • 时间复杂度：$O(n^3)$

优化做法

我们有：$i + 2j + 3k = d$

枚举 $i,j$ 后，$k$ 的值可直接求出：

\[ k = \frac{d - i - 2j}{3} \]

需要注意：

  • 判断 $d - i - 2j$ 是否为 $3$ 的倍数（否则 $k$ 不是整数）
  • 判断 $0 \leq k \leq n$，确保卡片数量合法

时间复杂度降为 $O(n^2)$，显著提高运行速度。

问题变形

当问题修改为使用三种卡片求组合出 $\leq d$ 的方案数时，一样可以进行优化。

此时方程为：$i+2j+3d\leq d$。

当枚举 $i,j$。计算出 $k$:

\[ k \leq \frac{d - i - 2j}{3} \]

由于 $k$ 必须为整数，因此 $k$ 可以取 $[0,\lfloor \dfrac{d-i-2j}{3}\rfloor]$ 之间的所有整数。

int ans = 0;
for (int i = 0; i <= n; i++)
{
    for (int j = 0; j <= n; j++)
    {
        int k = (d - i - 2 * j) / 3;
        ans += k;
    }
}

例题二：珠心算测验（加强版）

朴素做法

时间复杂度：$O(n^3)$。

\[ \begin{array}{ll} 1 & \textbf{sort(A)}\\ 2 & \textbf{for } i\gets 1\textbf{ to }n\\ 3 & \qquad \textbf{for } j\gets i+1\textbf{ to }n\\ 4 & \qquad \qquad \textbf{for } k\gets j+1\textbf{ to }n\\ 5 & \qquad \qquad \qquad \textbf{if } A[i]+A[j] = A[k] \textbf{ and } vis[A[k]] = 0\\ 6 & \qquad \qquad \qquad \qquad \textbf{cnt}\gets \textbf{cnt}+1\\ 7 & \qquad \qquad \qquad \qquad \textbf{vis[A[k]]}\gets 1 \end{array}\]

优化做法

如果我们只枚举前两个数 $a_i$ 与 $a_j$：

那么 $a_k = a_i + a_j$ 是唯一确定的。

  • 双重循环枚举 $a_i, a_j$，给 $a_i + a_j$ 打上标记。
  • 最后遍历原序列，若 $\texttt{vis[a[i]] == true}$ 则累计一次答案。

时间复杂度：$O(n^2)$。

注意 vis 数组的空间问题。

\[ \begin{array}{ll} 1 & \textbf{sort(A)}\\ 2 & \textbf{for } i\gets 1\textbf{ to }n\\ 3 & \qquad \textbf{for } j\gets i+1\textbf{ to }n\\ 4 & \qquad \qquad \textbf{vis[A[i] + A[j]]}\gets \texttt{true}\\ 5 & \texttt{ans} \gets 0\\ 6 & \textbf{for } i\gets 1\textbf{ to }n\\ 7 & \qquad \texttt{if }\textbf{vis[A[i]]}\texttt{ == true}\\ 8 & \qquad \qquad \texttt{ans} \gets \texttt{ans} + 1 \end{array}\]

乘积类

此类问题的特点是：乘积值已知，需反推满足乘积条件的两个数。

常见形式：寻找所有整数对 $(i, j)$ 满足 $i \times j = n$。

枚举 $i$，判断 $n \bmod i = 0$ 是否成立：

  • 若成立，则 $j = \dfrac{n}{i}$。
  • 整数对 $(i, j)$ 满足条件。

若题目要求 $i\leq j$，则 $i$ 只需枚举到 $\sqrt{n}$。

基础应用：

  • 判断质数：只需要检验 $n$ 在 $[2,\sqrt{n}]$ 之间是否存在因子。
  • 求因子个数：只需要枚举 $[1,\sqrt{n}]$ 之间的因子，既可以算出另一半的所有因子情况。

例题一：[CSP-J 2022] 解密（$60$ 分解法）

题意：

给定三个整数 $n, e, d$，找到一对正整数 $(p, q)$ 满足：

  • $n = p \times q$
  • $e \times d = (p - 1)(q - 1) + 1$
  • $p \leq q$

思路

$n = p \times q$ 表明 $p, q$ 为 $n$ 的一对因子。

由第二个条件联立判断当前 $(p, q)$ 是否满足。

利用 枚举因子对 方法，只需遍历 $p$ 从 $1$ 到 $\sqrt{n}$：

  • 若 $n \bmod p = 0$，则 $q = \dfrac{n}{p}$
  • 再判断是否满足 $e \times d = (p - 1)(q - 1) + 1$

时间复杂度：$O(t\sqrt{n})$。

根据数据范围可以得到 $60$ 分，满分需要其他做法，这里暂不赘述。

杂项

例题一：输出完全平方数

朴素做法

  • 枚举 $[1,n]$ 的所有数字 $i$。
  • 判断 $i$ 是否是完全平方数
  • 复杂度：$O(n)$

优化

直接枚举 平方根 $i$，其中 $i\in [1,\sqrt{n}]$。

直接输出 $i\times i$ 即可，时间复杂度：$O(\sqrt{n})$，注意 long long。

例题二：区间枚举Ⅲ

当固定左端点 $l$ 后，随着右端点 $r$ 的前进，区间和 $sum$ 也在变化。

具体来说：

  • 假设区间 $[l,r]$ 的和为 $sum$。
  • 那么当 $r\to r+1$ 时，$sum$ 在上一次的基础上新增了 $a[r+1]$ 而已。
  • 因此无需重新遍历整个区间，直接累加变化量即可在 $O(1)$ 的复杂度内求出新区间 $[l,r+1]$ 的和。
for (int l = 1; l <= n; l++)
{
    int sum = 0;
    for (int r = l; r <= n; r++)
    {
        sum += a[r]; // 累加变化量 a[r]
        if (sum % 2 == 0)
        {
            ans++;
        }
    }
}
cout << ans;

例题三：[ABC343C] 343

朴素做法

  • 枚举 $[1,n]$ 的所有数字 $i$。
  • 判断 $i$ 是否是立方回文数
  • 复杂度：肯定超时。

优化

直接枚举 立方根 $i$，其中 $i\in [1,10^6]$。

通过 $i^3$ 算出立方数记作 $x$。

使用数位拆分或字符串的方法判断 $x$ 是否是回文数即可。

时间复杂度：$O(N^{\frac{1}{3}}\log{N})$。

贡献法

问题引入

给定一个 $n \times m$ 的矩阵 $a$，元素值均在 $1 \sim 3$ 之间，计算整个矩阵的元素和。

方法一：直接求和

  • 双重循环遍历每个元素，逐个累加：$sum = sum + a_{i,j}$
  • 时间复杂度：$O(nm)$

方法二：按值分类

  • 预处理每个数值的出现次数 $cnt_1, cnt_2, cnt_3$
  • 答案为：$cnt_1 \times 1 + cnt_2 \times 2 + cnt_3 \times 3$
  • 总时间复杂度仍为 $O(nm)$，但计算更有结构性。

贡献法的核心思想

  • 将每个“元素的影响”视作其对最终答案的“贡献”。
  • 不直接聚焦整体，而是统计 每类元素 如何累计其贡献。

例题一：统计方形（数据加强版）

朴素做法

  • 枚举所有可能的矩形区域
  • 只需确定左上角 $(x_1, y_1)$ 与右下角 $(x_2, y_2)$
  • 用四重循环实现全矩形枚举

注意：

  • 确保 $x_2 \geq x_1$ 且 $y_2 \geq y_1$，避免重复与非法区域
  • 判断是否为正方形：若满足 $x_2 - x_1 = y_2 - y_1$
  • 时间复杂度：$O(n^2 m^2)$
for (int x1 = 1; x1 <= n; x1++)
    for (int y1 = 1; y1 <= m; y1++)
        for (int x2 = x1; x2 <= n; x2++)
            for (int y2 = y1; y2 <= m; y2++)
                if (x2 - x1 == y2 - y1)
                    sum1++;
                else
                    sum2++;

贡献法转变枚举对象

  • 与其枚举每个矩形位置，不如枚举其长宽 $(i, j)$
  • 统计 $i \times j$ 大小的矩形在矩阵中的数量。即对答案的贡献

贡献怎么算？

即解决在一个 $n\times m$ 的矩阵中，有多少个 $i\times j$ 的小矩阵。

答：$(n - i + 1) \times (m - j + 1)$ 个。

横向有 $n - i + 1$ 个起点，纵向有 $m - j + 1$ 个起点 所有大小为 $i \times j$ 的矩形贡献均可用该式一次性统计

时间复杂度：$O(n\times m)$

for (int i = 1; i <= n; i++)    // 高度
    for (int j = 1; j <= m; j++) // 宽度
    {
        if (i == j) // 长和宽相等
            sum1 += (n - i + 1) * (m - j + 1);
        else
            sum2 += (n - i + 1) * (m - j + 1);
    }

本题还可用数学公式实现 $O(1)$，可自行探索

例题二：[AHOI2005] 约数研究

朴素做法

  • 外层循环枚举 $1 \sim n$ 的每个整数；
  • 内层循环统计每个 $i$ 的因子个数；
  • 外层循环 $O(n)$，内层复杂度约为 $O(\sqrt{i})$；
  • 整体时间复杂度为 $O(n \sqrt{n})$，在数据范围下无法通过。
int f(int n)
{
    int sum = 0;
    for (int i = 1; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            sum++;
            int j = n / i;
            if (i != j)
                sum++;
        }
    }
    return sum;
}
int main()
{
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += f(i);    
    } 
    cout << ans;
    return 0;
}

贡献法

朴素做法从“每个数出发”枚举其因子，难以优化；

尝试转换思路：从“因子”的角度出发，考虑它对结果的贡献；

枚举所有 $1 \sim n$ 的因子，统计它分别作为因子的次数；

例如：

  • 因子 $1$ 出现 $\left\lfloor \frac{n}{1} \right\rfloor$ 次；
  • 因子 $2$ 出现 $\left\lfloor \frac{n}{2} \right\rfloor$ 次；
  • 因子 $i$ 出现 $\left\lfloor \frac{n}{i} \right\rfloor$ 次；

故总数为：

\[ \left\lfloor \frac{n}{1} \right\rfloor+\left\lfloor \frac{n}{2} \right\rfloor+...+\left\lfloor \frac{n}{n} \right\rfloor \]

时间复杂度为 $O(n)$，可通过本题。

拓展练习

求 $1 \sim n$ 每个整数的因子和：

\[ \begin{aligned} ans &= \sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor \times i \\ &= \left\lfloor \frac{n}{1} \right\rfloor \cdot 1 + \left\lfloor \frac{n}{2} \right\rfloor \cdot 2 + \cdots + \left\lfloor \frac{n}{n} \right\rfloor \cdot n \end{aligned} \]

同样可以 $O(n)$ 计算。

未来学习数论分块还可以降低至 $O(\sqrt{n})$。

例题三：完全平方数

朴素做法

  • 枚举所有区间 $[l, r]$；
  • 对每个区间内的所有数，判断是否为完全平方数；
  • 判断方法：对于数 $k$，计算 $x = \lfloor \sqrt{k} \rfloor$；
  • 若满足 $x \times x = k$，则 $k$ 为完全平方数；

复杂度：$O(n^3)$，无法通过。

贡献法

由于 $n \leq 10^{12}$，不可能线性遍历所有数；

但 $\leq n$ 的完全平方数最多只有 $\sqrt{n} \leq 10^6$ 个；

枚举每个平方数 $x = i^2$，计算它被多少个区间包含；

最终答案即为所有平方数的总贡献之和。

以 $n = 4$ 为例：

  • 完全平方数有 $1$ 和 $4$；
  • $1$ 被 $[1,1],[1,2],[1,3],[1,4]$ 共 $4$ 个区间包含；
  • $4$ 被 $[1,4],[2,4],[3,4],[4,4]$ 共 $4$ 个区间包含；

答案为 $4 + 4 = 8$。

因此直接枚举所有完全平方数：

  • 枚举所有 $i$，满足 $i^2 \leq n$ 即可；

    for (long long i = 1; i * i <= n; i++)
{
    long long x = i * i;
}

  • 时间复杂度 $O(\sqrt{n})$。

一个数 $x$ 被多少个区间包含？

  • 左端点 $\leq x$ 有 $x$ 种选择；
  • 右端点 $\geq x$ 有 $n - x + 1$ 种选择；
  • 所以 $x$ 的贡献是：$x \times (n - x + 1)$；
  • 每个平方数 $x = i^2$，累加其贡献即可。
  • 计算过程中注意取模，防止中间溢出。
for (long long i = 1; i * i <= n; i++)
{
    long long x = i * i;
    long long l = x, r = n - x + 1;
    ans += l % mod * r % mod;
    ans %= mod;
}

优化上下界

枚举类问题中，缩小循环上界 是常见且有效的优化方式。

例如在完全平方数问题中，枚举 $\leq n$ 的完全平方数时，只需遍历 $\sqrt{n}$ 个数：

  • $i \times i \leq n$

再如，若求非负整数解满足 $x^3 + y^3 \leq n$ 且 $n \leq 10^{18}$。

  • 则 $x, y$ 的上界为 $n^{1/3} \approx 10^6$
  • 明显比 $10^{18}$ 小很多。

例题：四方定理（四平方和）

朴素做法

枚举 $a \leq b \leq c \leq d$，判断是否满足：

\[ a^2 + b^2 + c^2 + d^2 = n \]

观察到 $a + b + c + d$ 是固定值 $\Rightarrow$ 考虑将 $d$ 用前面三个推出：

\[ d^2 = n - a^2 - b^2 - c^2 \]

验证 $d$ 是否为整数平方，且满足 $d \geq c$

时间复杂度：$O(n^3)$（仍过大）

优化

第一重循环（枚举 $a$）

  • 根据 $a \leq b \leq c \leq d$，若 $a$ 太大，后面三项无法凑出 $n$
  • 所以需满足：
\[ 4 \times a^2 \leq n \]
  • 因此第一层循环为：$\texttt{for (int a = 0; 4 * a * a <= n; a++)}$

第二层循环 $b$（保证 $b \geq a$）：

\[ a^2 + 3b^2 \leq n \quad \Rightarrow \quad \texttt{for (int b = a; a * a + 3 * b * b <= n; b++)} \]

第三层循环 $c$（保证 $c \geq b$）：

\[ a^2 + b^2 + 2c^2 \leq n \quad \Rightarrow \quad \texttt{for (int c = b; a * a + b * b + 2 * c * c <= n; c++)} \]

计数类

此类问题特点：数据量大，数值域小。

例如出题人设置 $a_i \leq 10^5$（而非 $10^9$），即便 $n \leq 10^5$，依然可以考虑值域优化。

从值域角度进行枚举/计数，或许是解题关键。

例题一：CF1742D - Coprime

朴素解法

暴力枚举 $a_i, a_j$

  • 双重循环判断是否满足 $\gcd(a_i, a_j) = 1$。
    • 求 $\gcd$ 可以用 GCC 自带的函数 __gcd(a, b)。
  • 若满足，更新 $i + j$ 的最大值。
  • 时间复杂度为：$O(n^2 \log a_i)$。
    • 其中 $\log_{a_i}$ 是求 $\gcd$ 的时间复杂度。

优化解法

注意到 $a_i \leq 10^3$。

可以从 值域角度枚举所有数值对 $(i,j)$。

如果 $\gcd(i, j) = 1$，就查找数组中是否出现过 $i$ 和 $j$。

  • 同一数值可能多次出现，我们只关心其 最靠后的索引位置。

具体实现：

  • 创建数组 $\texttt{pos[1001]}$，记录每个数值的最大下标。
  • 对于每个 $a[i]$ 执行：pos[a[i]] = i

多次覆盖后，$\texttt{pos[x]}$ 最终是 $x$ 的最后一次出现位置。

  • 枚举 $i, j \in [1, 1000]$，若 $\gcd(i, j) = 1$ 且 $\texttt{pos[i], pos[j]}$ 都存在：
\[ \texttt{ans} \leftarrow \max(\texttt{ans}, \texttt{pos[i]} + \texttt{pos[j]}) \]

时间复杂度：$O(V^2 \log V), \quad V \leq 1000$