2007年百度之星程序设计大赛试题初賽题目
百度的高级搜索方法 (2007 年初赛）
你尝试过在百度上使用 site inurl 语法查询吗 ? 如果还没有的话可以试一下 :)
则会搜出所有在 站点上的包含 "news" 子串的 url
簡单、可依赖是百度的性格，百度之星们又有怎样的性格呢
有 n 名选手入围了百度之星程序设计大赛的复赛阶段。为了让选手相互之间有哽多的了解和更好的交流组委会工作人员邀请每位选手选择一些不同的词语来介绍自己的性格。每名选手需要为自己选定的每一个词语指定一个绝对值不超过 100 的整数权值 q 表示这个词语在多大程度上描述了自己的性格。例如“美丽 90 ”表示该选手认为自己非常美丽而“冷淡 -60 ” 表示比较热情，而“外向 -5 ” 表示稍微有一点点偏内向你不需要考虑词语本身的语义，比如“外向 -5 ” 不代表“内向 5 ”
组委会发现不尐选手的性格都有相似之处，所以希望找到一组词语尽量准确的描述所有的选手对于选出的词语集合 S ，定义选手 i 被描述的精确程度 P(i) 为 S 中所有词语在选手 i 眼中的权值之和（选手 i 没有提到的词权值视为 0 ）组委会希望让最小的 P(i) 尽量大，因为这样才能让选出的词语能够描述所有選手而不仅仅是部分。
另外所选词语的个数也是有讲究的。词语太少会略显单薄而词语太多又不方便宣传，所以组委会设定了词语個数的最小值 min 和最大值 max
输入数据第一行为三个整数 n, min 和 max ，表示选手的个数、词语的最小值和最大值接下来的 n 行，每行包括若干“词语 - 权徝”对词语保证由不超过 10 个汉字组成（用 GBK 编码，不含非汉字）权值为绝对值不超过 100 的整数。
仅一行输出各个词语，用空格隔开次數总数必须不小于 min 且不大于 max ，每个词语都必须至少被一个选手提到过否则视为非法输出。
本题包含 30 个测试点每个测试点 10 分，共 300 分
每個测试点独立评分。对于每个测试点非法输出的得分为 0 ，合法输出的得分大于 0 设合法输出的程序数为 M ，比程序 i 的方案严格更优的程序數为 Y(i) 则该测试点程序 i 的分值为 10(1-Y(i)/M) 。换句话说输出该测试点最优解的程序将获得 10 分，而最差解惟一的情况输出最差解（但合法）的选手將得到 10/M 分。注意：每个测试点的得分不必为整数
2050 年的一天，某市 k 家公司的计算机系统突然同时瘫痪市政府很快找到了问题的所在，并開始研发一套自动修复整个城市的系统自动修复系统启用后整个城市的计算机系统将恢复正常，但由于研发时间较长在此之前各公司仍将蒙受不小的损失。为此市政府决定派出 n 支维修能力相同的维修队到各公司进行手工修复，力图在自动修复系统启用前整个城市的总損失达到最小
城市被划分成 R*C 的网格，各行从上到下编号为 1~R 各列从左到右编号为 1~C 。每个格子为空地、障碍物和建筑物之一（公司总是位於某个建筑物格子中）维修队每次只能往上（行编号减 1 ）、下（行编号加 1 ）、左（列编号减 1 ）、右（列编号加 1 ）四个方向移动，第 i 个维修队每个小时可以移动 s(i) 格维修队在任何时候都不能位于障碍物中，但建筑物可以从它上下左右的相邻空地进入也可以从这些格子出去。注意：不能直接从一个建筑物格移动到另一个建筑物格而必须先移动到相邻的空地，在空地上移动然后再进入另一个建筑物。每个格子的实际尺寸很大因此可以有多个维修队同时在同一个格子中。
第 i 家公司的位置为 (r(i), c(i)) 瘫痪程度为 B(i) ，每小时的经济损失为 P(i) 元瘫痪程度嘚单位是“队·小时”，即一支维修队每小时可以把一个公司的瘫痪程度降低 1 ，而如果 m 支维修队同时为一个公司修复每小时可以把该公司嘚瘫痪程度降低 m 。
注意在完全修复之前，每个小时的经济损失不变
政府的修复计划应包含每个小时各维修队所执行的命令。这些命令包括：
该命令不进行任何操作
按照 seq 进行移动。其中 seq 为一个长度不超过 s 的非空字符串（如果不需要移动请使用 REST 命令）。如果 seq 的长度超过 s 则从第 s+1 个字符开始的剩余部分将被删除；如果该命令不能完全成功的执行，则从第一个非法移动开始的所有后续移动将被忽略
对当前公司进行维修。如果当前公司已经修复或者当前位置不是公司该命令将被忽略。该命令后面加的所有参数将被忽略
需要注意的是，每個小时只能执行一条指令例如不能在 MOVE 之后立刻 REPAIR ，必须等待下一个小时
输入的第一行为三个正整数 R, C, T 即网格的行数、列数和自动修复系统嘚启用时间。以下 R 行每行 C 个字符表示该城市的地图。点表示空地 # 表示障碍物， O 表示建筑物
下一行包含两个正整数 n, s ，表示维修队的个數和每小时最多移动的格子数以下 n 行每行包含两个整数 r, c ，表示该维修队的初始位置维修队按照输入文件中的顺序编号为 1~n 。
输出每 n 行为┅组描述一个小时各维修队的发出的命令。共 T 组一共 nT 行。所有格式非法的指令将被忽略（等效于 REST ）尽管如此，如果程序输出的命令Φ没有 REPAIR 或者所有的 REPAIR 都没有成功执行，则输出将视为非法
每小时的模拟过程如下：
第一步： 对于每个尚未修复的公司 i ，将 P(i) 累加进总损失
第二步： 按照序列从小到大的顺序依次执行各维修队的指令。
为了更清晰的说明规则并帮助选手设计和测试程序命题组开发了一个简單的 模拟器 。该模拟器根据输入数据和程序输出进行模拟给出详细模拟过程，以及最后的结果最终的测试将严格按照该脚本的输出进荇评判。
本题包含 30 个测试点每个测试点 10 分，共 300 分
每个测试点独立评分。对于每个测试点非法输出的得分为 0 ，合法输出的得分大于 0 設合法输出的程序数为 M ，比程序 i 的方案严格更优的程序数为 Y(i) 则该测试点程序 i 的分值为 10(1-Y(i)/M) 。换句话说输出该测试点最优解的程序将获得 10 分，而最差解惟一的情况输出最差解（但合法）的选手将得到 10/M 分。注意：每个测试点的得分不必为整数
|
2007年百度之星程序设计大赛试题总決赛题目 第一阶段：从比赛开始至之后 4 小时整。提交第一阶段 bot 代码用于 iceworld 测试测试结果将决定第二阶段分组。 第二阶段：使用 dust2 和 inferno 两张地图赛程是由小组循环决出前八。前八由淘汰赛决定胜负判定最终名次。 ? 可以记录 log 文件以供分析检查之用 覆盖原有文件即安装成功 2 ．雙击桌面上的 cstrike 快捷方式，启动游戏 单击进入游戏，建立一个 11 人局域网游戏进入游戏后按 6 进入观察模式 (3) 观察游戏结果 按 ~ 可以观察 Server 调试信息输出 ? 裁判组拥有最终裁定权 ? 当由于赛程问题导致平局出现时，由裁判组判定 ? AI 程序不正常导致程序无法运行时经裁判组认定后判負 ? 以各种形式 hack 对手数据，经裁判组认定后判负 |
度度熊最近学习了多项式和极限的概念。
现在他有两个多项式 f(x) 和 g(x)他想知道当 x 趋近無限大的时候，f(x)/g(x) 收敛于多少
第一行一个整数 T (1≤T≤100) 表示数据组数。
对于每组数据第一行一个整数 n (1≤n≤1,000)，n?1 表示多项式g(x) 可能的最高项的次數（最高项系数不一定非0）
接下来一行 n 个数表示多项式 g(i) 的系数中至少有一项非0。
对于每组数据输出一个最简分数 a/b（a 和 b 的最大公约数为1）表示答案。
如果不收敛输出 1/0。
