USACO 2022-2023賽季試題解析係列（12月晉級賽）

大家好，USACO試題解析係列在新賽季又和大家見麵啦！截至北京時間本周二晚，USACO 本賽季第一場晉級賽正式結束,  滿分同學會(hui) 當場晉級，沒有當場晉級的同學可以耐心等待一周之內(nei) 出成績。

各位同學度過了上周緊張又充實的一個(ge) 周末，不少考銅級的同學會(hui) 覺得相比以往，本次銅級可謂難出天際了，上個(ge) 賽季各個(ge) 級別難度已經往上拉了一波，這個(ge) 賽季其他幾個(ge) 級別難度倒還好，沒有再往上拉多少，但是作為(wei) 入門級的銅級還是繼續在往上拉難度。

我們(men) 題解係列對於(yu) Benjamin Qi大佬多次介紹過，這次他給大家上了一課，哪怕是暴力枚舉(ju) 也可以煩死你。Benjamin Qi大佬給選手們(men) 帶來的這道看似簡單，但殺傷(shang) 力極強的銅級第3題，首先一部分選手壓根兒(er) 沒整明白逆向工程的整個(ge) 過程，淘汰！

明白之後，麵對頗有挑戰的枚舉(ju) 過程，寫(xie) 到崩潰，淘汰！去年筆者分析命題趨勢後，告訴各位後麵日子不好過哦，已然成真。

推薦各位同學認真讀一讀題解，感受下命題難度的提升趨勢。

更多內(nei) 容，請參考下文解析。

大家的眼睛是雪亮的，成績不是靠口頭喊出來的，而是需要一步一步長期耕耘才能結出碩果。能夠在官方題解公布之前，原創全部組別題解的機構，是真硬核！

（需要轉載的請注明來源，尊重他人勞動成果）

以下內(nei) 容是各大級別的賽題解析，供同學們(men) 參考交流。

第1題

題目解析：

第一題的命題質量比較好，具有一定區分度。如果上來就打暴力解，不好意思，頂多2/3的分數給到你，注意題目中N的範圍是1~10^5, 不超過O(nlogn)的時間複雜度才能通過。目前銅級中極少遇到二分，因此這個(ge) O(nlogn)通常是給咱們(men) 用sort函數做排序用的，排序處理完，再用O(n)的算法即可通過。雖然是第一題，但是沒有送分，還是具備一定的區分作用，篩掉部分隻會(hui) 簡單模擬的選手。

核心代碼如下：

sort(c, c + n); // 先排序處理 long long ans = 0, minT = 0;for (int i = 0; i < n; i++) { // 注意兩(liang) 個(ge) int相乘結果數據範圍可能會(hui) 溢出 if (1LL * c[i] * (n - i) > ans) { ans = 1LL * c[i] * (n - i); minT = c[i]; }}cout << ans << ' ' << minT << endl;

第2題

題目解析：

這題也有些挑戰，首先得仔細看明白題意，如何用最少的草皮滿足所有牛的需求。注意題目中N的範圍是1~10^5, 無腦直接暴力，頂多拿到2/3的分數。正解需要利用一個(ge) 貪心策略，依次為(wei) 每頭牛去種草，種的位置和上一個(ge) 放相同種類草的位置間隔盡可能的拉大，取決(jue) 於(yu) k的值。

核心代碼如下：

// 以種G為(wei) 例if(curPos - lastPos > k){ cnt++; // 草皮數 +1 int plantPos = curPos; if(curPos + k < n){ plantPos = curPos + k; // 間隔盡可能大 } // 考慮目標位置被占用的情況 if(ans[plantPos]!='.' && plantPos - 1 >= 0){ plantPos--; } lastPos = plantPos; ans[plantPos] = 'G'; // 記錄結果}

第3題

題目解析：

這一題給大家上了一課，哪怕是暴力枚舉(ju) 也可以煩死你。Benjamin Qi大佬給選手們(men) 帶來的這道看似簡單，但殺傷(shang) 力極強的銅級題。首先一部分選手壓根兒(er) 沒整明白逆向工程的整個(ge) 過程，淘汰！明白之後，麵對頗有挑戰的枚舉(ju) 過程，寫(xie) 到崩潰，淘汰！整體(ti) 思路就是枚舉(ju) 它可能的第一個(ge) 分支代碼是啥，然後篩選出剩餘(yu) 的行，繼續枚舉(ju) 第二個(ge) 分支，依次下去，每一輪篩選出的剩餘(yu) 行數必須越來越少，直至全部篩選完，否則就輸出"LIE"。

核心代碼如下：

// mask[i] = -1待選該位置0或1皆可//         = 0待選該位置隻能為(wei) 0//         = 1待選該位置隻能為(wei) 1memset(mask, -1, sizeof(mask));filteLines(...);while (true) { // n0代表回答為(wei) 0的數量、n1代表回答為(wei) 1的數量 if (n0 == 0 || n1 == 0) { cout << "OK" << endl; break; } bool ok = false; for (int i = 0; i < n; i++) { // column // all[i][?]統計第i列中0和1的個(ge) 數 if (all[i][0] > 0 && all[i][1] > 0) { // only1[i][?]統計所有回答為(wei) 1的行中，第i列中0和1的個(ge) 數 // all 0 -> 0 or all 0 -> 1 if (only1[i][0] == 0 || only1[i][0] == all[i][0]) { ok = true; mask[i] = 1; } // all 1 -> 0 or all 1 -> 1 if (only1[i][1] == 0 || only1[i][1] == all[i][1]) { ok = true; mask[i] = 0; } } } if (!ok) { cout << "LIE" << endl; break; } filteLines(...);}

第1題

題目解析

根據題意，要求把一棵樹中的每個(ge) 點的值分配均勻，首先可以利用DFS在O(n)範圍內(nei) 找到哪些點對之間需要搬運以及搬運的數量，如果直接輸出這些有向邊，答案錯誤。這裏有個(ge) 細節，過程中可能會(hui) 出現搬運的起點是個(ge) 負數，因此咱們(men) 需要想辦法按照某種順序輸出這些邊。這些有向邊構成一個(ge) DAG(有向無環圖），立馬可以想到寫(xie) 一個(ge) 拓撲排序即可搞定。

核心代碼如下：

void dfs(int cur, int fa) { for (int to : g[cur]) { if (to != fa) dfs(to, cur); } if (num[cur] != avg) { ans++; if (num[cur] > avg) { // 子節點超平均值，子搬到父 v[cur].push_back({fa, num[cur] - avg}); num[fa] += num[cur] - avg; indegree[fa]++; } else { // 父節點超平均值，父搬到子 v[fa].push_back({cur, -num[cur] + avg}); num[fa] += num[cur] - avg; indegree[cur]++; } }}

第2題

題目解析：

此題為(wei) 一個(ge) 博弈論問題，我們(men) 需要找到一個(ge) 必贏或必輸的局麵。每個(ge) 房間的牛頭數如果是4的倍數那麽(me) 後手贏，否則先手贏。為(wei) 什麽(me) 呢？由於(yu) 隻能取1個(ge) 或者不超過當前房間牛頭數的質數，因此：

• 對於總數為4的倍數的情況，假如先手取1個，後手取3個，如先手取2個，後手取2個，如先手取3個，後手取1個。其餘依次類推，始終保持後手取完後，剩餘的數為4的倍數，結果後手必贏。
• 對於總數非4的倍數的情況，先手第一次取(N%4)個，剩下來的就是4的倍數，結果先手必贏。

經過上述分析，可知隻要找到經過步數最少的一個(ge) 房間看誰贏就好了，其中有個(ge) 細節，就是如果有多個(ge) 經過步數最小的房間怎麽(me) 辦呢？需要記錄其中哪個(ge) 房間先到達。

核心代碼如下：

int minwin = INT_MAX, minlose = INT_MAX;bool firsthandWin = true;for (int i = 1; i <= n; i++) { if (num[i] % 4 == 0) { // 4的倍數那麽(me) 後手贏 minlose = min(minlose, num[i] / 4); if (num[i] / 4 < minwin) firsthandWin = false; } else { // 否則先手贏 minwin = min(minwin, steps[num[i]]); if (steps[num[i]] < minlose) firsthandWin = true; }}if (firsthandWin) cout<<"Farmer Johnn";else cout<<"Farmer Nhojn";

第3題

題目解析：

此題是一道不算難的構造題，先把每個(ge) 區間長度為(wei) 2，差值不為(wei) 0的子數組找到, 其中兩(liang) 個(ge) 數必不相同，然後看每個(ge) 區間長度為(wei) 3的子數組，如果大區間差值是兩(liang) 個(ge) 小區間差值之和，那麽(me) 說明單調性相同，否則說明單調性相反，依次構造即可。

核心代碼如下：

x[1] = 666; // 初始值挑個(ge) 你喜歡的數即可 x[2] =  x[1] + a[t[1]][t[2]]; // t[i]映射原始位置 int sign = 1; // cnt記錄有多少個(ge) 數和前一位不同 for (int i = 2; i <= cnt; i++) { if (a[t[i - 2]][t[i]] == a[t[i - 2]][t[i - 1]] + a[t[i - 1]][t[i]]) { // 差大區間差值是兩(liang) 個(ge) 小區間差值之和，單調性相同 x[i] = x[i - 1] + sign * a[t[i - 1]][t[i]]; }else { // 否則說明單調性相反 sign *= -1; x[i] = x[i - 1] + sign * a[t[i - 1]][t[i]]; } } // 最後輸出數列時要記得映射一下下標

第1題

題目解析：

觀察一個(ge) 貪心性質，就是說要用cones代替的那些肯定是需求最少的，按這點排序之後就肯定是先用cones再用moonies了，分成兩(liang) 部分背包即可。

第2題

題目解析：

用set維護所有能看到的對，修改時暴力往後找會(hui) 被阻擋的對刪除即可，

每對隻會(hui) 被刪除一次，可以保證均攤複雜度通過。

第3題

題目解析：

要使得組中度數最小的點盡可能大，則用一個(ge) 優(you) 先隊列每次刪除度最小的點即可，但這樣不好統計，因此可以將這個(ge) 過程倒過來變成加邊，然後用啟發式合並維護過程中的答案，找最大的即可。

第1題

限於(yu) 篇幅，Platinum題目就不貼了

題目解析：

維護 d1 d2  f3 f4 g3 g4  6個(ge) 數組，表示經過指定邊數的最短路，具體(ti) 見代碼

long long d1[320][320]; // i to j 1 edgelong long d2[320][320]; // i to j 2 edges long long f3[320]; // 1 to i 3 edgeslong long f4[320]; // 1 to i 4 edges long long g3[320]; // i to n 3 edgeslong long g4[320]; // i to n 4 edges d1[x][y] = a[x][y];for (int j = 1; j <= n; j++) { d2[x][j] = min(d2[x][j], d1[x][y] + d1[y][j]); d2[j][y] = min(d2[j][y], d1[j][x] + d1[x][y]);} // f3 g3 as second edgefor (int j = 1; j <= n; j++){ f3[j] = min(f3[j], d1[1][x] + d1[x][y] + d1[y][j]); g3[j] = min(g3[j], d1[j][x] + d1[x][y] + d1[y][n]);}// f3 g3 as third edgef3[y] = min(f3[y], d2[1][x] + d1[x][y]);g3[x] = min(g3[x], d1[x][y] + d2[y][n]); // f4 g4 as second/third edge for (int j = 1; j <= n; j++){ f4[j] = min(f4[j], d1[1][x] + d1[x][y] + d2[y][j]); f4[j] = min(f4[j], d2[1][x] + d1[x][y] + d1[y][j]); g4[j] = min(g4[j], d2[j][x] + d1[x][y] + d1[y][n]); g4[j] = min(g4[j], d1[j][x] + d1[x][y] + d2[y][n]);} // as fourth edgef4[y] = min(f4[y], f3[x] + d1[x][y]);g4[x] = min(g4[x], d1[x][y] + g3[y]);

第2題

題目解析：

用並查集做啟發式合並 初始每條邊對應並查集的一個(ge) 點，對於(yu) 並查集的每個(ge) 點，維護一個(ge) 集合，表示包含哪些點，合並集合的時候考慮2件事，有一些邊加重了，算了2次，需要從(cong) 答案中減去新增了多少條邊。

第3題

題目解析：

總體(ti) 思路是這樣的，不斷讓字符串由短變長，支持這樣幾種操作

兩(liang) 端+H

兩(liang) 端+G

一端+G

考慮所有H之間的配對情況，這樣就不會(hui) 有錯位的問題了。

不好做的是一段+G怎麽(me) 做，這種情況主要是對稱軸移動了1

求和是 abs(對稱軸 * 2 - p[i] - p[p.size() - 1 - i])

對稱軸*2增加1，abs可能增加1可能減少1

用2個(ge) 變量記錄（對稱軸 * 2 - p[i] - p[p.size() - 1 - i] ）為(wei) 正的i的個(ge) 數，為(wei) 負的i的個(ge) 數。

在增長的過程中用一個(ge) 數組記錄（p[i] + p[p.size() - 1 - i]）出現的次數

為(wei) 了維護差值為(wei) 正的i的個(ge) 數和為(wei) 負的i的個(ge) 數。