• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Climber.pI的OI之路

            Through the darkest dark,may we see the light.

            USACO Training Chapter 4 ~ 6 Summary

            Section 4.1

            2010.08.26 TEXT Optimization Techniques

            2010.10.19 PROB Beef McNuggets 多重背包+裴蜀定理

            2011.08.07 PROB Fence Rails DFS+剪枝

            2011.03.24 PROB Fence Loops DFS / 最小環(huán)(Floyd)

            2011.08.10 PROB Cryptcowgraphy DFS+剪枝+字符串處理

            Section 4.2

            2011.08.10 TEXT "Network Flow" Algorithms

            2011.03.19 PROB Drainage Ditches 最大流(Edmonds-Karp)

            2011.03.19 PROB The Perfect Stall 最大流 / 二分圖最大匹配(Hungary)

            2011.08.10 PROB Job Processing 二分+貪心

            2011.08.11 PROB Cowcycles DFS+剪枝

            Section 4.3

            2011.08.11 TEXT Big Numbers

            2011.08.08 PROB Buy Low, Buy Lower DP+統(tǒng)計方案數(shù)+高精度

            2011.08.12 PROB The Primes DFS+剪枝

            2011.08.12 PROB Street Race DFS判斷連通性

            2011.08.11 PROB Letter Game 枚舉+優(yōu)化

            Section 4.4

            2011.08.13 PROB Shuttle Puzzle 數(shù)學(xué) / BFS

            2011.08.13 PROB Pollutant Control 最小割

            2011.08.16 PROB Frame Up 拓撲排序

             Section 5.1

            2011.08.17 TEXT Convex Hulls

            2011.08.17 PROB Fencing the Cows 凸包(Graham-Scan)

            2011.08.16 PROB Starry Night Floodfill + 模擬

            2011.08.13 PROB Musical Themes 二分 / DP

            Section 5.2

            2011.08.17 PROB Snail Trail DFS

            2011.08.17 PROB Electric Fences 模擬退火 / 局部搜索 / 隨機化搜索

            2011.08.17 PROB Wisconsin Squares DFS

            Section 5.3

            2011.08.17 TEXT Heuristics & Approximate Searches

            2011.08.18 PROB Milk Measuring DFS-ID + DP / DP

            2011.08.18 PROB Window Area 矩形切割 + 模擬

            2011.08.18 PROB Network of Schools 強連通分量(Tarjan)

            2010.08.19 PROB Big Barn DP

            Section 5.4

            2011.08.18 PROB All Latin Squares DFS+剪枝 / DFS+置換群

            2011.08.19 PROB Canada Tour DP / DP+刷表法

            2011.08.20 PROB Character Recognition 統(tǒng)計 + DP

            2011.08.19 PROB Betsy's Tour DFS+剪枝 / SCDP

            2011.08.18 PROB TeleCowmunication 最小割

            Section 5.5

            2011.08.21 PROB Picture 離散化 + 掃描 / 線段樹

            2011.08.20 PROB Hidden Passwords 枚舉+優(yōu)化 / 最小后綴

            2011.08.21 PROB Two Five Cantor展開 + DFS

            Section 6.1

            2011.08.21 PROB Postal Vans DP / SCDP

            2011.08.21 PROB A Rectangular Barn DP(懸線法)

            2011.08.21 PROB Cow XOR 枚舉+優(yōu)化

            大致學(xué)習(xí)了這些東西:

            1. DFS, 以及常見的優(yōu)化技巧

            2. 二分法轉(zhuǎn)化為判定性問題

            3. <string>的使用

            4. 離散化思想

            5. Tarjan算法(強連通分量)

            6. 懸線法求最大子矩陣

            7. Hungary算法(棋盤覆蓋, 最小路徑覆蓋)

            8. 拓撲排序的DFS實現(xiàn)

            9. DP的刷表法實現(xiàn)(白書P172) 

            10. Edmonds-Karp算法

            11. Graham-Scan算法求凸包, 水平線實現(xiàn)

            個人以為對于NOIp來說, USACO Training Chapter4之后的內(nèi)容的主要價值在于訓(xùn)練調(diào)試能力, DFS+剪枝的題目非常多, 對于訓(xùn)練暴搜來說是很好的教材. 算法上的話, Chapter4以后的NOIp新內(nèi)容只有二分法和DFS優(yōu)化技巧, 但是對于算法組合能力的要求有了進一步提升, 只有基礎(chǔ)非常扎實才能在短時間內(nèi)AC題目.

            不過目前的調(diào)試能力仍然有限, 不太復(fù)雜的DFS可能需要30 ~ 50min, 較為復(fù)雜的DFS可能需要2~3h甚至更長的時間才能調(diào)試通過. 對于NOIp來說還是太長了, 簡單DFS應(yīng)該在20min內(nèi)調(diào)試成功, 復(fù)雜一些也應(yīng)該在1h內(nèi)調(diào)試成功. 這方面還需要進一步訓(xùn)練.

            這次寫USACO Training跳過了4道題, 分別是1.4的某道矩形, 3.4.1的計算幾何, 4.4.2和5.4.5的兩道最小割. 如果日后打算參加GDKOI/GDOI的話, 再彌補網(wǎng)絡(luò)流/SCDP/高級數(shù)據(jù)結(jié)構(gòu)(Trie/線段樹/SBT/樹狀數(shù)組)這方面的內(nèi)容. Chapter5和Chapter6的幾道題還是很難理解題解, 也沒有掌握.

            不管怎么說, 我比一年前還是強了很多.

            posted on 2011-08-23 13:26 Climber.pI 閱讀(489) 評論(0)  編輯 收藏 引用


            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            激情综合色综合久久综合| 一本色道久久88综合日韩精品 | 久久综合久久久| 伊人久久免费视频| 中文字幕久久波多野结衣av| 久久99热这里只频精品6| 囯产精品久久久久久久久蜜桃 | 波多野结衣AV无码久久一区| 久久婷婷五月综合国产尤物app | 国内精品久久久久影院免费| 亚洲国产精品无码久久九九 | 国产一级持黄大片99久久| 精品国产婷婷久久久| 亚洲精品午夜国产VA久久成人| 久久久WWW免费人成精品| 91精品国产高清久久久久久io| 亚洲?V乱码久久精品蜜桃| 国产精品VIDEOSSEX久久发布| 婷婷久久香蕉五月综合加勒比| 蜜桃麻豆www久久| 亚洲国产美女精品久久久久∴| 国产免费久久久久久无码| 久久精品国产亚洲AV大全| 人妻无码中文久久久久专区| 国产三级精品久久| 久久久久久久99精品免费观看| 麻豆AV一区二区三区久久| 狠狠色丁香婷婷久久综合五月| 国产精自产拍久久久久久蜜| AAA级久久久精品无码片| 欧美精品一区二区精品久久| 奇米影视7777久久精品| 久久精品久久久久观看99水蜜桃 | 亚洲中文字幕无码久久精品1| 久久激情五月丁香伊人| 青青草原1769久久免费播放| 国产精品久久久久久福利漫画| 精品久久久久久国产| 久久99国产精品久久99| 亚洲狠狠综合久久| 国产精品va久久久久久久|