07年NOIp模拟赛byMatrix67比赛已顺利结束题目内容在此发布

1、询|縛2007-10-05 8:28| （$24 Comments |本文内容遵从 转载请注明出自2007年10月5日，我举办了一次NOlp模拟赛。现在比赛已经顺利结束了，以 下是这次比赛的题目题目一览题目名称 传播Matrix67 的情书（二）表白机器人题目类型传统传统送给MM勺生日礼物流言的传传统源文件名称 lovelttr.(pas/c/cpp)robot.(pas/c/cpp)gift.(pas/c/cpp)rumor.(pas/c/cpp)输出文件 名时间限制1秒1秒1秒1秒内存限制64M64M64M64M测试点10个10个10个10个分值100分100分100分100分输入文件 名

2、Problem 1: lovelttrMatrix67 的情书（二）问题描述28是一个很特别的数字。它是一个完全数，是一个三角形数，是前五 个素数的和。天上有 28星宿，人有 28颗牙齿；土星绕太阳公转一周需要 28年， 从一只猴子的释放到整座城市的沦陷只需 28 天。当然， Matrix67 偏爱这个数字 是有原因的：这是一个关心 MM身体和计算安全期都必须用到的数字。总之， Matrix67非常喜欢数字28,他甚至希望数字28能够出现在他给MM写的情书里。Matrix67 的情书只由数字、大小写字母、空格、换行符和各种英文半 角标点符号组成。 除去所有其它的字符， 仅保留文本中的数字和字母

3、， 则整个情 书可以看作是一个 36 进制数。比如，句子“ I Love you! ”可以转化为，因为 (ILOVEYOU)36 = ()10 。 Matrix67 希望从情书中截取一个或若干个连续的句子， 使得它所对应的十进制数能够被 28整除。 Matrix67 希望知道他的情书中有多少 个文本片段满足这样的条件。我们认为，只有句号、感叹号、问号三种符号才是句子结束的标志(当 然整篇文章的结束也标志着最后一句话结束，即使文章最末尾没有任何标点符 号)。 Matrix67 的情书里保证没有不能表示任何数字的“空句子”，即任意两 个句子结束标志之间至少会出现一个数字或字母。输入数据输入数据是一

4、篇合法的英文文章，包括英文大小写字母、数字、空格、 回车和半角的标点符号。输出数据输出满足要求的文本片段个数。 一个满足要求的文本片段是指一个或若 干个连续的句子，将它们当作 36进制后得到的数可以被 28整除。样例输入I WILL SHOW YOUYes, I am still amazedthat I have you. It's 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 t

5、he truth of your conviction. I've never been with someone who suited me so perfectly. You seduced me with your sexy body and strong spirit, and you've kept me with your tender heart. I know you that I can't have you completely and maybe not even for much longer. But I'm still happy.

6、A part of you has become part of me and that is enough.You'll laugh when I say this, but I dream about you every night. Probably because I can't see you often enough. But when I'm awake I know that you are the furthest thing from a dream. SometimesI imagine that you are built from solid

7、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 pr

8、oblems always spilling over onto everyone else.I want you to know how muchyou've 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 I've wasted too much time. But now my direction seems clear, and I have confidence in m

9、yfuture. The past doesn't seemto matter anymore. You've made me see possibilities I would never have imagined before.Yes, I want to please you. But it's through pleasing you that I'll become a better and stronger person. There is nothing I want more than to transform myself through y

10、ou. You challenge meto 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 I'll always have your love.Forever yours,Matrix67样例输出6数据规模对于 30%的输入数据，输入文件大小不超过 50KB；对于 100%的输入数据，输入文件大小不超过 1MB。Prob

11、lem 2: gift送给MM的生日礼物问题描述10月11日是MM勺生日，Matrix67打算自己DIY 些抱枕送给MM Matrix67 手中有一块矩形花布，花布分成了 M x N 个小格子，有些格子的花色 相同，有些格子勺花色不同。为了使最终成品更美观， Matrix67 希望用于 DIY 勺布匹都是正方形勺， 并且满足布匹花色上下对称且左右对称。 为此，他希望能 计算出这块花布里一共包含有多少个上下对称且左右对称勺小正方形。举例来说， Matrix67 手中勺花布大小为 6 x 4 ，上面共有 5种花色：ABACDADCDEAAABABAADDCBBA则这块布里一共有 26 个上下对称且

12、左右对称的正方形，其中包括最左上角的3x3正方形、右边4个A组成的2x2正方形，当然还有24个1x1的小正 方形。输入数据第一行输入两个用空格隔开的正整数 M,N,表示Matrix67手中的格子 布分为M行N列。以下M行每行N个字符，描述布匹的花色。我们用 26个大写字母来区 别不同的花色，相同的字母代表相同的花色，不同的字母代表不同的花色。输出数据输出在 Matrix67 的格子布中切出一块花色左右对称且上下对称的正方 形共有多少种方案。样例输入4 6ABACDADCDEAAABABAADDCBBA样例输出数据规模对于 30%的数据， M,N<=10；对于 100%的数据， M,N&l

13、t;=200。Problem 3: rumor流言的传播问题描述昨天下午，Matrix67陪MMB去逛街，走累了后去咖啡店歇了歇脚；再 后来MM陪Matrix67去了一趟书店，之后两人去电影院看了一场电影。 从电影院 出来后已经很晚了，考虑到 MM的安全问题，Matrix67先送MM回到宿舍，然后 自己才回去。第二天Matrix67起床后发现问题严重了：昨天和MM出去玩本来什 么都没发生， 但现在一些不堪入耳的流言正疯狂传播， 很多细节都说得有鼻子有 眼的。在澄清事实并抓出元凶的同时， Matrix67 希望切断一些流言传播的路径， 尽可能减缓流言传播的速度。除去Matrix67和他的MM学校

14、里还有N个人。这N个人形成了 M对双 向的朋友关系，这些朋友关系连通了所有N个人。不同的朋友间传递消息的速度 各不相同。如果A和B是第i对朋友，那么当其中一个人听到流言后，他会在 Ti 的时间内传给另一个人。现在， Matrix67 只知道流言并没有传遍整个学校， 但他不知道哪些人已经听说了这个流言。 他希望切断尽可能少的朋友关系， 使得 无论是哪些人已经获知了流言， 流言都无法以原来的速度传给一个新的人 （即新 的得知此流言的人的出现将变得更晚）。换句话说， Matrix67 希望找到一个最 小的边集E,使得对任意一个不等于全集的点集 S,恰好只有一个顶点在S里的 边中权值最小的那一条在边集

15、 E中。输入数据第一行输入两个用空格隔开的正整数 N和M,分别表示学校的人数和朋友关系数以下M行每行有三个用空格隔开的正整数，其中第i行的三个正整数为 Ai, Bi, Ti ，表示Ai和Bi是第i对朋友，它们之间传递消息需要 Ti的时间。 输入数据保证0<Ai工Bi<=N, 0<Ti<=2 000 000 000,且对任意i乞 都有Ti工Tj。输出数据你需要输出你所得到的最小值和具体的方案。输出文件的第一行是一个正整数， 代表你的最优方案中需要切断的朋友 关系数。以下若干行每行一个正整数， 表示你的方案里需要切断的朋友关系在输 入数据中的编号 （即你需要切断的是输入数据

16、中给的第几条边） 。这些数必须按 照增序排列输出。如果有多种最优方案， 你只需要输出其中一种即可。 我们的评测系统会 自动判断你的输出数据的正确性。样例输入4 41 2 24 3 42 3 31 3 1样例输出31样例说明(1)o/ 1 / 2/ (4) o-o-o (2)4(3) 3首先， (3)-(4) 这条边必须去掉，否则若只有 4 号同学得知流言，流 言将以相同的速度传给下一个人。 对于其它三条边， 只需要去掉权值较小的两条 即可，这样不论获知流言的是哪个(些)人，所有可以继续向外传播流言的边中 最小的那一条一定已经被去掉了。可以证明，去掉三条边已经是最优的答案了。数据规模对于 30%

17、的数据， N<=10，M<=20；对于 50%的数据， N<=100，M<=1 000；对于 100%的数据， N<=10 000， M<=100 000。Problem 4: robot表白机器人问题描述永远不要以为 Matrix67 就是传说中的情圣。很少有人知道， Matrix67 竟然不好意思主动向MM表白！为此，Matrix67派出他的表白机器人，帮他完成 这一项光荣而艰巨的任务。Matrix67和MM所在的地方可以看作是一个封闭的平面空间，里面分成 了 M x N个房间，某些房间之间可能有墙。 Matrix67总在最左下角的那个房间， MM、在最

18、右上角的那个房间。Matrix67需要给它的机器人输入一系列方向指令， 控制机器人避开墙壁到达 MM所在的位置。如果L表示向左移一格，R表示向右 移一格，U表示向上移一格，D表示向下移一格，那么在下图所示的 4x4平面地 图里，命令序列RURUU可以让机器人从起点（左下角）到达终点（右上角）。#-#-#-#-#| |F# # #1 1#-#| |#11#-#| |# # # #| S#-#-#-#-#但问题远远没有这么简单。由于设计上的缺陷， Matrix67 的机器人只 能记忆K条指令。这就意味着，当机器人的行走路线过长时，指令不一定能完整 地输入机器人。这怎么办呢？ Matrix67 想到

19、一个好办法：如果让机器人反复执 行预先给定的K条指令，那么恰当的指令序列也能使机器人到达终点（虽然这样可能会走很多重复的路）。机器人会忽略所有命令它撞墙的指令。也就是说，如 果下一个指令对应的方向上是一面墙的话，机器人将跳过该指令。 Matrix67 希 望知道，是否存在一个长度为K的命令序列，若机器人反复执行这段指令，最终 会到达MM所在的地方。对于上面给出的例子，当 K=4时，RRLU是一个合法的答 案。输入数据第一行输入四个用空格隔开的正整数 M N W和K,表示该平面区域内 有M行N列小房间，房间与房间之间共有 W面墙，Matrix67需要给机器人输入 的指令长度为 K。以下W行每行四

20、个数Ai, Aj, Bi, Bj，表示第Ai行Aj列的房间与Bi行 Bj 列的房间之间有一面墙。输出数据你的输出数据应该是一个由L、R、U D四种字符组成的长度为K的字 符串，表示一个合法的指令序列。 机器人反复执行这串指令后最终可以到达右上 角的房间。输入数据保证有唯一解，因此你不用考虑多解或无解的情况。样例输入4 4 5 41 2 1 32 2 2 31 4 2 42 4 3 43 1 3 2样例输出RRLU数据规模对于 30%的数据， K<=4；对于100%勺数据，M,Nv=5 K<=&对题目有任何疑问请在下面提出。很多人都对第一题有比较大的疑问。这里再给出一组样例

21、如果输入文件是那么输出为4。4个满足要求的文本片段为：S = 28S = 28SS = 10362SSC = 130620Posted inTags:,Trackback:我猜您可能还喜欢：24条回复sofa楼层：板凳 I 2007-10-05 8:32| Neptun 说:BanDeng尚在乎？楼层：地毯 |2007-10-05 8:35| alex 说：第一题中的"36进制"是以'0'为0还是'a'为0?回复：当然是以0为0咯楼层：地板 |2007-10-05 8:44| Renjor 说：第一题里面多个句子组成的数字是相乘还是去掉标点视

22、为一个句子处理回复：去掉标点视为一个句子处理楼层： 地下室 |2007-10-05 8:50| anthony 说：请问4*4的对称是怎么定义的？回复：上面两行和下面两行对折后重叠，左边两列和右边两列对折后重叠。比如，下面的图形就是上下对称且左右对称的。ABBADCCDDCCDABBA楼层： 地基 |2007-10-05 8:57| SWj 说：关于第一题如果一篇文章有三句组成.每句都能被28整除 那最后答案是3还是6?楼层: 地壳 |2007-10-05 9:07| oibeg inner说:大牛出的题目好难啊楼层：地幔 |2007-10-05 9:11| tea 说：第一题文件怎么读才算结束啊？回复：用EOF楼层：地核 |2007-10-05 9:24| snmyj 说：请问第一题的标题算不算第一个句子的内容回复：标题算作是整个输入数据中第一句的一部分关于第一题 如果一篇文章有三句组成.每句都能被28整除 那最后答案是3还是6?回复：这个不太方便回答。不妨看看后面给出的样例2楼层：11楼|2007-10-05 9:30|匿名龙神号 说:“Matrix67 的情书”这个名词勾起了我无限美好的回忆楼层:12 楼 |2007-10-05 10:04| upsuper 说:这也过难掉了吧。NOlp会有这样难度的么。楼层: