犀牛國(guó)際教育旗下指定官方網(wǎng)站~

課程咨詢熱線 400-656-1680

全網(wǎng)獨(dú)家!2023 USACO(全國(guó)賽)考題&答案解析發(fā)布,速領(lǐng)~

發(fā)布時(shí)間:2023-03-30 10:05:50

編輯:lisa來(lái)源:未知瀏覽:

  USACO美國(guó)信息學(xué)奧賽,是申請(qǐng)全球計(jì)算機(jī)專業(yè)強(qiáng)校的申請(qǐng)利器,在CS專業(yè)眾多錄取學(xué)生的背景履歷中都少不了它的身影。每年12月/1月/2月共3場(chǎng)月賽,3月/4月有一場(chǎng)美國(guó)公開(kāi)賽!

  

  2023年USACO美國(guó)公開(kāi)賽,昨日剛比賽結(jié)束!

  USACO美國(guó)計(jì)算機(jī)奧賽考題難度如何呢?現(xiàn)在公布考題&答案&解析,各位同學(xué)速來(lái)領(lǐng)取!

  USACO美國(guó)公開(kāi)賽銅牌3大考題

P1 FEB

P2 MOO LANGUAGE

P3 ROTATE AND SHIFT


 

  USACO OPEN,今年考情如何?

  犀牛USACO競(jìng)賽輔導(dǎo)石老師認(rèn)為:

  本次USACO公開(kāi)賽銅牌考試還是以暴力搜索和模擬為主,尤其是第二題,需要仔細(xì)審題,該題也比較有意思,結(jié)合了語(yǔ)言中的語(yǔ)法知識(shí),很多學(xué)生很容易在這里犯懵。如果不仔細(xì)理解題意,很有可能連題都看不懂。

  本次考試1,2題都有考察到字符串的知識(shí)點(diǎn),如果對(duì)與字符串知識(shí)點(diǎn)不了解的學(xué)生就要多加小心了。

  通常USACO OPEN的考試難度比一般月賽要難一些,并且考試時(shí)長(zhǎng)為五小時(shí)(月賽為4小時(shí)),對(duì)學(xué)生來(lái)說(shuō)是一大考驗(yàn)。

  USACO美國(guó)公開(kāi)賽(銅牌考題解析)

  考題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),

  對(duì)于下面的情況 整體減一可以得到和上面一樣的結(jié)論。

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

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

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

  考察知識(shí)點(diǎn): 分類討論

  考題2:

  # P2

  (分類討論題)

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

  其次考慮單詞的數(shù)量,這個(gè)不能超過(guò)conjunction的數(shù)量+.的數(shù)量;

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

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

  考察知識(shí)點(diǎn): 模擬

  考題3:

  # P3

  考慮一個(gè)位置上的值p假如從a[i]變成a[i+1],那么下一次對(duì)他進(jìn)行變化一定是由當(dāng)前a[i]移動(dòng)過(guò)去造成的,

  所以每個(gè)點(diǎn)的運(yùn)動(dòng)都具有周期性,每經(jīng)過(guò)t秒,就會(huì)往后移動(dòng)t的距離。

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

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

  《USACO公開(kāi)賽銅牌考題》答案

銅牌第一題:
#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美國(guó)公開(kāi)賽

  各級(jí)別競(jìng)賽考題及解析,在線咨詢即可領(lǐng)取


 

USACO比賽結(jié)束,犀牛重磅講座來(lái)襲

ChatGPT4.0降臨,學(xué)CS刻不容緩
更多計(jì)算機(jī)賽事準(zhǔn)備和問(wèn)題探討
在線預(yù)約4月7日韓婷老師的精彩分享

相關(guān)標(biāo)簽:
TOP