2009年暑假集训讲义2009年暑假集训讲义上海交通大学 马融上海交通大学 马融第一讲 穷举与贪心...................................................................................................................3集市班车 (FairShuttle,USACO2009Feb)...............................................................................4翻转棋 (Fliptile,USACO2007Nov)..........................................................................................5翻转奶牛 (FaceTheRightWay,USACO2007Mar).................................................................6第二讲 背包问题.......................................................................................................................7分数膨胀 (ScoreInflation,USACO3.1)....................................................................................8货币系统 (MoneySystems,USACO2.3)..................................................................................9奶牛博览会 (CowExhibition,USACO2003Nov)...................................................................10太空电梯 (SpaceElevator,USACO2005Mar).......................................................................11牛奶量取 (MilkMeasuring,USACO5.3)................................................................................12第三讲 动态规划选讲.............................................................................................................13抓苹果 (AppleCatching,USACO2004Nov)..........................................................................15最廉回文 (CheapestPalindrome,USACO2007Open)..........................................................17麦香牛块 (BeefMcNuggets,USACO4.1)..............................................................................19道路重建 (RebuildingRoads,USACOFeb2002)....................................................................20第四讲 最小生成树问题.........................................................................................................22建造道路 (BuildingRoads,USACO2007Dec).......................................................................23安慰奶牛 (CheeringuptheCows,USACO2008Nov)...........................................................24地震 (Earthquake,USACO2001Open)..................................................................................26第五讲 最短路径问题.............................................................................................................28道路翻新 (RevampingTrails,USACO2009Feb)....................................................................29道路障碍 (Roadblocks,USACO2006Nov)............................................................................31奶牛慢跑 (CowJogging,USACO2008Mar)..........................................................................33第六讲 广度优先遍历.............................................................................................................35青铜莲花池 (BronzeLilypadPond,USACO2007Feb)...........................................................36白银莲花池 (SilverLilypadPond,USACO2007Feb).............................................................37黄金莲花池 (LilypadPond,USACO2007Feb).......................................................................39第七讲 USACO竞赛试题选讲................................................................................................41哞哞大学之奖学金 (MooUniversity-FinancialAid,USACO2004Mar)..............................42哞哞大学之校队选拔 (MooUniversity-TeamTryouts,USACO2004Mar).........................44哞哞大学之匹萨预定 (MooUniversity-EmergencyPizzaOrder,USACO2004Mar)..........46第八讲 USACO竞赛试题选讲(续)....................................................................................48黄金平衡 (USACO2007Mar)................................................................................................49奶牛排名 (RankingtheCows,USACO2007Mar)..................................................................50奶牛交通 (CowTraffic,USACO2007Mar).............................................................................51校庆聚会 (Ural1039).............................................................................................................52