上海USACO培訓丨2023年USACO公開賽各組別真題免費領??！

2023年USACO競賽公開賽已經(jīng)結束。這次USACO競賽的難度有多大？犀牛教育計算機競賽教研組的石老師分析了2023年USACO競賽銅組的試題，供大家參考。需要其他組別試題，請找在線客服領取

考題1：

考慮每一段"XFF...FFY"可以產(chǎn)生多少貢獻，

結論是如果X=Y,能產(chǎn)生0,2,4,6,...的貢獻，

否則能產(chǎn)生1,3,5,7,...的貢獻，

對于下面的情況 整體減一可以得到和上面一樣的結論。

再考慮邊緣,FF...FFY可以產(chǎn)生多少貢獻?

發(fā)現(xiàn)能產(chǎn)生0,1,2,...的貢獻，

于是我們可以分別統(tǒng)計這兩種，加上初始答案即可。

考察知識點: 分類討論

考題2：

(分類討論題)

首先我們可以去考慮conjunction的數(shù)量，這個不能超過.的數(shù)量;

其次考慮單詞的數(shù)量，這個不能超過conjunction的數(shù)量+.的數(shù)量;

然后我們可以通過枚舉transitive-verb的數(shù)量和intransitive-verb的數(shù)量來確定單詞的最多個數(shù);

最后我們依次將單詞拼接在一起即可。

考察知識點: 模擬

考題3：

考慮一個位置上的值p假如從a[i]變成a[i+1],那么下一次對他進行變化一定是由當前a[i]移動過去造成的，

所以每個點的運動都具有周期性，每經(jīng)過t秒，就會往后移動t的距離。

其中t=a[i+1]-a[i],特殊的,我們令a[k+1]=a[1]+n

考察知識點 :周期性的發(fā)現(xiàn)

銅牌第一題：

#include

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<

rep(i,0,n-1)

if (t[i]) cout<

return 0;

}

銅牌第二題：

#include

#include

#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 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 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 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<

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

W+=Q[i]+". ";

for (int i=0;i+1

cout<

cout<

}

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;

}