请选择 进入手机版 | 继续访问电脑版

Lazarus中文社区

 找回密码
 立即注册

QQ登录

只需一步,快速开始

版权申明
查看: 4832|回复: 1

第二十三届全国信息学奥林匹克竞赛(2006)第二试

[复制链接]

该用户从未签到

发表于 2010-8-19 10:21:30 | 显示全部楼层 |阅读模式
题目名称               最大获利               聪明的导游                神奇口袋
目录                         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

【评分方法】
本题没有部分分,你的程序的输出只有和我们的答案完全一致才能获得满分,否则不得分。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

该用户从未签到

发表于 2010-8-21 17:22:29 | 显示全部楼层
不错哦!
回复 支持 反对

使用道具 举报

QQ|手机版|小黑屋|Lazarus中国|Lazarus中文社区 ( 鄂ICP备16006501号-1

GMT+8, 2021-4-18 07:12 , Processed in 0.060525 second(s), 25 queries .

Powered by Discuz! F1.0 Build 20160930

© 2001-2021 Comsenz Inc. & Discuz! Fans

快速回复 返回顶部 返回列表