历届试题翻硬币

问题描述

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作，那么要求：

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度<1000

输出格式

一个整数，表示最小操作步数。

样例输入1

**********
o****o****

样例输出1

样例输入2

*o**o***o***
*o***o**o***

样例输出2

思路：贪心思想，遍历两个字符串，从第一个不同的字符开始翻转下去，没翻转一次，就验证是否相同，是则结束输出翻转次数，否，继续翻转下去，直到两个字符串相同。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int array1[1000];
 4 int array2[1000];
 5 int check(int m,int length,int array1[],int array2[])
 6 {
 7     int flag=1;
 8     for(int i=m;i<length;i++)
 9     {
10         if(array1[i]!=array2[i]){
11             flag=0;
12             break;
13         }
14     }
15     return flag;
16 }
17 
18 int main()
19 {
20   //  cout << 1^1 << " " << 0^1 << endl;
21     string a;
22     string b;
23     cin >> a >> b;
24     memset(array1,0,sizeof(array1));
25     memset(array2,0,sizeof(array2));
26     int len=a.length();
27     for(int i=0;i<len;i++)
28     {
29         if(a[i]=='*') array1[i]=1;
30         if(a[i]=='o') array1[i]=0;
31         if(b[i]=='*') array2[i]=1;
32         if(b[i]=='o') array2[i]=0;
33     }
34     int sum=0;
35     for(int i=0;i<len-1;i++)
36     {
37 
38         if(array1[i]!=array2[i]){
39             array2[i]^=1;
40             array2[i+1]^=1;
41             sum++;
42         }
43         int test=check(i,len,array1,array2);
44         if(test==1) break;
45         if(test==0) continue;
46     }
47     cout << sum << endl;
48     return 0;
49 }

用到的c++知识

1.异或满足交换律。

2.相同两个数异或为0。

3.0异或一个数为那个数本身

历届试题 翻硬币

历届试题翻硬币