快捷通道

QQ登录

只需要一步，快速开始

  注册地址  找回密码

数学建模社区-数学中国

留学>>
12下一页
返回列表 发新帖
查看: 16579|回复: 13
打印 上一主题 下一主题

2006年百度之星程序设计大赛复赛题目4：彩球游戏

  [复制链接]
字体大小: 正常 放大
厚积薄发 实名认证       

1341

主题

738

听众

2万

积分

数学中国总编辑

  • TA的每日心情
    衰
    2016-11-18 10:46

    • 签到天数: 206 天

    [LV.7]常住居民III

    超级版主

    社区QQ达人 邮箱绑定达人 元老勋章 发帖功臣 新人进步奖 原创写作奖 最具活力勋章 风雨历程奖

    群组: 2011年第一期数学建模

    群组: 第一期sas基础实训课堂

    群组: 第二届数模基础实训

    群组: 2012第二期MCM/ICM优秀

    群组: MCM优秀论文解析专题
    跳转到指定楼层
    1#
    发表于 2010-5-6 19:12 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定

    彩球游戏
    6 g+ ~2 x' Y# y# b


    - [2 @0 d7 |. s6 G1 J

    X博士是一个研究儿童智力开发方法的科学家，他为幼儿教育领域做出了许多贡献。最近，X博士正在研究一种适合儿童的游戏，用以辅助发展儿童的观察力、注意力和思维能力。经过连日的构思，X博士终于设计出了一种游戏：彩球游戏。

    彩球游戏是一种单人参与的游戏，游戏首先给出一串由许多不同颜色的小球组成的小球序列，以及一个整数参数M（M≥2）。一段连续的具有相同颜色的小球序列称为连续同色序列。小孩，即游戏参与者，每次可以向任意一段连续同色序列插入一个同色小球，使该序列的长度加一。当一段连续同色序列在插入一个同色小球后其长度达到M时，该序列就会爆炸消失，然后原序列两边的其余小球会重新连成一串，如果两段相同颜色的连续同色序列在此时连接在一起，它们就会合并形成一段新的连续同色序列。如果新形成的连续同色序列长度达到M，这段序列也会爆炸消失，然后重复上述过程，直到没有新的长度达到M的连续同色序列出现为止。游戏的目标很简单，就是插入尽量少的小球，使得所有小球都爆炸消失掉。

    通过长时间的游戏和不断提高游戏水平，这个游戏可以很好地开发儿童的观察力、注意力和思维能力。但是X博士仍然面临着一个困难的问题，他还需要设计出一个游戏演示AI程序，可以以最优的方式（即插入的小球数量最小）进行游戏，用于游戏教学，或者在游戏中对小孩给出提示。X博士并不擅长此类程序，因而他无法完成这个任务，你可以帮助他吗？

    输入格式：

    输入文件包含多组测试数据。每组测试数据第一行为整数M（2≤M≤20），第二行为一条非空的字符串，由大写字母组成且长度不超过200，表示初始的一串小球，不同的字母表示不同的小球颜色。初始时可能会存在一些长度达到M的连续同色序列，但这些序列不会马上爆炸消失。

    输出格式：

    每组测试数据输出一行，表示至少需要插入多少次小球才能使所有小球爆炸消失掉。

    输入样例：

    3

    AAABAAA

    3

    ABBABBA

    输出样例：

    2

    2

    说明：

    共有5个测试数据集，每个测试数据集为一个输入文件，包含多组测试数据。每个测试数据集从易到难分别为5、10、15、30和40分，对每个测试数据集分别执行一次程序，每次必须在运行时限30秒内结束程序并输出正确的答案才能得分。

    所有数据均从标准输入设备（stdin/cin）读入，并写出到标准输出设备 （stdout/cout）中。

    五个测试数据集中输入初始小球队列的长度分别不大于10、20、50、100和200，各有不超过5000组测试数据。

    - V1 @" d& u! P$ Z5 O: ~

    5 T, N# t9 L: u9 N; I0 h1 E: j5 f; h3 I


    1 Z4 R* U8 O5 a, r

    zan
    转播转播0 分享淘帖0 分享分享1 收藏收藏0 支持支持1 反对反对0 微信微信
    回复

    使用道具 举报

    亦萌        

    0

    主题

    3

    听众

    57

    积分

    升级  54.74%

  • TA的每日心情
    开心
    2011-9-27 09:21

    • 签到天数: 10 天

    [LV.3]偶尔看看II

    群组: 数学建摸协会

    群组: 数学建模培训课堂2
    2#
    发表于 2011-8-7 14:38 |只看该作者 |招呼Ta 关注Ta
    回复

    使用道具 举报

    qo1211 实名认证       

    0

    主题

    3

    听众

    50

    积分

    升级  47.37%

  • TA的每日心情
    开心
    2013-4-16 14:01

    • 签到天数: 14 天

    [LV.3]偶尔看看II

    自我介绍
    我是来虚心求学的~o~
    3#
    发表于 2011-9-1 16:39 |只看该作者 |招呼Ta 关注Ta
    一共有几种颜色的小球呢？
    回复

    使用道具 举报

    覃伎岩        

    0

    主题

    4

    听众

    7

    积分

    升级  2.11%

    该用户从未签到
    4#
    发表于 2011-12-8 04:31 |只看该作者 |招呼Ta 关注Ta
    讲得不错哦，顶楼主" Q* h9 B+ q9 z8 p4 a2 q- G
    回复

    使用道具 举报

    pxwgih        

    0

    主题

    4

    听众

    151

    积分

    升级  25.5%

  • TA的每日心情
    开心
    2012-1-16 11:09

    • 签到天数: 1 天

    [LV.1]初来乍到
    5#
    发表于 2012-1-1 10:06 |只看该作者 |招呼Ta 关注Ta
    呵呵，不错
    回复

    使用道具 举报

    6#
    无效楼层，该帖已经被删除
    王凯明 实名认证       

    0

    主题

    4

    听众

    175

    积分

    升级  37.5%

  • TA的每日心情
    擦汗
    2014-8-24 16:59

    • 签到天数: 66 天

    [LV.6]常住居民II

    自我介绍
    西安电子科技大学

    群组: Matlab讨论组

    群组: 2013年国赛B题讨论组
    7#
    发表于 2012-5-17 23:31 |只看该作者 |招呼Ta 关注Ta
    谢谢，题目好难
    回复

    使用道具 举报

    wangchen881202 实名认证       

    1

    主题

    2

    听众

    663

    积分

  • TA的每日心情
    开心
    2012-8-9 11:28

    • 签到天数: 2 天

    [LV.1]初来乍到

    自我介绍
    我啥也不会……啥也别问我……=。=

    新人进步奖

    群组: Matlab讨论组
    8#
    发表于 2012-6-1 00:21 |只看该作者 |招呼Ta 关注Ta |邮箱已经成功绑定
    就你这个样子，这个年龄，已经跌破发行价了。
    7 e. g( ~9 Z1 z! m/ E& Z+ M7 l/ z6 ~8 ]7 r4 T9 h
    ~~~~哼..哼..哼...& f# N2 F* @& ?. Y. {3 h! I4 _
    回复

    使用道具 举报

    treemantan 实名认证       

    1

    主题

    3

    听众

    414

    积分

  • TA的每日心情
    怒
    2014-3-8 01:13

    • 签到天数: 4 天

    [LV.2]偶尔看看I

    自我介绍
    Treeman

    群组: Matlab讨论组

    群组: 数学建模

    群组: 数学建模培训课堂2

    群组: 计算机考研

    群组: 数学趣味、游戏、IQ等
    9#
    发表于 2012-6-8 22:00 |只看该作者 |招呼Ta 关注Ta
    我身边的朋友们啊，你们快点出名吧，这样我的回忆录就可以畅销了5 I2 N3 h1 G! J/ b/ B
    0 g+ R. d, y( L/ I
    赫赫
    / N" X" ^% u% ?% ^" V: @
    回复

    使用道具 举报

    liupeng723911 实名认证       

    9

    主题

    3

    听众

    2210

    积分

    升级  7%

  • TA的每日心情
    怒
    2012-3-25 10:36

    • 签到天数: 9 天

    [LV.3]偶尔看看II

    自我介绍
    华南理工大学计算机科学与工程学院

    新人进步奖

    群组: 华南理工大学
    10#
    发表于 2012-6-27 19:33 |只看该作者 |招呼Ta 关注Ta
    谢谢哦，辛苦辛苦！
    回复

    使用道具 举报

    12下一页
    返回列表 发新帖
    高级模式
    B Color Image Link Quote Code Smilies
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩

    • 电话咨询

    • 04714969085

    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问：王兆丰

    GMT+8, 2026-10-9 06:04 , Processed in 0.511036 second(s), 101 queries .

    回顶部