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

課程咨詢熱線 400-656-1680

2024年USACO考題新鮮出爐!黃金組別考情分析

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

編輯:犀牛牛來源:犀牛國(guó)際教育瀏覽:

USACO計(jì)算機(jī)編程競(jìng)賽的1月月賽已經(jīng)完美結(jié)束啦,這次題目難度比較大,不少學(xué)生在參加USACO競(jìng)賽時(shí),對(duì)計(jì)算機(jī)語(yǔ)言運(yùn)用還是不夠熟練,那么我們一起來復(fù)盤以下2024年1月考題情況,一起來看下,文末有USACO競(jìng)賽輔導(dǎo),在線咨詢客服老師~

USACO 2024年1月黃金組別考情分析

第1題

考察算法:二分,觀察性質(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)

第2題

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

和銀組第一題類似

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

我們會(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)部要么要求一定是前綴最大值/一定不是前綴最大值/沒有要求),求最終合法的方案數(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)沒有要求時(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)$

第3題

考察算法:二分

注意到分給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í)間且沒有被插入到序列中的數(shù),將它插入到序列中

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

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

2023-2024年USACO活動(dòng)時(shí)間

第一次月賽:2023年12月15日-18日

第二次月賽:2024年1月26日-29日

第三次月賽:2024年2月16日-19日

美國(guó)公開賽:2024年3月15日-18日

(中國(guó)學(xué)生只能參加到公開賽)

集訓(xùn)營(yíng):2024年5月23日-6月1日

EGOI:2024年7月21日-27日(荷蘭)

IOI:2024年9月1日-8日(埃及)

報(bào)名方式:參賽者可隨時(shí)在官網(wǎng)注冊(cè)賬號(hào),注冊(cè)。報(bào)名,只需在活動(dòng)時(shí)間登陸完成答題即可。

官網(wǎng)地址:usaco.org

提交之后,官網(wǎng)會(huì)發(fā)送一份郵件到您郵箱,郵件中有賬號(hào)密碼

利用已知的賬號(hào)于密碼,登錄USACO賬號(hào),即可開始考試


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