河南省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
【感謝 飯盒 提供】
本文版权遵循 CC BY-NC-SA 4.0发布，转载需附带本文链接。