USACO競賽2020-2021新賽季第一場即將開始，為(wei) 方便同學了解題目思路，奇思孵化準備了四期《USACO題解》專(zhuan) 題，本期進入第四期解題思路提供 2019-2020賽季各級別晉級題目題解參考，希望能為(wei) 同學們(men) 提供有用的幫助。
1
Task1
題目：
由於(yu) 高傳(chuan) 染性的牛傳(chuan) 染病 COWVID-19 的爆發，Farmer John 非常擔憂他的奶牛們(men) 的健康。為(wei) 了限製疾病的傳(chuan) 播，Farmer John 的 N 頭奶牛（2≤N≤105）決(jue) 定踐行“社交距離”，分散到農(nong) 場的各處。農(nong) 場的形狀如一維數軸，上有 M 個(ge) 互不相交的區間（1≤M≤105），其中有可用來放牧的青草。奶牛們(men) 想要使她們(men) 位於(yu) 不同的整數位置，每個(ge) 位置上均有草，並且最大化 D 的值，其中 D 為(wei) 最近的兩(liang) 頭奶牛之間的距離。請幫助奶牛們(men) 求出 D 的最大可能值。
輸入格式（文件名：socdist.in）：
輸入的第一行包含 N 和 M。以下 M 行每行用兩(liang) 個(ge) 整數 a 和 b 描述一個(ge) 區間，其中 0≤a≤b≤1018。沒有兩(liang) 個(ge) 區間有重合部分或在端點處相交。位於(yu) 一個(ge) 區間的端點上的奶牛視為(wei) 在草上。
輸出格式（文件名：socdist.out）：
輸出 D 的最大可能值，使得所有奶牛之間的距離均不小於(yu) D 單位。保證存在 D>0 的解。
輸入樣例：
5 3
0 2
4 7
輸出樣例：
2
取到 D=2 的一種方式是令奶牛們(men) 處在位置 0、2、4、6 和 9。
測試點性質：
測試點 2-3 滿足 b≤105。
測試點 4-10 沒有額外限製。
解析：本題用二分去做，我們(men) 二分 D 的值，然後再 Θ(N+M) 貪心掃一遍，如果可以放得下就往大的找，否則往小的找。我們(men) 二分的範圍是從(cong) 0 到maxbi，因為(wei) 最壞的情況是每頭牛都緊緊挨著一起，最優(you) 的情況是一頭牛在數軸原點，另一頭牛在數軸的最大值處。雖然數軸是無限長的，但是在本題中，小於(yu) 00的部分對答案沒有貢獻，大於(yu) maxbi的部分也對答案沒有貢獻，所以我們(men) 假設數軸是從(cong) 0 到maxbi 的。二分的複雜度為(wei) Θ(log(maxbi ))，判斷是否滿足條件的複雜度為(wei) Θ(N+M)。
Task 2
題目：Farmer John 的奶牛們(men) 的早餐最愛當然是麥片了！事實上，奶牛們(men) 的胃口是如此之大，每頭奶牛一頓飯可以吃掉整整一箱麥片。最近農(nong) 場收到了一份快遞，內(nei) 有 M 種不同種類的麥片（1≤M≤105）。不幸的是，每種麥片隻有一箱！N 頭奶牛（1≤N≤105）中的每頭都有她最愛的麥片和第二喜愛的麥片。給定一些可選的麥片，奶牛會(hui) 執行如下的過程如果她最愛的麥片還在，取走並離開。否則，如果她第二喜愛的麥片還在，取走並離開。否則，她會(hui) 失望地哞叫一聲然後不帶走一片麥片地離開。奶牛們(men) 排隊領取麥片。對於(yu) 每一個(ge) 0≤i≤N−1，求如果 Farmer John 從(cong) 隊伍中移除前 i 頭奶牛，有多少奶牛會(hui) 取走一箱麥片。
輸入格式（文件名：cereal.in）：輸入的第一行包含兩(liang) 個(ge) 空格分隔的整數 N 和 M。對於(yu) 每一個(ge) 1≤i≤N，第 i 行包含兩(liang) 個(ge) 空格分隔的整數 fi 和 si（1≤fi，si≤M，且 fi≠si），為(wei) 隊伍中第 i 頭奶牛最喜愛和第二喜愛的麥片。 輸出格式（文件名：cereal.out）：對於(yu) 每一個(ge) 0≤i≤N−1，輸出一行，包含對於(yu) i 的答案。
輸入樣例：4 21 21 21 21 2
輸出樣例：2221如果至少兩(liang) 頭奶牛留下，那麽(me) 恰有兩(liang) 頭奶牛取走了一箱麥片。 測試點性質：測試點 2-3 滿足 N,M≤1000。測試點 4-10 沒有額外限製。
解析：Level 1：我們(men) 很容易想到，從(cong) 00 到 N-1N−1 枚舉(ju) ，然後模擬奶牛選擇麥片的過程。其中 hi 表示第 i 種麥片被選擇的情況，ci表示第 i 頭奶牛喜歡的麥片。我們(men) 從(cong) 0 到 N−1 都進行了枚舉(ju) ，而每次算答案的時候要遍曆每一頭牛，所以時間複雜度為(wei) Θ(N2)。這裏N≤105，所以我們(men) 的複雜度是不行的。因為(wei) 我們(men) 要算出 NN 個(ge) 答案，所以複雜度至少為(wei) Θ(N)，故我們(men) 隻能優(you) 化 solve函數。Level 2：我們(men) 想想，當減少一頭牛時，會(hui) 發生什麽(me) 情況？如果它選擇了麥片，那麽(me) 它的麥片可能被其他奶牛選擇；如果沒有選擇麥片，那麽(me) 答案不會(hui) 改變。但是，這樣還是要找一下有哪頭奶牛需要這個(ge) 麥片，所以優(you) 化不了多少。怎麽(me) 辦呢？如果我們(men) 增加奶牛，即倒著求每個(ge) 答案，最後倒著輸出就行了。如果增加一頭奶牛，又會(hui) 出現什麽(me) 情況呢？如果它最喜歡的麥片沒有被選擇，那麽(me) 它就會(hui) 選它，且不影響其他奶牛；如果它最喜歡的麥片被選擇，因為(wei) 它的優(you) 先級比其他牛都高，所以會(hui) 把其他牛的麥片“搶”過來，其他牛隻能“退而求其次”。這樣代碼就很好寫(xie) 啦，遞歸求解即可，因為(wei) 所有奶牛最多選兩(liang) 次，所以 solve函數的複雜度是Θ(1) 的，整個(ge) 代碼的時間複雜度為(wei) Θ(N)。實現方法見代碼注釋：ci表示第 i 頭奶牛的喜好，hi表示拿走第 i 種麥片的牛的編號，resi表示移走 i-1 頭牛的答案，cur 是計算答案的計數器。因為(wei) 領麥片的牛越多，領到麥片的牛就越多，所以越往後麵，cur就越大，故每次計算的時候 cur不需要清零。
Task 3題目：在 COWVID-19 爆發期間 Farmer John 的奶牛們(men) 為(wei) 了安全進行了隔離，她們(men) 想到了一種全新的方式緩解無聊：研究高等物理！事實上，她們(men) 甚至成功發現了一種新的亞(ya) 原子粒子，她們(men) 將其命名為(wei) “哞粒子”。
奶牛們(men) 正在進行一項有關(guan) N 個(ge) 哞粒子的實驗（1≤N≤105）。粒子 i 的“自旋”可以用範圍在 −109…109 之間的兩(liang) 個(ge) 整數 xi 和 yi 來描述。有時兩(liang) 個(ge) 哞粒子會(hui) 發生相互作用。自旋為(wei) (xi,yi) 和 (xj,yj) 的兩(liang) 個(ge) 粒子之間僅(jin) 當 xi≤xj 並且 yi≤yj 時會(hui) 發生相互作用。在這些條件下，有可能這兩(liang) 個(ge) 粒子中的一個(ge) 會(hui) 消失（另一個(ge) 粒子不會(hui) 發生任何變化）。在任意給定的時刻，至多隻有一次相互作用會(hui) 發生。
奶牛們(men) 想要知道在經過一些任意的相互作用之後剩餘(yu) 的哞粒子的最小數量。
輸入格式（文件名：moop.in）：輸入的第一行包含一個(ge) 整數 N，為(wei) 哞粒子的初始數量。以下 N 行每行包含兩(liang) 個(ge) 空格分隔的整數，為(wei) 一個(ge) 粒子的自旋。每個(ge) 粒子的自旋各不相同。
輸出格式（文件名：moop.out）：輸出一個(ge) 整數，為(wei) 經過一些任意的相互作用之後剩餘(yu) 的哞粒子的最小數量。
輸入樣例：41 00 1-1 00 -1
輸出樣例：1一個(ge) 可能的相互作用順序：粒子 1 和 4 相互作用，粒子 1 消失。粒子 2 和 4 相互作用，粒子 4 消失。粒子 2 和 3 相互作用，粒子 3 消失。僅(jin) 留下粒子 2。 輸入樣例：30 01 1-1 3
輸出樣例：2粒子 3 不能與(yu) 任何其他兩(liang) 個(ge) 粒子相互作用，所以它必然會(hui) 留下。粒子 1 和 2 中必然留下至少一個(ge) 。 測試點性質：測試點 3-6 滿足 N≤1000。測試點 7-12 沒有額外限製。
解析：題意簡述有 N 個(ge) 粒子，每個(ge) 粒子都有描述其自身的參數 x,y 。規定兩(liang) 個(ge) 粒子可以相互作用當且僅(jin) 當其中任意一個(ge) 粒子的 x,y都分別比另一個(ge) 粒子的 x,y 大。相互作用的規則是刪掉其中任意一個(ge) ，保留另一個(ge) 。其中1≤N≤105。題目分析我們(men) 可以這樣想，把所有可以相互作用的點之間連邊，將輸入數據表示成一張圖，這張圖中可能含有許多互不聯通的子圖。
上圖是一種 N=9時的情況，拿 8,5,1,4 這一組說，我們(men) 每次可以刪去其中任意一個(ge) 點，而隻要刪掉的不是割點，我們(men) 下一次就還可以繼續刪。由於(yu) 沒有一個(ge) 圖可以滿足所有點都是割點，所有我們(men) 每次都一定可以找到一個(ge) 非割點並刪去，知道隻剩一個(ge) 點。所以我們(men) 隻需要找到其中有多少個(ge) 互不聯通的子圖就可以了。現在我們(men) 已經可以得到一半的分了，但想要 AC就必需在小於(yu) O(n2) )的時間內(nei) 找出集合數，當然這就需要再次從(cong) 題目中找特殊性質了。那麽(me) 第二個(ge) 技巧就是把 x,y在數軸上表示出來（看到 x,y就放到數軸上是個(ge) 不錯的習(xi) 慣）。總結一下就是先對數據按 x 排序，如果當前的 i 的 yi≤min(y1，y2 ......yi-1 ) 因為(wei) 排序後它是滿足 xi ≥max(x1，x2 ......xi-1 ) 的，所以此時這個(ge) i 不會(hui) 和前麵任意一個(ge) 數分到一組，則它會(hui) 是新的一組，那就把統計的 cnt+1就好了。所以隻要O(n log(n)) 排個(ge) 序再加上 O(n)邊遍曆邊統計就完事了！：
2
Task 1題目：疲於(yu) 對付他難以整平的頭發，Farmer John 決(jue) 定去理發。他有一排 N（1≤N≤105）縷頭發，第 i 縷頭發初始時長度為(wei) Ai 微米（0≤Ai≤N）。理想情況下，他想要他的頭發在長度上單調遞增，所以他定義(yi) 他的頭發的“不良度”為(wei) 逆序對的數量：滿足 i<j 及 Ai>Aj 的二元對 (i,j)。對於(yu) 每一個(ge) j=0,1,…,N−1，FJ 想要知道他所有長度大於(yu) j 的頭發的長度均減少到 j 時他的頭發的不良度。（有趣的事實：人類平均確實有大約 105 根頭發！）
輸入格式（文件名：haircut.in）：輸入的第一行包含 N。第二行包含 A1,A2,…,AN。
輸出格式（文件名：haircut.out）：對於(yu) 每一個(ge) j=0,1,…,N−1，用一行輸出 FJ 頭發的不良度。注意這個(ge) 問題涉及到的整數大小可能需要使用 64 位整數型存儲(chu) （例如，C/C++ 中的“long”）。 輸入樣例：55 2 3 3 0
輸出樣例：04457輸出的第四行描述了 FJ 的頭發長度減少到 3 時的逆序對數量。A=[3,2,3,3,0] 有五個(ge) 逆序對：A1>A2,A1>A5,A2>A5,A3>A5, 和 A4>A5。 測試點性質：測試點 2 滿足 N≤100。測試點 3-5 滿足 N≤5000。測試點 6-13 沒有額外限製。解析：題意概括：
有長為(wei) n的序列 a[1...n],∀a[i](0<i≤n),a[i]≤n。
請你按 j(j=0,1,2,...,n-1依次輸出把大於(yu) j 的 a[i]變為(wei) j 後逆序對的個(ge) 數。
思路：
這是一道很好的思考題，我們(men) 可以把 a[1..n] 按從(cong) 小到大的順序排序，對於(yu) 每個(ge) a[i]，在原序列中它前麵比它大的數的個(ge) 數即為(wei) 其對 j=a[i]+1,a[i]+2,...,n時的答案的貢獻。然後從(cong) 0 到 (n−1) 枚舉(ju) j。每次枚舉(ju) 先輸出答案，再把答案加上等於(yu) j 的 a[i]的貢獻即可。
這個(ge) 貢獻可以利用樹狀數組維護區間和把複雜度降為(wei) O(logn) 。具體(ti) 實現方式為(wei) 先往樹狀數組的每一位上放1。然後每遍曆到一個(ge) a[i]，將它在原序列中的位置對應的樹狀數組值改為(wei) 0，其貢獻即為(wei) 它在原序列中的位置前還有多少 1，即 query(num[i]-1),（num[i]為(wei) a[i]在原序列中的位置）。
Task 2題目：Farmer John 的 N 頭奶牛（1≤N≤2*105）每頭都有一種最喜歡的顏色。奶牛們(men) 的編號為(wei) 1…N，每種顏色也可以用 1…N 中的一個(ge) 整數表示。存在 M 對奶牛 (a,b)，奶牛 b 仰慕奶牛 a（1≤M≤2*105）。有可能 a=b，此時一頭奶牛仰慕她自己。對於(yu) 任意顏色 c，如果奶牛 x 和 y 都仰慕一頭喜歡顏色 c 的奶牛，那麽(me) x 和 y 喜歡的顏色相同。給定這些信息，求一種奶牛喜歡顏色的分配方案，使得每頭奶牛最喜歡的顏色中不同顏色的數量最大。由於(yu) 存在多種符合這一性質的分配方案，輸出字典序最小的（這意味著你應當依次最小化分配給奶牛 1…N 的顏色）。 輸入格式（文件名：fcolor.in）：輸入的第一行包含 N 和 M。以下 M 行每行包含兩(liang) 個(ge) 空格分隔的整數 a 和 b（1≤a,b≤N），表示奶牛 b 仰慕奶牛 a。同一對奶牛可能會(hui) 在輸入中多次出現。 輸出格式（文件名：fcolor.out）：對於(yu) 1…N 中的每一個(ge) i，用一行輸出分配給奶牛 i 的顏色。
輸入樣例：9 121 24 25 84 66 92 98 78 37 19 43 53 4
輸出樣例：123112323在下圖中，用粗邊框圓表示的是最喜歡顏色 1 的奶牛。
測試點性質：測試點 2-3 滿足 N,M≤103。測試點 4-10 沒有額外限製。解析：簡單描述一下算法：從(cong) 1~n遍曆所有點，將這些點的後繼節點合並;從(cong) 1~n遍曆所有點，將它和和它最終屬於(yu) 同一個(ge) 點的染上同一個(ge) 顏色cur，然後++cur;我們(men) 使用並查集維護節點合並，因為(wei) 合並後每個(ge) 點隻會(hui) 有一個(ge) 後繼節點（我們(men) 每步會(hui) 把所有的後繼節點合成一個(ge) 點），想到在每個(ge) 節點並查集的祖先處維護這個(ge) 後繼的編號，開一個(ge) 數組存即可。合並兩(liang) 個(ge) 節點其實就是對應合並由它和它的後繼構成的兩(liang) 條鏈封裝一個(ge) 函數，大概像這樣：
因為(wei) 每個(ge) 節點最多被合並一次，並查集同時加上按秩合並和路徑壓縮優(you) 化後，總複雜度會(hui) 是O(n*α(n))也就是O(n)的。
Task 3題目：Farmer John（又）想到了一個(ge) 新的奶牛晨練方案！如同之前，Farmer John 的 N 頭奶牛（1≤N≤104）站成一排。對於(yu) 1≤i≤N 的每一個(ge) i，從(cong) 左往右第 i 頭奶牛的編號為(wei) i。他告訴她們(men) 重複以下步驟，直到奶牛們(men) 與(yu) 她們(men) 開始時的順序相同。給定長為(wei) N 的一個(ge) 排列 A，奶牛們(men) 改變她們(men) 的順序，使得在改變之前從(cong) 左往右第 i 頭奶牛在改變之後為(wei) 從(cong) 左往右第 Ai 頭。例如，如果 A=(1,2,3,4,5)，那麽(me) 奶牛們(men) 總共進行一步。如果 A=(2,3,1,5,4)，那麽(me) 奶牛們(men) 總共進行六步。每步之後奶牛們(men) 從(cong) 左往右的順序如下：0 步：(1,2,3,4,5)1 步：(3,1,2,5,4)2 步：(2,3,1,4,5)3 步：(1,2,3,5,4)4 步：(3,1,2,4,5)5 步：(2,3,1,5,4)6 步：(1,2,3,4,5)求所有正整數 K 的和，使得存在一個(ge) 長為(wei) N 的排列，奶牛們(men) 需要進行恰好 K 步。由於(yu) 這個(ge) 數字可能非常大，輸出答案模 M 的餘(yu) 數（108≤M≤109+7，M 是質數）。
輸入格式（文件名：exercise.in）：輸入的第一行包含 N 和 M。
輸出格式（文件名：exercise.out）：輸出一個(ge) 整數。
輸入樣例：5 1000000007
輸出樣例：21存在排列使得奶牛需要進行 1、2、3、4、5 以及 6 步。因此，答案為(wei) 1+2+3+4+5+6=21。
測試點性質：測試點 2-5 滿足 N≤102。測試點 6-10 沒有額外限製。解析：
發現如果循環了幾次可以回到原地，當且僅(jin) 當形成了一個(ge) 環，假如設每個(ge) 環的長度是 ai，那麽(me) 可以發現 k=lcmai ，又知道lcm 其實就是將那幾個(ge) 數分解質因數，然後取每個(ge) 質數的最高次冪乘起來，所以我們(men) 可以想到枚舉(ju) 素數來做dp。我們(men) 設 f(i,j)f(i,j) 表示前 i 個(ge) 素數總和為(wei) j的所有 k 的總和，枚舉(ju) 第 個(ge) 素數的冪進行轉移，因為(wei) 之前並沒有用過第 個(ge) 素數，所以應把上一個(ge) 狀態乘上 pki，所以直接有方程 f(i,j)=∑f(i−1,j− pki)× pki接著發現這個(ge) 東(dong) 西可以滾動數組壓縮一下，於(yu) 是可以省掉一維 f(j)=∑f(j− pki )× pki，倒序枚舉(ju) 即可，初始狀態 f(0)=1，最後答案是∑f(i)。
【競賽報名/項目谘詢+微信：mollywei007】
評論已經被關(guan) 閉。