全国青少年信息学(计算机)奥林匹克分区联赛复赛模拟试题一

1、复赛模拟试题一（3小时,满分400分）说明：1.严格按照题目所要求的格式进行输入、输出，否则严重影响得分。2.题目测试数据有严格的时间限制5s，超时不得分。3.输入文件格式不用判错;从输入文件读入数据，输入文件名在程序中从键盘读入， 计算结果输出到屏幕。4.程序完成后，要按指定的提交文件名编译成EXE文件，指定的文件名如下：问题A: 天使的起誓（TENSHI NO YUBIKILI）问题描述：TENSHI非常幸运的被选为掌管智慧之匙的天使。在正式任职之前，她必须和其他新当选的天使一样，要宣誓。宣誓仪式是每位天使各自表述自己的使命，她们的发言稿被放在N个呈圆形排列的宝盒中。这些宝盒按顺时针方向被

2、编上号码、N-1、N。一开始天使们站在编号为N的宝盒旁。她们各自手上都有一个数字，代表她们自己的发言稿所在的盒子是从号盒子开始按顺时针方向的第几个。例如：有个盒子，那么如果TENSHI手上的数字为，那么她的发言稿所在盒子就是第个。现在天使们开始按照自己手上的数字来找发言稿，先找到的就可以先发言。TENSHI一下子就找到了，于是她最先上台宣誓：“我将带领大家开启NOI之门”TENSHI宣誓结束以后，陆续有天使上台宣誓。可以有一位天使找了好久都找不到她的发言稿，原来她手上的数字M非常大，她转了好久都找不到她想找的宝盒。任 务：请帮助这位天使找到她想找的宝盒的编号。输入格式：输入文件有两行分别正整数

3、N和M，其中N、M满足81000 2 N 10，2 M 10输出格式：文件只有一行即宝盒的编号样例一样例二问题B: 步步高升（Step by Step）问题描述：春节的时候TENSHI去逛花市。她来到一个卖盆竹的摊位，看到一盆叫做“步步高升”的盆竹。“步步高升，步步高升”学习就是要一步一步来，不能急，要打好基础。在稳固的基础上才谈得上步步高升！TENSHI若有所思。她看到这盆东西好意头，于是想买下。谁知一问价钱，“不贵不贵，才。”TENSHI差点没昏倒，囊中羞涩嘛。但是TENSHI还是很想买下来，于是她就在一旁观察。观察了一段时间，她发现这个卖盆竹的人和别人杀价很有规律。设此人第i次报价为Wi

4、元，那么他第i+1次报的价格为WiA或Wi B。到了最后，TENSHI以Z元成交，高高兴兴的回家去了。任 务 ：求TENSHI把盆竹的价格由W1元杀到Z元的方法总数。输入格式：输入文件第一行有两个正整数W1和Z。第二行有两个正整数A和B。它们满足条件：10 W1 106，1 Z 106 ，Z < W12 A 、B 10000，AB输出格式：将方法总数输出，只有一行。注意：结果不超过MAXLONGINT样例一样例二问题C: 竞赛真理（Truth of Contest）问题描述：TENSHI在经历了无数次学科竞赛的失败以后，得到了一个真理：做一题就要对一题！但是要完全正确地做对一题是要花很多

5、时间（包括调试时间），而竞赛的时间有限。所以开始做题之前最好先认真审题，估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。 当然，如果做完了预先选择的题目之后还有时间，但是这些时间又不足以完全解决一道题目，应该把其他的题目用贪心之类的算法随便做做，争取“骗”一点分数。任 务 ：根据每一题解题时间的估计值，确定一种做题方案（即哪些题目认真做，哪些题目“骗”分，哪些不做），使能在限定的时间内获得最高的得分，输入格式：输入文件的第一行有两个正整数N和T，表示题目的总数以及竞赛的时限（单位秒）。以下的N行，每行个正整数W1i 、T1i 、W2i 、T2i ，分别表示第i题

6、：完全正确做出来的得分，完全正确做出来所花费的时间（单位 秒），“骗”来的分数，“骗”分所花费的时间（单位秒）。其中，3 N 30，2 T 30000，1 W1i 、W2i 1000，1 T1i 、T2i T。输出格式：直接把所能得到的最高分值输出只有一行。样例一样例二问题D: 标点符号（Punctuation Mark）问题描述：有一天，TENSHI发现了一本叫Road to NOI的书。这本书是用英语写的，奇怪的是这本书完全没有标点符号，也没有空格！也就是说这本书整篇都是由一连串字母组成的。TENSHI研究了一会，发现了一种断句的方法：1)单词是由字母组成的，并且都可以在天使字典（和魔鬼字典相对的）找到，且这些单词是不区分大小写的（也就是说TenShi和tenshi是一个单词）2)每个单词的长度不超过。3)句子是由至少三个单词组成的，并且这些单词的字母总数是这些单词个数的倍数。例如：iwanttoseeheragain 可以看成是这样一句话：I want to see her again. 因为单词数为，且字母总数为，是的倍数。4)句子的第一个字母不一定要是大写字母。5)每个句子的字母总数不超过。任 务 ：给出一个字典以及一串字母，请为这串字母划分句子，使句子总数最多。输入格式：输入文件的第一行为一个正整数N（3