2023-2024年USACO首次月考題目出爐！銅組第三題真題及解析

2023-2024賽季UASCO首場月賽已經圓滿結束，晉級賽的最新試題也已經公布。沒能當場晉級的同學們可以耐心等待一周，一周內USACO官方將會公布本次晉級賽成績。如果沒有晉級，12月可以當做一個練手+熟悉賽制的環節，1、2月的月賽持續發力，USACO可以重復挑戰。

今天給大家分享銅級試題和解析，參賽的同學來看看解題思路，沒參賽的同學來看看難度如何？

銅組第三題

INPUT FORMAT（標準輸入）：

第一個將由一個整數T組成，表示獨立測試用例的數量（1≤T≤10）。

每個測試用例的第一行由一個整數N組成。

第二行由N組成

整數hi（1≤hi≤109）

表示i的初始高度

第th株（英寸）。

第三行由N組成

整數ai（1≤ai≤109）

表示英寸數i每株植物每天都在生長。

第四行由N組成不同整數ti表示FJ給你的數組。保證N的總和

在所有測試用例中，不超過2·10^5。

輸出格式（管道標準輸出）：

輸出T行，每個測試用例的答案在不同的行上。如果不可能，輸出?1。

請注意，此問題中涉及的大尺寸整數可能需要使用64位整數數據類型（例如，C/C++中的“long-long”）。

樣本輸入：

6
1
10
1
0
2
7 3
8 10
1 0
2
3 6
10 8
0 1
2
7 3
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 0

樣本輸出：

0
3
2
5
-1
-1

在第一個樣本輸入中，有6個測試用例。

在第一個測試案例中，只有一個工廠，因此在第0天滿足條件。

在第二個測試案例中，我們需要第一個植物比第二個植物短。第1天之后，高度分別為15和13。第二天之后，高度都是23。第3天之后，高度分別為31和33，這是滿足條件的第一天。

第三個和第四個測試用例與第二個類似。

在第五個測試案例中，兩種植物的初始高度均為7，生長速率均為8。因此，它們總是有相同的高度，因此這種條件永遠不會得到滿足。

在第六個測試案例中，最初不滿足條件，并且增長率相同。所以這個條件永遠不能滿足。

樣本輸入：

2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 0

樣本輸出：

4
7

在第二個樣本輸入中，有2個測試用例。

在第一個測試案例中，第4天之后的最終高度為19、20、21、18、16。

在第二個測試案例中，第7天之后的最終高度為25、17、19、35、36。

評分：

輸入3：N≤2

輸入4-5：N≤50

且ai，hi≤103

輸入6-8：N≤103

輸入9-13：沒有其他限制。

試題解析

考慮根據最終的排序結果來確定有多少條件，容易發現其實只有$n-1$個有效的不等式，即第1個小于第2個，第2個小于第3個，...

根據不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t對應的范圍

最終對于所有不等式結果求出交集，如果不為空就輸出最小值，否則輸出-1

時間復雜度：O(n)

知識點：簡單數學

核心代碼如下：

USACO歷年真題及參考書，掃碼領??！【翰林提供報名指導服務】USACO歷年真題及參考書

2023-2024年USACO活動時間

第一次月賽：2023年12月15日-18日

第二次月賽：2024年1月26日-29日

第三次月賽：2024年2月16日-19日

美國公開賽：2024年3月15日-18日

（中國學生只能參加到公開賽）

集訓營：2024年5月23日-6月1日

EGOI：2024年7月21日-27日（荷蘭）

IOI：2024年9月1日-8日（埃及）

報名方式：參賽者可隨時在官網注冊賬號，注冊。報名，只需在活動時間登陸完成答題即可。

官網地址：usaco.org

提交之后，官網會發送一份郵件到您郵箱，郵件中有賬號密碼

利用已知的賬號于密碼，登錄USACO賬號，即可開始考試