---
title: "翻硬币"
created: 2025-11-28
tags:
  - 算法
---

# 翻硬币

## 题目 [翻硬币](https://www.acwing.com/problem/content/1210/)

![[image-8002504b.png]]

## 思路分析

给定初始状态 以及一些操作 询问最少多少次操作能变成目标状态

这类模型一般有两种写法

      宽搜（每个状态看做一个点 通过某种操作使得状态1变成状态2 就在他们之间连一条边 最后其实就是一个求最短距离的问题）但适合数据范围较小的问题

      尝试递推出每个开关应该继续的操作


也就是说 第一个状态只有第一个能确定（比对答案状态）

而一旦确定第一个状态 后面都不能改变前面的状态 只能对后面的连续开关做操作

每次前一个状态都能确定后一个状态如何

并没有选择性（看起来有多种选择性 实际上要是有解的话 就必然只有一个解）

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

string source,aim;

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

int main()
{
    cin>>source>>aim;
    int res=0;
    for(int i=0;i+1<source.size();i++){
        if(source[i]!=aim[i]){
            turn(i),turn(i+1);
            res++;
        }
    }
    cout<<res<<endl;
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[简单斐波那契(递推实现)|简单斐波那契(递推实现)]] 🏠 [[00-刷题理模型]] ➡️ [[费解的开关|费解的开关]]