算法实战：模幂、构造、背包、贪心及堆维护六题精析

前言

这组题目选自洛谷，涵盖了多种经典算法模型，非常适合用于蓝桥杯备赛或日常算法训练。通过实际案例，我们可以更好地掌握从模板到具体解题的转化过程。

本期重点涉及以下技术点：数学（快速幂取模）、图论构造、01 背包问题转化、贪心算法、DFS 搜索加剪枝以及模拟配合小根堆维护最小值。

题目清单

1. 转圈游戏

题目： P1965 [NOIP 2013 提高组] 转圈游戏

解法：数学 + 快速幂

n 个数一圈（循环），计算 (x + m * 10^k) % n 的值即为移动后的位置。

由于 0 < k < 10^9，也就是 10 的 9 次方，非常大，需要用到可以取模的快速幂，一边乘一边取模。用 long long 来存。

代码：

#include <iostream>
using namespace std;
typedef long long LL;

LL n, m, k, x;

LL qpow(LL a, LL b, LL p) {
    LL ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return ret;
}

int main() {
    cin >> n >> m >> k >> x;
    cout << (x + m * qpow(10, k, n)) % n << endl;
    return 0;
}

2. System Administrator（系统管理员）

题目： CF22C System Administrator

解法：构造

要满足题目要求：去掉一个点后，图不连通，那么就构造一个点 v 左边连一个点，右边连 n - 2 个点。因为这道题目的边有限，且要用完，这种方式连的边最多，且满足题目要求。

重要的性质：

n 个点如果至少要连 n - 1 条边，所以 m < n - 1 时，连通图就不存在。所以 m > n - 1；

当有一个顶点与 v 相连，并且与其他顶点都不相连时，最大的边数可由以下方法来求：对于一个无向图，n 个顶点，最多有 n(n - 1) / 2 条边。（结论），因为每一个点可以和剩下的 n-1 个点连一条边，那么就是 n(n - 1)，且因为两个点只有一条无向边，会多算一次就/2。综上，可以算满足题目要求的情况：一个点连左边一个点，边数 1，这个点加上右边一共 n - 1 个点边数 (n - 1) * (n - 2) / 2 + 1。所以 m < (n - 1) * (n - 2) / 2 + 1。

综上所述，n - 1 < m < (n - 1) * (n - 2) / 2 + 1，可以用于判断 m 是否合法。

如果 m 在范围内，那么图存在，一定能构造出来，可以先在 v 的左边放置一个顶点 w，在另一边放剩余的 n-2 个点，将所有的点 (除了 v 本身)，连在 v 上，然后将它们（除了 w）相互连接起来。

代码：

#include <iostream>
using namespace std;
typedef long long LL;

LL n, m, v;

int main() {
    cin >> n >> m >> v;
    if (m < n - 1 || m > (n - 1) * (n - 2) / 2 + 1) {
        cout << -1 << endl;
    } else {
        // 此处省略具体建图逻辑，核心在于判断范围
        // 若需输出方案，按上述构造思路输出即可
    }
    return 0;
}