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

課程咨詢熱線 400-656-1680

2023年USACO 3月公開賽銅組真題及解析！附USACO競(jìng)賽輔導(dǎo)

發(fā)布時(shí)間：2023-03-29 18:13:10

編輯：小妹來(lái)源：網(wǎng)絡(luò)瀏覽：次

2023年3月24-27日 USACO US.OPEN美國(guó)公開賽順利結(jié)束。大家感覺(jué)怎么樣？本次US.OPEN美國(guó)公開賽難度是月賽的1.5倍，題目難度較大。同時(shí)，近三年公開賽的難度是逐年遞增的。本次考試還是以暴力搜索和模擬為主，尤其是第二題，需要仔細(xì)審題，如果不理解題意會(huì)很難下手。


銅組第1、2題都考察了字符串的知識(shí)點(diǎn)，如果對(duì)字符串知識(shí)點(diǎn)不了解的學(xué)生就要多加小心了。
第3題是一道邏輯題目，有點(diǎn)類似2020年2月銅組P3 swapity swap。

 

USACO教研組老師為大家解析了本次公開賽銅組的題目。

 

圖片

2023年USACO公開賽銅組P1

數(shù)理邏輯題，需注意問(wèn)題轉(zhuǎn)化

 

P1題目：

圖片
圖片

向下滑動(dòng)查看

 

 

題目解析

 

USACO的第一道題目需要分析出題目的性質(zhì)，分為F左右都有元素和F只有一邊有元素進(jìn)行討論,問(wèn)題轉(zhuǎn)化之后就比較簡(jiǎn)單了。

 

考慮每一段"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ì)這兩種，加上初始答案即可

 

代碼如下：

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
#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;}

 

圖片

2023年USACO公開賽銅組P2

模擬題，需分析問(wèn)題先后性

 

P2題目：

圖片
圖片
圖片
圖片

 

向下滑動(dòng)查看

 

 

題目解析

 

USACO的第二道題目是一個(gè)模擬題，比較考驗(yàn)選手的代碼能力。選手需要有清晰的思路分析問(wèn)題的先后性，明白先確定什么值再確定什么值。

 

分類討論題

 

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

 

其次考慮短句的數(shù)量，這個(gè)不能超過(guò)conjunction的數(shù)量+.的數(shù)量

 

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

 

接著我們依次將相應(yīng)的單詞拼接成短句,顯然多出來(lái)的noun會(huì)添加在"transitive-verb"的后面

 

最后我們將短句拼接成句子，如果有多的"conjunction"符號(hào)就用它連接起來(lái)

 

代碼如下：

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
#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; //¥Ê¥¢4÷÷µ•¥        rep(i,1,n)        {            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;}

 

圖片

2023年USACO公開賽銅組P3

數(shù)理邏輯題，總結(jié)樣例規(guī)律

 

P3題目：

圖片
圖片

向下滑動(dòng)查看

 

 

題目解析

 

USACO的第三道題目也是一個(gè)性質(zhì)題，初看這個(gè)問(wèn)題很難解決，仔細(xì)觀察可以發(fā)現(xiàn)對(duì)于每個(gè)點(diǎn)它的移動(dòng)是具有周期性的，發(fā)現(xiàn)了這個(gè)代碼就比較簡(jiǎn)單了。

 

考慮一個(gè)位置上的值p假如從a[i]位置移動(dòng)到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

 

因此可以計(jì)算每個(gè)點(diǎn)進(jìn)行了幾輪移動(dòng)進(jìn)行模擬

 

代碼如下：

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
#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;}

 

廣子來(lái)了

圖片

 

犀牛計(jì)算機(jī)教研組以USACO組織推薦的官方網(wǎng)站USACO guide上的知識(shí)點(diǎn)為主，對(duì)各組別算法進(jìn)行了整理和更新，并創(chuàng)作了500+的模擬真題，助力學(xué)生沖擊USACO金銀成績(jī)！

 

USACO競(jìng)賽沖沖沖！

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