- X-NEW-
點擊在線咨詢
領(lǐng)取計算機(jī)資料和備考規(guī)劃
課程咨詢熱線 400-656-1680
發(fā)布時間：2024-02-02 09:34:32
編輯：Lisa來源：未知瀏覽：次
USACO競賽1月月賽真題解析有嗎？USACO競賽怎么備考？USACO競賽真題解析來啦，參加了2024年1月的USACO月賽的同學(xué)，快來對答案！
USACO計算機(jī)競賽的1月月賽悄然落幕！參賽的同學(xué)們覺得題目難嗎？給大家整理了此次銀牌考試試題+題解+代碼，考完的同學(xué)們可以來參考交流一下。想要領(lǐng)取此次真題全部解析和有備考計劃的同學(xué)，可以在線領(lǐng)取
- X-NEW-
USACO 2024年1月銀牌第一題
題解分析：
有q對(x,y)的輸入，每對表示前1~x個數(shù)右邊第一個比它們大的數(shù)必須在下標(biāo)為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 （字典序最小）
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
//注意有時候需要反悔，由于當(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é)點的樹。每次traversal相當(dāng)于從根出發(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。
因此實際上只需要考慮前k個potion。而由于potion是依靠traversal獲取的，因此potion和traversal,也就是葉節(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ù)和到達(dá)點個數(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，進(jìn)行檢驗（看看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){ //標(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的參賽選手必須依次通過青銅、白銀、黃金，直至最高級鉑金，不可跳級，但是實力足夠，可以連續(xù)晉級。鉑金級選手如果有足夠的精力，可以繼續(xù)參賽打排名，爭取拿到美國國家集訓(xùn)隊（Camp）的Offer。因此在備賽過程中，可以提前準(zhǔn)備，不必等通過一個級別后再開始學(xué)習(xí)下一個級別。
AP體系學(xué)生
AP體系有CSA和CSP兩門課程，如果同學(xué)們學(xué)的是CSA，那默認(rèn)大家是掌握一定的編程基礎(chǔ)，如會寫Java，那同學(xué)們在備考的時候可能會時間會稍微短一點。如果是學(xué)CSP課程的同學(xué)們，可能知識儲備相對比較弱，大家可以通過老師給定的推薦備考時間，結(jié)合自身的情況進(jìn)行備考~這邊建議大家預(yù)留出來3- 6個月的時間去復(fù)習(xí)。
AL體系學(xué)生
IB體系學(xué)生
IB課程也是分兩類，一個是HL，一個是SL。HL可能會掌握了一些數(shù)據(jù)結(jié)構(gòu)和算法，如果說對于算法有一定的更深理解，那這里可能會時間會相對短一點。
