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

3天前比赛题解51

一、问题背景与理解

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

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

二、暴力BFS解法分析

2.1 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;
}

2.2 BFS解法的问题

虽然BFS能够保证找到最短路径，但当字符串长度n较大时，状态空间会呈指数级增长(2^n)，导致时间和空间复杂度都不可接受，这就是为什么会出现"超时"的情况。

三、贪心算法优化

3.1 贪心算法思路

通过观察可以发现，这个问题实际上可以使用贪心算法在线性时间内解决：

从左到右逐个比较两个字符串的字符

当发现不匹配的字符时，执行翻转操作

每次翻转都会影响后续k-1个字符的状态

最后检查整个字符串是否匹配

3.2 贪心算法实现

#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;
}

3.3 贪心算法正确性证明

贪心算法的正确性基于以下观察：

每个位置最多只需要翻转一次

翻转顺序不影响最终结果

从左到右处理可以确保前面的状态不会被后续操作破坏

四、算法复杂度分析

‌BFS解法‌：

时间复杂度：O(2^n)

空间复杂度：O(2^n)

适用于n很小的情况

‌贪心解法‌：

时间复杂度：O(n)