USACO 2022 赛季试题解析系列(12月晋级赛-铜级)

USACO 2022赛季第一次月赛已落下帷幕,本次竞赛中,参加铜组总人数是9974 人,最终顺利升级的学生比率为15%,银组的比赛更为残酷,总共有3676位参赛者,最终顺利升级的学生比率为12%。顺利通过了晋级的学生应该为自己庆祝一下,这个升级比例并不高。

今年铜牌组和银牌组的录取分数相较于去年,都低了100 分,去年是800 分才能顺利升级,今年则是700 分就能升级了。官方就铜组情况描述中特意说明了今年为何降低分数,大概意思是说铜组的通过值之所以设置的低一些,说明这次铜组竞赛不包含任何凑数的简单问题,有些问题甚至包括一些有趣的大挑战,具体的英文描述如下:

【干货】USACO 2022 赛季试题解析系列(12月晋级赛-铜级)为方便同学了解题目思路,USACO教学组准备了《USACO题解》专题,本期进入针对本次铜组竞赛,进行详细的题目解析,为学生提供思路和题解参考,希望能为同学们提供有用的帮助。

【干货】USACO 2022 赛季试题解析系列(12月晋级赛-铜级)

Bronze Problem1

Lonely Photo

(孤独的牛)

 

【干货】USACO 2022 赛季试题解析系列(12月晋级赛-铜级)

思路:我们需要记录长度大于等于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

(牛牛们的空调)

 

【干货】USACO 2022 赛季试题解析系列(12月晋级赛-铜级)

【干货】USACO 2022 赛季试题解析系列(12月晋级赛-铜级)

思路:我们首先定义 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

(一路向家)

 

【干货】USACO 2022 赛季试题解析系列(12月晋级赛-铜级)

【干货】USACO 2022 赛季试题解析系列(12月晋级赛-铜级)

【干货】USACO 2022 赛季试题解析系列(12月晋级赛-铜级)

思路:这个问题中的子任务首先解决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 的人数在进一步提升,具体的对比数据如下:

【干货】USACO 2022 赛季试题解析系列(12月晋级赛-铜级)

可以看到,参加的总人数比去年多了3千人,今年的参赛选手来自全世界90个国家,相比于去年同一时间多了10个国家,说明USACO竞赛也正在得到更多国家学生的认可。对于想要学习编程的学生来说,USACO信息学的目标和学习路径都是被证明的、非常权威的体系,建议想让孩子接触编程的家长,可以考虑下USACO竞赛这套体系!

【竞赛报名/项目咨询+微信:mollywei007】

上一篇

AIME I&II卷如何选考?AIME试卷平均分与晋级分数线分析

下一篇

USACO 2022 赛季试题解析系列(12月晋级赛-银级)

你也可能喜欢

  • 暂无相关文章!

评论已经被关闭。

插入图片
返回顶部