2005年百度之星程序设计大赛试题初赛题目
第一题（共四题 100 分）：连续正整数（ 10 分）
题目描述：一个正整数有可能可以被表示为 n(n>=2) 个连续正整数之和，如：
15=1+2+3+4+5
15=4+5+6
15=7+8
请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。
输入数据：一个正整数，以命令行参数的形式提供给程序。
输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出 “NONE” 。
例如，对于 15 ，其输出结果是：
1 2 3 4 5
4 5 6
7 8
对于 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 。
输入数据：程序读入已被命名为 input.txt 的输入数据文本文件，该文件的行数在 1 到 1,000,000 之间，每行有用一个空格分隔的 2 个正整数，这 2 个正整数的大小次序随机，每个数都在 1 和 2^32-1 之间。（为便于调试，您可下载测试 input.txt 文件，实际运行时我们会使用不同内容的输入文件。）
输出数据：在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出 0 。
评分标准：程序输出结果必须正确，内存使用必须不超过 256MB ，程序的执行时间越快越好。
百度之星程序设计大赛试题 -3
第三题（共四题 100 分）：字符串替换（ 30 分）
题目描述：请编写程序，根据指定的对应关系，把一个文本中的字符串替换成另外的字符串。
输入数据：程序读入已被命名为 text.txt 和 dict.txt 的两个输入数据文本文件， text.txt 为一个包含大量字符串（含中文）的文本，以 whitespace 为分隔符； dict.txt 为表示字符串（ 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 文件，实际运行时我们会使用不同内容的输入文件。）
输出数据：在标准输出上打印 text.txt 被 dict.txt 替换后了的整个文本。
评分标准：程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。
第四题（共四题 100 分）：低频词过滤（ 40 分）
题目描述：请编写程序，从包含大量单词的文本中删除出现次数最少的单词。如果有多
个单词都出现最少的次数，则将这些单词都删除。
输入数据：程序读入已被命名为 corpus.txt 的一个大数据量的文本文件，该文件包含英
文单词和中文单词，词与词之间以一个或多个 whitespace 分隔。（为便于调试，您可下载
测试 corpus.txt 文件，实际运行时我们会使用不同内容的输入文件。）
输出数据：在标准输出上打印删除了 corpus.txt 中出现次数最少的单词之后的文本（
词与词保持原来的顺序，仍以空格分隔）。
评分标准：程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。
2005年百度之星程序设计大赛试题总决赛题目
题目描述：
八方块移动游戏要求从一个含 8 个数字（用 1-8 表示）的方块以及一个空格方块（用 0 表示）的 3x3 矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4 个方向可移动，在四个角落上有 2 个方向可移动，在其他位置上有 3 个方向可移动。例如，假设一个 3x3 矩阵的初始状态为：
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 。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。
请设计有效的（细节请见评分规则）算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径，并用 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
评分规则：
1 ）我们将首先使用和自测用例不同的 10 个 start.txt 以及相同的 goal.txt ，每个测试用例的运行时间在一台 Intel Xeon 2.80GHz 4 CPU/ 6G 内存的 Linux 机器上应不超过 10 秒（内存使用不限制），否则该用例不得分；
2 ）每个选手的总分（精确到小数点后 6 位） =10 秒钟内能产生正确结果的测试用例数量 x10+ （ 1/ 产生这些正确结果的测试用例的平均运行毫秒 ) ；
3 ）如果按此评分统计仍不能得出总决赛将决出的一、二、三等奖共计九名获奖者，我们将先设 N=2 ，然后重复下述过程直至产生最高的 9 位得分：用随机生成的另外 10 个有解的 start.txt 再做测试，并对这 10*N 个测试用例用 2 ）中公式重新计算总分， N++ 。
2006年百度之星程序设计大赛试题初赛题目
2006 年百度之星程序设计大赛初赛题目 1
饭团的烦恼
“午餐饭团“是百度内部参与人数最多的民间组织。
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
饭团点菜的需求如下：
1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
输入数据描述如下：
第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
紧接着 N 行，每行的格式如下：
菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
例：
水煮鱼 30 1 1
紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
输出数据：
对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
说明：
1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
输入样例
3 2 2
水煮鱼 30 1 1
口水鸡 18 1 1
清炖豆腐 12 0 0
1 1 1 1
输出样例
口水鸡
清炖豆腐
12.00
时间要求： 1S 之内