百度之星2010程序设计大赛 复赛试题（下）

百度爱好者（Baiduer.com.cn）消息 2010年6月19日，2010百度之星大赛复赛展开。百度爱好者给大家带了复赛题目，供有兴趣的朋友研究。复赛共十题，下期五期。分别是购物搜索调研、内存碎片、蜗牛、午餐聚会、玉树驰援。

1.购物搜索调研 (时限：1000ms)

问题描述

“有啊”是百度旗下的电子商务购物平台，每天都有上百万的用户在平台上搜索自己想要购买的商品。为了给用户更 好的搜索体验，工程师们准备做一次搜索策略的调研工作。

假设对于某一个特定的查询词来说，一共有N个相关商品，并且通过人工标注得到每个商品与查询词的相关度rel_i。 当用户输入这个查询词时，可以采取一种非常简单的响应策略，就是在N个相关商品中随机的找一段连续的商品子序列返回给用户。 工程师认为，在每次返回结果中相关度的最小值代表了本次搜索结果的分数score。

用户在搜索时，心中往往会对结果有个期望分数expect，当搜索结果的分数score高于用户的预期 expect时，该用户的满意度为score – expect；否则用户的满意度为0。

假设在上述响应策略中，返回的子序列是完全随机的（即每段连续子序列被选中的概率完全相同），你的任务是计算 每个用户满意度的数学期望。

输入格式

输入第一行包含一个正整数T，表示测试数据的组数。每组测试数据的第一行为相关商品的数量N， 第二行为N个整数，分别表示每个商品与查询词的相关度rel_i（用空格分隔）。 第三行为一个正整数M，表示参与调研的用户数量，接下来的M行中的每一行都是一个整数expect，表示该用户在搜索时预期的分数值。 其中1 <= T <= 10，1 <= N, M <= 100,000, -10⁹ <= rel_i, expect <= 10⁹。

输出格式

对于每组测试数据，首先输出一行 “Case #:”，其中#表示测试数据编号（从1开始），注意空格与大小写。 接下来的M行，按照输入顺序依次给出每个用户在这种响应策略下满意度的期望值，每个用户占一行。 为了避免精度问题，期望值用最简分数 “A/B” 表示，其中A与B互质，B是正整数。当结果是整数时，应只输出A。

样例输入

 3

3

1 3 5

1

2

4

5 -2 1 4

2

1

-1

3

2 4 10

1

0

样例输出

 Case 1:

5/6

Case 2:

7/10

3/2

Case 3:

4

样例说明

在Case 1中，可能返回的子序列一共有6个[1], [3], [5], [1 3], [3 5], [1 3 5]，对应的分数（相关度最小值）为1, 3, 5, 1, 3, 1，用户满意度依次为0, 1, 3, 0, 1, 0。 每个子序列被返回的概率相同，即为1/6。根据数学期望的定义 可以得出该用户的满意度期望值是5/6。

 

2.内存碎片  ( 时限：1000ms )

问题描述

在服务器上运行的模块，往往要连续运行几个月不重启。这期间，各种程序会不停地申请、释放内存，因而导致大量 的内存碎片。 例如，有一块大小为4K的内存，还有一块5K的内存，但是由于二者地址不连续，无法从中申请一块6K的连续内存。

解决这个问题的方法之一是使用内存池，即把已释放的内存块链起来，而不直接还回操作系统，下一次申请这个大小 的内存块的时候，直接从链表里获得内存即可。 然而，这样做有个风险：用户可能在一段时间内只需要长度为L的内存，过一段时间后全部释放；接下来申请长度为L’的内存，造成长度为L的内存大量浪费。为 了避免上述风险， 一般的做法是：当程序申请长度为L的内存时，也可以给它分配一快长度为L’（L’>L）的更大的内存块，并且限 制内存池中内存长度的种类。

给出n个内存块申请，你的任务是计算出在最好情况下，至少需要多少内存才能满足所有的需求。

注意：有的内存池允许将内存块串连起来，组成一个更大的内存块，但是串联需要使用指针，在管理小内存的时候比 较浪费，所以本题规定内存块不许串连。

输入格式

第一行为两个正整数N和K，其中N表示内存请求的数目，K表示内存池中允许有K种不同的长度的内存块。以下N 行每行包含两个正整数L_i和C_i， 表示申请长度为L_i的内存块C_i次。N<=10000, K<=200, L_i < 1000000, C_i<=10000。

输出格式

输出仅一个整数，即在最好情况下，至少需要多少内存才能满足所有的需求。

样例输入

 3 2

10 1

11 1

20 1

样例输出

 42

样例解释

长度为11的块两个，长度为20的一个。

评分标准

本题有20组数据，每组数据结果正确的情况下，计算时间不得超过1秒。其中，75%的输入数据满足K<=16。

 

3.蜗牛 (时限：1000ms )

问题描述

一只蜗牛某天早晨掉进了深为L尺的井中。蜗牛每天白天可以向上爬若干尺，晚上休息时会向下滑若干尺。蜗牛一旦 到达井口或井底，便不再下滑。

假设蜗牛每天向上爬的尺数均为不超过10的正整数，而下滑的尺数为不超过5的正整数。蜗牛在第N天白天里(含 第N天白天结束时)爬出了井，你的任务是统计有多少种可能的爬升/下滑情况。 对于两种爬升/下滑情况，当存在对应的白天上爬或者晚上下滑的尺数不同时，即视为不同的情况。

输入格式

第一行：井深L。其中L为正整数，且L<=100；

第二行：爬出的天数N。其中N为正整数，且N<=300；

输出格式

输出一个正整数，为可能的爬升/下滑情况总数。如不可能在N天白天里(含第N天白天结束时)爬出深为L的井，则应输出0。

样例1

输入：

27

3

输出：

6

解释：

输入指明井深为27。蜗牛掉下去后，在第3天白天爬出了井。一共有6种可能的上升/下滑情况组合：

(  9, -1) (10, -1) 10 8+9+10=27

(10, -1) (  9, -1) 10 9+8+10=27

(10, -1) (10, -1)   9 9+9+  9=27

(10, -1) (10, -1) 10 9+9+10>27 (第3天白天未结束时，爬出了井)

(10, -1) (10, -2) 10 9+8+10=27

(10, -2) (10, -1) 10 8+9+10=27

样例2

输入：

5

4

输出：

5033

样例3

输入：

42

12

输出：

3106744105061936231

评分标准

本题有20组数据，每组数据结果正确的情况下，计算时间不得超过1秒。其中，75%的输入数据满足N<=12。

4.午餐聚会 (时限：5000ms )

问题描述

随着百度公司业务规模的不断扩大，员工人数数量激增。为适应互联网的快速变化，保持公司的灵活性，原来的一个 部门被划分为好几个小组便于组织和管理。 划分成几个小组后，基本保证了组内员工的协作性和灵活性，然而不同组之间的员工由于业务上无太多联系，致使组与组之间的员工相对生疏。 为加强公司团队的整体性，促进不同组之间经验的分享，增进不同组之间员工的交流，公司决定在同一部门不同组之间开展“午餐聚会”活动。

操作方法很简单：每次从每个组中各随机选出一名员工一起吃午饭。假设这个部门有N个组，那么每次参加午餐聚会 的人数就为N。 注意，如果这N个人的组合已经出现过一次，则需要重新随机选取。如果某次聚会后，部门中任意两个不同组的员工都曾一同参加过午餐聚会， 表明认识、交流的目的已经达到，因此 不再继续举行午餐聚会。

由于每次参加聚会的人选是随机确定的，总的聚会次数可能很小，也可能很大。为了做预算，你需要计算出聚会次数 的最小值和最大值，并给出最小值对应的方案。

输入格式

第一行为一个正整数，即该部门的组数N（N<=6），接下来的N行，每行包含一个正整数i，代表该组的 员工数（i<=10）。

输出格式

输出第一行包含两个数min和max，其中min为最小聚会次数，max为最大聚会次数。以下min行描述了 聚会次数最小的方案，其中每行描述一次聚会，包含n个参加聚会的员工代号， 从左到右依次代表第一组、第二组、第三组…的组员编号（每组的各组员编号为0到n-1）。

样例输入

4

2

2

2

2

样例输出

5 13

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

1 1 1 1

评分方法

本题包含若干组的数据。这些数据满足上述规模限制，并且参考程序可以在2秒之内得到正确结果。注意：参考程序并不能保证对满足规模限制的任意数据在2秒之内出解，但那些“高难度数据”不会用来评测选手程序。

5.玉树驰援 (时限：120000ms )

问题描述

4小时以前：青海玉树发生强烈地震，大量房屋倒塌，人员伤亡惨重。灾区急需救援。

2小时以前：政府迅速成立救灾指挥中心。全国各地情系玉树，纷纷筹集救援物资。

1小时以前：指挥中心将若干与玉树有直接或间接道路交通的地区作为集散点。救援物资分批就近到达集散点后，再由汽车运进灾区。一 批物资有一个唯一的编号，并由若干个集装箱组成。集散点已有不同数量的汽车在等候，指挥中心可以根据需要进行运输调度。汽车装卸物资的时间可忽略不计。一 辆汽车一次最多只能运1个集装箱。

30分钟以前：部分道路由于损坏和堵塞，汽车通行需要较长的时间；部分道路情况更加严重，已经不具备通车条件。指挥中心决定修复 和疏通道路，使道路恢复通车，或缩短通行时间。施工需要一定的时间，而且要封闭道路，即在此过程中不能有汽车在该道路上行驶。足够数量的施工队已经待命， 可以随时对多条道路进行施工。

现在（2010/4/14 11:49）：你被紧急征召到指挥中心。你的任务是调度物资运输和道路施工，在最短的时间内将所有物 资运送到玉树灾区。

输入格式

输入由三部分信息组成，依次为交通信息、汽车初始分布信息和物资就绪信息。相邻部分之间用一个空行(\n)隔开。

第一部分：玉树周边的交通信息。每行描述一条道路，格式如下：

地点A 地点B该道路施工所需小时数(t0) 施工前行驶所需小时数(t1) 施工后行驶所需小时数(t2)

值间以一个空格隔开。道路总数不超过256条，任意两地间最多只有一条双向道路直达。地点名为英文字母和数字组 成的字符串，长度不超过7字节。玉树的地点名为”Yushu”。 t0, t1, t2为整数。如果t1 = -1，表示该条道路在施工完成前无法通车；其它情况下，t0，t1, t2均大于0且不大于24。

一个空行之后，是第二部分：汽车初始分布信息。每行描述某个集散点初始时有多少汽车在等候，格式如下：

地点 数量

值间以一个空格隔开。集散点总数不超过64，单个集散点汽车的初始数量不超过1024。

一个空行之后，是第三部分：物资就绪信息。每行描述一批物资在何时何地就绪，格式如下：

yyyy/mm/dd HH:MM arrive 地点 物资编号 集装箱数量

值间用一个空格隔开。其中，yyyy/mm/dd HH:MM的时间格式含义为：年/月/日 时:分。物资编号为英文字母和数字组成的字符串，长度不超过7字节。一批物资的集装箱数量不超过2048。

最后一部分以文件结束符结尾。

输入保证所有物资可以在有限时间内运到玉树。

输出格式

你的程序应当按时间顺序在标准输出上打印你下达执行的指令。每条指令一行（不超过255字节，以’\n’结 尾），每行各值间用一个空格隔开。指令格式具体如下：

道路施工指令

yyyy/mm/dd HH:MM fix 地点A 地点B

该指令表示在指定时间开始对地点A和地点B的直达道路上进行施工。一条道路不得重复施工。

货物运输指令

yyyy/mm/dd HH:MM trans 地点A 地点B 物资编号:本指令运输的集装箱数量

该指令表示在指定时间开始将某种指定数量的物资从地点A运输到地点B。地点A和地点B必须有直达道路。集装箱数量应为正整数。

空车移动指令

yyyy/mm/dd HH:MM move 地点A 地点B 本指令调动的汽车数量

该指令表示在指定时间开始将指定数量汽车从地点A调度到地点B。地点A和地点B必须有直达道路。汽车数量应为正整数。

注意：所有指令涉及到的时间不得早于2010/4/14 11:49（但可以相等），所有指令一旦下达就不能取消或中断。

样例输入

Yushu A1 7 14 7

Yushu A2 2 -1 5

A2 A3 4 9 6

Yushu 3

A1 40

A2 5

A3 15

2010/4/14 11:59 arrive A2 G1 10

样例输出

2010/4/14 11:49 fix Yushu A2

2010/4/14 11:49 move A3 A2 5

2010/4/14 13:59 trans A2 Yushu G1:5

2010/4/14 20:49 trans A2 Yushu G1:5

评分方法

选取用时最短的选手，按此时间取所有选手的即时快照。按物资到达数量降序排序，第1名满分，其后按物资到达数量 比给分。

注：如果没有一个选手完成运输，那么取所有选手的已完成量最大者，按其最后一批物资的到达时间取所有选手的即时快照。 如果所有选手均没有将任何物资运送到玉树，则该测试点所有选手均得0分。

如果输出的指令及其运行不符合题目规定，相应测试点得0分。

百度之星2010程序设计大赛 复赛试题（上）>>