百度之星历年赛题.doc

1、2005 年百度之星程序设计大赛试题初赛题目第一题（共四题 100 分）：连续正整数（ 10 分） 题目描述：一个正整数有可能可以被表示为 n(n=2) 个连续正整数之和，如： 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。 输入数据：一个正整数，以命令行参数的形式提供给程序。 输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用

2、一个空格分隔。如果没有符合要求的序列，输出 “NONE” 。 例如，对于 15 ，其输出结果是： 1 2 3 4 5 4 5 6 7 8 对于 16 ，其输出结果是： NONE 评分标准：程序输出结果是否正确。 百度之星程序设计大赛试题 -2 第二题（共四题 100 分）：重叠区间大小（ 20 分） 题目描述：请编写程序，找出下面 “ 输入数据及格式 ” 中所描述的输入数据文件中最大重叠区间的大小。对一个正整数 n ，如果 n 在数据文件中某行的两个正整数（假设为 A 和 B ）之间，即 A=n=B ，则 n 属于该行；如果 n 同时属于行 i 和 j ，则 i 和 j 有重叠区间；重叠区间的

3、大小是同时属于行 i 和 j 的整数个数。 例如，行（ 10 20 ）和（ 12 25 ）的重叠区间为 12 20 ，其大小为 9 ；行（ 20 10 ）和（ 12 18 ）的重叠区间为 10 12 ，其大小为 3 ；行 (20 10) 和（ 20 30 ）的重叠区间大小为 1 。 输入数据：程序读入已被命名为 input.txt 的输入数据文本文件，该文件的行数在 1 到 1,000,000 之间，每行有用一个空格分隔的 2 个正整数，这 2 个正整数的大小次序随机，每个数都在 1 和 232-1 之间。（为便于调试，您可下载测试 input.txt 文件，实际运行时我们会使用不同内容的输入

4、文件。） 输出数据：在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出 0 。 评分标准：程序输出结果必须正确，内存使用必须不超过 256MB ，程序的执行时间越快越好。 百度之星程序设计大赛试题 -3 第三题（共四题 100 分）：字符串替换（ 30 分） 题目描述：请编写程序，根据指定的对应关系，把一个文本中的字符串替换成另外的字符串。 输入数据：程序读入已被命名为 text.txt 和 dict.txt 的两个输入数据文本文件， text.txt 为一个包含大量字符串（含中文）的文本，以 whitespace 为分隔符； dict.txt 为表示字符串（

5、 s1 ）与字符串（ s2 ）的对应关系的另一个文本（含中文），大约在 1 万行左右，每行两个字符串（即 s1 和 s2 ），用一个 t 或空格分隔。 dict.txt 中各行的 s1 没有排序，并有可能有重复，这时以最后出现的那次 s1 所对应的 s2 为准。 text.txt 和 dict.txt 中的每个字符串都可能包含除 whitespace 之外的任何字符。 text.txt 中的字符串必须和 dict.txt 中的某 s1 完全匹配才能被替换。（为便于调试，您可下载测试 text.txt 和 dict.txt 文件，实际运行时我们会使用不同内容的输入文件。） 输出数据：在标准输出上

6、打印 text.txt 被 dict.txt 替换后了的整个文本。 评分标准：程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。 第四题（共四题 100 分）：低频词过滤（ 40 分） 题目描述：请编写程序，从包含大量单词的文本中删除出现次数最少的单词。如果有多 个单词都出现最少的次数，则将这些单词都删除。 输入数据：程序读入已被命名为 corpus.txt 的一个大数据量的文本文件，该文件包含英 文单词和中文单词，词与词之间以一个或多个 whitespace 分隔。（为便于调试，您可下载 测试 corpus.txt 文件，实际运行时我们会使用不同内容的输入文件。） 输出数据：在

7、标准输出上打印删除了 corpus.txt 中出现次数最少的单词之后的文本（ 词与词保持原来的顺序，仍以空格分隔）。 评分标准：程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。 2005 年百度之星程序设计大赛试题总决赛题目题目描述： 八方块移动游戏要求从一个含 8 个数字（用 1-8 表示）的方块以及一个空格方块（用 0 表示）的 3x3 矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4 个方向可移动，在四个角落上有 2 个方向可移动，在其他位置上有 3 个方向可移动。例如，假设一个 3x3 矩阵

8、的初始状态为： 8 0 3 2 1 4 7 6 5 目标状态为： 1 2 3 8 0 4 7 6 5 则一个合法的移动路径为： 8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3 2 1 4 = 2 0 4 = 0 2 4 = 8 2 4 = 8 2 4 = 8 0 4 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为 5 。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。 请设计有效的（细节请见评分规则）算法找到从八方块的某初试状

9、态到某目标状态的所有可能路径中的最短路径，并用 C/C+ 实现。 输入数据： 程序需读入已被命名为 start.txt 的初始状态和已被命名为 goal.txt 的目标状态，这两个文件都由 9 个数字组成（ 0 表示空格， 1-8 表示 8 个数字方块），每行 3 个数字，数字之间用空格隔开。 输出数据： 如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出 -1 。 自测用例： 如果输入为： start.txt 和 goal.txt ，则产生的输出应为： 5 又例，如果用 7 8 4 3 5 6 1 0 2 替换 start.txt 中的内容，则产生的输出应为： 21

10、评分规则： 1 ）我们将首先使用和自测用例不同的 10 个 start.txt 以及相同的 goal.txt ，每个测试用例的运行时间在一台 Intel Xeon 2.80GHz 4 CPU/ 6G 内存的 Linux 机器上应不超过 10 秒（内存使用不限制），否则该用例不得分； 2 ）每个选手的总分（精确到小数点后 6 位） =10 秒钟内能产生正确结果的测试用例数量 x10+ （ 1/ 产生这些正确结果的测试用例的平均运行毫秒 ) ； 3 ）如果按此评分统计仍不能得出总决赛将决出的一、二、三等奖共计九名获奖者，我们将先设 N=2 ，然后重复下述过程直至产生最高的 9 位得分：用随机生成的

11、另外 10 个有解的 start.txt 再做测试，并对这 10*N 个测试用例用 2 ）中公式重新计算总分， N+ 。 2006 年百度之星程序设计大赛试题初赛题目2006 年百度之星程序设计大赛初赛题目 1 饭团的烦恼 “午餐饭团“ 是百度内部参与人数最多的民间组织。 同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。 参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。 但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团

12、的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。 饭团点菜的需求如下： 1 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。 2 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。 3 请紧记，百度饭团在各大餐馆享受 8 折优惠。 输入数据描述如下： 第一行包含三个整数 N ， M ， K （ 0=0) 输出 对输入的 N,K 如果 N 个员工通过一定的分组方式可能会一共需要 K

13、 场比赛，则输出 “YES“, 否则输出 “NO“, 每组数据占一行。 所有的输入输出均为标准输入输出。 例子 输入文件 : 2 0 2 1 3 1 3 2 输出 : YES YES NO YES 2006 年百度之星程序设计大赛初赛题目 4 2007-05-14 17:39 剪刀石头布 N 个小孩正在和你玩一种剪刀石头布游戏。 N 个小孩中有一个是裁判，其余小孩分成三组（不排除某些组没有任何成员的可能性），但是你不知道谁是裁判，也不知道小孩们的分组情况。然后，小孩们开始玩剪刀石头布游戏，一共玩 M 次，每次任意选择两个小孩进行一轮，你会被告知结果，即两个小孩的胜负情况，然而你不会得知小孩具体

14、出的是剪刀、石头还是布。已知各组的小孩分别只会出一种手势（因而同一组的两个小孩总会是和局），而裁判则每次都会随便选择出一种手势，因此没有人会知道裁判到底会出什么。请你在 M 次剪刀石头布游戏结束后，猜猜谁是裁判。如果你能猜出谁是裁判，请说明最早在第几次游戏结束后你就能够确定谁是裁判。 输入格式： 输入文件包含多组测试数据。每组测试数据第一行为两个整数 N 和 M （ 1 N 500 ， 0 M 2000 ），分别为小孩的个数和剪刀石头布游戏进行的次数。接下来 M 行，每行两个整数且中间以一个符号隔开。两个整数分别为进行游戏的两个小孩各自的编号，为小于 N 的非负整数。符号的可能值为“ = ”、

15、“ ”和“ 1 12 01 23 1 0 输出样例： Can not determine Player 1 can be determined to be the judge after 4 lines Impossible Player 0 can be determined to be the judge after 0 lines 说明： 共有 5 个测试数据集，每个测试数据集为一个输入文件，包含多组测试数据。每个测试数据集从易到难分别为 5 、 10 、 15 、 30 和 40 分，对每个测试数据集分别执行一次程序，每次必须在运行时限 3 秒内结束程序并输出正确的答案才能得分。 所有数据均从标准输入设备（ stdin/cin ）读入，并写出到标准输出设备 （ stdout/cout ）中。 五个测试数据集中输入 N 分别不大于 20 、 50 、 100 、 200 和 500 ，各有 10 组测试数据。 2006 年百度之星程序设计大赛初赛题目 5 座位调整 题目描述： 百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。 调整的方法如下： 1 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。