USACO 2021-2022 賽季的2月月賽已落下帷幕，對於(yu) 絕大部分學生來說，本賽季已經全部結束。三月份的月賽叫做公開賽，主要是為(wei) 了選拔國際奧林匹克候選選手，整體(ti) 題目難度上會(hui) 比12月-2月的3次月賽都要難一些，如果前三次月賽沒能順利晉級，在公開賽上晉級的希望更渺茫。
Bronze Problem1
Sleeping in Class
題解：通過讀題我們(men) 可以知道本題有兩(liang) 個(ge) 問題：
(一) 調整數據讓數組的每個(ge) 元素相等。
(二) 記錄下相等元素數組的最小操作數。
首先通過題目描述我們(men) 可以明確數組中的元素隻能相鄰兩(liang) 兩(liang) 相加，碰到這種有固定規則的題，我們(men) 通常可以使用簡單的循環通過操作數組的下標來解決(jue) 這個(ge) 問題。
1. 操作過程就是從(cong) 數組的第一個(ge) 元素開始相加相鄰元素，直到滿足一定條件，現在我們(men) 來一起分析一下結束的條件，數組內(nei) 元素相加應該符合什麽(me) 樣的規範停止呢？
a）可知一個(ge) 數組的元素皆相等有固定的情況，我們(men) 來打個(ge) 比方，比如說數組內(nei) 元素相加的總和為(wei) 10，那麽(me) 此時數組滿足題意隻有如下幾種情況：。
b）10個(ge) 1組成相等元素，5個(ge) 2滿足相等元素，2個(ge) 5滿足相等元素，1個(ge) 10滿足相等元素。我們(men) 來延伸一下，數組的總和值如果為(wei) n的情況下，那麽(me) 隻要n%i==0（i為(wei) 從(cong) n到1的遞減），我們(men) 就可以延伸出相應符合題意的數組。
2. 接下來我們(men) 來考慮一下記錄符合題意數組的操作數，首先我們(men) 來準備一個(ge) 最差的情況（必然發生）來做保底，如果數組有m項，那麽(me) 最差情況為(wei) m-1次，先把它記錄下來。
a）下麵我們(men) 就是要完成每種情況的匹配了，首先匹配的是當前數組元素項數（m）的情況，每個(ge) 元素是n（總和）/m，若匹配則記錄下此時的操作數0，不匹配的話使操作數加1，繼續讓完成n/(m-1)，是否繼續匹配，匹配就記錄操作，不匹配按照這個(ge) 規律繼續，我們(men) 隻需要在最後留下最少的操作數即可。
b）案例：數組總和24，那麽(me) 24,12,8,6,3,2,1（24%n==0）n都是我們(men) 需要判定的判定點。
代碼如下：
#include <iosestream>
#include <vector>
using namespace std;
vector<int> a;
int check()
{
int n;
cin >> n;
int s = 0;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
a.push_back(x);
s += x;
}
if (s == 0)
{
return 0;
}
int ans = n;
while (ans == n)
ans--;
for (int x = n; x > 0; x--)
{
if (s % x == 0)
{
int res = s / x;
int ok = 1;
int t = 0;
for (int i = 0; i < n; ++i)
{
int cur = 0;
int j = i;
while (j < n and cur + a[j] <= res)
{
cur += a[j++];
}
if (cur != res)
{
ok = 0;
break;
}
t += j - i - 1;
i = j - 1;
}
if (ok == 0)
continue;
else
{
ans = min(ans, t);
}
}
}
return ans;
}
int main()
{
int T;
cin >> T;
while (T--)
{
cout << check() << endl;
}
return 0;
}
（向下滑動，查看所有代碼）
Bronze Problem2
Photoshoot 2
題解：通過讀題我們(men) 可以知道我們(men) 的任務目標是讓第一個(ge) 排列A變成第二個(ge) 排列B並且執行最小的操作數，由此我們(men) 可以分解成兩(liang) 個(ge) 問題：
(一) 調整第一個(ge) A以有序的方式讀入。
(二) 聯立排列A和B，如果出現不相同的情況使得操作數加1。
首先通過題目描述我們(men) 可以明確數組A以及數組B中的元素，碰到這種有固定排列目標的題，我們(men) 通常可以使用數組離散化來解決(jue) 這個(ge) 問題。
1. 操作過程就是先讓排列A有序化讀入，為(wei) 此我們(men) 可以使用數組來解決(jue) 這個(ge) 問題。
a）循環讀入排列中的元素，b[x] = i。通過這種方式可以使當前排列有序化。案例中的（5,1,3,2,4）這樣就可以有序化操作變為(wei) 5:1,1:2,3:3,2:4,4:5（本題使用關(guan) 聯式容器map同樣適用）。
b）此時我們(men) 需要對第二個(ge) 數組有序化操作，關(guan) 鍵是此時可以把兩(liang) 個(ge) 數組/關(guan) 聯式容器聯立起來，由題目可知，兩(liang) 個(ge) 數組的元素數量一定相等且數值相等，隻是有可能排列方式不同而已，關(guan) 鍵就是要把它們(men) 聯立起來，對於(yu) 第二個(ge) 數組a[i] = b[x]，案例（4,5,2,1,3）可以找到1:5,2:1,3:4,4:2,5:3。
2. 此時我們(men) 來看看變序之後的數組5 1 4 2 3，從(cong) 右往左看，3右方的最小值（包含自己）為(wei) 3,2為(wei) 2,4為(wei) 2,1為(wei) 1,5為(wei) 1，此時可得1 1 2 2 3，與(yu) 原數組相比較5 1 4 2 3，元素不同操作數則加1,1+1=2，可得結果為(wei) 2。
a）minn = min(minn, a[i])，這就是對數組取小值的操作內(nei) 容。
b）if (a[i] > c[i]) ans++; 增加操作數。
c）自己來思考一下1 2 3 4 5與(yu) 1 2 3 4 5的匹配結果。
代碼如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int main()
{
int n;
cin >> n;
int a[MAXN], b[MAXN], c[MAXN], cur, minn;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
b[x] = i;
}
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
a[i] = b[x];
}
minn = a[n];
for (int i = n; i >= 1; i--)
{
minn = min(minn, a[i]);
c[i] = minn;
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] > c[i])
ans++;
}
cout << ans << endl;
return 0;
}
（向下滑動，查看所有代碼）
Bronze Problem3
Blocks
題解：通過讀題我們(men) 可以知道本題有兩(liang) 個(ge) 問題：
(一) 獨立記錄下4個(ge) 立方體(ti) 的字母。
(二) 搜索每一種情況下目標單詞與(yu) 現有的立方體(ti) 排列是否匹配。
首先通過題目描述我們(men) 可以明確有4個(ge) 獨立的立方體(ti) 儲(chu) 存字母，通過這些字母去匹配出現的單詞（COW MOO…），幸運的是，在時間複雜度上給了我們(men) 很大的寬容，所以我們(men) 可以嚐試暴力搜索的方式解決(jue) 一下。
1. 如何記錄下立方體(ti) 的字母呢？
a）我們(men) 可以使用數組a[26]來記錄這些出現的字母（單詞都是由26個(ge) 英文字母組成的）。遍曆整個(ge) 單詞我們(men) 可以記錄下某個(ge) 單詞是否出現過，a[x-‘A’]=1,這樣做還可以去掉重複的多餘(yu) 元素。
b）下麵我們(men) 可以把它們(men) 放到另外一個(ge) 動態數組中，這樣就完整記錄下一個(ge) 立方體(ti) 的字母了。
c）以上操作重複四次，記下四個(ge) 立方體(ti) 。
2. 這時我們(men) 就要用到暴力搜索了，此時最多我們(men) 有6x6x6x6種情況，則可以使用4次循環用於(yu) 模擬所有的情況，如果發生匹配，說明可以用木塊拚出單詞，如果不能匹配，就不能用木塊拚出單詞，相對應的輸出yes和no。
a）在循環之下，我們(men) 新建一個(ge) 動態數組去儲(chu) 存單詞並定義(yi) 一個(ge) false的標簽，開始用四個(ge) 立方體(ti) 進行循環，這裏我們(men) 用四個(ge) for循環模擬出每一次木塊情況，接下來就是讓單詞的數組進行比對等出結果就好。
b）案例：MOO不匹配是因為(wei) 我們(men) 無法用這四個(ge) 木碼。
代碼如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int a[26] = {0};
vector<int> tz[5];
for (int i = 1; i <= 4; i++)
{
string s;
cin >> s;
for (char x : s)
a[x - 'A'] = 1;
for (int j = 0; j < 26; j++)
if (a[j])
{
tz[i].push_back(j);
a[j] = 0;
}
}
int t = n;
while (t--)
{
vector<int> word;
string s;
cin >> s;
for (char x : s)
{
word.push_back(x -'A');
}
bool flag = false;
for (int i1 = 0; i1 < tz[1].size(); i1++)
{
for (int i2 = 0; i2 < tz[2].size(); i2++)
{
for (int i3 = 0; i3 < tz[3].size(); i3++)
{
for (int i4 = 0; i4 < tz[4].size(); i4++)
{
a[tz[1][i1]]++;
a[tz[2][i2]]++;
a[tz[3][i3]]++;
a[tz[4][i4]]++;
int sum = 0;
for (int j = 0; j < word.size(); j++)
{
if (a[word[j]])
{
sum++;
a[word[j]]--;
}
else
break;
}
a[tz[1][i1]] = 0;
a[tz[2][i2]] = 0;
a[tz[3][i3]] = 0;
a[tz[4][i4]] = 0;
if (sum == word.size())
{
flag = true;
break;
}
}
if (flag) break;
}
if (flag) break;
}
if (flag) break;
}
if (flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
（向下滑動，查看所有代碼）
本期 USACO 2021-2022賽季2月月賽的銅升銀題解就到這裏了，我們(men) 下周銀升金題解見，敬請期待！
USACO 題目的特色就在於(yu) 靈活。對於(yu) 這種線上比賽來說，如果題目能簡單的套用算法，隨便搜索一下對應的算法代碼，那這個(ge) 比賽還有什麽(me) 參與(yu) 的價(jia) 值？
USACO 考題的側(ce) 重點就在於(yu) 考核你使用算法分析問題的能力，所以平時做題的時候，可以把題目的問題類型和算法做一個(ge) 關(guan) 聯對應，這樣更容易從(cong) 問題入手，快速聯想到對應算法。
距離2022-2023賽季的USACO競賽還有10個(ge) 月的充足時間，計劃參賽的同學就開始製定學習(xi) 計劃了，以備在下一賽季順利晉級。
【競賽報名/項目谘詢+微信：mollywei007】
評論已經被關(guan) 閉。