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

課程咨詢熱線 400-656-1680

2023-2024賽季USACO競(jìng)賽考試真題及解析新鮮出爐!

發(fā)布時(shí)間:2023-12-25 09:56:18 編輯:Lisa來(lái)源:未知

2023-2024賽季USACO競(jìng)賽考試真題及解析新鮮出爐!對(duì)于在本賽季參加USACO競(jìng)賽的各位同學(xué),12月的月賽考題和解析犀牛國(guó)際已為大家解析出來(lái)。另外,關(guān)于USACO競(jìng)賽的課程輔導(dǎo),有需要的同學(xué)可以了解。

USACO競(jìng)賽真題展示
-

就在昨晚,2023年的USACO競(jìng)賽首場(chǎng)月季考試結(jié)束,小編也是拿到了考試的第一手真題,關(guān)于本次USACO競(jìng)賽考試銅升銀,真題如下:

01

圖片

01
犀牛解析:
圖片

這個(gè)題是個(gè)有意思的暴力問(wèn)題

考慮一個(gè)子問(wèn)題:

一個(gè)數(shù)初始是1,每一次操作是讓它乘2,要求這個(gè)數(shù)小于等于n,求最多能操作多少次

這個(gè)問(wèn)題的答案比較顯然是log2n次

那考慮當(dāng)前的問(wèn)題,考慮第一頭牛,如果牛比甘蔗矮,那么它吃完甘蔗后高度乘22;如果牛比甘蔗高,此輪吃甘蔗結(jié)束。

所以這一題直接暴力模擬做到甘蔗被吃完復(fù)雜度就是對(duì)的。

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

知識(shí)點(diǎn):暴力,時(shí)間復(fù)雜度分析

02

圖片

02
犀牛解析
圖片

首先我們可以根據(jù)輸入計(jì)算出1的擴(kuò)散時(shí)間最長(zhǎng)是多少(時(shí)間越長(zhǎng)需要的初始點(diǎn)就越少)

注意邊界和中間的計(jì)算方式不同,中間擴(kuò)散的結(jié)果是1,3,5,...,2*n-1,而邊界是1,2,3,...,n$因?yàn)檫吔缈梢苑旁谧罱锹溟_始)

計(jì)算出最長(zhǎng)擴(kuò)散時(shí)間max_time后我們就可以對(duì)每一段連續(xù)為1計(jì)算初始最少需要放幾個(gè)1 : len = 2*max_time+1 (len代表連續(xù)1個(gè)數(shù))

最終將答案相加即可

復(fù)雜度:O(n)

知識(shí)點(diǎn):貪心,邊界條件判斷

03

圖片

03
犀牛解析
圖片

考慮根據(jù)最終的排序結(jié)果來(lái)確定有多少條件,容易發(fā)現(xiàn)其實(shí)只有$n-1$個(gè)有效的不等式,即第1個(gè)小于第2個(gè),第2個(gè)小于第3個(gè),...

根據(jù)不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t對(duì)應(yīng)的范圍

最終對(duì)于所有不等式結(jié)果求出交集,如果不為空就輸出最小值,否則輸出-1

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

知識(shí)點(diǎn):簡(jiǎn)單數(shù)學(xué)

 

圖片
USACO競(jìng)賽代碼解析
 
圖片
 

犀牛USACO競(jìng)賽真題解析

在線咨詢?cè)斍?/span>

 

 

圖片
如何學(xué)好USACO?數(shù)學(xué)基礎(chǔ)要扎實(shí)

 

雖然數(shù)學(xué)和編程有本質(zhì)上的區(qū)別,但之間卻存在著千絲萬(wàn)縷的聯(lián)系:

數(shù)學(xué)可以幫助我們按步驟完成計(jì)算,而編程幫助我們實(shí)現(xiàn)每個(gè)計(jì)算步驟。

編程的基礎(chǔ)是建立在數(shù)學(xué)之上。例如,樹、圖、堆等數(shù)據(jù)結(jié)構(gòu)以及貪心算法、動(dòng)態(tài)規(guī)劃等算法都需要應(yīng)用數(shù)學(xué)思維和方法。

USACO競(jìng)賽涉及問(wèn)題可以歸類為應(yīng)用數(shù)學(xué)或運(yùn)籌學(xué)

 

學(xué)好編程需要打好數(shù)學(xué)基礎(chǔ),包括
 
 
 
 
 
  • 能力:在for循環(huán)中經(jīng)常用到,類似小學(xué)數(shù)學(xué)的知識(shí)。

  • 數(shù)字的加減乘除:每種編程語(yǔ)言都內(nèi)置支持,不需要手動(dòng)計(jì)算。

  • 數(shù)和模運(yùn)算:偶爾會(huì)用到。

  • 集合運(yùn)算:交集、并集、差集,編程中用到的不多。

  • 布爾運(yùn)算:AND、OR等邏輯運(yùn)算。

  • 各種進(jìn)制:二進(jìn)制、十進(jìn)制、十六進(jìn)制等。

 
 
 
 
圖片

 

 
 
 
 
 
 
 
 
 

犀牛USACO競(jìng)賽課程輔導(dǎo)

 
 
 
 
 
 
 
 
 

犀牛國(guó)際USACO競(jìng)賽擁有專業(yè)的導(dǎo)師團(tuán)隊(duì),為學(xué)生提供更專業(yè)的課程輔導(dǎo)。USACO競(jìng)賽課程包含了銅沖銀,銀金沖以及沖鉑金的課程內(nèi)容,4-6人小班授課,也可一對(duì)一精品授課,支持中英和全英兩種授課語(yǔ)言。

 
 
 
犀牛USACO競(jìng)賽課程
 
 
 
 
USACO競(jìng)賽銅升銀培訓(xùn)班
 
 
01
圖片
 
USACO競(jìng)賽銀升金培訓(xùn)班
 
 
02
圖片
 
USACO競(jìng)賽金升鉑金培訓(xùn)班
 
 
03
圖片

 

犀牛USACO競(jìng)賽課程輔導(dǎo)

在線咨詢?cè)斍?/span>

 

圖片

犀牛國(guó)際培訓(xùn)課程開設(shè)了精品小班、一對(duì)一等多種班型,家長(zhǎng)和同學(xué)們可任意選擇,線下+線上同步授課,在上海、北京、南京、蘇州、無(wú)錫、杭州、廣州、深圳、青島、合肥、武漢、濟(jì)南、成都等地均設(shè)有線下校區(qū)。提升各科國(guó)際競(jìng)賽、國(guó)際課程、國(guó)際學(xué)校擇校與留學(xué)服務(wù),具體了解可點(diǎn)擊在線咨詢!

 

犀牛USACO競(jìng)賽課程輔導(dǎo)

在線咨詢?cè)斍?/span>

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