算法修炼：模幂、构造、背包、贪心、剪枝、堆维护六题精析 | 极客日志

C++算法

算法修炼：模幂、构造、背包、贪心、剪枝、堆维护六题精析

分析六道算法竞赛题目，涉及快速幂、图构造、动态规划、贪心、DFS 剪枝及小根堆。转圈游戏使用数学取模优化位置计算；系统管理员问题探讨图连通性构造条件；多米诺骨牌通过差值转化解决二维背包偏移；排队接水与接水问题分别应用贪心排序与优先队列模拟；荷斯坦奶牛采用 DFS 搜索配合最优性剪枝寻找最小饲料组合。内容包含完整 C++ 代码实现与思路解析。

XiaoPingzi发布于 2026/2/5更新于 2026/4/188K 浏览

算法修炼：模幂、构造、背包、贪心、剪枝、堆维护六题精析

在这里插入图片描述

这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战。锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。

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

在这里插入图片描述

题目清单

1.转圈游戏

在这里插入图片描述

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

在这里插入图片描述

解法：数学 + 快速幂

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

由于 0 < k < 10^9，就是 10(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;
    }
     ret;
}

{
    cin >> n >> m >> k >> x;
    cout << (x + m * (, k, n)) % n << endl;
     ;
}

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

#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;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        if (i != v) {
            cout << i << " " << v << endl;//v 点和其它点相连
            m--;
        }
    }
    int w = 1;
    if (w == v) w = 2;//选一个不是 v 的点
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++)//i 与 j 不同，只连一次
        {
            if (!m) return 0;
            if (i == v || i == w || j == v || j == w) continue;
            cout << i << " " << j << endl;
            m--;
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int OFFSET = 5000;
const int INF = 0x3f3f3f3f;
int f[1005][10005];
int a[1005];

int main() {
    int n;
    cin >> n;
    memset(f, 0x3f, sizeof(f));
    f[0][OFFSET] = 0;
    for (int i = 1; i <= n; ++i) {
        int u, d;
        cin >> u >> d;
        a[i] = u - d;
        for (int j = 0; j <= 10000; ++j) {
            if (j - a[i] >= 0 && j - a[i] <= 10000)
                f[i][j] = min(f[i][j], f[i - 1][j - a[i]]);
            if (j + a[i] >= 0 && j + a[i] <= 10000)
                f[i][j] = min(f[i][j], f[i - 1][j + a[i]] + 1);
        }
    }
    int ans = INF, best_j = 0;
    for (int j = 0; j <= 10000; ++j) {
        if (f[n][j] < ans) {
            ans = f[n][j];
            best_j = j;
        }
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10;
int n;
struct node {
    int t, id;
} a[N];
bool cmp(node& x, node& y) {
    return x.t < y.t;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].t;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n, cmp);
    double sum = 0, wait = 0;
    for (int i = 1; i <= n; i++) {
        cout << a[i].id << " ";
        sum += wait;
        wait += a[i].t;
    }
    cout << endl;
    printf("%.2lf\n", sum / n);
    return 0;
}

#include <iostream>
using namespace std;
const int N = 30;
int n, m;
int v[N];
int g[N][N];
int cnt;//记录当前选了多少个
int path;//记录选了哪些饲料
int ret = N;//记录最少选了
int st;//当前的决策是 path 是否满足奶牛的需要

bool check() {
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= m; j++) {
            if ((path >> j) & 1) sum += g[j][i];
        }
        if (sum < v[i]) return false;
    }
    return true;
}

void dfs(int pos) {
    //最优性剪枝
    if (cnt >= ret) return;
    if (check()) {
        ret = cnt;
        st = path;
        return;
    }
    if (pos > m) return;
    //选
    cnt++;
    path |= (1 << pos);//置为 1
    dfs(pos + 1);
    cnt--;
    path &= ~(1 << pos);//不选
    dfs(pos + 1);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];
    cin >> m;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) cin >> g[i][j];
    dfs(1);
    cout << ret << " ";
    for (int i = 1; i <= m; i++) {
        if ((st >> i) & 1) cout << i << " ";
    }
    return 0;
}

//模拟，小根堆，同时找 max
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m;

int main() {
    cin >> n >> m;
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 1; i <= m; i++)//初始化 m 个水龙头的结束时间，方便后面 n 次，不用提前存
        heap.push(0);
    int ret = 0;
    for (int i = 1; i <= n; i++)//维护 m 个水龙头的结束时间
    {
        int w;
        cin >> w;
        int t = heap.top();
        heap.pop();//min
        t += w;//累积起来
        heap.push(t);//加入维护
        ret = max(ret, t);
    }
    cout << ret << endl;
    return 0;
}