USACO 2021-2022 赛季的2月月赛已落下帷幕，对于绝大部分学生来说，本赛季已经全部结束。三月份的月赛叫做公开赛，主要是为了选拔国际奥林匹克候选选手，整体题目难度上会比12月-2月的3次月赛都要难一些，如果前三次月赛没能顺利晋级，在公开赛上晋级的希望更渺茫。
Bronze Problem1
Sleeping in Class
题解：通过读题我们可以知道本题有两个问题：
(一) 调整数据让数组的每个元素相等。
(二) 记录下相等元素数组的最小操作数。
首先通过题目描述我们可以明确数组中的元素只能相邻两两相加，碰到这种有固定规则的题，我们通常可以使用简单的循环通过操作数组的下标来解决这个问题。
1. 操作过程就是从数组的第一个元素开始相加相邻元素，直到满足一定条件，现在我们来一起分析一下结束的条件，数组内元素相加应该符合什么样的规范停止呢？
a）可知一个数组的元素皆相等有固定的情况，我们来打个比方，比如说数组内元素相加的总和为10，那么此时数组满足题意只有如下几种情况：。
b）10个1组成相等元素，5个2满足相等元素，2个5满足相等元素，1个10满足相等元素。我们来延伸一下，数组的总和值如果为n的情况下，那么只要n%i==0（i为从n到1的递减），我们就可以延伸出相应符合题意的数组。
2. 接下来我们来考虑一下记录符合题意数组的操作数，首先我们来准备一个最差的情况（必然发生）来做保底，如果数组有m项，那么最差情况为m-1次，先把它记录下来。
a）下面我们就是要完成每种情况的匹配了，首先匹配的是当前数组元素项数（m）的情况，每个元素是n（总和）/m，若匹配则记录下此时的操作数0，不匹配的话使操作数加1，继续让完成n/(m-1)，是否继续匹配，匹配就记录操作，不匹配按照这个规律继续，我们只需要在最后留下最少的操作数即可。
b）案例：数组总和24，那么24,12,8,6,3,2,1（24%n==0）n都是我们需要判定的判定点。
代码如下：
#include <iostream>
#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
题解：通过读题我们可以知道我们的任务目标是让第一个排列A变成第二个排列B并且执行最小的操作数，由此我们可以分解成两个问题：
(一) 调整第一个A以有序的方式读入。
(二) 联立排列A和B，如果出现不相同的情况使得操作数加1。
首先通过题目描述我们可以明确数组A以及数组B中的元素，碰到这种有固定排列目标的题，我们通常可以使用数组离散化来解决这个问题。
1. 操作过程就是先让排列A有序化读入，为此我们可以使用数组来解决这个问题。
a）循环读入排列中的元素，b[x] = i。通过这种方式可以使当前排列有序化。案例中的（5,1,3,2,4）这样就可以有序化操作变为5:1,1:2,3:3,2:4,4:5（本题使用关联式容器map同样适用）。
b）此时我们需要对第二个数组有序化操作，关键是此时可以把两个数组/关联式容器联立起来，由题目可知，两个数组的元素数量一定相等且数值相等，只是有可能排列方式不同而已，关键就是要把它们联立起来，对于第二个数组a[i] = b[x]，案例（4,5,2,1,3）可以找到1:5,2:1,3:4,4:2,5:3。
2. 此时我们来看看变序之后的数组5 1 4 2 3，从右往左看，3右方的最小值（包含自己）为3,2为2,4为2,1为1,5为1，此时可得1 1 2 2 3，与原数组相比较5 1 4 2 3，元素不同操作数则加1,1+1=2，可得结果为2。
a）minn = min(minn, a[i])，这就是对数组取小值的操作内容。
b）if (a[i] > c[i]) ans++; 增加操作数。
c）自己来思考一下1 2 3 4 5与 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
题解：通过读题我们可以知道本题有两个问题：
(一) 独立记录下4个立方体的字母。
(二) 搜索每一种情况下目标单词与现有的立方体排列是否匹配。
首先通过题目描述我们可以明确有4个独立的立方体储存字母，通过这些字母去匹配出现的单词（COW MOO…），幸运的是，在时间复杂度上给了我们很大的宽容，所以我们可以尝试暴力搜索的方式解决一下。
1. 如何记录下立方体的字母呢？
a）我们可以使用数组a[26]来记录这些出现的字母（单词都是由26个英文字母组成的）。遍历整个单词我们可以记录下某个单词是否出现过，a[x-‘A’]=1,这样做还可以去掉重复的多余元素。
b）下面我们可以把它们放到另外一个动态数组中，这样就完整记录下一个立方体的字母了。
c）以上操作重复四次，记下四个立方体。
2. 这时我们就要用到暴力搜索了，此时最多我们有6x6x6x6种情况，则可以使用4次循环用于模拟所有的情况，如果发生匹配，说明可以用木块拼出单词，如果不能匹配，就不能用木块拼出单词，相对应的输出yes和no。
a）在循环之下，我们新建一个动态数组去储存单词并定义一个false的标签，开始用四个立方体进行循环，这里我们用四个for循环模拟出每一次木块情况，接下来就是让单词的数组进行比对等出结果就好。
b）案例：MOO不匹配是因为我们无法用这四个木码。
代码如下：
#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月月赛的铜升银题解就到这里了，我们下周银升金题解见，敬请期待！
USACO 题目的特色就在于灵活。对于这种线上比赛来说，如果题目能简单的套用算法，随便搜索一下对应的算法代码，那这个比赛还有什么参与的价值？
USACO 考题的侧重点就在于考核你使用算法分析问题的能力，所以平时做题的时候，可以把题目的问题类型和算法做一个关联对应，这样更容易从问题入手，快速联想到对应算法。
距离2022-2023赛季的USACO竞赛还有10个月的充足时间，计划参赛的同学就开始制定学习计划了，以备在下一赛季顺利晋级。
【竞赛报名/项目咨询请加微信：mollywei007】
