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

課程咨詢熱線 400-656-1680

1月USACO計(jì)算機(jī)競(jìng)賽'金牌'解題分析!附備考資料領(lǐng)取!

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

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

USACO競(jìng)賽試題有嗎?USACO競(jìng)賽1月金牌試題解析在哪領(lǐng)?1月的USACO月賽結(jié)束后,很多學(xué)生都想知道自己答題怎么樣,有沒(méi)有可能晉級(jí),今天我們就金級(jí)試題做出相關(guān)解析,幫助學(xué)生回憶。
USACO計(jì)算機(jī)競(jìng)賽1月月賽已經(jīng)結(jié)束了!不知道同學(xué)答題情況如何?小編給大家整理了USACO計(jì)算機(jī)競(jìng)賽'金牌'解題分析,參賽的同學(xué)可以簡(jiǎn)單做個(gè)參考。當(dāng)然,打算參加2月月賽的同學(xué),可以掃碼領(lǐng)取小編整理的備考資料哦,希望可以對(duì)同學(xué)們有所幫助!

圖片
圖片

 

 

01

 

 

USACO 2024年1月金牌題目解析

X-NEW

2024年 Jan GOLD probelm1 Walking in Mannhattan

 

Au1:

算法:二分,觀察性質(zhì)

首先假設(shè)當(dāng)前在x軸朝向上行走,什么時(shí)候會(huì)轉(zhuǎn)向到y(tǒng)軸?

我們發(fā)現(xiàn)當(dāng)且僅當(dāng)當(dāng)前道路距離下一條道路是奇數(shù)距離的時(shí)候會(huì)轉(zhuǎn)向

于是我們可以考慮去二分轉(zhuǎn)向的次數(shù),計(jì)算出在當(dāng)前轉(zhuǎn)向次數(shù)下運(yùn)動(dòng)的距離,判斷它是否小于等于題目給出的運(yùn)動(dòng)距離

代碼實(shí)現(xiàn)較為復(fù)雜,需要注意細(xì)節(jié)

時(shí)間復(fù)雜度: $O((n+q)*log)

2024年 Jan GOLD problem2 Cowmpetency

 

Au2:

算法:動(dòng)態(tài)規(guī)劃

和銀組第一題類似

定義$i$這個(gè)位置是前綴最大值當(dāng)且僅當(dāng)$a[i]>a[j]$ (for all $1le j<i$)< p="">

我們會(huì)發(fā)現(xiàn)對(duì)于某個(gè)$(a[i],h[i])$相當(dāng)于要求$[a[i]+1,h[i]-1]$這一段不能是前綴最大值,$h[i]$這個(gè)位置必須是前綴最大值

最終我們將相同情況的序列合并在一起,那么就是有最多$3*Q$段的序列(每一段內(nèi)部要么要求一定是前綴最大值/一定不是前綴最大值/沒(méi)有要求),求最終合法的方案數(shù)

定義$dp[i][j]$代表當(dāng)前考慮到前$i$段數(shù),選的數(shù)的最大值是$j$的方案數(shù)

假設(shè)當(dāng)前這一段序列長(zhǎng)度為$len$

當(dāng)一定是前綴最大值時(shí):

$dp[i][j]=sum_{k=1}^{j-1} dp[i-1][k]$

當(dāng)一定不是前綴最大值時(shí):

$dp[i][j]=dp[i-1][j]*j^{len}$

當(dāng)沒(méi)有要求時(shí):

$dp[i][j]=dp[i-1][j]j^{len} + sum_{k=1}^{j-1} dp[i-1][k](j^{len} -(j-1)^{len})$

時(shí)間復(fù)雜度: $O(qclog)$

2024年 Jan GOLD problem3 Nap Sort

 

Au3:

算法:二分

注意到分給Bessie自己的數(shù)越多答案相應(yīng)的會(huì)越大,但是會(huì)越容易滿足題目限制

所以我們考慮去二分 分給Bessie的個(gè)數(shù)$mid$

那么它們分別被加入序列的時(shí)間就是$mid, mid + (mid-1) ,... , mid+...+1$

顯然我們比較希望盡量靠后的數(shù)能被加入到Bessie的序列中,所以對(duì)于每一個(gè)加入序列的時(shí)間我們可以貪心的去找到第一個(gè)大于當(dāng)前時(shí)間且沒(méi)有被插入到序列中的數(shù),將它插入到序列中

這個(gè)過(guò)程可以用類似于雙指針的思想來(lái)優(yōu)化

最終$min(數(shù)字最大值,mid*(mid+1)/2)$就是我們的答案

時(shí)間復(fù)雜度: $O(n*log)$

 

02

 

 

USACO競(jìng)賽復(fù)習(xí)技巧

X-NEW

 

溫故知新 整理錯(cuò)題

對(duì)曾刷過(guò)的USACO競(jìng)賽題目進(jìn)行復(fù)習(xí)重刷,重新梳理解題思路,做好筆記整理。備賽時(shí)還可以利用一些學(xué)習(xí)網(wǎng)站,與其他備賽選手交流解題思路。

 

對(duì)??键c(diǎn)重點(diǎn)復(fù)習(xí)

對(duì)USACO競(jìng)賽中的一些常考知識(shí)點(diǎn)進(jìn)行重點(diǎn)復(fù)習(xí),例如銀級(jí)??嫉闹R(shí)點(diǎn)包括排序、二分和并查集;金級(jí)??嫉闹R(shí)點(diǎn)包括動(dòng)態(tài)規(guī)劃、最短路徑等算法等,整理答題思路和模板,在比賽時(shí)可以大大節(jié)省答題時(shí)間。

 

考前多刷真題

考前一定要多刷歷年真題,從真題中總結(jié)競(jìng)賽的重難點(diǎn)、易錯(cuò)點(diǎn)、常考點(diǎn),查漏補(bǔ)缺,在正式考試前做好充足的準(zhǔn)備!

 

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

  犀牛USACO競(jìng)賽培訓(xùn)課程

  犀牛國(guó)際計(jì)算機(jī)競(jìng)賽教研團(tuán)隊(duì)依據(jù)美國(guó)下一代科學(xué)標(biāo)準(zhǔn)NGSS,美國(guó)計(jì)算機(jī)教師協(xié)會(huì)K-12教育標(biāo)準(zhǔn),美國(guó)共同核心州立標(biāo)準(zhǔn)CCSSS,設(shè)計(jì)編程課程。

  犀牛USACO競(jìng)賽采用體系化的專業(yè)教材,將競(jìng)賽知識(shí)點(diǎn)和國(guó)際課程知識(shí)點(diǎn)整合。USACO教研組老師曾帶出多名白金組學(xué)員,擁有專業(yè)的教學(xué)能力。

  USACO競(jìng)賽教材

  

圖片
圖片

  課程目標(biāo):完成USACO的知識(shí)點(diǎn)的學(xué)習(xí)。通過(guò)系統(tǒng)地梳理,充分的練習(xí)熟悉考試的題型和難點(diǎn)重點(diǎn),沖刺USACO競(jìng)賽高分

  USACO初級(jí)班:適合計(jì)算機(jī)編程剛?cè)腴T,語(yǔ)言基礎(chǔ)薄弱,無(wú)比賽經(jīng)驗(yàn)計(jì)劃申請(qǐng)計(jì)算機(jī)專業(yè)的中學(xué)生;

  USACO中級(jí)班:適合至少會(huì)一門計(jì)算機(jī)編程語(yǔ)言(推薦C++或Java),算法基礎(chǔ)一般,少量比賽經(jīng)驗(yàn)的學(xué)生

  USACO高級(jí)班:適合具有完善的計(jì)算機(jī)編程語(yǔ)言基礎(chǔ),有入門算法經(jīng)驗(yàn),一定比賽經(jīng)驗(yàn),如NOIP,USACO銀組等的學(xué)生

 

圖片

USACO競(jìng)賽備考,歡迎在線找客服老師了解 

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