2023年2月 USACO青銅組題目中文版
USACO以后可能不會(huì)提供題目的中文版了，但國(guó)內(nèi)小學(xué)生階段，要能通順地理解英文題意，可能會(huì)有一定難度。因此我每次在比賽開(kāi)始前，會(huì)把題目翻譯成中文，發(fā)在群里，供孩子們參考。我的翻譯自我感覺(jué)還不錯(cuò)，比洛谷里的那些UASCO題目翻譯得好多了 :p 。
Problem 1. 饑餓的奶牛?Hungry Cow
Bessie 是一頭饑餓的奶牛。每天晚餐時(shí)，只要谷倉(cāng)里有干草，她就會(huì)吃一捆。農(nóng)夫John不想讓Bessie挨餓，因此他會(huì)在某些天送去幾捆干草，送達(dá)時(shí)間是在早上（晚餐之前）。具體來(lái)說(shuō)，農(nóng)夫John會(huì)在第di天，送bi捆干草過(guò)去。（1≤di≤10^14， ?1≤bi≤10^9）
要求計(jì)算在前T天中，Bessie總共會(huì)吃掉多少捆干草。
輸入格式 (標(biāo)準(zhǔn)輸入):
第一行包括N和T（其中1 ≤ N ≤ 10^5， 1 ≤ T ≤ 10^14）(譯者注：下標(biāo)和上標(biāo)在純文本格式下不好表示，請(qǐng)自己轉(zhuǎn)換，pdf版就好一點(diǎn))
接下來(lái)N行，每一行包括di和bi，確保1 ≤ d1 < d2 < ? < dN ≤ T
輸出格式 (標(biāo)準(zhǔn)輸出):
輸出Bessie在前T天會(huì)吃掉的干草捆數(shù)。
注意：本題中的數(shù)字可能很大，需要使用64位整數(shù)類(lèi)型。（例如，在c/c++中，需要用long long）
樣例1輸入:
1 5
1 2
樣例1輸出:
2
說(shuō)明：在第1天早上，會(huì)有2捆干草送達(dá)。Bessie會(huì)在第1天吃掉一捆干草，在第2天吃掉另一捆干草。而在第3-5天，Bessie沒(méi)有任何干草可以吃。那么，Bessie在前5天中，總共吃了2捆干草。
?
?
樣例2輸入:
2 5
1 2
5 10
樣例2輸出:
3
說(shuō)明：在第1天早上，會(huì)有2捆干草送達(dá)。Bessie會(huì)在第1天和第2天各吃掉一捆干草。第3天和第4天Bessie沒(méi)有干草吃。在第5天早上，10捆干草送到。Bessie在第5天的晚餐上吃掉一捆。這樣Bessie在前5天中，總計(jì)吃掉3捆干草。
樣例3輸入：
2 5
1 10
5 10
樣例3輸出SAMPLE OUTPUT:
5
說(shuō)明：10捆干草在第一天早上送達(dá)。Bessie在第一天到第四天各吃了一捆干草。在第五天早上，又有10捆干草送達(dá)，這意味著谷倉(cāng)里有16捆干草。第五天的晚餐，Bessie又吃了一捆干草。Bessie在前5天里總共吃了5捆干草。
?
計(jì)分:
輸入數(shù)據(jù)?4-7:?T≤10^5；
輸入數(shù)據(jù)?8-13: 沒(méi)有額外限制。
Problem credits: Brandon Wang
?
?
Problem 2. 印章網(wǎng)格
印章畫(huà)（stamp painting）是在N×N格子的畫(huà)布上的黑白畫(huà)，其中某些單元格涂上了墨水，而其他單元格是空白的。它可以用N×N的字符數(shù)組來(lái)描述(1≤N≤20)。如果畫(huà)布的某方格內(nèi)有墨水，那么數(shù)組中對(duì)應(yīng)的第i行第j列元素為 * ，否則為 . 。
Bessie想創(chuàng)作一幅印章畫(huà), 因此農(nóng)夫John借給了她一個(gè)K×K（1 ≤ K ≤ N）大小的印章和一張N×N空白畫(huà)布。Bessie可以將印章順時(shí)針旋轉(zhuǎn)90度，而且只要印章完全落在畫(huà)布的網(wǎng)格內(nèi)，她就可以在畫(huà)布上的任何地方蓋章。正式地講就是，在蓋章時(shí)，Bessie會(huì)選擇兩整數(shù)i、j，滿(mǎn)足i∈[1, N?K+1]和j∈[1, N?K+1]。那么，對(duì)于印章上的某一點(diǎn)（i′, j′）（滿(mǎn)足1≤i′,j′≤K），如果印章的該（i′, j′）點(diǎn)上有墨水，那么畫(huà)布上的單元格?( i + i′- 1, j + j′- 1)就會(huì)被涂成黑色。一旦畫(huà)布的某單元格被涂成黑色，它就會(huì)一直保持黑色。
農(nóng)夫John想知道，Bessie用他的印章，能否創(chuàng)作出她想要的印章畫(huà)。對(duì)于T (1 ≤ T ≤ 100)組數(shù)據(jù)中的每一組，幫助農(nóng)夫John求出問(wèn)題的答案。
輸入格式 (標(biāo)準(zhǔn)輸入):
輸入的第一行包含T，即測(cè)試數(shù)據(jù)的數(shù)量。
每個(gè)測(cè)試數(shù)據(jù)以一個(gè)整數(shù)N開(kāi)始。后面跟著N行，每一行包含一個(gè)由 * 和 . 組成的字符串，表示Bessie想要繪制的印章畫(huà)。接下來(lái)一行是K。之后跟著K行，每一行包含一個(gè) * 和 . 組成的字符串，代表農(nóng)夫John的印章。
每一個(gè)連續(xù)的測(cè)試用例之間用換行符分隔。
輸出格式 (標(biāo)準(zhǔn)輸出):
對(duì)于每一個(gè)測(cè)試數(shù)據(jù)，在單獨(dú)的行上輸出“YES”或“NO”。
?
?
樣例輸入：SAMPLE INPUT:
4
2
**
*.
1
*
3
.**
.**
***
2
.*
**
3
...
.*.
...
3
.*.
...
...
3
**.
.**
..*
2
.*
*.
樣例輸出SAMPLE OUTPUT:
YES
YES
NO
YES
?
說(shuō)明：在第一個(gè)測(cè)試用例中，Bessie可以執(zhí)行以下蓋章順序:
在(1, 1)處蓋章
在(1, 2)處蓋章
在(2, 1)處蓋章
在第二個(gè)測(cè)試用例中，Bessie可以執(zhí)行以下蓋章順序:
在?(2, 2) 處蓋章
在?(2, 1) 處蓋章
旋轉(zhuǎn)?90度
旋轉(zhuǎn)90度
在(1, 2) 處蓋章
在第三個(gè)測(cè)試用例中，無(wú)法繪制中間的單元格。
在第四個(gè)測(cè)試案例中，Bessie可以執(zhí)行以下的蓋章順序:
旋轉(zhuǎn)?90度
在(1, 1)處蓋章
在(1, 2)處蓋章
在(2, 2)處蓋章
Problem credits: Benjamin Qi and Claire Zhang
?
?
Problem 3. 觀看 Mooloo電視臺(tái)
Bessie喜歡在Mooloo電視臺(tái)觀看節(jié)目。因?yàn)锽essie很忙，因此她已經(jīng)為接下來(lái)的N(1 ≤ N ≤ 10^5)天制定了觀看Mooloo的時(shí)間表。因?yàn)镸ooloo是付費(fèi)訂閱服務(wù)，所以她現(xiàn)在需要決定如何將需要支付的金額降至最低。
Mooloo有一個(gè)有趣的訂閱系統(tǒng)：連續(xù)d天訂閱Mooloo需要花費(fèi)d + K ( 1 ≤ K ≤ 10^9)個(gè)moony幣。您可以在任何時(shí)候開(kāi)始訂閱，并且如果當(dāng)前訂閱到期了，您可以隨時(shí)開(kāi)始重新訂閱，次數(shù)不限。給定這些條件，計(jì)算出Bessie為實(shí)現(xiàn)她的觀看計(jì)劃所需要支付的最少moony幣數(shù)量。
輸入格式 (標(biāo)準(zhǔn)輸入):
第一行包含整數(shù)N和K.
第二行包含N個(gè)整數(shù)，描述了Bessie觀看Mooloo的日子：
1 ≤ d1 < d2 < ? < dN ≤ 10^14
輸出格式 (標(biāo)準(zhǔn)輸出):
注意，這個(gè)問(wèn)題中涉及的大量整數(shù)可能需要使用64位整數(shù)數(shù)據(jù)類(lèi)型(例如, C/C++中的"long long").
輸入1樣例SAMPLE INPUT:
2 47 9
輸出1樣例SAMPLE OUTPUT:
7
說(shuō)明：Bessie在第7天購(gòu)買(mǎi)了為期三天的訂閱，花費(fèi)?d + K = 3 + 4 = 7個(gè)moony幣.
輸入2樣例SAMPLE INPUT:
2 31 10
輸出2樣例SAMPLE OUTPUT:
8
Bessie首先在第1天買(mǎi)了一天的訂閱，花費(fèi)d + K = 1 + 3 = 4個(gè)?moony幣. Bessie還在第10天購(gòu)買(mǎi)了為期一天的訂閱，花費(fèi)d + K = 1 + 3 = 4個(gè)moony幣。Bessie總共花8個(gè)moony幣。
計(jì)分SCORING:
輸入樣例 ? ? ?3-5:?N≤10
輸入樣例 6-12: 沒(méi)有額外限制
Problem credits: Danny Mittal
?
