P17（ACWing笔记本）

关键点

• 要发现考的是递推，这n-1个操作，每一个都是被唯一确 定的，是不需要枚举的。
  因为题目说了有解，所以遍历到倒数第二枚的时候，所有硬币状态就与目标相同了。

看似是宽搜实则是递推！

#include <iostream>
#include <cstring>

using namespace std;

string a, b; //设置成全局变量

void turn(int x) {
    if (a[x] == '*') a[x] = 'o';
    else a[x] = '*';
}

int main () {
    cin >> a >> b;
    int res = 0;

    for (int i = 0; i + 1 < a.size(); i ++)  // 操作次数 只需要枚举到倒数第二个字符，因为最后一个字符一定相等，答案一定保证有解
        if (a[i] != b[i]) {
            res ++;
            turn(i), turn(i + 1);
        }

    cout << res << endl;
    return 0;
}

扩展题

95 费解的开关 https://www.acwing.com/problem/content/97/
208 开关问题 https://www.acwing.com/problem/content/210/