热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

1208.翻硬币(递推)

1208.翻硬币题目链接小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用*表示正面,用o表示反面(是小写字母,不是零

1208. 翻硬币

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

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

比如,可能情形是:**oo***oooo

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

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

我们约定:把翻动相邻的两个硬币叫做一步操作。

输入格式
两行等长的字符串,分别表示初始状态和要达到的目标状态。

输出格式
一个整数,表示最小操作步数

数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1:

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

输出样例1:

5

输入样例2:

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

输出样例2:

1

题目解释


每次只能翻动相邻的两个硬币,所以我们可以假设每两个硬币之间有一个开关,如果要改变这相邻的两个硬币,那么就相当于打开这个开关,同时改变相邻两个硬币的状态,因此只需要 for 一次字符串长度即可


数学解法:蓝桥杯历届试题-翻硬币

递推解法:

#include
#include
#include
#include
#include
#include
#include
#includeusing namespace std;
typedef long long ll;
const int N=60;string a, b;int main()
{cin >> a >> b;int step &#61; 0;for(int i &#61; 0; i < a.size(); i &#43;&#43; ){if(a[i] !&#61; b[i]){if(a[i] &#61;&#61; &#39;*&#39;) a[i] &#61; &#39;o&#39;;else a[i] &#61; &#39;*&#39;;if(a[i &#43; 1] &#61;&#61; &#39;*&#39;) a[i &#43; 1] &#61; &#39;o&#39;;else a[i &#43; 1] &#61; &#39;*&#39;;step &#43;&#43; ;}}cout << step << endl;return 0;
}

推荐阅读
  • poj 3352 Road Construction ... [详细]
  • 本文介绍如何使用线段树解决洛谷 P1531 我讨厌它问题,重点在于单点更新和区间查询最大值。 ... [详细]
  • 本报告对2018年湘潭大学程序设计竞赛在牛客网上的时间数据进行了详细分析。通过统计参赛者在各个时间段的活跃情况,揭示了比赛期间的编程频率和时间分布特点。此外,报告还探讨了选手在准备过程中面临的挑战,如保持编程手感、学习逆向工程和PWN技术,以及熟悉Linux环境等。这些发现为未来的竞赛组织和培训提供了 valuable 的参考。 ... [详细]
  • 本文详细解析了 Android 系统启动过程中的核心文件 `init.c`,探讨了其在系统初始化阶段的关键作用。通过对 `init.c` 的源代码进行深入分析,揭示了其如何管理进程、解析配置文件以及执行系统启动脚本。此外,文章还介绍了 `init` 进程的生命周期及其与内核的交互方式,为开发者提供了深入了解 Android 启动机制的宝贵资料。 ... [详细]
  • [c++基础]STL
    cppfig15_10.cppincludeincludeusingnamespacestd;templatevoidprintVector(constvector&integer ... [详细]
  • 零拷贝技术是提高I/O性能的重要手段,常用于Java NIO、Netty、Kafka等框架中。本文将详细解析零拷贝技术的原理及其应用。 ... [详细]
  • Halcon之图像梯度、图像边缘、USM锐化
    图像梯度、图像边缘、USM锐化图像梯度、图像边缘、USM锐化图像梯度、图像边缘、USM锐化图像卷积:1.模糊2.梯度3.边缘4.锐化1.视频教程:B站、 ... [详细]
  • 单片微机原理P3:80C51外部拓展系统
      外部拓展其实是个相对来说很好玩的章节,可以真正开始用单片机写程序了,比较重要的是外部存储器拓展,81C55拓展,矩阵键盘,动态显示,DAC和ADC。0.IO接口电路概念与存 ... [详细]
  • [转]doc,ppt,xls文件格式转PDF格式http:blog.csdn.netlee353086articledetails7920355确实好用。需要注意的是#import ... [详细]
  • 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4277。作者:Bob Lee,日期:2012年9月15日。题目描述:给定n个木棍,求可以组成的不同三角形的数量,最多15根木棍。 ... [详细]
  • 题目《BZOJ2654: Tree》的时间限制为30秒,内存限制为512MB。该问题通过结合二分查找和Kruskal算法,提供了一种高效的优化解决方案。具体而言,利用二分查找缩小解的范围,再通过Kruskal算法构建最小生成树,从而在复杂度上实现了显著的优化。此方法不仅提高了算法的效率,还确保了在大规模数据集上的稳定性能。 ... [详细]
  • 本文探讨了基础二分法在数据报告生成中的应用及其优化策略。通过分析二分法在处理大规模数据集时的高效性和准确性,提出了若干改进措施,以提升数据报告的生成速度和质量。具体包括算法的并行化处理、数据预处理技术的应用以及异常值的处理方法,旨在为数据分析师提供更为高效和可靠的工具。 ... [详细]
  • 在尝试对 QQmlPropertyMap 类进行测试驱动开发时,发现其派生类中无法正常调用槽函数或 Q_INVOKABLE 方法。这可能是由于 QQmlPropertyMap 的内部实现机制导致的,需要进一步研究以找到解决方案。 ... [详细]
  • Codeforces竞赛解析:Educational Round 84(Div. 2评级),题目A:奇数和问题
    Codeforces竞赛解析:Educational Round 84(Div. 2评级),题目A:奇数和问题 ... [详细]
  • Android 构建基础流程详解
    Android 构建基础流程详解 ... [详细]
author-avatar
撩人的醉了
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有