题目名称 最大获利 聪明的导游 神奇口袋
目录 profit guide bag
可执行文件名 profit N/A bag
输入文件名 profit.in guide1.in~guide10.in bag.in
输出文件名 profit.out guide1.out~guide10.out bag.out
每个测试点时限 2秒 N/A 1秒
测试点数目 10 10 10
每个测试点分值 10 10 10
是否有部分分 无 有 无
题目类型 传统 提交答案 传统
提交源程序须加后缀
对于Pascal 语言 profit.pas N/A bag.pas
对于C 语言 profit.c N/A bag.c
对于C++ 语言 profit.cpp N/A bag.cpp
注意：最终测试时，所有编译命令均不打开任何优化开关
除了提交答案题以外，其余两题只需要向输出文件输出一行，行内不得有多余空白字符，行末须有一个换行/回车符，格式不对不能得分。
题1
最大获利
【问题描述】
新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。
在前期市场调查和站址勘测之后，公司得到了一共N 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要的成本为P[sub]i[/sub]（1≤i≤N）。
另外公司调查得出了所有期望中的用户群，一共M 个。关于第i 个用户群的信息概括为A[sub]i[/sub], B[sub]i[/sub] 和C[sub]i[/sub]：这些用户会使用中转站A[sub]i[/sub] 和中转站B[sub]i[/sub] 进行通讯，公司可以获益C[sub]i[/sub]。（1≤i≤M, 1≤A[sub]i[/sub], B[sub]i[/sub]≤N）THU 集团的CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）
【输入格式】
输入文件中第一行有两个正整数N 和M 。
第二行中有N 个整数描述每一个通讯中转站的建立成本，依次为P[sub]1 [/sub], P[sub]2[/sub], …,P[sub]N[/sub]。
以下M 行，第(i + 2)行的三个数A[sub]i[/sub], B[sub]i[/sub] 和C[sub]i[/sub] 描述第i 个用户群的信息。
所有变量的含义可以参见题目描述。
【输出格式】
你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。
【输入样例】
5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3
【输出样例】
4
【样例说明】
选择建立1、2、3 号中转站，则需要投入成本6，获利为10，因此得到最大收益4。
【评分方法】
本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。
【数据规模和约定】
80%的数据中：N≤200，M≤1 000。
100%的数据中：N≤5 000，M≤50 000，0≤C[sub]i[/sub]≤100，0≤P[sub]i[/sub]≤100。
题2
聪明的导游
【问题描述】
小佳最近迷上了导游这个工作，一天到晚想着带游客参观各处的景点。正好
M 市在举行NOI，来参观的人特别的多。不少朋友给小佳介绍了需要导游的人。
M 市有n 个著名的景点，小佳将这些景点从1 至n 编号。有一些景点之间存
在双向的路。小佳可以让游客们在任何一个景点集合，然后带着他们参观，最后
也可以在任何一个景点结束参观。不过，来参观的游客们都不愿去已经参观过的
地方。所以，小佳不能带游客们经过同一个景点两次或两次以上。
小佳希望你帮助他设计一个方案, 走可行的路线, 带游客们参观尽可能多的
地方。
【输入格式】
输入文件为 guide1.in~guide10.in，第一行为两个整数n,m，分别表示景点数
和路的条数。接下来m 行，每行两个整数a,b，表示景点a 和景点b 之间有一条
双向路。
【输出格式】
你需要将答案输出到guide1.out~guide10.out 中，guide?.out 为对应guide?.in
的答案。输出的第一行为p，表示你能找到的路径所经过的景点个数。接下来p
行，每行一个整数，按顺序表示你所找到的路径上的每一个景点。
【说明】
这是一道提交答案式的题目，你不需要提供任何源代码，只需要将自己的输
出文件放在与*.in 同一个目录即可。
【样例】
样例输入 样例输出
5 5 4
1 2 1
3 2 2
2 4 4
2 5 5
4 5
【样例说明】
题目可能有多解，该样例有4 个解，你只需输出其中任何一个解。
解1 解2 解3 解4
4 4 4 4
1 1 3 3
2 2 2 2
4 5 4 5
5 4 5 4
【评分方法】
你的评分将由你的答案与标准答案之间的差异来给定。设你的答案正确且参观的景点数为x，我们所给出的结果为ans，则按下表计算你的得分：
得分 条件 得分 条件
12 x > ans 5 x ≥ ans * 0.93
10 x = ans 4 x ≥ ans * 0.9
9 x ≥ ans–1 3 x ≥ ans * 0.8
8 x ≥ ans–2 2 x ≥ ans * 0.7
7 x ≥ ans–3 1 x ≥ ans * 0.5
6 x ≥ ans*0.95 0 x < ans * 0.5
如果有多项满足，则取满足条件中的最高得分。
题3
神奇口袋
【问题描述】
Pòlya 获得了一个奇妙的口袋，上面写着人类难以理解的符号。Pòlya 看得入了迷，冥思苦想，发现了一个神奇的模型（被后人称为Pòlya 模型)。为了生动地讲授这个神奇的模型，他带着学生们做了一个虚拟游戏：
游戏开始时，袋中装入a[sub]1[/sub]个颜色为1 的球，a[sub]2[/sub]个颜色为2 的球，…，a[sub]t[/sub]个颜色为t 的球，其中a[sub]i[/sub]∈Z[sup]+[/sup](1≤i≤t)。
游戏开始后，每次严格进行如下的操作：
从袋中随机的抽出一个小球（袋中所有小球被抽中的概率相等），Pòlya 独自观察这个小球的颜色后将其放回，然后再把d 个与其颜色相同的小球放到口袋中。
设c[sub]i[/sub]表示第i次抽出的小球的颜色(1≤c[sub]i[/sub]≤t)，一个游戏过程将会产生一个颜色序列(c[sub]1[/sub],c[sub]2[/sub],…,c[sub]n[/sub],…)。
Pòlya 把游戏开始时t 种颜色的小球每一种的个数a[sub]1[/sub],a[sub]2[/sub],…,a[sub]t[/sub] 告诉了所有学生。然后他问学生：一次游戏过程产生的颜色序列满足下列条件的概率有多大？
（见附件）
其中0<x1<x2<…<xn ， 1≤yi≤t 。换句话说， 已知(t,n,d,a[sub]1[/sub],a[sub]2[/sub],…,a[sub]t[/sub],x[sub]12[/sub]y[sub]1[/sub],x[sub]2[/sub],y[sub]2[/sub],...,x[sub]n[/sub],y[sub]n[/sub])，你要回答有多大的可能性会发生下面的事件：“对所有k,1≤k≤n，第x[sub]k[/sub]次抽出的球的颜色为y[sub]k[/sub]”。
【输入格式】
第一行有三个正整数t，n，d；第二行有t 个正整数a[sub]1[/sub],a[sub]2t[/sub],…,a[sub]t[/sub]，表示游戏开始时口袋里t 种颜色的球，每种球的个数。
以下n 行，每行有两个正整数x[sub]i[/sub],y[sub]i[/sub]，表示第x[sub]i[/sub] 次抽出颜色为的y[sub]i[/sub] 球。
【输出格式】
要求用分数形式输出（显然此概率为有理数）。输出文件包含一行，格式为：
分子/分母。同时要求输出最简形式（分子分母互质）。特别的，概率为0 应输出0/1，概率为1 应输出1/1。
【样例1】
输入
2 3 1
1 1
1 1
2 2
3 1
输出
1/12
【样例1 说明】
初始时，两种颜色球数分别为(1, 1)，取出色号为1 的球的概率为1/2；第二次取球之前，两种颜色球数分别为(2, 1)，取出色号为2 的球的概率为1/3；第三次取球之前，两种颜色球数分别为(2, 2)，取出色号为1 的球的概率为1/2，所以三次取球的总概率为1/12。
【样例2】
输入
3 1 2
1 1 1
5 1
输出
1/3
【数据规模和约定】
1≤t,n≤1000, 1≤a[sub]k[/sub],d≤10, 1≤x1<x2<…<x[sub]n[/sub]≤10000, 1≤y[sub]k[/sub]≤t
【评分方法】
本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。 |
|手机版|小黑屋|Lazarus中国|Lazarus中文社区
( 鄂ICP备16006501号-1 )
发表于 2010-8-19 10:21:30
发表于 2010-8-21 17:22:29
