13年第四届蓝桥杯C/C++大学B组真题———翻硬币
/* 第八题
题目标题：翻硬币
小明正在玩一个“翻硬币”的游戏。
桌面上摆放着呈一行排列的多个硬币。我们采用 * 标记正面，并用 o 标记反面（其中 o 代表非零的小写字母）
比如，可能情形是：oo*oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
小明面临的问题是：知道了起始状态以及目标状态后，在每次必须翻转相邻的两个硬币的前提下，
对于特定的情况而言，
最少需要多少次操作才能达到目标呢？
我们定义：每一次翻转相邻的两个硬币视为一步操作，
因此，
我们的目标就是确定完成这一转换所需的最小步数。
两个长度相同的字符串各自代表起始状态与目标状态。每条字符串的长度均小于1000个字符。
程序输出：
一个整数，表示最小操作步数
例如：
用户输入：
oo
程序应该输出：
5
再例如：
用户输入：
ooo***
ooo***
程序应该输出：
1
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：main函数应返回0
规定仅采用ANSI C/ANSI C++标准, 不得调用任何编译环境或操作系统的特殊函数。
所有调用的外部函数必须明确包含在源文件中的相应头文件中, 不得通过工程设置省略常用头文件。
提交时，注意选择所期望的编译器类型。
*/
分析：
审视题目时会注意到每行长度受限于1 个千字以下的规定，则显而易见地深搜这一方法并不适用，在这种情况下自然会想到存在某种规律性的东西需要考虑。通过分析给出的两组样例题，在初始状态和目标状态下不同位置上的硬币出现差异时会发现这些硬币下标之间的差值之和与移动步数之间有着密切的关系，请问接下来按照思路编写代码吧！
代码：
#include<stdio.h>
#include<string.h>
int main()
{
char str1[1010], str2[1010];
int str[1010];
scanf("%s%s",str1,str2);
int t = 0, len = strlen(str1);
for( int i = 0; i < len; i++ )
{
if( str1[i] != str2[i] )
{
//printf("%d<< \n",i);
str[t++] = i;
}
}
int sum = 0;
for( int i = 1; i < t; i += 2 )
{
//printf("<<%d ",str[i]);
sum = sum + str[i]-str[i-1];
}
printf("%d\n",sum);
return 0;
}