USACO比賽2021年1月銅組考試真題解析+考試入口！

隨著近幾年來(lái)出國(guó)留學(xué)的人越來(lái)越多,申本的難度也隨之不斷提高,學(xué)生們要有突出的基礎(chǔ)成績(jī),還要有過(guò)硬的“軟實(shí)力”,才能被名校所青睞。而受全球疫情的影響,準(zhǔn)留學(xué)生們提升軟實(shí)力的機(jī)會(huì)有所減少,海外項(xiàng)目不能參加,國(guó)內(nèi)部分活動(dòng)不能順利開展。

那么現(xiàn)階段有什么學(xué)術(shù)活動(dòng)活動(dòng),既提升學(xué)生的綜合能力又能被名校認(rèn)可,而且國(guó)內(nèi)學(xué)生足不出國(guó)就能參加。所以小編今天必須來(lái)給大家介紹一下：USACO全稱USA Computing Olympiad，美國(guó)信息學(xué)奧林匹克學(xué)術(shù)活動(dòng)。

比賽時(shí)間：3 月 25 日-3 月 28 日

比賽入口：usaco.org

報(bào)名時(shí)間：無(wú)需提前報(bào)名，賽時(shí)登錄賬號(hào)即可答題

比賽形式：線上

報(bào)名費(fèi)：無(wú)

獲取備賽計(jì)劃，考前查缺補(bǔ)漏、重點(diǎn)沖刺

【免費(fèi)領(lǐng)取】相關(guān)真題及解析，還有不定期的高能講座等你來(lái)參加！

以下是USACO比賽2021年1月銅組考試真題：第3題，一起來(lái)感受下難度吧~

題目解析

N最大為20，直接枚舉的復(fù)雜度為O(N*N!)，測(cè)試點(diǎn)1-5可以采用直接枚舉，當(dāng)N比較大時(shí)顯然會(huì)超時(shí)。

采用排列組合和乘法原理可以以較小的復(fù)雜度解此題。

以樣例為例：奶牛的高度可以從高到低排序：4 3 2 1，高度為4的奶牛可以安排到2個(gè)高度為4的牛棚，因而有2種可能性。高度為3的奶牛可以安排到2個(gè)高度為4的牛棚和1個(gè)高度為3的牛棚，因而有3種可能性，但由于可以安排高度為4的奶牛的牛棚一定可以安放高度為3的奶牛，這3種可能性中必定有1個(gè)用于安放高度為4的奶牛，則最終可能性為3-1=2。同理，高度為2的奶牛可以安排到4個(gè)牛棚中，但其中一個(gè)用于安放高度為4的奶牛，一個(gè)用于安放高度為3的奶牛，則最終可能性為4-1-1=2。高度為1的奶牛也可以安排到4個(gè)牛棚中，但一個(gè)用于安放高度4，一個(gè)用于安放高度3，一個(gè)用于安放高度2，則最終可能性為4-1-1-1=1。最后根據(jù)乘法原理，安排4頭奶牛的方法數(shù)為：2*(3-1)*(4-2)*(4-3)=8。該方法的時(shí)間復(fù)雜度為O(N^2)。

解法代碼

如果改進(jìn)，時(shí)間復(fù)雜度還可以優(yōu)化到O(N*logN)，只是本題的N很小，區(qū)別不大。代碼如下，可以思考下原因。

USACO學(xué)術(shù)活動(dòng)成本低，收益大，見(jiàn)效快！是一個(gè)非常值得參與的學(xué)術(shù)活動(dòng)哦~