USACO 2022赛季第一次月赛已落下帷幕，本次竞赛中，参加铜组总人数是9974 人，最终顺利升级的学生比率为15%，银组的比赛更为残酷，总共有3676位参赛者，最终顺利升级的学生比率为12%。顺利通过了晋级的学生应该为自己庆祝一下，这个升级比例并不高。
今年铜牌组和银牌组的录取分数相较于去年，都低了100 分，去年是800 分才能顺利升级，今年则是700 分就能升级了。官方就铜组情况描述中特意说明了今年为何降低分数，大概意思是说铜组的通过值之所以设置的低一些，说明这次铜组竞赛不包含任何凑数的简单问题，有些问题甚至包括一些有趣的大挑战，具体的英文描述如下：
为方便同学了解题目思路，USACO教学组准备了《USACO题解》专题，本期进入针对本次铜组竞赛，进行详细的题目解析，为学生提供思路和题解参考，希望能为同学们提供有用的帮助。
Bronze Problem1
Lonely Photo
(孤独的牛)
思路：我们需要记录长度大于等于3且正好包含一个G或者一个H的子字符串的数量。
最直接的解决方案时间是暴力搜索检查长度至少为3的每个子字符串，那么就会有O(N2)个这样的子字符串需要检查，并且每个子字符串都需要O(N)时间来进行验证，因此总运行时间为O(N3)。
如何提高：我们可以选择按照特定的顺序检查子字符串。固定子字符串中最左边的字符，然后开始向右扫描。如果我们看到至少三个字符，并且其中一个是G或者其中一个是H，则记录答案+1。依次循环遍历所有最左边的字符，最后获得答案。该解决方案的方法是件复杂度为O(N2)。
代码如下：
#include <iostream>
#include <string>
usingnamespacestd;
intmain() {
int n;
string s;
cin >> n >> s;
int ans = 0;
for(int i = 0; i < (int)s.size(); i++) {
int g = 0;
int h = 0;
for(int j = i; j < (int)s.size(); j++) {
if(s[j] == 'G') g++;
else h++;
if(g+h >= 3 && (g==1or h==1)) ans++;
}
}
cout << ans;
}
这个问题可以在O(N)时间复杂度内解决。对于每个字符，在进行遍历的时候，如果当前的字符与其下一个字符不相等，那么我们记录出来。在这种情况下，如果字符是G，那么子字符串要么至少有一边有两个H或者两边至少各有一个H，并且没有其余的G再次出现。我们可以直接向左和向右计算不匹配的字符数量并考虑这两种情况。
代码如下：
#include <iostream>
#include <string>
usingnamespacestd;
intmain() {
int n;
string s;
cin >> n >> s;
longlong ans = 0;
for(int i = 0; i < n; i++) {
int64_t lhs = 0;
if(i > 0and s[i-1] != s[i]) {
lhs++;
for(int k = i-2; k >= 0and s[k] == s[i-1]; k--) lhs++;
}
int64_t rhs = 0;
if(i+1 < n and s[i+1] != s[i]) {
rhs++;
for(int k = i+2; k < n && s[k] == s[i+1]; k++) rhs++;
}
ans += lhs * rhs + max(lhs-1, (longlong)0) + max(rhs-1, (longlong)0);
}
cout << ans;
}
Bronze Problem2
Air Cownditioning
(牛牛们的空调)
思路：我们首先定义 di = pi - ti 对所有的i 从 1… N. 请注意，di因此是每个奶牛i快乐所需要的温度变化量。现在，我们可以专注于使di为0，而不是让pi = ti。我们可以将t的某个子段中的所有值增加或者减少1一样，我们也可以将d的某个子段中的所有值增加或减少1。
那么我们就将问题变为如何尽可能少的改变使d处处为0。直观的讲，我们就需要避免增加已经是正数的d值，或者减少已经是负数的d值。我们更不想触碰已经是0的d值。
因此，我们可以尝试的一种策略如下，假设dN是正整数，找到最小的j，使得dj通过dN都是正数，然后将所有的这些数字减少1.如果dN为负数，则应用类似的逻辑，只是将尽可能多的负数增加1.换句话说，找到所有数字都为正数或者所有数字均为负数的最长后缀，然后将其全部调整为0.
代码如下：
#include <iostream>
usingnamespacestd;
intmain() {
int N;
cin >> N;
vector<int> p(N), t(N), d(N);
for (int i = 0; i < N; ++i)
cin >> p[i];
for (int i = 0; i < N; ++i)
cin >> t[i];
for (int i = 0; i < N; ++i)
d[i] = p[i] - t[i];
int first_nonzero = 0, ans = 0;
while (true) {
while (first_nonzero < N and d[first_nonzero] == 0)
++first_nonzero;
if (first_nonzero == N)
break;
int r = first_nonzero;
auto sgn = [&](int x) {// 定义匿名函数
if (x < 0)
return -1;
if (x > 0)
return1;
return0;
};
while (r + 1 < N and sgn(d[r + 1]) == sgn(d[first_nonzero]))
++r;
for (int i = first_nonzero; i <= r; ++i) {
if (d[i] < 0)
++d[i];
else
--d[i];
}
++ans;
}
cout << ans;
}
Bronze Problem3
Walking home
(一路向家)
思路：这个问题中的子任务首先解决K=1的问题，然后再解决K=2，K=3的问题。
K = 1：如果Bessie只能转弯一次，她必须在右上角或者左下角转弯。因此检查顶部航和右侧列是否为空，底部行和左侧列是否为空就足够了。
K = 2：如果Bessie要转两次，要么她走在最上面一行，右转走到下面一直走到底部，然后左转；要么沿着左栏走，左转，一直向右走，然后右转。在前一种情况下，我们可以暴力解决Bessie选择的所有列。在后一种情况下，我们可以暴力解决Bessie选择的所有行。
K = 3: 如果Bessie正好要转三个弯，那么Bessie最终会在网格中间的某个正方形中转弯，而这个放个既不在上面一排，也不会在下面一排，也不会在左边一列，也不在右边一列。那么我们就可以用暴力搜索来破解Bessie选择的所有内部方格。
对每一个测试样例时间复杂度为O(N3)：有O(N2)路径Bessie能够考虑，有O(N)个方块以验证是否为空。
代码如下：
#include <iostream>
#include <string>
#include <vector>
usingnamespacestd;
voidsolve() {
int n, k;
cin >> n >> k;
vector<string> g(n);
for(int i = 0; i < n; i++) cin >> g[i];
int ret = 0;
if(k >= 1) {
bool urcorner = true;
bool dlcorner = true;
for(int i = 0; i < n; i++) {
if(g[0][i] == 'H'or g[i][n-1] == 'H') urcorner = false;
if(g[i][0] == 'H'or g[n-1][i] == 'H') dlcorner = false;
}
ret += urcorner;
ret += dlcorner;
}
if(k >= 2) {
// use column j
for(int j = 1; j < n-1; j++) {
bool valid = true;
for(int i = 0; i < n; i++) {
if(g[i][j] == 'H') valid = false;
if(i < j and g[0][i] == 'H') valid = false;
if(i > j and g[n-1][i] == 'H') valid = false;
}
ret += valid;
}
// use row i
for(int i = 1; i < n-1; i++) {
bool valid = true;
for(int j = 0; j < n; j++) {
if(g[i][j] == 'H') valid = false;
if(j < i and g[j][0] == 'H') valid = false;
if(j > i and g[j][n-1] == 'H') valid = false;
}
ret += valid;
}
}
if(k >= 3) {
for(int i = 1; i < n-1; i++) {
for(int j = 1; j < n-1; j++) {
// RDRD
bool valid = g[i][j] == '.';
for(int a = 0; a < n; a++) {
if(a <= i and g[a][j] == 'H') valid = false;
if(a >= i and g[a][n-1] == 'H') valid = false;
if(a <= j and g[0][a] == 'H') valid = false;
if(a >= j and g[i][a] == 'H') valid = false;
}
ret += valid;
valid = g[i][j] == '.';
// DRDR
for(int a = 0; a < n; a++) {
if(a <= i and g[a][0] == 'H') valid = false;
if(a >= i and g[a][j] == 'H') valid = false;
if(a <= j and g[i][a] == 'H') valid = false;
if(a >= j and g[n-1][a] == 'H') valid = false;
}
ret += valid;
}
}
}
cout << ret << endl;
}
intmain() {
int t;
cin >> t;
while(t--) solve();
}
本期 USACO 2022赛季12月月赛铜升银晋级题解就到这里了，我们下周银升金晋题解见，敬请期待！
总体而言今年参加USACO 的人数在进一步提升，具体的对比数据如下：
可以看到，参加的总人数比去年多了3千人，今年的参赛选手来自全世界90个国家，相比于去年同一时间多了10个国家，说明USACO竞赛也正在得到更多国家学生的认可。对于想要学习编程的学生来说，USACO信息学的目标和学习路径都是被证明的、非常权威的体系，建议想让孩子接触编程的家长，可以考虑下USACO竞赛这套体系！
【竞赛报名/项目咨询请加微信：mollywei007】
