課程咨詢熱線 400-656-1680
發(fā)布時(shí)間：2023-03-30 10:05:50
編輯：lisa來源：未知瀏覽：次
USACO美國信息學(xué)奧賽，是申請全球計(jì)算機(jī)專業(yè)強(qiáng)校的申請利器，在CS專業(yè)眾多錄取學(xué)生的背景履歷中都少不了它的身影。每年12月/1月/2月共3場月賽，3月/4月有一場美國公開賽!
2023年USACO美國公開賽，昨日剛比賽結(jié)束!
USACO美國計(jì)算機(jī)奧賽考題難度如何呢?現(xiàn)在公布考題&答案&解析，各位同學(xué)速來領(lǐng)取!
USACO美國公開賽銅牌3大考題
P1 FEB
P2 MOO LANGUAGE
P3 ROTATE AND SHIFT
USACO OPEN，今年考情如何?
犀牛USACO競賽輔導(dǎo)石老師認(rèn)為：
本次USACO公開賽銅牌考試還是以暴力搜索和模擬為主，尤其是第二題，需要仔細(xì)審題，該題也比較有意思，結(jié)合了語言中的語法知識，很多學(xué)生很容易在這里犯懵。如果不仔細(xì)理解題意，很有可能連題都看不懂。
本次考試1，2題都有考察到字符串的知識點(diǎn)，如果對與字符串知識點(diǎn)不了解的學(xué)生就要多加小心了。
通常USACO OPEN的考試難度比一般月賽要難一些，并且考試時(shí)長為五小時(shí)(月賽為4小時(shí))，對學(xué)生來說是一大考驗(yàn)。
USACO美國公開賽(銅牌考題解析)
考題1：
# P1
考慮每一段"XFF...FFY"可以產(chǎn)生多少貢獻(xiàn)，
結(jié)論是如果X=Y,能產(chǎn)生0,2,4,6,...的貢獻(xiàn)，
否則能產(chǎn)生1,3,5,7,...的貢獻(xiàn)，
對于下面的情況 整體減一可以得到和上面一樣的結(jié)論。
再考慮邊緣,FF...FFY可以產(chǎn)生多少貢獻(xiàn)?
發(fā)現(xiàn)能產(chǎn)生0,1,2,...的貢獻(xiàn)，
于是我們可以分別統(tǒng)計(jì)這兩種，加上初始答案即可。
考察知識點(diǎn): 分類討論
考題2：
# P2
(分類討論題)
首先我們可以去考慮conjunction的數(shù)量，這個(gè)不能超過.的數(shù)量;
其次考慮單詞的數(shù)量，這個(gè)不能超過conjunction的數(shù)量+.的數(shù)量;
然后我們可以通過枚舉transitive-verb的數(shù)量和intransitive-verb的數(shù)量來確定單詞的最多個(gè)數(shù);
最后我們依次將單詞拼接在一起即可。
考察知識點(diǎn): 模擬
考題3：
# P3
考慮一個(gè)位置上的值p假如從a[i]變成a[i+1],那么下一次對他進(jìn)行變化一定是由當(dāng)前a[i]移動過去造成的，
所以每個(gè)點(diǎn)的運(yùn)動都具有周期性，每經(jīng)過t秒，就會往后移動t的距離。
其中t=a[i+1]-a[i],特殊的,我們令a[k+1]=a[1]+n
考察知識點(diǎn) :周期性的發(fā)現(xià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;
}
重磅福利限時(shí)領(lǐng)取
2023年USACO美國公開賽
各級別競賽考題及解析，在線咨詢即可領(lǐng)取
USACO比賽結(jié)束，犀牛重磅講座來襲
ChatGPT4.0降臨，學(xué)CS刻不容緩
更多計(jì)算機(jī)賽事準(zhǔn)備和問題探討
在線預(yù)約4月7日韓婷老師的精彩分享
