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

課程咨詢熱線 400-656-1680

2024 USACO計算機競賽真題解析(完整版)

發(fā)布時間:2024-02-04 10:21:51

編輯:Lily來源:網(wǎng)絡(luò)瀏覽:

2024 USACO計算機競賽真題解析來啦,USACO計算機競賽的1月月賽已經(jīng)落幕!上期老師給大家講解了銅牌的真題解析,今天老師給大家整理了此次USACO銀牌考試試題+題解+代碼,考完的同學們可以來參考交流一下。想要領(lǐng)取此次真題全部解析和有備考計劃的同學,客服領(lǐng)取~

 

 
 
 
USACO 2024年1月銀牌第一題
圖片

題解分析

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

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

 

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

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

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

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

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

 

注意事項:這題有T個測試,每個輸出最后不能帶空格

 

代碼

//Q x y 的限制等價于是y是前綴最大值,x+1~y-1內(nèi)的元素不能是前綴最大值
//貪心,對于不是前綴最大值的填1,是前綴最大值的填前綴max再+1
//注意有時候需要反悔,由于當前值是前綴最大值但是題目要求它不能是,只能把之前的值改大
#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é)點的樹。每次traversal相當于從根出發(fā),沿著父子關(guān)系一直走,一個traversal的終點一定是一個葉節(jié)點,因此最小的traversal數(shù)必定為葉節(jié)點數(shù)量,可以用dfs得到,假設(shè)這個數(shù)量是k

 

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

 

此時來看題目對potion的描述,每次traversal會在一個節(jié)點生成一個potion,下一次traversal前消失,而我們只會有k(dp[1])traversal。

因此實際上只需要考慮前kpotion。而由于potion是依靠traversal獲取的,因此potiontraversal,也就是葉節(jié)點,是一對一綁定的。

 

假設(shè)我們目前在某個節(jié)點p,從點p出發(fā)獲得的potion數(shù)量不會超過點p的子樹擁有的葉節(jié)點數(shù)量。我們再用一個樹上DP,potion[p]表示點p的子樹擁有的potion數(shù)量,狀態(tài)轉(zhuǎn)移方程為potion[fa] += potion[child]。統(tǒng)計完畢后再令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]代表每個點往下葉子個數(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]代表每個點往下葉子個數(shù)和到達點個數(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]]++; //只有前葉子個數(shù)個是有用的
    dfs2(1,0);
    cout<<f[1]<<endl;
    return 0;
}

 
 
 

 

 
 
 
USACO 2024年1月銀牌第三題

 

圖片

題解分析

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

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

 

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

 

代碼

//抽屜原理 4個數(shù)里一定有一個相同種類的 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){ //檢驗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個數(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];
        }
    }
    //找到最小差值 隨便找其實也是對的
    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){ //標記因數(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;
}

 
 
 

 

這次沒有發(fā)揮好的同學,并不影響之后參加第二個月USACO競賽,大家可以繼續(xù)努力,期待接下來的2月的月賽~

 

注意競賽時間:2月16日-2月19日

圖片

這里小編也給大家準備了USACO的必刷題庫~有需要的可以領(lǐng)取~

 

USACO競賽題庫領(lǐng)取

 

USACO歷年真題是每個參賽者的寶貴資源,我們會及時發(fā)布新鮮出爐的解析與試題;

 

訪問USACO官網(wǎng)(https://www.usaco.org/),注冊并登錄后,即可獲得官方提供的歷屆比賽題目及練習平臺; 

 

犀牛教育為大家整理了USACO競賽題庫,包含近十年經(jīng)典考題(包含源碼),對于想要USACO沖刺升級的學生,這套USACO競賽備考題庫資料,非常適合大家。可以根據(jù)自己的需求領(lǐng)取!

 

圖片
圖片
圖片
圖片
 
USACO題庫
圖片
圖片
圖片
圖片
 
USACO題庫

 

USACO競賽源碼

 

圖片

 

USACO競賽試題+課程

在線客服咨詢

相關(guān)標簽:
TOP