2023年USACO公开赛题目全解析！不同年级学生如何备考USACO竞赛？ |
| 时间：2023-04-26 17:02:50 作者：犀牛教育 来源：犀牛教育 |
想要挑战计算机的相关竞赛，对计算机感兴趣的，参加USACO竞赛是非常有必要的。2023年USACO竞赛3月公开赛已结束，首先先恭喜犀牛32位学子在本次公开赛中取得优异的成绩，成功晋级！接下来犀牛老师给大家介绍下2023年USACO竞赛公开赛真题解析，USACO晋级规则是什么？USACO想要拿奖，还是不建议自学，那么上海北京USACO培训课程哪里好？希望对大家有帮助 ！
2023年3月24-27日 USACO US.OPEN美国公开赛顺利结束。大家感觉怎么样呢？
本次US.OPEN美国公开赛难度是月赛的1.5倍，题目难度较大。同时，近三年公开赛的难度是逐年递增的。
犀牛计算机教研组创作了500+的模拟真题以及培训课程，助力学生冲击USACO金银成绩！想了解的加老师微信18710542862咨询~
本次考试还是以暴力搜索和模拟为主，尤其是第二题，需要仔细审题，如果不理解题意会很难下手。与我们考前预测是一致的USACO 3月公开赛独家考情预测！
铜组第1、2题都考察了字符串的知识点，如果对字符串知识点不了解的学生就要多加小心了。
第3题是一道逻辑题目，有点类似2020年2月铜组P3 swapity swap。
USACO教研组老师为大家解析了本次公开赛铜组的题目。我们一起来看看~
P1题目：
P1 FEB:
Bessie and Elsie are plotting to overthrow Farmer John at last! They plan it out over (1 <= N <= 2 * 10 ** 5) text messages. Their conversation can be represented by a string S of length N where Is is either B or E, meaning the ith message was sent by Bessie or Elsie, respectively.
However, Farmer John hears of the plan and attempts to intercept their conversation. Thus, some letters of S are F, meaning Farmer John obfuscated the message and the sender is unknown.
The excitement level of a non-obfuscated conversation is the number of times a cow double-sends - that is, the number of occurrences of substring BB or EE in S. You want to find the excitement level of the original message, but you don’t know which of Farmer John’s messages were actually Bessie’s / Elsie’s. Over all possibilities, output all possible excitement levels of S.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line will consist of one integer N.
The next line contains S
OUTPUT FORMAT (print output to the terminal / stdout):
First output K, the number of distinct excitement levels possible. On the next K lines, output the excitement levels, in increasing order.
SAMPLE INPUT:
4
BEEF
SAMPLE OUTPUT:
2
1
2
SAMPLE INPUT:
9
FEBFEBFEB
SAMPLE OUTPUT:
2
2
3
SAMPLE INPUT:
10
BFFFFFEBFE
SAMPLE OUTPUT:
3
2
4
6
SCORING:
• Inputs 4-8: N ≤ 10
• Inputs 9-20: No additional constraints.
USACO竞赛的第一道题目需要分析出题目的性质，分为F左右都有元素和F只有一边有元素进行讨论,问题转化之后就比较简单了。
考虑每一段"XFF...FFY"可以产生多少贡献
结论是如果X=Y,能产生0,2,4,6,...的贡献
否则能产生1,3,5,7,...的贡献
对于下面的情况,整体减一可以得到和上面一样的结论
再考虑边缘,FF...FFY可以产生多少贡献
发现能产生0,1,2,...的贡献
于是我们可以分别统计这两种，加上初始答案即可
代码如下：
#include <iostream>
#define rep(i,h,t) for (int i=h;i<=t;i++)#define dep(i,t,h) for (int i=t;i>=h;i--)int n;char s[200010];bool t[200010];int main(){ scanf("%d",&n); scanf("%s",s+1); int O=0; rep(i,1,n) if (s[i]==s[i-1]&&s[i]!='F') O++; int Q1=0,Q2=0; rep(i,1,n) { if (s[i]=='F') { int j=i; while (s[j]=='F'&&j<=n) j++; j--; int num=j-i+1; if (i!=1&&j!=n) { if (s[i-1]==s[j+1]) num++; O+=num%2; Q1+=num/2; } else Q2+=num; i=j; } } rep(i,0,Q1) rep(j,0,Q2) t[i*2+j+O]=1; int OO=0; rep(i,0,n-1) if (t[i]) OO++; cout<<OO<<endl; rep(i,0,n-1) if (t[i]) cout<<i<<endl; return 0;}
using namespace std;
算法的灵活应用能力，一定是通过在解决实际问题的过程中不断训练，同时刷历年真题来进一步提升算法的应用能力，这个训练是非常有必要的。
只有通过刷题才能清楚自己所学的算法是否真的理解了，通过算法的应用，不断查漏补缺，把这些算法真正掌握。
扫码添加微信小助手
在线回复“USACO真题”领
TEL：13012833750（同微）
针对不同的同学，想要参加USACO竞赛，该如何准备，我们针对不同的基础，给出参赛建议：
 1.对于没有编程基础的学生如何备赛？
建议从python或者java入手，上手较快。学习主要内容为数据结构，编程语法，配合一定强度的练习，可以初步通过第一轮铜级的选拔。
2.对于有部分编程基础的学生如何备赛？
比如在读AP计算机的高一高二同学可以从C++或者C入手。作为编程语言中强大且基础的两门，无论是应付比赛还是在以后读本科或者工作中使用，提前学习C++和C都是不错的选择。
3.对于有编程基础及编程经验的学生如何备赛？
比如参加过国内NOI的同学，设定的目标可以直接冲击至少金级别以上的奖项。
在有数据结构和编程语法的前提下，需要系统的学习一些常见算法，比如排序等等。同时大量练习官方的金，白金级别的真题。
犀牛教育(X-NEW)，由业内多名教学专家共同组建，90%以上名师来自全球TOP前50的世界名校，教学团队整体教学经验均2000小时以上！
USACO竞赛培训辅导课程
添加小助手在线咨询
2023年3月24-27日 USACO US.OPEN美国公开赛顺利结束。大家感觉怎么样呢？
本次US.OPEN美国公开赛难度是月赛的1.5倍，题目难度较大。同时，近三年公开赛的难度是逐年递增的。
犀牛计算机教研组创作了500+的模拟真题以及培训课程，助力学生冲击USACO金银成绩！想了解的加老师微信18710542862咨询~
本次考试还是以暴力搜索和模拟为主，尤其是第二题，需要仔细审题，如果不理解题意会很难下手。与我们考前预测是一致的USACO 3月公开赛独家考情预测！
铜组第1、2题都考察了字符串的知识点，如果对字符串知识点不了解的学生就要多加小心了。
第3题是一道逻辑题目，有点类似2020年2月铜组P3 swapity swap。
USACO教研组老师为大家解析了本次公开赛铜组的题目。我们一起来看看~
P1题目：
P1 FEB:
Bessie and Elsie are plotting to overthrow Farmer John at last! They plan it out over (1 <= N <= 2 * 10 ** 5) text messages. Their conversation can be represented by a string S of length N where Is is either B or E, meaning the ith message was sent by Bessie or Elsie, respectively.
However, Farmer John hears of the plan and attempts to intercept their conversation. Thus, some letters of S are F, meaning Farmer John obfuscated the message and the sender is unknown.
The excitement level of a non-obfuscated conversation is the number of times a cow double-sends - that is, the number of occurrences of substring BB or EE in S. You want to find the excitement level of the original message, but you don’t know which of Farmer John’s messages were actually Bessie’s / Elsie’s. Over all possibilities, output all possible excitement levels of S.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line will consist of one integer N.
The next line contains S
OUTPUT FORMAT (print output to the terminal / stdout):
First output K, the number of distinct excitement levels possible. On the next K lines, output the excitement levels, in increasing order.
SAMPLE INPUT:
4
BEEF
SAMPLE OUTPUT:
2
1
2
SAMPLE INPUT:
9
FEBFEBFEB
SAMPLE OUTPUT:
2
2
3
SAMPLE INPUT:
10
BFFFFFEBFE
SAMPLE OUTPUT:
3
2
4
6
SCORING:
• Inputs 4-8: N ≤ 10
• Inputs 9-20: No additional constraints.
USACO的第一道题目需要分析出题目的性质，分为F左右都有元素和F只有一边有元素进行讨论,问题转化之后就比较简单了。
考虑每一段"XFF...FFY"可以产生多少贡献
结论是如果X=Y,能产生0,2,4,6,...的贡献
否则能产生1,3,5,7,...的贡献
对于下面的情况,整体减一可以得到和上面一样的结论
再考虑边缘,FF...FFY可以产生多少贡献
发现能产生0,1,2,...的贡献
于是我们可以分别统计这两种，加上初始答案即可
代码如下：
#include <iostream>
using namespace std;#define rep(i,h,t) for (int i=h;i<=t;i++)#define dep(i,t,h) for (int i=t;i>=h;i--)int n;char s[200010];bool t[200010];int main(){ scanf("%d",&n); scanf("%s",s+1); int O=0; rep(i,1,n) if (s[i]==s[i-1]&&s[i]!='F') O++; int Q1=0,Q2=0; rep(i,1,n) { if (s[i]=='F') { int j=i; while (s[j]=='F'&&j<=n) j++; j--; int num=j-i+1; if (i!=1&&j!=n) { if (s[i-1]==s[j+1]) num++; O+=num%2; Q1+=num/2; } else Q2+=num; i=j; } } rep(i,0,Q1) rep(j,0,Q2) t[i*2+j+O]=1; int OO=0; rep(i,0,n-1) if (t[i]) OO++; cout<<OO<<endl; rep(i,0,n-1) if (t[i]) cout<<i<<endl; return 0;}
算法的灵活应用能力，一定是通过在解决实际问题的过程中不断训练，同时刷历年真题来进一步提升算法的应用能力，这个训练是非常有必要的。
只有通过刷题才能清楚自己所学的算法是否真的理解了，通过算法的应用，不断查漏补缺，把这些算法真正掌握。
针对不同的同学，想要参加USACO竞赛，该如何准备，我们针对不同的基础，给出参赛建议：
1.对于没有编程基础的学生如何备赛？
建议从python或者java入手，上手较快。学习主要内容为数据结构，编程语法，配合一定强度的练习，可以初步通过第一轮铜级的选拔。
2.对于有部分编程基础的学生如何备赛？
比如在读AP计算机的高一高二同学可以从C++或者C入手。作为编程语言中强大且基础的两门，无论是应付比赛还是在以后读本科或者工作中使用，提前学习C++和C都是不错的选择。
3.对于有编程基础及编程经验的学生如何备赛？
比如参加过国内NOI的同学，设定的目标可以直接冲击至少金级别以上的奖项。
在有数据结构和编程语法的前提下，需要系统的学习一些常见算法，比如排序等等。同时大量练习官方的金，白金级别的真题。
犀牛教育(X-NEW)，由业内多名教学专家共同组建，90%以上名师来自全球TOP前50的世界名校，教学团队整体教学经验均2000小时以上！
USACO竞赛培训辅导课程
添加小助手在线咨询
TEL：13012833750（同微）
初级班：计算机编程刚入门，语言基础薄弱，无比赛经验计划申请计算机专业的中学生
中级班：至少会一门计算机编程语言(推荐C++或Java)，算法基础一般，少量比赛经验
高级班：有完善的计算机编程语言基础，有入门算法经验，一定比赛经验，如NOIP，USACO银组等
|
犀牛USACO课程 |
|
课程 |
班型 |
课时 |
|
USACO白金级班 |
4-8人班 |
40h |
|
USACO金级班 |
4-8人班 |
40h |
|
USACO银级班 |
4-8人班 |
40h |
|
USACO铜级班 |
4-8人班 |
40h |
初级班：计算机编程刚入门，语言基础薄弱，无比赛经验计划申请计算机专业的中学生
中级班：至少会一门计算机编程语言(推荐C++或Java)，算法基础一般，少量比赛经验
高级班：有完善的计算机编程语言基础，有入门算法经验，一定比赛经验，如NOIP，USACO银组等
|
犀牛USACO课程 |
|
课程 |
班型 |
课时 |
|
USACO白金级班 |
4-8人班 |
40h |
|
USACO金级班 |
4-8人班 |
40h |
|
USACO银级班 |
4-8人班 |
40h |
|
USACO铜级班 |
4-8人班 |
40h |
|
关键字：USACO竞赛,美国计算机奥林匹克竞赛,USACO竞赛辅导班,
|
