USACO美國信息學奧賽，是申請全球計算機專(zhuan) 業(ye) 強校的申請利器，在CS專(zhuan) 業(ye) 眾(zhong) 多錄取學生的背景履曆中都少不了它的身影。每年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⋅105) 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≤109).
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公開賽銅牌考試還是以暴力搜索和模擬為(wei) 主，尤其是第二題，需要仔細審題，該題也比較有意思，結合了語言中的語法知識，很多學生很容易在這裏犯懵。如果不仔細理解題意，很有可能連題都看不懂。
本次考試1，2題都有考察到字符串的知識點，如果對與(yu) 字符串知識點不了解的學生就要多加小心了。
通常USACO OPEN的考試難度比一般月賽要難一些，並且考試時長為(wei) 五小時（月賽為(wei) 4小時），對學生來說是一大考驗。
USACO美國公開賽（銅牌考題解析）
考題1：
# P1
考慮每一段"XFF...FFY"可以產(chan) 生多少貢獻，
結論是如果X=Y,能產(chan) 生0,2,4,6,...的貢獻，
否則能產(chan) 生1,3,5,7,...的貢獻，
對於(yu) 下麵的情況 整體(ti) 減一可以得到和上麵一樣的結論。
再考慮邊緣,FF...FFY可以產(chan) 生多少貢獻？
發現能產(chan) 生0,1,2,...的貢獻，
於(yu) 是我們(men) 可以分別統計這兩(liang) 種，加上初始答案即可。
考察知識點: 分類討論
考題2：
# P2
（分類討論題）
首先我們(men) 可以去考慮conjunction的數量，這個(ge) 不能超過.的數量；
其次考慮單詞的數量，這個(ge) 不能超過conjunction的數量+.的數量；
然後我們(men) 可以通過枚舉(ju) transitive-verb的數量和intransitive-verb的數量來確定單詞的最多個(ge) 數；
最後我們(men) 依次將單詞拚接在一起即可。
考察知識點: 模擬
考題3：
# P3
考慮一個(ge) 位置上的值p假如從(cong) a[i]變成a[i+1],那麽(me) 下一次對他進行變化一定是由當前a[i]移動過去造成的，
所以每個(ge) 點的運動都具有周期性，每經過t秒，就會(hui) 往後移動t的距離。
其中t=a[i+1]-a[i],特殊的,我們(men) 令a[k+1]=a[1]+n
考察知識點 :周期性的發現
《USACO公開賽銅牌考題》答案
銅牌第一題：
#include <iosestream>
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 <iosestream>
#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 <iosestream>
#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年曆史，是世界範圍內(nei) 極具認可的計算機賽事。
其官網為(wei) 美國有名的在線題庫，更是美國中學生的官方賽事網站。專(zhuan) 門為(wei) 信息學競賽選手準備，但必須在注冊(ce) 後才能進入題庫。
#01、USACO比賽說明：
USACO是美國含金量極高的一個(ge) 信息學奧賽，分為(wei) 銅、銀、金、鉑金級別，需要學生從(cong) 銅級開始比賽，層層晉級。USACO比賽的難度也是隨著級別依次遞增，學生需要在規定的時間內(nei) 完成3道題目。
USACO每個(ge) 賽季線上比賽共4輪，分別為(wei) 12月、1月、2月月賽及3月公開賽。每個(ge) 人都可以參加，不限國籍。訓練營一般是在線下舉(ju) 行，隻有在USACO比賽中晉級鉑金且是美國籍學生才可以參加。
USACO每一輪比賽，參賽者可以選擇比賽時間期內(nei) （周五到周一任意時間窗口）參賽，通常3場月賽的比賽長達4小時，美國公開賽的比賽長達5小時。USACO美國公開賽各級別比賽難度是高於(yu) 月賽各級別比賽難度的。
#02、USACO晉級規則
學生參加USACO計算機奧賽提交代碼（提交次數無限製）後，係統會(hui) 自動給出評分，每個(ge) 編程問題的分值都是333.333分，總分是1000分。如果拿到滿分，係統會(hui) 提示直接晉級，則可在本次月賽中繼續挑戰更高難度的試題。一般新注冊(ce) 的學生自動歸類為(wei) 銅牌比賽，
學生若在月賽中能拿到接近滿分的分數則可以一直晉級到鉑金，也可以在後續的月賽/公開賽中挑戰更高級別的比賽。相對而言參加USACO比賽拿到更高級別獎項的機會(hui) 還是比較多的。
一般月賽考試結束後，會(hui) 劃出晉級分數線。如果成功晉級，可在下個(ge) 月的比賽中參加更高級別的競賽。一般來說，高於(yu) 750分或800分的分數通常可以獲得晉級。
【競賽報名/項目谘詢+微信：mollywei007】
評論已經被關(guan) 閉。