USACO十一算法camp小結(jié)-Day1
Day1?總結(jié)
單獨(dú)約談各位學(xué)員，了解大家的基礎(chǔ)，編程語言學(xué)習(xí)歷史，和比USACO的計(jì)劃
根據(jù)各位同學(xué)的語言基礎(chǔ)調(diào)整課程形式，降低課程難度
快速了解OI賽事的特點(diǎn)
練習(xí)2018USACO2月銅題1-3題（首次中文題），熟悉USACO賽事的難度，比賽形式
答題通過情況（AC）
銅1?全員通過
銅2?黃常麟 韓子鍵 余鐵琳 陳晟勱 石博聞 徐常捷
銅3?余鐵琳?孔伯銘?石博聞?Daniel
銀1?石博聞?Daniel?孔伯銘(部分)
銀2?石博聞
6.下午講解算法：倍增，排序，貪心，歐幾里德算法等 算法詳細(xì)內(nèi)容及參考資料總結(jié)：
7. 晚餐全體人員聚餐
8.聚餐后部分學(xué)員繼續(xù)攻克代碼，直到現(xiàn)在(晚上10：00pm)
畢克導(dǎo)師課程講稿(含大量參考鏈接內(nèi)容，信息量大，建議收藏)
1自我介紹
畢克
2010 ～ 2013，?家莊?中。
NOI 2012 ?牌。
2013 ～ 2017，清華?學(xué)。
5 次區(qū)域賽/EC-FINAL ?牌。
沒去過 IOI，也沒去過 ACM World Final。現(xiàn)在在?港上學(xué)（劃?）。
三?愛好：?賽，出題，講課。
QQ:751723392,?Email:wwwwodddd@gmail.com
2Competitive programming
算法?賽?是?種?較成熟的?賽形式。
簡(jiǎn)單來說，就是按照題?要求，讀取指定格式的輸?，經(jīng)過?些處理，按照指定格式輸出。最簡(jiǎn)單的輸出?較就是逐字節(jié)?較，也就是輸出必須和答案?模?樣，才算正確；當(dāng)然也有
的題?是 Special Judge，也就是只要滿??定條件即可。
?般情況下，除了反作弊的需要之外，不關(guān)注代碼如何實(shí)現(xiàn)的。
?常客觀。?便??調(diào)試。
增加?個(gè)參賽選?，額外代價(jià)很低。
對(duì)于?中階段
中國(guó)的?賽有 NOIP 和 NOI。美國(guó)的?賽有 USACO。
2.1???? 學(xué)習(xí)的意義
?中階段學(xué)習(xí) OI，可以保送?學(xué)。
?學(xué)階段學(xué)習(xí) ACM，可以獲得部分公司的青睞。（然后也可以?賽，出題，講課，?上經(jīng)濟(jì)獨(dú)?之路。）
3評(píng)測(cè)結(jié)果
3.1AC (Accepted)
表?通過。
3.2WA (Wrong Answer)
表?程序成功運(yùn)?，但是輸出和標(biāo)準(zhǔn)答案不?樣，或者是沒有通過 Special Judge 的檢測(cè)。
3.3 CE (Compile Error)
編譯失敗，需要注意在線的編譯器和你使?的編譯器不?定?樣，有?常多的原因會(huì)導(dǎo)致本機(jī)可以編輯，提交得到 CE。
3.4RE (Runtime Error)
表?程序崩潰。
有三種可能，數(shù)組越界，爆棧，除以 0。
3.5 TLE (Time Limit Exceeded)
程序使?的時(shí)間過長(zhǎng)，沒有順利運(yùn)?完成。
有兩種可能，算法太慢，或者是出現(xiàn)了死循環(huán)。
3.6MLE (Memory Limit Exceeded)
程序使?的空間過?，沒有順利運(yùn)?完成。
3.7OLE (Output Limit Exceeded)
程序不停的輸出，于是被結(jié)束了。
4 常見錯(cuò)誤
4.1不要輸出任何多余字符
不要輸出任何多余字符，提?語句，或者是調(diào)試語句。
?如不要輸出 please input an integer: 或者 the answer is。
4.2程序要順利結(jié)束
在上古時(shí)期寫程序，如果什么都不加，程序編譯運(yùn)?后會(huì)?閃?過。所以常常在結(jié)尾加上 system("pause") 或者 while(1);
4.3看清題目數(shù)據(jù)范圍
除了剛開始學(xué)編程，絕?多數(shù)題?都需要?定優(yōu)化，?定要考慮在最壞的情況下程序能否運(yùn)?。
復(fù)雜度 (Complexity)
5.1時(shí)間復(fù)雜度
我們特別關(guān)注運(yùn)?時(shí)間與輸?規(guī)模的關(guān)系。
對(duì)于運(yùn)?時(shí)間，我們?般考慮基本操作的次數(shù)。
?如可以認(rèn)為?次運(yùn)算是基本操作，?次賦值或者?較也是基本操作。
特別的，?般情況下并不關(guān)?常數(shù)問題，?如 a += b 可以看做?次基本操作，也可以看做兩次基本操作。
這就是?家常常說的 O(n)，O(n2) 的意思。
5.2????? 空間復(fù)雜度
對(duì)于算法?賽來說，不需要特別關(guān)注這個(gè)內(nèi)容。
?個(gè) int 是 4 字節(jié)，106 個(gè) int 是 4MB，其他的空間??以此類推。需要注意的是，即使什么都不寫，也會(huì)占??百 KB 的空間。
USACO?比賽介紹
12 ?，1 ?，2 ?，和?場(chǎng) US Open。
每次分為四個(gè)級(jí)別：Bronze, Silver, Gold, Platinum。
每次在 72 ?時(shí)中選擇 4 ?時(shí)參加（不要問我如何防?作弊） 剛開始只能參加 Bronze，達(dá)到?定分?jǐn)?shù)之后可以參加下?級(jí)。
?賽實(shí)時(shí)返回結(jié)果。
不要抄襲，?賽中不要進(jìn)?代碼上的交流。
不能打表，你不能本機(jī)運(yùn)算出所有輸?的答案，然后打表提交。（當(dāng)然我覺得打表主要和出題?平有關(guān)）
7C++
學(xué)會(huì)查?檔。
中??檔
英??檔
另?份英??檔
7.1????? 變量
各個(gè)類型的變量是有范圍的，具體來說跟?進(jìn)制有關(guān)。反碼
補(bǔ)碼
?家注意浮點(diǎn)數(shù) double 的存儲(chǔ)?式，類似科學(xué)計(jì)數(shù)法
IEEE 754
7.2運(yùn)算符
注意運(yùn)算優(yōu)先級(jí)，尤其是位運(yùn)算部分。注意異或和 power。
注意短路運(yùn)算?與位運(yùn)算的區(qū)別。
注意單?運(yùn)算符負(fù)號(hào)，與減法的區(qū)別注意運(yùn)算中類型的強(qiáng)制轉(zhuǎn)換
7.3判斷和循環(huán)
沒什么好講的，相信?家已經(jīng)掌握了。
STL
我認(rèn)為 C++ 中?較有?的東西：
next_permutation sort
set map
priority_queue
7.5 信息學(xué)
信息學(xué)不需要 C++ 中華麗的特性。信息學(xué)寫的代碼基本是?次性的。
C++ 可以提供底層和頂層的書寫?式。
? Pascal 便于書寫。
? Python 效率?。
與之類似的還有 Java 語?，不過效率稍低。
信息學(xué)不關(guān)??戶體驗(yàn)，只需要輸出應(yīng)該輸出的即可。時(shí)間復(fù)雜度是影響程序速度的重要指標(biāo)。
8Java
Java 是?個(gè)完全?向?qū)ο蟮恼Z?基本語法和 C++ ?常相似但是要注意以下的不同。
庫函數(shù)的區(qū)別?如排序，等函數(shù)，Java 的?法和 C++ 完全不同。還有?些容器，?如 Map Set 等也很不相同。
另外 Java 中對(duì)于對(duì)象（結(jié)構(gòu)體）都是傳引?，?不是傳值。這也是值得注意的?點(diǎn)。
9Python
9.1交互式
Python 的交互功能?常好?，推薦每個(gè)?都學(xué)習(xí)使?。
并且 Python ?持計(jì)算?精度，可以?來當(dāng)進(jìn)階版的計(jì)算器。
9.2 變量
變量不需要聲明，不需要明確類型。
9.3 運(yùn)行速度
Python 的運(yùn)?速度?常慢，并且不容易被估計(jì)。并不建議在需要優(yōu)化效率的情況下使?。
Python 2 和 Python 3
Linux 計(jì)算機(jī)?般默認(rèn)安裝 Python 2，所以建議學(xué)習(xí) Python 2。當(dāng)然如果你已經(jīng)會(huì)了 Python 3，也不?換，了解 Python2 和 3 的差別即可。
10USACO 2017
?共有四場(chǎng)?賽。難度逐漸增加。
從 2018 February 開始，題?描述開始有了簡(jiǎn)體中?版。
11USACO 2017 December Contest, Bronze, Problem 1. Blocked Billboard
11.1題目背景
Blocked Billboard
11.2題目大意
求矩形?積交
11.3 題目解法
求矩形?積交
12USACO 2017 December Contest, Bronze, Problem 2. The Bovine Shuffle
12.1題目背景
The Bovine Shuffle
12.2題目大意
數(shù)組的嵌套使?。
12.3題目解法
數(shù)組的嵌套使? s[a[a[a[i]]]]。
13USACO 2017 December Contest, Bronze, Problem 3. Milk Measurement
13.1題目背景
Milk Measurement
13.2題目大意
模擬，三個(gè)數(shù)字求最?值。
13.3題目解法
模擬，三個(gè)數(shù)字求最?值。
14USACO 2018 January Contest, Bronze, Problem 1. Blocked Billboard II
14.1題目背景
Blocked Billboard II
14.2題目大意
分類討論，矩形?積交。
14.3 題目解法
分類討論，矩形?積交。
15USACO 2018 January Contest, Bronze, Problem 2. Life- guards
15.1 題目背景
Lifeguards
15.2題目大意
枚舉，模擬。
15.3 題目解法
枚舉，模擬。
16 USACO 2018 January Contest, Bronze, Problem 3. Out of Place
16.1題目背景
Out of Place
16.2題目大意
?個(gè)有序的數(shù)列中，插?了?個(gè)數(shù)字。
問?少多少次交換，可以使得這個(gè)序列再次變得有序。初始的序列中可能有相同的數(shù)字。
16.3題目解法
排序之后，檢查有多少個(gè)數(shù)字發(fā)?了變化。如果沒有，答案是 0。
如果有 k 個(gè)，那么需要 k ? 1 次交換。
17USACO 2018 February Contest, Bronze, Problem 1. Teleportation
17.1題目背景
Teleportation
17.2題目大意
數(shù)軸上兩點(diǎn)之間的距離。
17.3 題目解法
數(shù)軸上兩點(diǎn)之間的距離。
18 USACO 2018 February Contest, Bronze, Problem 2. Hoofball
18.1題目背景
Hoofball
18.2????? 題目大意
英語題
”the cow farthest to the left among these” 是指最左邊的，?不是指距離左邊最遠(yuǎn)的。
18.3 題目解法
對(duì)于?頭?來說，如果沒?給他球，那么 John 必須給他。
特別的，如果對(duì)于孤?的 2 頭?，他們互相傳，那么 John 也必須給其中?個(gè)?。
19 USACO 2018 February Contest, Bronze, Problem 3. Taming the Herd
19.1 題目背景
Taming the Herd
19.2????? 題目大意
題目解法
如果?天是 x(x > 0)，那么前?天必須是 x ? 1。如果?天需要是不同的數(shù)值，那么?解。
第?天必須是 0。
在滿?以上條件的情況下，所有 ?1 都可以變?yōu)?0 或變?yōu)橹暗臄?shù)字加?。
20USACO 2018 US Open Contest, Bronze, Problem 1. Team Tic Tac Toe
20.1 題目背景
Team Tic Tac Toe
20.2 題目大意
閱讀理解題
20.3 題目解法
選出來的 2 個(gè)字母?序。
必須是存在??，兩個(gè)都有才可以。
21USACO 2018 US Open Contest, Bronze, Problem 2. Milking Order
21.1? 題目背景
Milking Order
21.2題目大意
題目解法
考慮如何判斷?解，如果可以判斷?解，枚舉 1 ?的位置，然后判斷是否有解即可。
22 USACO 2018 US Open Contest, Bronze, Problem 3. Family Tree
22.1 題目背景
Family Tree
22.2????? 題目大意
題目解法
模擬
倍增
?處最?的就是快速冪
快速冪可以處理所有滿?結(jié)合律的東西。
24 Luogu P1226
24.1? 題目背景
24.2? 題目大意
快速冪
24.3 題目解法
快速冪
見多識(shí)?的同學(xué)可能覺得這個(gè)題可以?歐拉定理搶救?下。并沒有必要。
排序 (sort)
3 個(gè) O(n2) 排序。
3 個(gè) O(n log n) 排序。
快速排序，最常?。
歸并排序，可以算逆序?qū)Α?/p>
堆排序，只需要 O(1) 的額外空間。
貪心算法 (Greedy algorithm)
有很多?常好的貪?題?。
但是因?yàn)樾枰闹R(shí)過于艱深，所以只好先挑?些簡(jiǎn)單的。
27??????? Luogu P1007
27.1????? 題目背景
27.2????? 題目大意
題目解法
假設(shè)相遇之后不是同時(shí)調(diào)頭，?是互相穿過。
28??????? Luogu P1208
28.1????? 題目背景
P1208 [USACO1.3] 混合?奶 Mixing Milk
28.2????? 題目大意
題目解法
按價(jià)格排序，然后貪?。
29??????? Luogu P1223
29.1????? 題目背景
29.2????? 題目大意
題目解法
對(duì)于第 i 個(gè)?，如果他倒數(shù)第 j 個(gè)接?，那么對(duì)全局的貢獻(xiàn)是 jti。所以接?快的，應(yīng)該先接?。
30??????? bzoj 2563
30.1????? 題目背景
30.2????? 題目大意
題目分析
貪?！
遞歸
遞歸本質(zhì)上并不需要存在，只是為了程序容易實(shí)現(xiàn)。
?些例?：階乘，F(xiàn)ibonacci 數(shù)。遞推式，終?條件。
32??????? 歐幾里得算法
計(jì)算最?公約數(shù)：歐??得算法
33??????? 搜索
枚舉所有的狀態(tài)。
33.1????? 枚舉所有子集
枚舉??為 n 的集合的所有?集。
?位運(yùn)算。
枚舉?集的?集。
33.2????? 枚舉固定大小的子集
枚舉??為 n 的集合的所有??為 m 的?集。
next permutation
似乎有?種?位運(yùn)算的?法，但是我記不得了。
33.3????? 枚舉所有排列
枚舉 1 到 n 的所有排列。深搜。
next permutation。
值得注意的是。next permutation 處理有重復(fù)元素的時(shí)候，不會(huì)把相同的排列?成 2 次。
33.4????? 其他
但是在很多情況下，還是需要?深搜的
34??????? 深度優(yōu)先搜索（搜索）
?棧。
但是因?yàn)橛羞f歸，這個(gè)棧，并不需要你來實(shí)現(xiàn)。
?般適?于：找到任意?個(gè)解，或者找到所有解。或者是狀態(tài)?常?，不適合深度優(yōu)先搜索。
34.1????? 細(xì)節(jié)
核?在于狀態(tài)更新與復(fù)原。
有的時(shí)候還需要標(biāo)記 visited 數(shù)組，表?這個(gè)狀態(tài)被搜過了。
35??????? 剪枝
遇到?些不合法的狀態(tài)，可以直接剪枝，?不是等到枚舉到最后再剪枝。
36??????? 廣度優(yōu)先搜索（搜索）
?隊(duì)列。
需要??實(shí)現(xiàn)隊(duì)列。
?般適?于：找到步數(shù)最?的解。 注意隨著步數(shù)增加，狀態(tài)指數(shù)增長(zhǎng)。
36.1????? 細(xì)節(jié)
核?在于把狀態(tài)壓縮，要能存下。
有的時(shí)候還需要標(biāo)記 visited 數(shù)組，表?這個(gè)狀態(tài)被搜過了。
37??????? 雙向廣度優(yōu)先搜索
從最開始的狀態(tài)和最后的狀態(tài)?起搜索。
這樣只需要最?步數(shù)的?半，就可以搜出答案了。
隨著步數(shù)增加，狀態(tài)指數(shù)增長(zhǎng)，步數(shù)減少?半，狀態(tài)減少明顯！
38??????? IDA*
每個(gè)狀態(tài)很?，并不能?搜？ 要求最?步數(shù)？
枚舉最?步數(shù)，然后深搜判斷有沒有解。
每多?層，多花費(fèi)的時(shí)間是上?層的數(shù)倍，上?層的時(shí)間可以忽略。
39??????? Luogu P1219
39.1????? 題目背景
39.2????? 題目大意
經(jīng)典問題?皇后。
39.3????? 題目解法
直接深搜即可。
40??????? Luogu P1312
40.1????? 題目背景
40.2????? 題目大意
NOIP 2011 的?個(gè)搜索模擬題。
40.3????? 題目解法
41??????? bzoj 1501
41.1????? 題目背景
41.2????? 題目大意
暴?搜索。
41.3????? 題目分析
需要努?寫代碼。
翰林USACO課程體系流程圖
以上就是關(guān)于【USACO十一算法camp小結(jié)-Day1】的解答，如需了解學(xué)校/賽事/課程動(dòng)態(tài)，可至翰林教育官網(wǎng)獲取更多信息。
往期文章閱讀推薦：
翰林9周年重磅鉅惠！最高75折+千元推薦禮！限100位快來預(yù)約！
國(guó)際生親身經(jīng)歷有償征稿！翰林學(xué)長(zhǎng)學(xué)姐說招募開啟！
翰林AMC8視頻課重磅上線！
國(guó)際競(jìng)賽真題資源免費(fèi)領(lǐng)取
