百度之星历年赛题.doc

2005 年百度之星程序设计大赛试题初赛题目第一题(共四题 100 分):连续正整数( 10分) 题目描述:一个正整数有可能可以被表示为 n(n&gt;=2) 个连续正整数之和,如: 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列。输入数据:一个正整数,以命令行参数的形式提供给程序。输出数据:在标准输出上打印出符合题目描述的全部正整数序列,每行一个序列,每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列,按各序列的最小正整数的大小从小到大打印各序列。此外,序列不允许重复,序列内的整数用一个空格分隔。如果没有符合要求的序列,输出“ NONE ”。例如,对于 15,其输出结果是: 1234545678对于 16,其输出结果是: NONE 评分标准:程序输出结果是否正确。百度之星程序设计大赛试题-2 第二题(共四题 100 分):重叠区间大小( 20分) 题目描述:请编写程序,找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。对一个正整数 n,如果 n在数据文件中某行的两个正整数(假设为 A和 B)之间,即 A<=n<=B 或 A>=n>=B ,则 n属于该行;如果 n同时属于行 i和 j,则 i和 j有重叠区间;重叠区间的大小是同时属于行 i和 j的整数个数。例如,行( 10 20)和( 12 25)的重叠区间为[12 20] ,其大小为 9;行( 20 10)和( 12 18)的重叠区间为[10 12] ,其大小为 3;行(20 10) 和( 20 30)的重叠区间大小为 1。输入数据:程序读入已被命名为 的输入数据文本文件,该文件的行数在 1到 1,000,000 之间, 每行有用一个空格分隔的 2个正整数,这 2个正整数的大小次序随机,每个数都在 1和 2^32-1 之间。(为便于调试,您可下载测试 文件,实际运行时我们会使用不同内容的输入文件。) 输出数据:在标准输出上打印出输入数据文件中最大重叠区间的大小,如果所有行都没有重叠区间,则输出0。评分标准:程序输出结果必须正确,内存使用必须不超过 256MB ,程序的执行时间越快越好。百度之星程序设计大赛试题-3 第三题(共四题 100 分):字符串替换( 30分) 题目描述:请编写程序,根据指定的对应关系,把一个文本中的字符串替换成另外的字符串。输入数据:程序读入已被命名为 和 的两个输入数据文本文件, 为一个包含大量字符串(含中文)的文本,以 whitespace 为分隔符; 为表示字符串( s1)与字符串( s2)的对应关系的另一个文本(含中文),大约在 1万行左右,每行两个字符串(即 s1和 s2),用一个\t或空格分隔。 中各行的 s1没有排序,并有可能有重复,这时以最后出现的那次 s1所对应的 s2为准。 和 中的每个字符串都可能包含除 whitespace 之外的任何字符。 中的字符串必须和 中的某 s1完全匹配才能被替换。(为便于调试,您可下载测试 和 文件, 实际运行时我们会使用不同内容的输入文件。) 输出数据:在标准输出上打印 被 替换后了的整个文本。评分标准:程序输出结果必须正确,内存使用越少越好,程序的执行时间越快越好。第四题(共四题 100 分):低频词过滤( 40分) 题目描述:请编写程序,从包含大量单词的文本中删除出现次数最少的单词。如果有多个单词都出现最少的次数,则将这些单词都删除。输入数据:程序读入已被命名为 的一个大数据量的文本文件,该文件包含英文单词和中文单词,词与词之间以一个或多个 whitespace 分隔。(为便于调试,您可下载测试 文件,实际运行时我们会使用不同内容的输入文件。) 输出数据:在标准输出上打印删除了 中出现次数最少的单词之后的文本( 词与词保持原来的顺序,仍以空格分隔)。评分标准:程序输出结果必须正确,内存使用越少越好,程序的执行时间越快越好。 2005 年百度之星程序设计大赛试题总决赛题目题目描述: 八方块移动游戏要求从一个含 8个数字(用 1-8 表示)的方块以及一个空格方块(用0表示)的 3x3 矩阵的起始状态开始,不断移动该空格方块以使其和相邻的方块互换,直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动,在四个角落上有