河南省2010年信息学奥林匹克竞赛试题(HAOI2010)
文章目录
2010****河南省信息学奥林匹克竞赛试题(高中组选拔赛一试)
考试时间:210分钟(3小时30分)
题目
源文件名(*.c/cpp/pas)
输入数据文件
输出数据文件
测试点时限
内存限制
测试点个数
计数
perm
perm.in
perm.out
1s
512MB
10
工厂选址
factory
factory.in
factory.out
1s
512MB
10
软件安装
install
install.in
install.out
1s
512MB
10
第1题:计数(文件名:perm.pas/c/cpp,时限1s)
你有一组非零数字(不一定唯一),你可以在其中插入任意个0,这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,10200,等等。
现在给定一个数,问在这个数之前有多少个数。(注意这个数不会有前导0)。
输入
只有1行,为1个整数n.
输出
只有整数,表示N之前出现的数的个数。
样例
perm.in
1020
perm.out
7
数据范围:n的长度不超过50,答案不超过263-1.
第2题:工厂选址(文件名:factory.c/cpp/pas,时限1s)
某地区有m左煤矿,其中第i号矿每年产量为ai吨,现有火力发电站一个,每年需用煤b吨,每年运行的固定费用(包括折旧费,不包括煤的运费)为h元,每吨原煤从第i号矿运到原有发电厂的运费为Ci0(i=1,2,…,m;j=1,2,…,n)。
现规划新建一个发电厂,m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂,每年运行的固定费用为hi元。每吨原煤从第i号矿运到j号备选厂址的运费为Cij(i=1,2,…,m;j=1,2,…,n)。
试问:应把新厂厂址选取在何处?m座煤矿开采的原煤应如何分配给两个发电厂,才能使每年的总费用(发电厂运行费用与原煤费用之和)为最小。
输入
第1行: m b h n
第2行: a1 a2 … am (0<=ai<=500,a1+a2+…+an>=b)
第3行: h1 h2 … hn (0<=hi<=100)
第4行: C10 C20 … Cm0 (0<=Cij<=50)
第5行: C11 C21 … Cm1
… …
第n+4行:C1n C2n … Cmn
输出
第1行:新厂址编号,如果有多个编号满足要求,输出最小的。
第2行:总费用
样例
factory.in
4 2 7 9
3 1 10 3
6 3 7 1 10 2 7 4 9
1 2 4 3
6 6 8 2
4 10 8 4
10 2 9 2
7 6 6 2
9 3 7 1
2 1 6 9
3 1 10 9
4 2 1 8
2 1 3 4
factory.out
8
49
数据范围
对于30%的数据,n<=50,m<=100,b<=100
对于60%的数据,n<=50,m<=100,b<=10000
对于所有数据,n<=50,m<=50000,b<=10000
大规模输入数据,对于C++,谨慎使用cin/cout.推荐采用scanf和printf.
第3题:软件安装(文件名:install.c/cpp/pas,时限1s)
现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M的计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。
但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件吗i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么他能够发挥的作用为0。
我们现在知道了软件之间的依赖关系:软件i依赖Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则Di=0,这是只要这个软件安装了,它就能正常工作。
输入
第1行:N,M (0<=N<=100,0<=M<=500)
第2行:W1,W2, … Wi, … ,Wn
第3行:V1,V2, … Vi, … ,Vn
第4行:D1,D2, … Di, … ,Dn
输出
一个整数,代表最大价值。
样例
install.in
3 10
5 5 6
2 3 4
0 1 1
instal.out
5
2010****河南省信息学奥林匹克竞赛试题(高中组选拔赛二试)
考试时间:150分钟(2小时半)
题目
源文件名(*.c/cpp/pas)
输入
数据文件
输出
数据文件
测试点时限
内存限制
测试点个数
最长公共子序列
lcs
lcs.in
lcs.out
1s
10
订货
order
order.in
order.out
1s
10
第1题:最长公共子序列(文件名:lcs.pas/c/cpp,时限1s)
字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=「x0,x1,…,xm-1」,序列Y=「y0,y1,…,yk-1」是X的子序列,存在X的一个严格递增下标序列<i0,i1,…,ik-1>,使得对所有的j=0,1,…,k-1,有xij = yj。例如,X=「ABCBDAB」,Y=「BCBD」是X的一个子序列。
对给定的两个字符序列,求出他们最长的公共子序列长度,以及最长公共子序列个数。
输入
第1行为第1个字符序列,都是大写字母组成,以「.」结束。长度小于5000。
第2行为第2个字符序列,都是大写字母组成,以「.」结束。长度小于5000。
输出
第1行输出上述两个最长公共子序列的长度。
第2行输出所有可能出现的最长公共子序列个数,答案可能很大,只要将答案对100,000,000求余即可。
样例
lcs.in
ABCBDAB.
BACBBD.
lcs.out
4
7
第2题:订货(文件名:order.c/cpp/pas,时限1s)
某公司估计市场在第i个月对某产品的需求量为Ui,已知在第i月该产品的订货单价为di,上个月月底未销完的单位产品要付存贮费用m,假定第一月月初的库存量为零,第n月月底的库存量也为零,问如何安排这n个月订购计划,才能使成本最低?每月月初订购,订购后产品立即到货,进库并供应市场,于当月被售掉则不必付存贮费。假设仓库容量为S。
输入
第1行:n,m,S (0<=n<=50,0<=m<=10,0<=S<=10000)
第2行:U1,U2,…,Ui,…,Un (0<=Ui<=10000)
第3行:d1,d2,…,di,…,dn (0<=di<=100)
输出
只有1行,一个整数,代表最低成本
样例
order.in
3 1 1000
2 4 8
1 2 4
order.out
34
【感謝 飯盒 提供】
题外话:我帮你整理了包括 AI 写作、绘画、视频(自媒体制作)零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效,辅助工作和生活?限时报名。
© 转载需附带本文链接,依据 CC BY-NC-SA 4.0 发布。