算法实战：模幂、构造、背包、贪心等六题精析

前言

这些题目摘录自洛谷，均为典型例题，考察各类算法的综合运用。适合用于蓝桥杯及各类算法竞赛的备战练习，旨在通过具体题目巩固算法模板，提升解题思维。

本期涉及的核心算法包括：数学（可取模的快速幂）、图构造、01 背包问题转化、贪心算法、DFS 暴搜加剪枝，以及模拟配合小根堆维护最小值。

题目清单

1. 转圈游戏

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

![转圈游戏示意图]

解法：数学 + 快速幂

这是一个典型的循环移位问题。n 个数围成一圈，计算移动后的位置公式为 (x + m * 10^k) % n。

由于 k 的范围可能达到 10^9，直接计算 10^k 会溢出，必须使用快速幂算法并在每一步乘法后取模。同时，中间结果建议使用 long long 类型存储以防止溢出。

代码实现：

#include <iostream>
using namespace std;

typedef long long LL;

LL n, m, k, x;

// 快速幂函数：计算 (a^b) % p
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，使其左侧连接 1 个点，右侧连接剩余的 n-2 个点。这种方式在边数有限的情况下能最大化满足条件。