当前位置: 首页 > news >正文

翻硬币

翻硬币


问题描述

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

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

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

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

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

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

输入格式

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

输出格式

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

样例输入1
**********
o****o****
样例输出1
5
样例输入2
*o**o***o***
*o***o**o***
样例输出2
1

Algorithm

题目标签是贪心算法,但是我们可以利用另外一种思想来解决问题:自动机。

这道题目是一个简单的有限自动机:https://baike.baidu.com/item/%E6%9C%89%E9%99%90%E8%87%AA%E5%8A%A8%E6%9C%BA/8700995?fr=aladdin 

这个灵感来源于洛谷的一个统计单词的题目:https://www.luogu.org/problemnew/solution/P1308

题目比较简单,上代码。


 

AC

 1 /*
 2 * 虽说是贪心算法,但是我在洛谷看见过一篇
 3 * 统计单词个数的算法,用到了有限自动机的
 4 * 思想,这里也拿来试试
 5 * https://baike.baidu.com/item/%E6%9C%89%E9%99%90%E8%87%AA%E5%8A%A8%E6%9C%BA/8700995?fr=aladdin 
 6 */
 7 #include<iostream>
 8 #include<string>
 9 
10 #define flipud(a) (a == 'o')?'*':'o';
11 
12 using namespace std;
13 
14 int solve(string a, string b)
15 {
16     // 自动机:逐个字符对比,相同则他们的状态为不变,反之变化,计数+1 
17     // char S[2] = {'*', 'o'};    // 题目比较简单,状态集可以不要 
18     int len = a.size(), c = 0;
19     for(int i=0;i<len-2;i++){
20         if(a.at(i) != b.at(i)){
21             b.at(i+1) = flipud(b.at(i+1));
22             c++;
23         }
24     }
25     c += (*(a.end()-1) == *(b.end()-1))?0:1;
26     return c;
27 }
28 
29 int main()
30 {
31     string x, y;
32     while(cin>>x>>y)
33     {
34         cout<<solve(x, y)<<endl;
35     }
36     
37     return 0;
38  } 
View Code

 

 

转载于:https://www.cnblogs.com/mabeyTang/p/10268720.html

相关文章:

  • How cc Works 中文译文
  • 如何优雅地查看 JS 错误堆栈?
  • [转]IPTABLES中SNAT和MASQUERADE的区别
  • PaddlePaddle-GitHub的正确打开姿势
  • Codeforces 1097 Alex and a TV Show
  • 第八届(2018)CSR年度盛典在北京举办
  • 身残心不残 河北大城63岁独身老人捐献遗体
  • Spring Batch JSON 支持
  • settings配置数据库和日志
  • K-means 怎么选 K ?
  • 蚂蚁金服庆涛:OceanBase支撑2135亿成交额背后的技术原理
  • Electron构建跨平台应用Mac/Windows/Linux
  • 每个 JavaScript 开发者都该了解的 ES2018 新特性
  • 混合式开发框架资料汇总
  • Python爬虫初学者需要了解的知识与技能
  • 2017前端实习生面试总结
  • C# 免费离线人脸识别 2.0 Demo
  • flask接收请求并推入栈
  • golang中接口赋值与方法集
  • JavaScript函数式编程(一)
  • Java应用性能调优
  • linux安装openssl、swoole等扩展的具体步骤
  • Linux链接文件
  • log4j2输出到kafka
  • PAT A1092
  • Phpstorm怎样批量删除空行?
  • Redis中的lru算法实现
  • thinkphp5.1 easywechat4 微信第三方开放平台
  • Zsh 开发指南(第十四篇 文件读写)
  • 技术攻略】php设计模式(一):简介及创建型模式
  • 强力优化Rancher k8s中国区的使用体验
  • 使用iElevator.js模拟segmentfault的文章标题导航
  • 算法-图和图算法
  • 一些基于React、Vue、Node.js、MongoDB技术栈的实践项目
  • 与 ConTeXt MkIV 官方文档的接驳
  • #{}和${}的区别是什么 -- java面试
  • #pragam once 和 #ifndef 预编译头
  • #每天一道面试题# 什么是MySQL的回表查询
  • (09)Hive——CTE 公共表达式
  • (1)安装hadoop之虚拟机准备(配置IP与主机名)
  • (16)Reactor的测试——响应式Spring的道法术器
  • (175)FPGA门控时钟技术
  • (Mac上)使用Python进行matplotlib 画图时,中文显示不出来
  • (Redis使用系列) Springboot 实现Redis消息的订阅与分布 四
  • (附源码)ssm本科教学合格评估管理系统 毕业设计 180916
  • (强烈推荐)移动端音视频从零到上手(上)
  • (三分钟了解debug)SLAM研究方向-Debug总结
  • (转)MVC3 类型“System.Web.Mvc.ModelClientValidationRule”同时存在
  • *上位机的定义
  • .babyk勒索病毒解析:恶意更新如何威胁您的数据安全
  • .NET 8.0 中有哪些新的变化?
  • .NET开源的一个小而快并且功能强大的 Windows 动态桌面软件 - DreamScene2
  • @property括号内属性讲解
  • @RequestBody详解:用于获取请求体中的Json格式参数
  • [ 英语 ] 马斯克抱水槽“入主”推特总部中那句 Let that sink in 到底是什么梗?