河南省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 釋出。