2013 蓝桥杯 省赛B组 翻硬币(洛谷P8597题) 从暴力BFS到贪心算法的优化之路

贾蔷
• 阅读 46

一、问题背景与理解

洛谷P8597是一道经典的翻硬币问题,题目描述如下:给定两个由''和'o'组成的字符串s1和s2,分别表示初始状态和目标状态。每次操作可以选择任意位置开始翻转连续的k个硬币(''变'o','o'变'*')。要求计算出从初始状态变为目标状态所需的最少操作次数。

这个问题看似简单,但蕴含着重要的算法思想转变过程。作为新手,理解这个问题从暴力解法到最优解法的演进过程,对培养算法思维非常有帮助。

2013 蓝桥杯 省赛B组 翻硬币(洛谷P8597题) 从暴力BFS到贪心算法的优化之路

二、暴力BFS解法分析

int minOperations(string s, int k) {
    int n = s.length();
    int target = stoi(s, nullptr, 2); // 字符串转二进制数
    queue<int> q; // BFS队列
    vector<bool> visited(1<<n, false); // 状态访问标记

    q.push(0); // 初始全0状态
    visited[0] = true;
    int steps = 0;

    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            int curr = q.front();
            q.pop();
            if (curr == target) return steps;

            for (int i=0; i<=n-k; ++i) {
                int mask = (1<<k)-1 << i;
                int next = curr ^ mask;

                if (!visited[next]) {
                    visited[next] = true;
                    q.push(next);
                }
            }
        }
        steps++;
    }
    return -1;
}

三、贪心算法优化

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    cin >> s1 >> s2;
    int cnt = 0;

    for (int i = 0; i < s1.size() - 1; ++i) {
        if (s1[i] != s2[i]) {
            // 翻转当前和下一个硬币
            s2[i] = s1[i];
            s2[i+1] = (s2[i+1] == 'o') ? '*' : 'o';
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

​原文:蓝桥杯 2013 省B 洛谷P8597题翻硬币 从暴力BFS到贪心算法的优化之路

点赞
收藏
评论区
推荐文章
贾蔷 贾蔷
3星期前
蓝桥杯2023接龙数列(洛谷P9242)题解:动态规划与数字首尾匹配的完美应用
一、题目解读这道蓝桥杯省赛真题要求找出数字序列中最长的接龙子序列(每个数字的首位等于前一个数字的末位),并计算需要删除的最少数字个数。题目考察动态规划的实际应用能力,是理解数字特征处理和状态转移的典型案例。二、解题步骤1.处理n1的特殊边界情况2.读取输入
贾蔷 贾蔷
3星期前
2025年GESP七级等价消除(洛谷P11965)代码解析与优化策略
一、题目解读2025年GESP七级考试中的“等价消除(洛谷P11965)”问题要求统计给定字符串中满足等价条件的子串数量。所谓“等价子串”,是指子串中所有字符出现的次数均相同。题目需要高效算法解决,考验对字符串处理和状态压缩的掌握。二、解题思路采用位运算
贾蔷 贾蔷
5天前
牛客12576题全解析:动态规划+质因数分解解决跳跃问题
一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂度,避免暴力枚举的指数级耗时。二、解题思路采用“动态规划
贾蔷 贾蔷
5天前
2023年GESP六级小杨握手问题(洛谷B3874):Fenwick树求解逆序对的代码解析
一、题目解读“小杨的握手问题”源自2023年GESP六级考试(对应洛谷题目B3874)。题目描述为:给定一个长度为N的排列,每次将当前数与之前未访问过的数握手,求总共握手次数。本质上是求排列中逆序对的个数,即统计每个数右侧比它小的元素数量。需设计高效算法在
深度学习 深度学习
5天前
【CSP-S 2019】括号树(洛谷P5658):栈+DFS
一、题目解读括号树问题(洛谷P5658)要求处理一个由括号序列转化的树结构:每个节点表示一个括号,'('为子节点,')'为父节点。题目给定一棵n个节点的树,需计算每个节点的深度(括号层数),并输出所有节点深度与节点编号乘积的异或和。核心在于将括号序列转化为
深度学习 深度学习
5天前
洛谷1111题解:基于Kruskal算法与并查集的最小生成树实现
一、题目解读洛谷1111题是一道经典的图论问题,要求构建一个无向图的最小生成树,并输出其最大边权值。题目核心在于通过给定的边集合,找到连接所有节点的最小权值子集,同时保证无环。这通常涉及最小生成树算法(如Kruskal)的应用,需要高效处理边权重与节点连通
深度学习 深度学习
5天前
2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解
一、题目解读2024年蓝桥杯省B组题目“前缀总分”(对应洛谷P12124)要求计算给定字符串集合中,所有前缀的最长公共前缀(LCP)的总分,并找出通过移动字符位置后可能获得的最大总分。题目考察字符串处理与动态规划能力,需高效计算LCP并优化得分策略。二、解
深度学习 深度学习
5天前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
深度学习 深度学习
4天前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,
贾蔷 贾蔷
2天前
【2023 CSP-S密码锁(洛谷P9752)】题解:动态规划与集合交集的巧妙应用
一、题目解读2023年CSPS的“密码锁”题目(洛谷P9752)要求破解一种环形密码锁机制。题目给定n组状态,每个状态由5个数字组成,通过“单拨圈”或“双相邻拨圈”操作可改变数字。正确密码需满足:通过操作能从初始状态转换到所有给定状态,且给定状态本身不能作