2026-10-10 秋招XX笔试复盘：因数统计与小偷分配

第一题：因数统计

题目大意

给定 $n$、$Q$ 和数组 $A$，其中 $n\le2\times10^5$，数组元素在 $0\sim10^6$。有 $Q$ 个询问，每次给一个 $K$，问有多少个正整数 $d$ 能整除数组里至少 $K$ 个数。

下面按有限候选范围 $1\le d\le10^6$、$1\le K\le n$ 写参考实现。如果候选正因子没有上界，且数组中至少有 $K$ 个0，答案就会是无穷多，因为所有正整数都能整除0。

我当时的想法

我先筛出每个数的全部因数，存成 vector<int> factor[1000001]，再遍历数组，对每个数的因子累加计数，最后按整除数量做后缀和。

思路分析

先统计每个数出现多少次，记为 freq[x]。固定一个候选因子 $d$，它能整除的正数就是 $d,2d,3d,\ldots$，所以枚举这些倍数，把出现次数加起来。

与给每个数存整张因数表相比，这样只保存频次数组，不需要一百万个 vector，也没有逐个扩容和保存所有因数的开销。所有倍数循环的总次数是

算出每个 $d$ 的整除数量后，再统计“恰好整除 $t$ 个数”的因子有几个，对这个数组做后缀和。询问至少 $K$ 个，就能直接查表。

如果数组里有 0，每个候选正因子都要额外加上 freq[0]。这也是不能从 factor[0] 里找因数的原因。

总时间复杂度 $O(n+M\log M+Q)$，空间复杂度 $O(M+n)$。

参考代码

候选正因子限定在 [1,M]，代码同时处理数组中的 0。

#include <bits/stdc++.h>
using namespace std;

// 条件：a[i] 在 [0, M]，候选正因子 d 限定在 [1, M]。
// 返回 answer[k]：能整除至少 k 个数组元素的候选 d 的个数。
vector<int> divisorAnswers(const vector<int>& a, int M) {
    int n = a.size();
    vector<int> freq(M + 1, 0);
    for (int x : a) ++freq[x];

    vector<int> answer(n + 2, 0);
    for (int d = 1; d <= M; ++d) {
        int count = freq[0];  // 任意正整数都整除 0。
        for (int x = d; x <= M; x += d)
            count += freq[x];
        ++answer[count];
    }
    for (int k = n - 1; k >= 0; --k)
        answer[k] += answer[k + 1];
    return answer;
}

// auto answer = divisorAnswers(a, 1000000);
// 对 1 <= K <= a.size() 的询问，直接读取 answer[K]。

第二题：小偷分配

题目大意

最大 $1000\times1000$ 的方格，每格有小偷，警察从 $(1,1)$ 出发。警察和小偷都只能向右或向下，到最后一行强制停止。所有小偷先走完，警察再走，最终抓走停留格子里的全部小偷，问警察最多能抓多少。

每个小偷可以独立选择路径。下面按小偷整体协作、尽量减少警察最终抓捕人数的 min-max 模型分析；若改成每个人分别最大化自己的生存概率，还需要约定警察在并列最优时怎样选列。

我当时的想法

我先把网格压成两行：前 $n-1$ 行按列相加，最后一行单独留下。再从右往左处理，尽量把可达位置中人数较少的列填平，而不是只看一个总平均。

思路分析

只看每一列，不必保留上方小偷具体在哪一行。记前 $n-1$ 行的人数和为 $U_j$，最后一行的人数为 $B_j$，总和为 $S_j=U_j+B_j$。

$B_j$ 已经在最后一行，不能移动。上方每个小偷都可以停在不小于自己初始列号的任意列。所以问题变成：把第 $j$ 列的 $U_j$ 个人分配到右侧各列，使最终最高的一列尽可能低。

假设能把每列都压到不超过 $T$，必须满足两类限制：

• 底座不能移动，所以每个 $B_j\le T$。
• 第 $j$ 列到最后一列的人不能跑到左边，所以这个后缀的总人数不能超过后缀的总容量，即 $\sum_{t=j}^{n-1}S_t\le(n-j)T$。

这些限制也足够。先把底座放好，每列还剩 $T-B_j$ 个位置，再从右往左安排可移动的人。处理第 $j$ 列时，右边已经安排的人只消耗右边容量；后缀限制保证第 $j$ 列剩下的人仍有地方放。

因此答案是

底座这一项不能省。例如 $U=[0,0,0]$、$B=[100,0,0]$，总人数虽然能除以 3，但第一列那 100 个人根本不能动。只看整体平均同样不够：$U=[0,20]$、$B=[0,0]$ 时，右边的 20 个人无法向左分，答案仍是 20。

读入网格要 $O(n^2)$，之后计算答案只要 $O(n)$，除网格外的空间为 $O(n)$。人数合计用 long long。

参考代码

下面按后缀容量公式实现。

#include <bits/stdc++.h>
using namespace std;

// n*n 网格，人数非负；按小偷整体协作的 min-max 模型计算。
long long minCaught(const vector<vector<long long>>& grid) {
    int n = grid.size();
    vector<long long> total(n, 0);
    long long answer = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            total[j] += grid[i][j];
    }
    for (int j = 0; j < n; ++j)
        answer = max(answer, grid[n - 1][j]);

    long long suffix = 0;
    for (int j = n - 1; j >= 0; --j) {
        suffix += total[j];
        long long columns = n - j;
        long long ceiling = suffix / columns + (suffix % columns != 0);
        answer = max(answer, ceiling);
    }
    return answer;
}