USACO美国信息学奥赛，是申请全球计算机专业强校的申请利器，在CS专业众多录取学生的背景履历中都少不了它的身影。每年12月/1月/2月共3场月赛，3月/4月有一场美国公开赛！
2023年USACO美国公开赛，昨日刚比赛结束！
USACO美国计算机奥赛考题难度如何呢？现在公布考题&答案&解析，各位同学速来码住！
USACO美国公开赛铜牌3大考题
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 SOUTPUT 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.
P2 MOO LANGUAGE
Farmer John is interested in better interacting with his fellow cows, so he decided he will learn the moo language!
Moo language is actually quite similar to English, but more minimalistic. There are only four types of words: nouns, transitive verbs, intransitive verbs, and conjunctions. Every two consecutive words must be separated by a space. There are also only two types of punctuation: periods and commas. When a period or comma appears after a word, it appears directly after the word, and is then followed by a space if another word appears next.
A sentence needs to follow one of the following formats:
•Type 1: noun + intransitive verb.
•Type 2: noun + transitive verb + noun(s). Specifically, at least one noun must follow the transitive verb, and there must be a comma in front of every following noun besides the first following noun.
Two sentences may be joined into a compound sentence if a conjunction is placed in between them. The resulting compound sentence cannot be further joined with other sentences or other compound sentences. Every sentence (or compound sentence, if two sentences are joined) must end with a period.
Farmer John has a word bank of N words, C commas, and P periods (
1≤ P,C ≤N≤10 ** 3). He may only use a word or punctuation mark as many times as it appears in the word bank. Help him output a sequence of sentences containing the maximum possible number of words.
Each input file contains T (1≤T≤100) independent instances of this problem.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T, the number of instances. Each instance is specified as follows:
The first line consists of three integers, N, C, and P.
The N following lines will consist of two strings. The first string will be the word itself that FJ can use (a string of at least 1 and at most 10 lowercase letters), and the second string will be either one of the following: noun, transitive-verb, intransitive-verb, or conjunction, denoting the type of the word. It is possible the same word occurs more than once in FJ's word bank, but it will always have the same type each time it appears.
OUTPUT FORMAT (print output to the terminal / stdout):
In the first line, output the maximum possible number of words.
In the second line, output any sequence of sentences with the maximum possible number of words. Any valid sequence will be accepted.
The grader is sensitive to whitespace, so make sure not to output any extraneous spaces, particularly at the end of each line.
SAMPLE INPUT:
3
1 1 1
bessie noun
10 5 4
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
24 5 4
but conjunction
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
bob noun
impressed transitive-verb
cow noun
impressed transitive-verb
leaped intransitive-verb
elsie noun
bella noun
buttercup noun
pushed transitive-verb
mooed intransitive-verb
envy noun
john noun
nhoj noun
SAMPLE OUTPUT:
0
9
nhoj mooed. farmer taught elsie, bessie and john flew.
23
nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.
For the first test case, the only valid sequence is the empty sequence. For each of the next two test cases, it is possible to construct a sequence of sentences using every word from the word bank except for one.
SCORING:
•Inputs 2-6: N≤10
•Inputs 7-11: N≤100
•Inputs 12-16: N≤1000
•Inputs with remainder 2 when divided by 5: There are no transitive verbs.
•Inputs with remainder 3 when divided by 5: There are no intransitive verbs.
•Inputs with remainder 4 when divided by 5: There are no conjunctions.
P3 ROTATE AND SHIFT
**Note: The time limit for this problem is 4s, 2x the default.**
To celebrate the start of spring, Farmer John's N cows (1≤N≤2⋅10**5) have invented an intriguing new dance, where they stand in a circle and re-order themselves in a predictable way.
Specifically, there are N positions around the circle, numbered sequentially from 0 to N - 1, with position 0 following position N - 1. A cow resides at each position. The cows are also numbered sequentially from 0 to N - 1.
Initially, cow i starts in position i. You are told a set of K positions 0 = A1 < A2 < … < Ak < N that are "active", meaning the cows in these positions are the next to move (1 <= K <= N).
In each minute of the dance, two things happen. First, the cows in the active positions rotate: the cow at position A1 moves to position A2, the cow at position A2 moves to position A3, and so on, with the cow at position Ak moving to position A1. All of All of these K moves happen simultaneously, so the after the rotation is complete, all of the active positions still contain exactly one cow. Next, the active positions themselves shift: A1 becomes A1 + 1, A2 becomes A2 + 1, and so on(if Ai = N -1 for some active position, then Ai circles back around to 0).
Please calculate the order of the cows after T minutes of the dance (1≤T≤10**9).
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains three integers N, K, and T.
The second line contains K integers representing the initial set of active positions A1,A2,…Ak. Recall that A1 = 0 and that these are given in increasing order.OUTPUT FORMAT (print output to the terminal / stdout):
Output the order of the cows after T minutes, starting with the cow in position 0, separated by spaces.
SAMPLE INPUT:
5 3 4
0 2 3
SAMPLE OUTPUT:
1 2 3 4 0
For the example above, here are the cow orders and A for the first four timesteps:
Initial, T = 0: order = [0 1 2 3 4], A = [0 2 3]
T = 1: order = [3 1 0 2 4]
T = 1: A = [1 3 4]
T = 2: order = [3 4 0 1 2]
T = 2: A = [2 4 0]
T = 3: order = [2 4 3 1 0]
T = 3: A = [3 0 1]
T = 4: order = [1 2 3 4 0]
SCORING:
•Inputs 2-7: N≤1000,T≤10000
•Inputs 8-13: No additional constraints.
USACO OPEN，今年考情如何？
本次USACO公开赛铜牌考试还是以暴力搜索和模拟为主，尤其是第二题，需要仔细审题，该题也比较有意思，结合了语言中的语法知识，很多学生很容易在这里犯懵。如果不仔细理解题意，很有可能连题都看不懂。
本次考试1，2题都有考察到字符串的知识点，如果对与字符串知识点不了解的学生就要多加小心了。
通常USACO OPEN的考试难度比一般月赛要难一些，并且考试时长为五小时（月赛为4小时），对学生来说是一大考验。
USACO美国公开赛（铜牌考题解析）
考题1：
# P1
考虑每一段"XFF...FFY"可以产生多少贡献，
结论是如果X=Y,能产生0,2,4,6,...的贡献，
否则能产生1,3,5,7,...的贡献，
对于下面的情况 整体减一可以得到和上面一样的结论。
再考虑边缘,FF...FFY可以产生多少贡献？
发现能产生0,1,2,...的贡献，
于是我们可以分别统计这两种，加上初始答案即可。
考察知识点: 分类讨论
考题2：
# P2
（分类讨论题）
首先我们可以去考虑conjunction的数量，这个不能超过.的数量；
其次考虑单词的数量，这个不能超过conjunction的数量+.的数量；
然后我们可以通过枚举transitive-verb的数量和intransitive-verb的数量来确定单词的最多个数；
最后我们依次将单词拼接在一起即可。
考察知识点: 模拟
考题3：
# P3
考虑一个位置上的值p假如从a[i]变成a[i+1],那么下一次对他进行变化一定是由当前a[i]移动过去造成的，
所以每个点的运动都具有周期性，每经过t秒，就会往后移动t的距离。
其中t=a[i+1]-a[i],特殊的,我们令a[k+1]=a[1]+n
考察知识点 :周期性的发现
《USACO公开赛铜牌考题》答案
铜牌第一题：
#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;
}
铜牌第二题：
#include <iostream>
#include <vector>
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
using namespace std;
struct nd{
int a,b,c,d;
bool operator <(const nd x)const{
return d>x.d;
}
};
int main()
{
int T;
cin>>T;
while (T--)
{
int n,c,p;
cin>>n>>c>>p;
string A,B;
vector<string> Q1,Q2,Q3,Q4;
{
cin>>A>>B;
if (B=="noun") Q1.push_back(A);
if (B=="intransitive-verb") Q2.push_back(A);
if (B=="transitive-verb") Q3.push_back(A);
if (B=="conjunction") Q4.push_back(A);
}
int maxand=min((int)(Q4.size()),p);
int maxword=maxand+p;
vector<nd> ans;
rep(s1,0,Q3.size())
{
int s2=min((int)(Q2.size()),maxword-s1);
s2=min(s2,(int)(Q1.size())-2*s1);
int s3=min(c,(int)(Q1.size())-2*s1-s2);
if (!s1) while (s3>0) s3--;
if (s1<0||s2<0||s3<0) continue;
ans.push_back({s1,s2,s3,3*s1+2*s2+s3});
}
sort(ans.begin(),ans.end());
int s1=0,s2=0,s3=0,O=0;
if (ans.size())
{
s1=ans[0].a,s2=ans[0].b,s3=ans[0].c,O=ans[0].d;
}
vector<string> Q;
rep(i,1,s2)
{
Q.push_back(Q1.back()+" "+Q2.back());
Q1.pop_back(); Q2.pop_back();
}
rep(i,1,s1)
{
string s=Q1.back()+" "+Q3.back();
Q1.pop_back(); Q3.pop_back();
s+=" "+Q1.back();
Q1.pop_back();
if (i==1)
{
while (s3--)
{
s+=", "+Q1.back();
Q1.pop_back();
}
}
Q.push_back(s);
}
int round=min((int)(Q4.size()),(int)(Q.size())/2);
cout<<O+round<<endl;
string W;
rep(i,0,round-1)
{
W+=Q[i*2]+" "+Q4.back()+" "+Q[i*2+1]+". ";
Q4.pop_back();
}
for (int i=round*2;i<Q.size();i++)
W+=Q[i]+". ";
for (int i=0;i+1<W.length();i++)
cout<<W[i];
cout<<endl;
}
return 0;
}
铜牌第三题：
#include <iostream>
#include <vector>
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,k,t;
int main()
{
cin>>n>>k>>t;
vector<int> a(n+10),L(n+10),R(n+10),p(n+10);
vector<bool> h(n+10);
rep(i,1,k) cin>>a[i];
a[k+1]=a[1]+n;
rep(i,1,k) h[a[i]]=1;
rep(i,0,n-1)
if (h[i]) L[i]=i; else L[i]=L[i-1];
rep(i,1,k) R[a[i]]=a[i+1]-a[i];
rep(i,0,n-1)
{
int tim=t-i+L[i];
int round=tim/R[L[i]];
if (tim%R[L[i]]!=0) round++;
p[(i+round*R[L[i]])%n]=i;
}
rep(i,0,n-2) cout<<p[i]<<" ";
cout<<p[n-1];
return 0;
}
美国计算机奥赛USACO全解
USACO（United States of America Computing Olympiad, 美国计算机奥林匹克竞赛) 是一项针对全世界所有的高中信息学竞赛选手的一项竞赛，已有29年历史，是世界范围内极具认可的计算机赛事。
其官网为美国有名的在线题库，更是美国中学生的官方赛事网站。专门为信息学竞赛选手准备，但必须在注册后才能进入题库。
#01、USACO比赛说明：
USACO是美国含金量极高的一个信息学奥赛，分为铜、银、金、铂金级别，需要学生从铜级开始比赛，层层晋级。USACO比赛的难度也是随着级别依次递增，学生需要在规定的时间内完成3道题目。
USACO每个赛季线上比赛共4轮，分别为12月、1月、2月月赛及3月公开赛。每个人都可以参加，不限国籍。训练营一般是在线下举行，只有在USACO比赛中晋级铂金且是美国籍学生才可以参加。
USACO每一轮比赛，参赛者可以选择比赛时间期内（周五到周一任意时间窗口）参赛，通常3场月赛的比赛长达4小时，美国公开赛的比赛长达5小时。USACO美国公开赛各级别比赛难度是高于月赛各级别比赛难度的。
#02、USACO晋级规则
学生参加USACO计算机奥赛提交代码（提交次数无限制）后，系统会自动给出评分，每个编程问题的分值都是333.333分，总分是1000分。如果拿到满分，系统会提示直接晋级，则可在本次月赛中继续挑战更高难度的试题。一般新注册的学生自动归类为铜牌比赛，
学生若在月赛中能拿到接近满分的分数则可以一直晋级到铂金，也可以在后续的月赛/公开赛中挑战更高级别的比赛。相对而言参加USACO比赛拿到更高级别奖项的机会还是比较多的。
一般月赛考试结束后，会划出晋级分数线。如果成功晋级，可在下个月的比赛中参加更高级别的竞赛。一般来说，高于750分或800分的分数通常可以获得晋级。
【竞赛报名/项目咨询请加微信：mollywei007】
