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

課程咨詢(xún)熱線(xiàn) 400-656-1680

1月USACO計(jì)算機(jī)競(jìng)賽'銀牌'解題分析(完整版可領(lǐng)?。?/h1>

發(fā)布時(shí)間:2024-02-02 09:34:32

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

USACO競(jìng)賽1月月賽真題解析有嗎?USACO競(jìng)賽怎么備考?USACO競(jìng)賽真題解析來(lái)啦,參加了2024年1月的USACO月賽的同學(xué),快來(lái)對(duì)答案!
USACO計(jì)算機(jī)競(jìng)賽的1月月賽悄然落幕!
參賽的同學(xué)們覺(jué)得題目難嗎?給大家整理了此次
銀牌考試試題+題解+代碼,考完的同學(xué)們可以來(lái)參考交流一下。想要領(lǐng)取此次真題全部解析和有備考計(jì)劃的同學(xué),可以在線(xiàn)領(lǐng)取


 

- X-NEW-

USACO 2024年1月銀牌第一題

 

題解分析

q對(duì)(x,y)的輸入,每對(duì)表示前1~x個(gè)數(shù)右邊第一個(gè)比它們大的數(shù)必須在下標(biāo)為y的位置,這句話(huà)還有一個(gè)隱藏含義就是第x+1到第y-1個(gè)數(shù)必須比前1~x個(gè)數(shù)的最大值要小,即第y個(gè)數(shù)比前y-1個(gè)數(shù)都要大(代碼中稱(chēng)為前綴最大值)

用一個(gè)前綴和數(shù)組pre_max[i]表示前i個(gè)數(shù)中的最大值,則a[y]至少為pre_max[y-1]+1

現(xiàn)在從左往右遍歷a[N],分類(lèi)討論每一個(gè)a[i]的情況:

1.a[i]==0且位置i是前綴最大值,令a[i]=pre_max[y-1]+1

2.a[i]==0 且不是前綴最大值,根據(jù)貪心思路令a[i]=1 (字典序最小)

3.a[i]不為0,是第x+1到第y-1個(gè)數(shù)的其中一個(gè),但是比前x個(gè)數(shù)要大,破壞了前綴最大值的要求,此時(shí)需要把之前的某個(gè)能改的值提高為a[i]

對(duì)全部a[N]修改完畢后,再重新for循環(huán)掃描一遍看看新的a[N]有沒(méi)有沖突,有沖突輸出-1

注意事項(xiàng):這題有T個(gè)測(cè)試,每個(gè)輸出最后不能帶空格

 

代碼

//Q x y 的限制等價(jià)于是y是前綴最大值,x+1~y-1內(nèi)的元素不能是前綴最大值
//貪心,對(duì)于不是前綴最大值的填1,是前綴最大值的填前綴max再+1
//注意有時(shí)候需要反悔,由于當(dāng)前值是前綴最大值但是題目要求它不能是,只能把之前的值改大
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N],sum[N],f[N],b[N];
int main(){
    int T;
    cin>>T;
    while (T--){
        int n,m,c;
        cin>>n>>m>>c;
        for (int i=1;i<=n;i++) cin>>a[i];
        for (int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            f[y]=1; //f代表是前綴最大值
            sum[x+1]++; sum[y]--; //前綴和看哪些不是前綴最大值
        }
        for (int i=1;i<=n;i++) sum[i]+=sum[i-1];
        int mx=1;
        int pre=0;
        for (int i=1;i<=n;i++){
            if (a[i]==0){
                if (f[i]) a[i]=mx+1; //前綴max
                else a[i]=1; //不是前綴max
                if (sum[i]==0) pre=i; //記錄能修改的位置
            }
            if (sum[i]>0&&a[i]>mx){
                a[pre]=a[i];
            }
            mx=max(mx,a[i]); //最大值
        }
        bool tt=1;
        for (int i=1;i<=n;i++) { //判斷是否合法
          b[i]=max(b[i-1],a[i]);
          if (a[i]>c) tt=0;
          if (b[i-1]<a[i]&&sum[i]>0) tt=0;
          if (b[i-1]>=a[i]&&f[i]) tt=0;
        }
        if (!tt){
            cout<<-1<<endl;
        } else {
            for (int i=1;i<n;i++) cout<<a[i]<<" ";
            cout<<a[n]<<endl;
        }
        for (int i=1;i<=n+10;i++) sum[i]=0,f[i]=0;
    }
    return 0;
}

 

USACO 2024年1月銀牌第二題

圖片

 

題解分析

以房間1為根節(jié)點(diǎn)的樹(shù)。每次traversal相當(dāng)于從根出發(fā),沿著父子關(guān)系一直走,一個(gè)traversal的終點(diǎn)一定是一個(gè)葉節(jié)點(diǎn),因此最小的traversal數(shù)必定為葉節(jié)點(diǎn)數(shù)量,可以用dfs得到,假設(shè)這個(gè)數(shù)量是k。

可以用樹(shù)上DP來(lái)記錄每個(gè)節(jié)點(diǎn)的子樹(shù)擁有的葉節(jié)點(diǎn)數(shù)量,狀態(tài)轉(zhuǎn)移方程為dp[fa] += dp[child],dp[1]就是整棵樹(shù)擁有的葉節(jié)點(diǎn)數(shù)量

此時(shí)來(lái)看題目對(duì)potion的描述,每次traversal會(huì)在一個(gè)節(jié)點(diǎn)生成一個(gè)potion,下一次traversal前消失,而我們只會(huì)有k個(gè)(dp[1]個(gè))traversal

因此實(shí)際上只需要考慮前k個(gè)potion。而由于potion是依靠traversal獲取的,因此potiontraversal,也就是葉節(jié)點(diǎn),是一對(duì)一綁定的。假設(shè)我們目前在某個(gè)節(jié)點(diǎn)p,從點(diǎn)p出發(fā)獲得的potion數(shù)量不會(huì)超過(guò)點(diǎn)p的子樹(shù)擁有的葉節(jié)點(diǎn)數(shù)量。我們?cè)儆靡粋€(gè)樹(shù)上DP,potion[p]表示點(diǎn)p的子樹(shù)擁有的potion數(shù)量,狀態(tài)轉(zhuǎn)移方程為potion[fa] += potion[child]。統(tǒng)計(jì)完畢后再令potion[p] = min(potion[p], dp[p])。

最終potion[1]就是本題答案。

 

代碼

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int> G[N];
int a[N],f[N],dp[N];
void dfs(int x,int y){ //dp[x]代表每個(gè)點(diǎn)往下葉子個(gè)數(shù)
    for (auto v:G[x])
      if (v!=y){
            dfs(v,x);
            dp[x]+=dp[v];
      }
    if (!dp[x]) dp[x]=1;
}
void dfs2(int x,int y){//f[x]代表每個(gè)點(diǎn)往下葉子個(gè)數(shù)和到達(dá)點(diǎn)個(gè)數(shù)的min
    int ans=0;
    for (auto v:G[x])
      if (v!=y){
            dfs2(v,x);
            f[x]+=f[v];
      }
    f[x]=min(f[x],dp[x]);
}
int main(){
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);  
    }
    dfs(1,0);
    for (int i=1;i<=dp[1];i++) f[a[i]]++; //只有前葉子個(gè)數(shù)個(gè)是有用的
    dfs2(1,0);
    cout<<f[1]<<endl;
    return 0;
}

 

USACO 2024年1月銀牌第三題

 

圖片

 

題解分析

抽屜原理+同余性質(zhì)

題目等價(jià)于N個(gè)數(shù)除以L最多只有3個(gè)不同的余數(shù),根據(jù)抽屜原理,任意選擇4個(gè)不同的數(shù) ,必定至少有兩個(gè)數(shù)a[i]a[j]除以L的余數(shù)相同(即模L同余)。由同余的基本性質(zhì)可知abs(a[i]-a[j])必定能被L整除。

因此本題只需要從a[N]中任選4個(gè)不同的數(shù),枚舉它們的兩兩差值(一共有 = 6 ),對(duì)這6個(gè)數(shù),枚舉它們的所有因子fac,進(jìn)行檢驗(yàn)(看看a[1]a[N]除以fac是不是最多只有3個(gè)余數(shù)),符合要求則令ans+=fac。

 

代碼

//抽屜原理 4個(gè)數(shù)里一定有一個(gè)相同種類(lèi)的 L一定是a[i]-a[j]的因數(shù)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int a[N],f[N],n;
int sum=0;
void check(int x){ //檢驗(yàn)x是否合法
    vector<int> v;
    for (int i=1;i<=n;i++){
        int t=a[i]%x;
        bool pp=0;
        for (auto p:v){
            if (p==t) pp=1;
        }
        if (!pp) v.push_back(t);
        if (v.size()>3) break;
    }
    if (v.size()<=3) sum+=x;    
}
signed main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;
    //排序去重
    if (n<=3){
        //3個(gè)數(shù)任意答案都合法
        int x=a[1]/4;
        cout<<(x+1)*x/2<<endl;
        return 0;
    }
    int ans=1e10,now=1;
    for (int i=1;i<=n-3;i++) {
        if (a[i+3]-a[i]<ans){
            now=i;
            ans=a[i+3]-a[i];
        }
    }
    //找到最小差值 隨便找其實(shí)也是對(duì)的
    vector<int> v;
    map<int,bool> M;
    v.push_back(a[now+1]-a[now]);
    v.push_back(a[now+2]-a[now]);
    v.push_back(a[now+3]-a[now]);
    v.push_back(a[now+2]-a[now+1]);
    v.push_back(a[now+3]-a[now+1]);
    v.push_back(a[now+3]-a[now+2]);
    for (auto vv:v){ //標(biāo)記因數(shù)
        if (vv>0){
            for (int j=1;j*j<=vv;j++)
            if (vv%j==0)
            {
                M[j]=1;
                M[vv/j]=1;
            }
        }
    }
    for (auto v:M){
        if (v.first*4<=a[1]){
            check(v.first);
        }
    }
    cout<<sum<<endl;
    return 0;
}

圖片

USACO備考:
 

USACO的參賽選手必須依次通過(guò)青銅、白銀、黃金,直至最高級(jí)鉑金,不可跳級(jí),但是實(shí)力足夠,可以連續(xù)晉級(jí)。鉑金級(jí)選手如果有足夠的精力,可以繼續(xù)參賽打排名,爭(zhēng)取拿到美國(guó)國(guó)家集訓(xùn)隊(duì)(Camp)的Offer。因此在備賽過(guò)程中,可以提前準(zhǔn)備,不必等通過(guò)一個(gè)級(jí)別后再開(kāi)始學(xué)習(xí)下一個(gè)級(jí)別。


AP體系學(xué)生

AP體系有CSA和CSP兩門(mén)課程,如果同學(xué)們學(xué)的是CSA,那默認(rèn)大家是掌握一定的編程基礎(chǔ),如會(huì)寫(xiě)Java,那同學(xué)們?cè)趥淇嫉臅r(shí)候可能會(huì)時(shí)間會(huì)稍微短一點(diǎn)。如果是學(xué)CSP課程的同學(xué)們,可能知識(shí)儲(chǔ)備相對(duì)比較弱,大家可以通過(guò)老師給定的推薦備考時(shí)間,結(jié)合自身的情況進(jìn)行備考~這邊建議大家預(yù)留出來(lái)3- 6個(gè)月的時(shí)間去復(fù)習(xí)。

 

AL體系學(xué)生

如果同學(xué)是A Level 體系的話(huà),那么認(rèn)為這些同學(xué)是掌握計(jì)算機(jī)理論和數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)的。相比AP課程體系對(duì)很多代碼細(xì)節(jié)要求較高,而A Level課程體系要求自己寫(xiě)的代碼會(huì)少很多,故老師認(rèn)為同學(xué)們?cè)趥淇嫉谝粋€(gè)級(jí)別,即青銅升白銀的時(shí)間會(huì)稍長(zhǎng)一些,可能需要4-6個(gè)月。

 

IB體系學(xué)生

IB課程也是分兩類(lèi),一個(gè)是HL,一個(gè)是SL。HL可能會(huì)掌握了一些數(shù)據(jù)結(jié)構(gòu)和算法,如果說(shuō)對(duì)于算法有一定的更深理解,那這里可能會(huì)時(shí)間會(huì)相對(duì)短一點(diǎn)。

對(duì)于HL的同學(xué),在第一階段在備考3個(gè)月或者4個(gè)月的基礎(chǔ)上,還是能夠達(dá)到晉級(jí)白銀的水平。如果是SL的同學(xué),基礎(chǔ)相對(duì)較弱,因此要預(yù)留出來(lái)5到6個(gè)月做準(zhǔn)備才會(huì)保險(xiǎn)一點(diǎn)。

 

- X-NEW-

點(diǎn)擊在線(xiàn)咨詢(xún)

領(lǐng)取計(jì)算機(jī)資料和備考規(guī)劃

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