2026-04-01 某游戏厂暑期笔试复盘

题目一：交换下标相差 k 的元素，让数组字典序最大

题目大意

给定长度为 $N$ 的数组，$N\le10^5$，元素在 $[-10^9,10^9]$。每次可以交换下标相差 $k$ 的两个元素，操作次数不限。求能得到的字典序最大的数组。

思路分析

我当时就是按下标模 $k$ 分组，再在每组里排序。

每次交换只移动 $k$ 个位置，所以元素只能在下标模 $k$ 相同的位置之间移动。同组相邻位置可以交换，也就能任意重排。

想让字典序最大，就把每组最大的数放到这个组最靠前的位置，再放次大的，依次填回去就行。

时间复杂度 $O(N\log N)$，额外空间 $O(N)$。

代码

vector<long long> max_lexicographic(vector<long long> a, int k) {
    int n = a.size();
    for (int r = 0; r < min(k, n); ++r) {
        vector<long long> group;
        for (int i = r; i < n; i += k)
            group.push_back(a[i]);

        sort(group.rbegin(), group.rend());
        int p = 0;
        for (int i = r; i < n; i += k)
            a[i] = group[p++];
    }
    return a;
}

题目二：最近素数

题目大意

约 30 个查询，每次给一个 $10^9$ 范围内的正整数 $n$，找到与它绝对差最小的素数。两边距离相同时取较小的那个；如果 $n$ 本身是素数，就返回 $n$。

思路分析

我的做法

我先用埃氏筛预处理小范围内的素数，存下来。小数直接二分找前后两个素数，再比较距离；大数就在它附近开一个半径为 $5\times10^5$ 的窗口，用预处理的小素数做分段筛，再找距离最近的素数。这版 C++ 拿了满分，用时两百多毫秒。

当时我觉得这个窗口是凭经验定的，不知道算不算正解。但只要窗口内找到了素数，取其中最近的就是全局最近的：窗口外的数只会更远。真正需要补上的是窗口内没有素数时怎么办，可以继续扩大窗口，而不是直接结束。

分段筛本身也有几个边界：筛 $[L,R]$ 时，小素数要覆盖到 $\sqrt R$；每个素数 $p$ 从 $\max(p^2,\lceil L/p\rceil p)$ 开始标记，避免把 $p$ 自己筛掉；小于 2 的数单独排除。小数二分时也要保证两侧候选取全，尤其是预处理范围的上边界。

复习时的写法

查询只有约 30 次，也可以按距离 $d=0,1,2,\ldots$ 检查 $n-d$ 和 $n+d$。每次先查左边，找到的第一个素数就是答案，等距离取小值也自然满足。

判素数时先排除偶数，再试除到平方根。这版写起来短，但耗时取决于搜索距离和每次判定的开销，不能仅凭代码更短就说它比原来的分段筛更快。

代码

bool is_prime(long long x) {
    if (x < 2) return false;
    if (x % 2 == 0) return x == 2;
    for (long long d = 3; d <= x / d; d += 2)
        if (x % d == 0) return false;
    return true;
}

long long nearest_prime(long long n) {
    if (n <= 2) return 2;
    for (long long d = 0; ; ++d) {
        if (n - d >= 2 && is_prime(n - d)) return n - d;
        if (d > 0 && is_prime(n + d)) return n + d;
    }
}

题目三：01 串压缩的最小代价

题目大意

有 $T<100$ 组数据。每组给出长度为 $N$ 的 01 字符串、目标长度 $M$ 和费用数组 $A$，其中 $1\le M\le N\le500$，$1\le A[k]\le10^9$，费用不保证单调。

一次可以选择长度为 $k$ 的连续同字符子串，把它压成一个新符号，花费 $A[k]$，总长度减少 $k-1$。新符号不能再参与压缩，但其他位置仍可继续压缩。求把总长度恰好变成 $M$ 的最小费用，不能做到就输出 $-1$。

思路分析

我的思路

我先把目标看成恰好缩短 $D=N-M$。压一个长度为 $k$ 的子串，能缩短 $k-1$，代价是 $A[k]$，所以感觉是一个恰好装满的背包。

接着想统计 cnt[k]，记录长度为 $k$ 的连续同字符子串有多少个，把它当成多重背包里的物品数量。但这样会把重叠区间算成能同时选的物品。比如 000 有两个长度为 2 的子串，它们却不能同时压；要缩短 2，只能压整个长度为 3 的区间，费用是 $A[3]$，不能算成两次 $A[2]$。

我还漏掉了一个选择：一个长段既可以整段压成一个符号，也可以拆成几个互不重叠的部分分别压。只统计每种长度的数量，表达不出这些选择之间的关系。

按原串位置做 DP

新符号不能再次压缩，所以每个原位置最多参与一次压缩。最终结果就等于把原串切成若干块：

• 长度为 1 的块原样保留，费用为 0。
• 长度大于 1 的块必须全是同一种字符，压成一个符号，费用为 $A[k]$。

沿原串切块，就能保证选出的区间不重叠，也能表示一个长段分几次压的情况。

令 dp[i][j] 表示前 $i$ 个原字符处理成 $j$ 个字符的最小费用，初始 dp[0][0]=0。从位置 $i$ 开始有两种选择：

1. 保留当前字符，转移到 dp[i+1][j+1]，不增加费用。
2. 选一段从 $i$ 开始、长度为 $k\ge2$ 的同字符子串压缩，转移到 dp[i+k][j+1]，增加 $A[k]$。

答案是 dp[N][M]。费用最多会累加到 $10^9$ 的数百倍，要用 long long。

代码只保留已经缩短不超过 $D=N-M$ 的状态，每次压缩也不超过剩余缩短量。最坏时间复杂度为 $O(N^2\min(M,D+1))$，空间 $O(NM)$。这份 DP 按上面的题意写；所有测试组的总规模限制没有留下，不能据此保证原题时限下的表现。

代码

long long min_compression_cost(const string& s, int m,
                               const vector<long long>& cost) {
    int n = s.size();
    if (m < 1 || m > n) return -1;
    int need = n - m;
    const long long INF = (1LL << 62);

    // same[i]：从 i 开始的连续同字符段长度。
    vector<int> same(n, 1);
    for (int i = n - 2; i >= 0; --i)
        if (s[i] == s[i + 1]) same[i] = same[i + 1] + 1;

    vector<vector<long long>> dp(n + 1,
                                 vector<long long>(m + 1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < n; ++i) {
        // i-j 是已经缩短的长度；超过 need 的状态不再考虑。
        int low = max(0, i - need);
        int high = min(i, m - 1);
        for (int j = low; j <= high; ++j) {
            if (dp[i][j] == INF) continue;

            dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
            int max_k = min(same[i], need - (i - j) + 1);
            for (int k = 2; k <= max_k; ++k) {
                dp[i + k][j + 1] = min(dp[i + k][j + 1],
                                       dp[i][j] + cost[k]);
            }
        }
    }
    return dp[n][m] == INF ? -1 : dp[n][m];
}

三段都是复习用的核心函数，不是当时提交的原码。共用 #include <bits/stdc++.h> 和 using namespace std;；第三题的 cost 按长度从 1 开始下标。