Matrix67生日邀请赛-NOIP2007模拟赛(2).doc

NOIP2008全国信息学奥林匹克联赛模拟试题（第二阶段集训） 2008年X月XX日Matrix67邀请赛-NOIP2007模拟赛II测试时间：3小时【题目一览】题号第一题第二题第三题题目名称Matrix67的情书II送给MM的生日礼物表白机器人提交文件lovelttr.pas/c/cpgift.pas/c/cpprobot.pas/c/cpp输入文件lovelttr.ingift.inrobot.in输出文件lovelttr.outgift.outrobot.out时间限制1s1s1s分值100100100Matrix67的情书II【问题描述】28是一个很特别的数字。它是一个完全数，是一个三角形数，是前五个素数的和。天上有28星宿，人有28颗牙齿；土星绕太阳公转一周需要28年，从一只猴子的释放到整座城市的沦陷只需28天。当然，Matrix67偏爱这个数字是有原因的：这是一个关心MM身体和计算安全期都必须用到的数字。总之，Matrix67非常喜欢数字28，他甚至希望数字28能够出现在他给MM写的情书里。Matrix67的情书只由数字、大小写字母、空格、换行符和各种英文半角标点符号组成。除去所有其它的字符，仅保留文本中的数字和字母，则整个情书可以看作是一个36进制数。例如，句子“I Love you!”可以转化为1457771337246，因为(ILOVEYOU)36=(1457771337246)10。Matrix67希望从情书中截取一个或若干个连续的句子，使得它所对应的十进制数能够被28整除。Matrix67希望知道他的情书中有多少个文本片段满足这样的条件。我们认为，只有句号、感叹号、问号三种符号才是句子结束的标志（当然整篇文章的结束也标志着最后一句话结束，即使文章最末尾没有任何标点符号）。Matrix67的情书里保证没有不能表示任何数字的“空句子”，即任意两个句子结束标志之间至少会出现一个数字或字母。【输入格式】输入文件中是一篇合法的英文文章，包括英文大小写字母、数字、空格、回车和半角的标点符号。【输出格式】输出文件中为满足要求的文本片段个数。一个满足要求的文本片段是指一个或若干个连续的句子，将它们当作36进制后得到的数可以被28整除。【输入输出样例】输入：I WILL SHOW YOUYes, I am still amazed that I have you. Its still hard to understand how you chose me. How after just one short conversation you knew I was meant for you. But now I know the truth of your conviction. Ive never been with someone who suited me so perfectly. You seduced me with your sexy body and strong spirit, and youve kept me with your tender heart. I know you that I cant have you completely and maybe not even for much longer. But Im still happy. A part of you has become part of me and that is enough.Youll laugh when I say this, but I dream about you every night. Probably because I cant see you often enough. But when Im awake I know that you are the furthest thing from a dream. Sometimes I imagine that you are built from solid rock: a moving statue and an indestructible human being. You absolutely contain yourself and then again much more than yourself. Your confidence is consuming and your perspective is huge. You have no place in your life for jealousy or complaints. My friends seem so small in comparison, with their problems always spilling over onto everyone else.I want you to know how much youve opened my eyes and helped me truly see myself. Until now, my life has been an undecided back-and-forth, and now I know that Ive wasted too much time. But now my direction seems clear, and I have confidence in my future. The past doesnt seem to matter anymore. Youve made me see possibilities I would never have imagined before.Yes, I want to please you. But its through pleasing you that Ill become a better and stronger person. There is nothing I want more than to transform myself through you. You challenge me to grow beyond myself and leave my weaker self behind. I will show you how beautiful I can be, and I will show you how brilliant I can become. This way, I know Ill always have your love.Forever yours,Matrix67输出：6【数据范围】对于30%的数据，输入文件大小不超过50KB；对于100%的数据，输入文件大小不超过1MB。送给MM的生日礼物【问题描述】10月11日是MM的生日，Matrix67打算自己DIY一些抱枕送给MM。Matrix67手中有一块矩形花布，花布分成了MN个小格子，有些格子的花色相同，有些格子的花色不同。为了使最终成品更美观，Matrix67希望用于DIY的布匹都是正方形的，并且满足布匹花色上下对称且左右对称。为此，他希望能计算出这块花布里一共包含有多少个上下对称且左右对称的小正方形。举例来说，Matrix67手中的花布大小为64，上面共有5种花色：ABACDADCDEAAABABAADDCBBA则这块布里一共有26个上下对称且左右对称的正方形，其中包括最左上角的33正方形、右边4个A组成的22正方形，当然还有24个11的小正方形。【输入格式】输入文件中的第一行为两个正整数M，N，表示Matrix67手中的格子布分为M行N列。以下的M行，每行有N个字符，描述布匹的花色。我们用26个大写字母来区别不同的花色，相同的字母代表相同的花色，不同的字母代表不同的花色。【输出格式】输出文件中仅一行为一个整数，即在Matrix67的格子布中切出一块花色左右对称且上下对称的正方形共有多少种方案。【输入输出样例】输入：4 6ABACDADCDEAAABABAADDCBBA输出：26【数据范围】对于30%的数据，满足：M，N=10；对于100%的数据，满足：M，N=200。表白机器人【问题描述】永远不要以为Matrix67就是传说中的情圣。很少有人知道，Matrix67竟然不好意思主动向MM表白！为此，Matrix67派出他的表白机器人，帮他完成这一项光荣而艰巨的任务。Matrix67和MM所在的地方可以看作是一个封闭的平面空间，里面分成了MN个房间，某些房间之间可能有墙。Matrix67总在最左下角的那个房间，MM总在最右上角的那个房间。Matrix67需要给它的机器人输入一系列方向指令，控制机器人避开墙壁到达MM所在的位置。如果L表示向左移一格，R表示向右移一格，U表示向上移一格，D表示向下移一格，那么在下图所示的44平面地图里，命令序列RURUUR可以让机器人从起点（左下角）到达终点（右上角）。#-#-#-#-#| | F |# # # #-#| | |# # # #-#| | |# # # # #| S |#-#-#-#-#但问题远远没有这么简单。由于设计上的缺陷，Matrix67的机器人只能记忆K条指令。这就意味着，当机器人的行走路线过长时，指令不一定能完整地输入机器人。这怎么办呢？Matrix67想到一个好办法：如果让机器人反复执行预先给定的K条指令，那么恰当的指令序列也能使机器人到达终点（虽然这样可能会走很多重复的路）。机器人会忽略所有命令它撞墙的指令。也就是说，如果下一个指令对应的方向上是一面墙的话，机器人将跳过该指令。Matrix67希望知道，是否存在一个长度为K的命令序列，若机器人反复执行这段指令，最终会到达MM所在的地方。对于上面给出的例子，当K=4时，RRLU是一个合法的答案。【输入格式】输入文件中的第一行为四个正整数M，N，W和K，分别表示该平面区域内有M行N列小房间，房间与房间之间共有W面墙，Matrix67需要给机器人输入的指令长度为K。以下的W行，每行有四个数Ai，Aj，Bi，Bj，表示第Ai行Aj列的房间与Bi行Bj列的房