usaco教程.doc
- 格式:doc
- 大小:116.50 KB
- 文档页数:38
D*1FS_(20 -3215-M2Ersatzteilliste / Spare Parts ListSerie/Series D*1FSProp.-Wegeventile Prop.-DC-ValvesAusgabe / Effective:05/2000Vorläufige Ausgabe / Preliminary edition\\De-kaa-nt-pdm\DTP\Ersatzteillisten\relevantSiegel0400\3215\D1FS_3215-M2.docContentsD*1FS_(20-3215-M2Ersatzteilliste / Spare Parts ListProp.-Wegeventile / Prop.-DC ValvesD*1FS_(20HinweisDie in diesem Bulletin oder in Form anderer Informationendurch die Parker Hannifin GmbH, ihre Niederlassungen,Vertriebsbüros oder ihre autorisierten Werksvertretungengemachten Angaben sind für Anwender mitSachkenntnissen bestimmt. Vom Anwender ist eineÜberprüfung der über das ausgewählte Produkt gemachten Angaben auf Eignung für die geforderteFunktionen erforderlich. Bedingt durch dieunterschiedlichen Aufgaben und Arbeitsabläufe in einemSystem muß der Anwenderprüfen und sicherstellen, daßdurch die Eigenschaften des Produkts alle Forderungenhinsichtlich Funktion und Sicherheit des Systems erfülltwerden.NoteThis bulletin and other information from Parker HannifinGmbH, its subsidiaries, sales offices and authorizeddistributors provide product or system options for furtherinvestigation by users having technical expertise. Beforeyou select or use any product or system it is importantthat you analyse all aspects of your application andreview the information concerning the product or systemin the current product catalogue. Due to the variety ofoperating conditions and applications for these productsor systems, the user, through his own analysis andtesting, is solely responsible for marking the finalselection of the products and systems and assuring thatall performance and safety requirements of theapplication are met. The products are subject to changeby Parker Hannifin GmbH at any time without notice..Seitenlayout und Darstellungen können in diesem Bulletinaufgrund datentechnischer Umstellungen varriieren.In this edition, page layout and drawings methods may differdue to changes in data processing.Erroneous data cannot be excluded despite careful revision.Copyright © by Parker Hannifin GmbH, 1997Trotz sorgfälltiger Prüfung sind fehlerhafte Angaben nichtauszuschließen.Copyright © bei Parker Hannifin GmbH, 1997Parker Hannifin GmbHHydraulic Controls DivisionGutenbergstrasse 38D 41564 Kaarst (Büttgen( 02131 / 513-0Fax: 02131 / 513 230\\De-kaa-nt-pdm\DTP\Ersatzteillisten\relevantSiegel0400\3215\D1FS_3215-M2.doc D*1FS_(20-3215-M2Ersatzteilliste / Spare Parts ListProp.-Wegeventile / Prop.-DC ValvesD*1FS_(20Bestellcode\\De-kaa-nt-pdm\DTP\Ersatzteillisten\relevantSiegel0400\3215\D1FS_3215-M2.doc D*1FS_(20-3215-M2Ersatzteilliste / Spare Parts ListProp.-Wegeventile / Prop.-DC ValvesD*1FS_(20Ordering Code\\De-kaa-nt-pdm\DTP\Ersatzteillisten\relevantSiegel0400\3215\D1FS_3215-M2.doc D*1FS_(20-3215-M2Ersatzteilliste / Spare Parts ListProp.-Wegeventile / Prop.-DC ValvesD*1FS_(20Überblick Prop.-Ventil D*1FS / Overview prop.-valve D*1FS\\De-kaa-nt-pdm\DTP\Ersatzteillisten\relevantSiegel0400\3215\D1FS_3215-M2.docD*1FS_(20-3215-M2 Ersatzteilliste / Spare Parts List Ident-Nr Ident No Stck Qty Prop.-Wegeventile / Prop.-DC Valves D*1FS_(20 Bennenung Description Einsatz bei used at Pos Vorsteuerung (für alle Größen / Pilot valve (for all sizes 101D1FVE02BCVXW20 1 Vorsteuerung D*FS komplett Pilot valve D*FS complete Alle Größen All sizes Dichtungssätze / Seal kits 000 000 SK-D31FS-10 SK-D31FS-10 SK-D31FS-10V SK-D31FS-10V SK-D41FS-10 SK-D41FS-10 SK-D41FS-10V SK-D41FS-10V SK-D81FS-10 SK-D81FS-10 SK-D81FS-10V SK-D81FS-10V SK-D91FS-10 SK-D91FS-10 SK-D91FS-10V SK-D91FS-10V SK-D111FS-10 SK-D111FS-10 SK-D111FS-10V SK-D111FS-10V 1 1 Dichtungssatz BUNA N Seal kit complete BUNA N Dichtungssatz Fluorcarbon Seal kit complete Fluorocarbon Dichtungssatz BUNA N Seal kit complete BUNA N Dichtungssatz Fluorcarbon Seal kit complete Fluorocarbon Dichtungssatz BUNA N Seal kit complete BUNA N Dichtungssatz Fluorcarbon Seal kit complete Fluorocarbon Dichtungssatz BUNA N Seal kit complete BUNA N Dichtungssatz Fluorcarbon Seal kit complete Fluorocarbon Dichtungssatz BUNA N Seal kit complete BUNA N Dichtungssatz Fluorcarbon Seal kit complete Fluorocarbon NG10NG10 000 000 1 1 NG16 NG16 000 000 1 1 NG25 NG25 000 000 1 1 NG25 NG25 000 000 1 1 NG32 NG32 Positionskontrolle / Monitor switch (nur bei AusführungÜberdeckung / only with overlap-design D31/D41/D81/D91/ D111FS 859 5001762 1 ASEW001D09 Wegaufnehmer / Position transducer 869 5004108 1 AWEX020-D06 LVDT D31/D41/D81/D91/ D111FS \\De-kaa-nt-pdm\DTP\Ersatzteillisten\relevantSiegel0400\3215\D1FS_3215-M2.doc。
“初学者平台-USACO”的相关说明一、如何进入USACO平台1、直接在IE浏览器中键入网址/usacogate;2、如首次使用,请直接点击“Register here for a username/password”项,注册你的用户名和密码;否则,请输入用户名和密码(username/password)进行登陆。
二、可供题目(共100题左右,注意必须按顺序完成,否则将不能继续进行)Section 1.1.1PROB: Your Ride Is HerePROB: Greedy Gift GiversSection 1.1.2PROB: Broken NecklacePROB: Prime PalindromesPROB: The Errant PhysicistSection 1.1.3PROB: Mixing MilkPROB: Barn RepairPROB: What Time Is It?Section 1.1.4PROB: Checker ChallengePROB: SuperPrime RibPROB: Number TrianglesSection 1.2.1PROB: Shaping RegionsPROB: The CastlePROB: Ordered FractionsPROB: ContactSection 1.2.2PROB: Preface NumberingPROB: Runaround NumbersPROB: Money SystemsPROB: The Tamworth TwoPROB: Milking CowsSection 1.2.3PROB: OverfencingPROB: Bessie Come HomePROB: The ClocksPROB: Fractions to DecimalsSection 1.2.4PROB: Score InflationPROB: Mother's MilkPROB: Name That NumberPROB: Humble NumbersPROB: Palindromic SquaresPROB: FactorialsPROB: StringsobitsPROB: Prime CryptarithmPROB: Sorting A Three-Valued Sequence Section 1.3.1PROB: Riding The FencesPROB: Party LampsPROB: Dual PalindromesSection 1.3.2PROB: Agri-NetPROB: Home on the RangePROB: Calf FlacPROB: A GameSection 1.3.3PROB: CamelotPROB: Friday the ThirteenthPROB: Packing RectanglesPROB: Zero SumPROB: Controlling CompaniesSection 1.3.4PROB: Closed FencesPROB: Cow ToursPROB: American HeritagePROB: TransformationsSection 1.4.1PROB: Beef McNuggetsPROB: Fence RailsPROB: Fence LoopsPROB: CryptcowgraphyPROB: Arithmetic Progressions Section 1.4.2PROB: Drainage DitchesPROB: The Perfect StallPROB: Buy Low, Buy LowerPROB: Job ProcessingPROB: Frame UpSection 1.4.3PROB: The PrimesPROB: The Longest PrefixPROB: CowcyclesPROB: Shopping OffersPROB: Street RacePROB: Spinning WheelsPROB: Feed RatiosPROB: Shuttle PuzzlePROB: Magic SquaresPROB: Pollutant Control Section 1.5.1PROB: Healthy HolsteinsPROB: Subset SumsPROB: Starry NightPROB: All Latin Squares Section 1.5.2PROB: Fencing the CowsPROB: Canada TourSection 1.5.3PROB: Snail TrailPROB: PicturePROB: Window AreaPROB: Electric FencesPROB: Wisconsin SquaresPROB: Hamming Codes Section 1.5.4PROB: Avoiding Les EntarteursPROB: Map LabellingPROB: Milk MeasuringPROB: Network of SchoolsPROB: Big BarnSection 1.5.5PROB: StampsPROB: The CirclePROB: Character RecognitionPROB: Electric FencePROB: Betsy's TourPROB: TeleCowmunicationPROB: Wires and Switches Section 1.5.6PROB: Cow ScansPROB: PolygonPROB: Musical ThemesPROB: Raucous RockersPROB: Amazing BarnPROB: Letter Game。
Wizard1.单调队列优化①土地并购(Land Acquisition,2008Mar)②干草塔(Tower of Hay,2009Open)③又买饲料(Buying Feed,2010Nov)④玉米实验(Cornfields,2003Mar)⑤修剪草坪(Mowing the Lawn,2011Open)2.树型①焊接(Soldering,2011Open)②产奶比赛(Milk Team Select,2006Mar)③道路重建(Rebuilding Roads,Feb2002)④手机网络(Cell Phone Network,2008Jan)3.背包问题续①电子游戏(Video Game Troubles,2009Dec)②最少找零(The Fewest Coins,2006Dec)③三个代表(Jersey Politics,2005Feb)④录制唱片(Raucous Rockers,1996Qualifying Round)4.背包问题①股票市场(Stock Market,2009Feb)②奶牛会展(Cow Exhibition,2003Fall)③太空电梯(Space Elevator,2005Mar)④平分子集(Subset Sums,1998Spring)5.区间型①提交作业(Turning in Homework,2004Open)②抢鲜草(Grazing on the Run,2005Nov)③最优回文(Cheapest Palindrome,2007Open)④智取金币(Treasure Chest,2010Dec)6.其他一①打扫食槽(Cleaning Up,2009Mar)②奶牛自行车队(Cow Cycling,Feb2002)③滑雪缆车(Ski Lift,2006Mar)④奶牛飞盘队(Cow Frisbee Team,2009Mar)7.其他二①滑雪比赛(Bobsledding,2009Dec)②滑雪课程(Ski Lessons,2009Open)③方形牛棚(Big Barn,1997Fall)④接住苹果(Apple Catching,2004Nov)⑤公司利润(Profits,2011Jan)土地并购(Land Acquisition,2008Mar)首先我们按长与宽都递减の排序,如果有一个矩形长宽都不如另一个矩形,那么可以忽略它。
arico注塑机电脑说明书1.设备启动。
机器总电源开启,将开关OFF调至ON位置开启电源时观察是否在维修。
2.马达启动。
在注塑机操作面板上找到马达启动按钮,按下听到启动声音松开。
操作显示屏显示马达启动失败时,观察后安全门是否关闭及联系工务人员处理。
手动指示灯亮方可作动。
3.电热启动。
在注塑机操作面板上找到电热启动按钮,观察指示灯亮后松开按钮。
开启时注意是否有异音。
4.模具电热启动。
在温控箱左侧将电源开关OFF调至ON位置,再将各点20A漏电开关OFF调至ON位置。
20A漏电开关开启,目视保险丝是否损坏(底座指示灯亮保险丝已坏),手动指示灯亮方可作动。
5.模具温控箱参数温度设定。
按SET键显示器上出现光标,实际在(个、十、百)上,再使用调整设定温度,设定完成后按SET键复位。
按SET键不得超过5秒时间。
6.开、关模参数设定,及开、关模作动。
在手动状态下,按F2键显示屏转换为开、关模参数设定界面。
(1)行程设定:使用键移至此框,按数字键输入总行程长度,最后按Y键确认。
(2)开、合模压力设定:0-140KG/CM2。
(3)开、合模速度设定:0-99%。
(4)终止位置:0.0-最大开模行程(MM)。
(5)关模快速与开模连动不使用。
(6)手动状态下,按,为开模作动。
(7)手动状态下,按,为合模作动。
(8)合模:A.第一段压力、速度、终止位置设定,为控制开关模起动之震动程度,压力、速度可调小。
B.第二段压力、速度使模具快速合模,缩短合模时间,可调大。
C.低压设定为减少合模带来的冲击力,可调小。
D.高压设定为克服高压力,压力可调高,速度慢之。
(9)开模:A.一慢为克服高压合模压力,开模压力速度要大于合模压力速度。
B.一段为快速段,可调大。
C.二段为减轻高速开模带来的速度,可调小之。
D.二慢为控制开模位置误差值,调小压力速度。
7.中子参数设定及进、退作动图片上的参数是虚拟值,不可使用在状态显示界面手动模式下,按F5键显示屏转换为中子界面。
§4 工艺及器件仿真工具SILVACO-TCAD本章将向读者介绍如何使用SILV ACO公司的TCAD工具ATHENA来进行工艺仿真以及A TLAS来进行器件仿真。
假定读者已经熟悉了硅器件及电路的制造工艺以及MOSFET 和BJT的基本概念。
4.1 使用ATHENA的NMOS工艺仿真4.1.1 概述本节介绍用A THENA创建一个典型的MOSFET输入文件所需的基本操作。
包括:a. 创建一个好的仿真网格b. 演示淀积操作c. 演示几何刻蚀操作d. 氧化、扩散、退火以及离子注入e. 结构操作f. 保存和加载结构信息4.1.2 创建一个初始结构1定义初始直角网格a. 输入UNIX命令:deckbuild-an&,以便在deckbuild交互模式下调用A THENA。
在短暂的延迟后,deckbuild主窗口将会出现。
如图 4.1所示,点击File目录下的Empty Document,清空DECKBUILD文本窗口;图4.1 清空文本窗口b. 在如图4.2所示的文本窗口中键入语句go Athena ;图4.2 以“go athena”开始接下来要明确网格。
网格中的结点数对仿真的精确度和所需时间有着直接的影响。
仿真结构中存在离子注入或者形成PN结的区域应该划分更加细致的网格。
c. 为了定义网格,选择Mesh Define菜单项,如图4.3所示。
下面将以在0.6μm×0.8μm 的方形区域内创建非均匀网格为例介绍网格定义的方法。
图4.3 调用ATHENA网格定义菜单2 在0.6μm×0.8μm的方形区域内创建非均匀网格a. 在网格定义菜单中,Direction(方向)栏缺省为X;点击Location(位置)栏并输入值0;点击Spacing(间隔)栏并输入值0.1;b. 在Comment(注释)栏,键入“Non-Uniform Grid(0.6um x 0.8um)”,如图4.4所示;c. 点击insert键,参数将会出现在滚动条菜单中;图4.4 定义网格参数图 4.5 点击Insert键后d. 继续插入X方向的网格线,将第二和第三条X方向的网格线分别设为0.2和0.6,间距均为0.01。
USACO竞赛的流程大致如下:
1.在竞赛开放期间,选手需要进入竞赛页面参与比赛。
点击“Start the Contest!”键即
可开始比赛。
选手的比赛用时就会立即倒计时,且无法暂停。
2.进入题目页面后,选手可以点击标题查看相应题目并提交程序。
对于尚未提交的试题,
封面页会对应显示“Not submitted”。
对于已经提交的试题,封面页会对应显示“Submitted and Graded”。
3.选手需要按要求在自己的编程环境中完成题目,并提交cpp文件。
比赛会在时限过后自
动结束(如已经获得满分,则可以手动提前结束),只需在比赛结束前确保提交过已经完成的题目即可。
4.代码提交后,系统会自动给出评分,如果拿到了满分,系统会提示直接晋级。
如果没有
拿到满分,需要等待官方公布晋级分数线,每场月赛结束后一周内,官方会通过电子邮箱发放参赛选手的程序的评测结果。
成功晋级就可以在下一场月赛中参加更高级别的竞赛,没有成功晋级只能在下一场月赛中继续在原组别中打比赛。
我的usaco 总结Personalized Curriculum for Leo Kan; Last visit: 12 hours agoCongratulations! You have finished all available material.Chapter 1 DONE 2008.03.16 Getting startedChapter 2 DONE 2008.01.30 Bigger ChallengesChapter 3 DONE 2008.02.15 Techniques more subtleChapter 4 DONE 2008.03.09 Advanced algorithms and difficult drillsChapter 5 DONE 2008.04.04 Serious challengesChapter 6 DONE 2008.04.03 Contest Practice花了几个月时间,做完了USACO,感觉收获很大.做USACO之前和做USACO之后我感觉我的能力有很大的提升.USACO这个题库是一个完全适合信息学竞赛初学者的题库,它里面的内容由浅至难,很"经典"的一题Your Ride Is Here是只要会编程就能做的题目.接下来的内容可以使你掌握信息学竞赛中一些基本的也是很必要的算法和数据结构.如果只是想参加noip的话做完4甚至还不用就有拿奖的水平了(noip甚至连网络流,几何都不考)Chapter 1,正如它的标题所言Getting started,如果你只会编程而想踏入竞赛的门槛的话,做完Getting started,你就能对什么是竞赛有一点认识了.涉及基础的贪心,动态规划,搜索,模拟.特别需要提一下的我觉得是Checker Challenge 如果不用位运算那么它的剪枝有很大的技巧,很有启发性.另外Packing Rectangles是一道极度繁琐的题目,不考什么技巧,就考是否细心,如果是初学者很有必要练习一下,不是的话可以直接pass.DONE 2007.10.25 TEXT IntroductionSection 1.1 DONE 2008.03.16 TEXT Submitting SolutionsDONE 2007.10.26 PROB Your Ride Is Here [ANALYSIS] 无聊题DONE 2007.10.26 TEXT Contest Problem TypesDONE 2007.10.26 TEXT Ad Hoc ProblemsDONE 2007.10.26 PROB Greedy Gift Givers [ANALYSIS] 模拟DONE 2007.10.27 PROB Friday the Thirteenth [ANALYSIS] 模拟DONE 2007.10.27 PROB Broken Necklace [ANALYSIS] 枚举or动态规划Section 1.2 DONE 2007.10.27 TEXT Complete SearchDONE 2007.12.30 PROB Milking Cows [ANALYSIS] 贪心DONE 2007.12.30 PROB Transformations [ANALYSIS] 模拟DONE 2007.12.31 PROB Name That Number [ANALYSIS] 模拟DONE 2007.12.31 PROB Palindromic Squares [ANALYSIS] 模拟DONE 2007.12.31 PROB Dual Palindromes [ANALYSIS] 模拟Section 1.3 DONE 2007.12.31 TEXT Greedy AlgorithmDONE 2007.12.31 PROB Mixing Milk [ANALYSIS] 标准解法该是线段覆盖或线段树吧,但是作为chapter1 的题可以试试模拟DONE 2007.12.31 PROB Barn Repair [ANALYSIS] 贪心DONE 2007.12.31 TEXT Winning SolutionsDONE 2008.01.01 PROB Calf Flac [ANALYSIS] 枚举DONE 2008.01.01 PROB Prime Cryptarithm [ANALYSIS] 枚举Section 1.4 DONE 2008.01.01 TEXT More Search TechniquesDONE 2008.01.25 PROB Packing Rectangles [ANALYSIS] 模拟DONE 2008.01.14 PROB The Clocks [ANALYSIS] 搜索or枚举还有一种数学方法的 DONE 2008.01.25 PROB Arithmetic Progressions [ANALYSIS] 枚举DONE 2008.01.04 PROB Mother's Milk [ANALYSIS] 搜索Section 1.5 DONE 2008.01.25 TEXT Introduction to Binary NumbersDONE 2008.01.25 PROB Number Triangles [ANALYSIS] 动态规划DONE 2008.01.26 PROB Prime Palindromes [ANALYSIS] 枚举DONE 2008.01.26 PROB SuperPrime Rib [ANALYSIS] 枚举DONE 2008.01.26 PROB Checker Challenge [ANALYSIS] 搜索Chapter 2,它涉及一些算法了,比较基础的就是最短路径的Bessie Come Home,还有很大一部分是练习编程技巧的,其中一个比较实用的—位运算.Section 2.1 DONE 2008.01.26 TEXT Graph TheoryDONE 2008.01.26 TEXT Flood Fill AlgorithmsDONE 2008.01.27 PROB The Castle [ANALYSIS] Flood FillDONE 2008.01.27 PROB Ordered Fractions [ANALYSIS] 枚举or递归DONE 2008.01.27 PROB Sorting A Three‐Valued Sequence [ANALYSIS] 贪心DONE 2008.01.27 PROB Healthy Holsteins [ANALYSIS] 搜索DONE 2008.01.27 PROB Hamming Codes [ANALYSIS] 枚举(位运算)Section 2.2 DONE 2008.01.27 TEXT Data StructuresDONE 2008.01.27 TEXT Dynamic ProgrammingDONE 2008.01.28 PROB Preface Numbering [ANALYSIS] 模拟DONE 2008.01.28 PROB Subset Sums [ANALYSIS] 动态规划DONE 2008.01.28 PROB Runaround Numbers [ANALYSIS] 模拟DONE 2008.01.28 PROB Party Lamps [ANALYSIS] 枚举(位运算)Section 2.3 DONE 2008.01.28 PROB The Longest Prefix [ANALYSIS] 动态规划 DONE 2008.01.29 PROB Cow Pedigrees [ANALYSIS] 动态规划DONE 2008.01.29 PROB Zero Sum [ANALYSIS] 搜索DONE 2008.01.29 PROB Money Systems [ANALYSIS] 动态规划(背包模型)DONE 2008.01.29 PROB Controlling Companies [ANALYSIS] 搜索Section 2.4 DONE 2008.01.29 TEXT Shortest PathsDONE 2008.01.30 PROB The Tamworth Two [ANALYSIS] 搜索DONE 2008.01.30 PROB Overfencing [ANALYSIS] 搜索DONE 2007.11.25 PROB Cow Tours [ANALYSIS] 最短路DONE 2007.11.03 PROB Bessie Come Home [ANALYSIS] 最短路DONE 2008.01.30 PROB Fractions to Decimals [ANALYSIS] 模拟Chapter 3,更多的算法,最小生成树的Agri‐Net,欧拉回路的Riding The Fences, Sweet Butter这一题是最短路径,不过这题完全可以作为从初级图论题到中级图论题的一个过渡,需要用到bellman‐ford或SPFA,当然heap dijkstra也可以,再高级的Chapter 3的程度还未到,可以先不学.Home on the Range这题的动态规划是USACO 从Chapter1 开始以来新的一种动态规划方式,是在一个矩阵中判断一个位置和附近位置关系得到的状态转移方程. Feed Ratios这题可以枚举,但是有更好的方法(高斯消元,克莱姆法则…关于克莱姆法则请参见附录).closed fences是USACO的第一道几何题,详细题解看附录.Section 3.1 DONE 2008.01.30 TEXT Minimal Spanning TreesDONE 2007.11.03 PROB Agri‐Net [ANALYSIS] MSTDONE 2008.01.31 PROB Score Inflation [ANALYSIS] 动态规划DONE 2008.01.31 PROB Humble Numbers [ANALYSIS] 枚举DONE 2008.01.31 PROB Shaping Regions [ANALYSIS] 线段树or矩形覆盖DONE 2008.02.01 PROB Contact [ANALYSIS] 模拟DONE 2008.02.01 PROB Stamps [ANALYSIS] 动态规划(背包模型)Section 3.2 DONE 2008.02.01 TEXT Knapsack ProblemsDONE 2007.12.02 PROB Factorials [ANALYSIS] 可以用错误方法(保留部分位)过这题,但是这样做是错误的,仅仅对于小数据有效,正确方法是统计2和5 的个数然后计算DONE 2008.02.01 PROB Stringsobits [ANALYSIS] 康托展开DONE 2008.02.02 PROB Spinning Wheels [ANALYSIS] 模拟DONE 2007.11.19 PROB Feed Ratios [ANALYSIS] 枚举or高斯消元or克莱姆法则 DONE 2008.02.02 PROB Magic Squares [ANALYSIS] 搜索DONE 2008.02.05 PROB Sweet Butter [ANALYSIS] 最短路Section 3.3 DONE 2008.02.05 TEXT Eulerian ToursDONE 2008.02.05 PROB Riding The Fences [ANALYSIS] 欧拉路DONE 2008.02.08 PROB Shopping Offers [ANALYSIS] 动态规划(背包模型)DONE 2008.02.09 PROB Camelot [ANALYSIS] 搜索+贪心DONE 2008.02.09 PROB Home on the Range [ANALYSIS] 动态规划DONE 2008.02.09 PROB A Game [ANALYSIS] 动态规划Section 3.4 DONE 2008.02.12 TEXT Computational GeometryDONE 2008.02.12 PROB Closed Fences [ANALYSIS] 几何DONE 2007.11.22 PROB American Heritage [ANALYSIS] 递归,经典,入门必做 DONE 2008.02.15 PROB Electric Fence [ANALYSIS] pick公式(其实直接枚举效率更高且简单)DONE 2008.02.15 PROB Raucous Rockers [ANALYSIS] 动态规划(背包模型)Chapter 4,可以找到一点点竞赛感觉了…算法方面有网络流Drainage Ditches,二分图最大匹配The Perfect Stall,很多经典问题,例如Pollutant Control的求最小割集. Chapter 4的每一题都很有价值,对于初学者能长很多经验的比如dfsid这种搜索技巧.Section 4.1 DONE 2008.02.18 TEXT Optimization TechniquesDONE 2008.02.19 PROB Beef McNuggets [ANALYSIS] 动态规划+枚举DONE 2008.03.01 PROB Fence Rails [ANALYSIS] 搜索(dfsid)DONE 2008.02.20 PROB Fence Loops [ANALYSIS] 最小环(它给出的是边的联通关系而不是点的联通关系)对于这种需要自己构图的题目可以用搜索.DONE 2008.02.22 PROB Cryptcowgraphy [ANALYSIS] 搜索+elfhashSection 4.2 DONE 2008.03.01 TEXT "Network Flow" AlgorithmsDONE 2008.02.22 PROB Drainage Ditches [ANALYSIS] 网络流DONE 2007.12.11 PROB The Perfect Stall [ANALYSIS] 二分图匹配DONE 2008.03.02 PROB Job Processing [ANALYSIS] 动态规划+贪心DONE 2008.03.02 PROB Cowcycles [ANALYSIS] 搜索Section 4.3 DONE 2008.03.03 TEXT Big NumbersDONE 2007.12.02 PROB Buy Low, Buy Lower [ANALYSIS] 动态规划(最长不下降子序列)DONE 2008.03.05 PROB The Primes [ANALYSIS] 搜索,优化可以很多的,很有趣味性 DONE 2008.03.07 PROB Street Race [ANALYSIS] 求割点,搜索DONE 2008.03.07 PROB Letter Game [ANALYSIS] 枚举,我觉得它主要考预处理,预处理后其实只需枚举几十个Section 4.4 DONE 2008.03.07 PROB Shuttle Puzzle [ANALYSIS]DONE 2008.03.08 PROB Pollutant Control [ANALYSIS] 最小割DONE 2008.03.09 PROB Frame Up [ANALYSIS] 拓扑排序Chapter 5,很耐人寻味的一个章节,全是好题Section 5.1 DONE 2008.03.14 TEXT Convex HullsDONE 2008.03.11 PROB Fencing the Cows [ANALYSIS] 凸包DONE 2008.03.14 PROB Starry Night [ANALYSIS] flood fillDONE 2008.03.15 PROB Musical Themes [ANALYSIS] 动态规划or枚举Section 5.2 DONE 2008.03.16 PROB Snail Trail [ANALYSIS] 搜索DONE 2008.03.16 PROB Electric Fences [ANALYSIS] 几何DONE 2008.03.17 PROB Wisconsin Squares [ANALYSIS] 搜索,数据结构上如果用表能有很好的效果Section 5.3 DONE 2008.03.19 TEXT Heuristics & Approximate SearchesDONE 2008.03.20 PROB Milk Measuring [ANALYSIS] 动态规划or dfsid+动态规划/dfs(用dfs对于这题数据能有很好的效果0s出解)DONE 2008.03.21 PROB Window Area [ANALYSIS] 模拟+矩形覆盖DONE 2008.03.22 PROB Network of Schools [ANALYSIS] 图的连通性DONE 2008.03.22 PROB Big Barn [ANALYSIS] 动态规划Section 5.4 DONE 2008.03.23 PROB All Latin Squares [ANALYSIS] 搜索or错排(数学性很强,推广很难)DONE 2008.03.25 PROB Canada Tour [ANALYSIS] 网络流or动态规划DONE 2008.04.04 PROB Character Recognition [ANALYSIS] 统计+动态规划DONE 2008.03.28 PROB Betsy's Tour [ANALYSIS] 搜索DONE 2008.03.29 PROB TeleCowmunication [ANALYSIS] 最小割Section 5.5 DONE 2008.03.30 PROB Picture [ANALYSIS] 线段树DONE 2008.03.30 PROB Hidden Passwords [ANALYSIS] 枚举+KMP思想优化 DONE 2008.04.04 PROB Two Five [ANALYSIS] 搜索+康托展开Chapter 6,只有几题Section 6.1 DONE 2008.04.01 PROB Postal Vans [ANALYSIS] 动态规划DONE 2008.04.02 PROB A Rectangular Barn [ANALYSIS] 动态规划DONE 2008.04.03 PROB Cow XOR [ANALYSIS] 枚举+优化Usaco 总结 lzoi leokan /leokan附录一:题解索引Section2.1 DONE 2008.01.26 TEXT Graph TheoryDONE 2008.01.26 TEXT Flood Fill AlgorithmsDONE 2008.01.27 PROB The Castle [ANALYSIS]Section 1.0 DONE 2007.10.25(1.1的题目程序丢了,不必看1.1的题解)Section 1.1 DONE 2008.03.16TEXT Submitting SolutionsDONE 2007.10.26PROB Your Ride Is Here [ANALYSIS]DONE 2007.10.26TEXT Contest Problem TypesDONE 2007.10.26TEXT Ad Hoc ProblemsDONE 2007.10.26PROB Greedy Gift Givers [ANALYSIS]DONE 2007.10.27PROB Friday the Thirteenth [ANALYSIS]DONE 2007.10.27PROB Broken Necklace [ANALYSIS]Section 1.2 DONE 2007.10.27TEXT Complete SearchDONE 2007.12.30PROB Milking Cows [ANALYSIS]DONE 2007.12.30PROB Transformations [ANALYSIS]DONE 2007.12.31PROB Name That Number [ANALYSIS]DONE 2007.12.31PROB Palindromic Squares [ANALYSIS]DONE 2007.12.31PROB Dual Palindromes [ANALYSIS]Section 1.3 DONE 2007.12.31TEXT Greedy AlgorithmDONE 2007.12.31PROB Mixing Milk [ANALYSIS]DONE 2007.12.31PROB Barn Repair [ANALYSIS]DONE 2007.12.31TEXT Winning SolutionsDONE 2008.01.01PROB Calf Flac [ANALYSIS]DONE 2008.01.01PROB Prime Cryptarithm [ANALYSIS]Section 1.4 DONE 2008.01.01TEXT More Search TechniquesDONE 2008.01.25PROB Packing Rectangles [ANALYSIS]DONE 2008.01.14PROB The Clocks [ANALYSIS]DONE 2008.01.25PROB Arithmetic Progressions [ANALYSIS]DONE 2008.01.04PROB Mother's Milk [ANALYSIS]Section 1.5 DONE 2008.01.25TEXT Introduction to Binary NumbersDONE 2008.01.25PROB Number Triangles [ANALYSIS]DONE 2008.01.26PROB Prime Palindromes [ANALYSIS]DONE 2008.01.26PROB SuperPrime Rib [ANALYSIS]DONE 2008.01.26PROB Checker Challenge [ANALYSIS]DONE 2008.01.27 PROB Ordered Fractions [ANALYSIS]DONE 2008.01.27 PROB Sorting A Three-Valued Sequence [ANALYSIS]DONE 2008.01.27 PROB Healthy Holsteins [ANALYSIS]DONE 2008.01.27 PROB Hamming Codes [ANALYSIS]Section2.2 DONE 2008.01.27 TEXT Data StructuresDONE 2008.01.27 TEXT Dynamic ProgrammingDONE 2008.01.28 PROB Preface Numbering [ANALYSIS]DONE 2008.01.28 PROB Subset Sums [ANALYSIS]DONE 2008.01.28 PROB Runaround Numbers [ANALYSIS]DONE 2008.01.28 PROB Party Lamps [ANALYSIS]Section2.3 DONE 2008.01.28 PROB The Longest Prefix [ANALYSIS]DONE 2008.01.29 PROB Cow Pedigrees [ANALYSIS]DONE 2008.01.29 PROB Zero Sum [ANALYSIS]DONE 2008.01.29 PROB Money Systems [ANALYSIS]DONE 2008.01.29 PROB Controlling Companies [ANALYSIS]Section2.4 DONE 2008.01.29 TEXT Shortest Paths DONE 2008.01.30 PROB The Tamworth Two [ANALYSIS]DONE 2008.01.30 PROB Overfencing [ANALYSIS]DONE 2007.11.25 PROB Cow Tours [ANALYSIS]DONE 2007.11.03 PROB Bessie Come Home [ANALYSIS]DONE 2008.01.30 PROB Fractions to Decimals [ANALYSIS]Section 3.1 DONE 2008.01.30TEXT Minimal Spanning TreesDONE 2007.11.03PROB Agri-Net [ANALYSIS]DONE 2008.01.31PROB Score Inflation [ANALYSIS]DONE 2008.01.31PROB Humble Numbers [ANALYSIS]DONE 2008.01.31PROB Shaping Regions [ANALYSIS]DONE 2008.02.01PROB Contact [ANALYSIS]DONE 2008.02.01PROB Stamps [ANALYSIS]Section 3.2 DONE 2008.02.01TEXT Knapsack ProblemsDONE 2007.12.02PROB Factorials [ANALYSIS]DONE 2008.02.01PROB Stringsobits [ANALYSIS]DONE 2008.02.02PROB Spinning Wheels [ANALYSIS]DONE 2007.11.19PROB Feed Ratios [ANALYSIS]DONE 2008.02.02PROB Magic Squares [ANALYSIS](程序丢了)DONE 2008.02.05PROB Sweet Butter [ANALYSIS]Section 3.3 DONE 2008.02.05TEXT Eulerian ToursDONE 2008.02.05PROB Riding The Fences [ANALYSIS]DONE 2008.02.08PROB Shopping Offers [ANALYSIS]DONE 2008.02.09PROB Camelot [ANALYSIS]DONE 2008.02.09PROB Home on the Range [ANALYSIS]DONE 2008.02.09PROB A Game [ANALYSIS]Section 3.4 DONE 2008.02.12TEXT Computational GeometryDONE 2008.02.12PROB Closed Fences [ANALYSIS]DONE 2007.11.22PROB American Heritage [ANALYSIS]DONE 2008.02.15PROB Electric Fence [ANALYSIS]DONE 2008.02.15PROB Raucous Rockers [ANALYSIS]Section 4.1 DONE 2008.02.18 TEXT Optimization TechniquesDONE 2008.02.19 PROB Beef McNuggets [ANALYSIS]DONE 2008.03.01 PROB Fence Rails [ANALYSIS]DONE 2008.02.20 PROB Fence Loops [ANALYSIS]DONE 2008.02.22 PROB Cryptcowgraphy [ANALYSIS]Section 4.2 DONE 2008.03.01 TEXT "Network Flow" AlgorithmsDONE 2008.02.22 PROB Drainage Ditches [ANALYSIS]DONE 2007.12.11 PROB The Perfect Stall [ANALYSIS]DONE 2008.03.02 PROB Job Processing [ANALYSIS]DONE 2008.03.02 PROB Cowcycles [ANALYSIS]Section 4.3 DONE 2008.03.03 TEXT Big NumbersDONE 2007.12.02 PROB Buy Low, Buy Lower [ANALYSIS]DONE 2008.03.05 PROB The Primes [ANALYSIS]DONE 2008.03.07 PROB Street Race [ANALYSIS]DONE 2008.03.07 PROB Letter Game [ANALYSIS]Section 4.4 DONE 2008.03.07 PROB Shuttle Puzzle [ANALYSIS]DONE 2008.03.08 PROB Pollutant Control [ANALYSIS]DONE 2008.03.09 PROB Frame Up [ANALYSIS]Section 5.1 DONE 2008.03.14 TEXT Convex HullsDONE 2008.03.11 PROB Fencing the Cows [ANALYSIS]DONE 2008.03.14 PROB Starry Night [ANALYSIS]DONE 2008.03.15 PROB Musical Themes [ANALYSIS]Section 5.2 DONE 2008.03.16 PROB Snail Trail [ANALYSIS]DONE 2008.03.16 PROB Electric Fences [ANALYSIS]DONE 2008.03.17 PROB Wisconsin Squares [ANALYSIS]Section 5.3 DONE 2008.03.19 TEXT Heuristics & Approximate Searches DONE 2008.03.20 PROB Milk Measuring [ANALYSIS]DONE 2008.03.21 PROB Window Area [ANALYSIS]DONE 2008.03.22 PROB Network of Schools [ANALYSIS]DONE 2008.03.22 PROB Big Barn [ANALYSIS]Section 5.4 DONE 2008.03.23 PROB All Latin Squares [ANALYSIS]DONE 2008.03.25 PROB Canada Tour [ANALYSIS]DONE 2008.04.04 PROB Character Recognition [ANALYSIS]DONE 2008.03.28 PROB Betsy's Tour [ANALYSIS]DONE 2008.03.29 PROB TeleCowmunication [ANALYSIS]Section 5.5 DONE 2008.03.30 PROB Picture [ANALYSIS]DONE 2008.03.30 PROB Hidden Passwords [ANALYSIS]DONE 2008.04.04 PROB Two Five [ANALYSIS]Section 6.1 DONE 2008.04.01 PROB Postal Vans [ANALYSIS]DONE 2008.04.02 PROB A Rectangular Barn [ANALYSIS]DONE 2008.04.03 PROB Cow XOR [ANALYSIS]附录二:我写得比较详细的题解 USACO 3.1.4 Shaping Regions阅读了资料:薛矛的集训队论文参考了的方法:《信息学奥林匹克竞赛典型试题剖析》中的noi 97 年卫星覆盖解法,卫星覆盖是立体的立方体覆盖,它的退化就是矩形覆盖。
武藏控制器操作方法
武藏控制器是一种用于工业自动化和机器人控制的设备,其操作方法可以简单描述如下:
1. 首先,将武藏控制器与要控制的设备或机器人连接,并进行电源接入。
2. 打开武藏控制器的控制软件,选取合适的驱动器和控制参数。
通常需要根据具体情况进行调整。
3. 设置运动模式,例如选择点位控制或连续控制模式。
4. 编写程序或命令来实现所需的运动控制。
可以使用武藏控制器自带的编程软件或其他编程工具。
5. 对武藏控制器进行测试和调试,确保控制效果符合要求。
需要注意的是,由于武藏控制器的操作和编程比较复杂,一般需要专业的技术人员进行操作,特别是当控制的机器人或设备比较大型复杂时。
上海交通大学马融2009 年暑假集训讲义2009 年暑假集训讲义上海交通大学马融第一讲穷举与贪心 (3)集市班车(Fair Shuttle, USACO 2009 Feb) (4)翻转棋(Fliptile, USACO 2007 Nov) (5)翻转奶牛(Face The Right Way, USACO 2007 Mar) (6)第二讲背包问题 (7)分数膨胀(Score Inflation, USACO 3.1) (8)货币系统(Money Systems, USACO 2.3) (9)奶牛博览会(Cow Exhibition, USACO 2003 Nov) (10)太空电梯(Space Elevator, USACO 2005 Mar) (11)牛奶量取(Milk Measuring, USACO 5.3) (12)第三讲动态规划选讲 (13)抓苹果(Apple Catching, USACO 2004 Nov) (15)最廉回文(Cheapest Palindrome, USACO 2007 Open) (17)麦香牛块(Beef McNuggets, USACO 4.1) (19)道路重建(Rebuilding Roads, USACO Feb 2002) (20)第四讲最小生成树问题 (22)建造道路(Building Roads, USACO 2007 Dec) (23)安慰奶牛(Cheering up the Cows, USACO 2008 Nov) (24)地震(Earthquake, USACO 2001 Open) (26)第五讲最短路径问题 (28)道路翻新(Revamping Trails, USACO 2009 Feb) (29)道路障碍(Roadblocks, USACO 2006 Nov) (31)奶牛慢跑(Cow Jogging, USACO 2008 Mar) (33)第六讲广度优先遍历 (35)青铜莲花池(Bronze Lilypad Pond, USACO 2007 Feb) (36)白银莲花池(Silver Lilypad Pond, USACO 2007 Feb) (37)黄金莲花池(Lilypad Pond, USACO 2007 Feb) (39)第七讲USACO 竞赛试题选讲 (41)哞哞大学之奖学金(Moo University - Financial Aid, USACO 2004 Mar) (42)哞哞大学之校队选拔(Moo University - Team Tryouts, USACO 2004 Mar) (44)哞哞大学之匹萨预定(Moo University - Emergency Pizza Order, USACO 2004 Mar) (46)第八讲USACO 竞赛试题选讲(续) (48)黄金平衡(USACO 2007 Mar) (49)奶牛排名(Ranking the Cows, USACO 2007 Mar) (50)奶牛交通(Cow Traffic, USACO 2007 Mar) (51)校庆聚会(Ural 1039) (52)第九讲线段树 (54)上海交通大2009 年暑假集训讲义USACO 题目中常见的单词:上海交通大学马融第一讲穷举与贪心集市班车(Fair Shuttle, USACO 2009 Feb)逛逛集市,兑兑奖品,看看节目对农夫约翰来说不算什么,可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市,他们一定会筋疲力尽的。
我的USACO总结Congratulations!You have finished all available material.Chapter1DONE2008.12.16Getting startedChapter2DONE2008.12.24Bigger ChallengesChapter3DONE2009.01.15Techniques more subtleChapter4DONE2009.02.03Advanced algorithms and difficult drillsChapter5DONE2009.02.17Serious challengesChapter6DONE2009.02.20Contest Practice花了差不多四个月把USACO做完了,感觉收获很大,它就像一个私人教练能督促你学习一样,对于一个oier来说,USACO绝对是一个不可不做的经典OJ,为了整理一下知识点也当是一次巩固,便写下了这篇总结,以总结一下自己的疏漏,也希望能帮助到别人。
--湖南南县一中czz一、枚举枚举是我们用的比较多的一种算法,编程简单是它的优点,而时间效率低则是它的致命缺点,不过很多题目通过合理的优化比如减小枚举量等来优化算法。
The Clocks是第一道需要优化的枚举题,首先由于这题有9个时钟,而且每个的移动次数也不清楚,似乎无从开始,不过经过研究发现对于一个时钟如果移动四次就会便相当于没有移动,因此我们只需要枚举每个钟的四种状态共9^4共6561种状态,这样就不会超时了,不过如果进一步研究这个题目发现移动方案之间是有约束的,打个比方,A时钟由三种移动方案确定,如果其中的两种方案的次数已经知道,那么第三种方案也就会确定,因此我们只要枚举前三个方案的次数其他的便可以递推出来,状态只有4^3个,效率无疑大大提高。
Arithmetic Progressions这题由于题目要求按b升序排列,所以我们习惯性得把b放在外循环而a放在内循环,这样做加上剪枝后也会超时,由于剪枝时按a 剪枝时力度无疑会更大,因此我们可以把a提到外循环,相应的加一个快排,因此我们得出一个结论:把剪枝有利的尽量放在外循环。
USACO教程Complete Search 枚举搜索思想:写枚举搜索时应遵循KISS原则(Keep it simple stupid,译为“写最单纯愚蠢的程序”,意思是应把程序写得尽量简洁),竞赛时写程序的最终目标就是在限制时间内求出解,而不需太在意否还有更快的算法。
枚举搜索具有强大的力量,他用直接面向答案并尝试所有方案的方法发现答案。
这种算法几乎总是解题时你第一个想到的方法。
如果它能在规定的时间与空间限制内找出解,那么它常常很容易编写与调试。
这就意味着你可以有时间去解答其他难题,即那些不能显示枚举算法强大的题目。
如果你面对一道可能状态小于两百万的题目,那么你可以考虑使用枚举搜索。
尝试所有的状态,看看它们是否可行。
小心!小心!有时,题目不会直接要求你使用枚举算法。
例题1:派对灯[IOI 98]在一次IOI派对上有N个灯和4个灯开光,第一个开关可以使所有灯改变状态(关上开着的灯,开启关着的灯),第二个开关可以改变所有偶数位上灯的状态,第三个开关可以改变所有奇数位上灯的状态,第四个开关控制着灯1、4、7、10……(3n+1)。
告诉你N的值和所有按开关的次数(小于10,000次)。
并告诉你某些灯的状态(例如:7号灯是关着的,10号灯是开着的)请编程输出所有灯可能的最后状态。
很明显,每次按开关你都要偿试4种可能。
那么总共要试410000 次(大约106020),那意味着你没有足够的时间去使用枚举搜索,但是我们将枚举方法改进一下,那就可以使用枚举了。
因为无论有多少个灯,由于开关控制的特殊性,都会出现6个灯一次循环的情况,即1号灯的状态永远与7号灯,13号灯,19号灯……相同,2号灯的状态也永远与8号灯,14号灯,20号灯……相同。
同样,无论你按了多少次开关,按同一个开关两次就相当于没有按该开关,那么每一个开关就只需要考虑按一次或没有按,那么这题的枚举量就很小了。
例题2: 时钟调整[IOI 94]有九个钟被摆放在一个3 X 3的矩阵中,它们各自指向12:00,9:00,6:00,3:00中的一种,你的目的是将它们的指针全部调向12:00。
很遗憾,每一次调整你都只能从九种调整方案中选择一种执行(九种方案已被从1到9编号),每一种方案可以改变固定钟的状态(例如:方案1控制钟1,2,3,方案2控制钟1,4,7,方案3控制钟5,6,8,9……),即将方案指定的所有钟向前拨快3小时(使时针向顺时针方向旋转90度),请你输出一个数列,使得按该数列表示方案执行后,所有钟都指向12:00。
并且如果把整个序列看作一个数,要求该数最小。
最容易想到的方法是用递归枚举1到9的方案在该步使用。
很可怕,由于递归的层数在此没有限定,所以将用掉9k 的时间(k为层数),那可能是相当巨大的。
其实,不用紧张,细心的你一定会发现:当一个方案执行4次后,就相当于没有执行,又因为题目要求输出最优解,那么任意一个方案都没有必要4次以上执行。
也就是说,只需要枚举每一个方案的4种情况(没执行,执行1,2,3次)就可以了。
他仅有49 ,约262,072此枚举,我们的计算机1s内就可以算完,应该算是极快了。
类似问题:挤牛奶[USACO 1996 初赛]给出一个挤牛奶的顺序(农夫A 在300 秒到1000秒时挤牛奶, 农夫B从700 秒到12 00秒),要求输出:最长的有人挤牛奶的时间。
最长的没人挤牛奶的时间。
完全数牛与完全数牛群[USACO 1995 决赛]如果一个数可以由它的某几个约数相加得到,那么我们叫它完全数,如28 = 1 + 2 + 4 + 7 + 14。
而一对完全对数就是指两个数都可以由对方的约数相加得出。
同样一个完全数组就是一个数组的第一个数可以由第二个数的约数加和得到,第二个数也可以由第三个数的约数相加得到……最后一个数可以由第一个数的约数加和得到。
现在Farmer John已经将它的牛儿们编好了号(1到32000)请找出其中所有的完全数牛与完全数牛群。
贪心算法样例:牛棚修理[1999 USACO 春季公开赛]Farmer John 有一列牛棚,在一次暴风中,牛棚的一整面墙都被吹倒了,但还好不是每一间牛棚都有牛。
Farmer John 决定卖木料来修理牛棚,然而,刻薄的木材提供商却只能提供有限块的木料(木料的长度不限),现在告诉你关着牛的牛棚号,和提供的木材个数N,你的任务是编程求出最小的木块长度和。
(1 <= N <= 50)贪心思想:贪心思想的本质是每次都形成局部最优解,换一种方法说,就是每次都处理出一个最好的方案。
例如:在样例中,若已经发现N = 5 时的最优解,那么我们可以直接利用N = 5 的最优解构成N = 4 的最优解,而不用去考虑那些N = 4 时的其他非最优解。
贪心算法的最大特点就是快。
通常,二次方级的存储要浪费额外的空间,而且很不幸,那些空间经常得不出正解。
但是,当使用贪心算法时,这些空间可以帮助算法更容易实现且更快执行。
贪心的难点:贪心算法有两大难点:如何贪心:怎样才能从众多可行解中找到最优解呢?其实,大部分都是有规律的。
在样例中,贪心就有很明显的规律。
但你得到了N = 5 时的最优解后,你只需要在已用上的5块木板中寻找最靠近的两块,然后贴上中间的几个牛棚,使两块木板变成一块。
这样生成的N = 4 的解必定最优。
因为这样木板的浪费最少。
同样,其他的贪心题也会有这样的性质。
正因为贪心有如此性质,它才能比其他算法要快。
贪心的正确性:要证明贪心性质的正确性,才是贪心算法的真正挑战,因为并不是每次局部最优解都会与整体最优解之间有联系,往往靠贪心生成的解不是最优解。
这样,贪心性质的证明就成了贪心算法正确的关键。
一个你想出的贪心性质也许是错的,即使它在大部分数据中都是可行的,你必须考虑到所有可能出现的特殊情况,并证明你的贪心性质在这些特殊情况中仍然正确。
这样经过千锤百炼的性质才能构成一个正确的贪心。
在样例中,我们的贪心性质是正确的。
如下:假设我们的答案盖住了较大的空牛棚连续列,而不是较小的。
那么我们把那部分盖空牛棚的木板锯下来,用来把较小的空牛棚连续列盖住,还会有剩余。
那么锯掉它们!还给木材商!同时我们的解也变小了。
也就是说,我们获得更优的解。
所以,靠盖住较大空牛棚连续列的方法无法获得最优解,我们也应该尽量贪心那些距离小的木板合并。
如果仍有一个空牛棚连续列与我们的答案盖住的那个相同,我们同样使用上述的方法。
会发现获得的新解与原解相同,那么不论我们选哪个,结果都将一样。
由此可见,如果我们合并的两块木板间距离最短,那么总能获得最优解。
所以,在解题的每一步中,我们都只需要寻找两块距离最小的木板并合并它们。
这样,我们获得的解必定最优。
结论:如果有贪心性质存在,那么一定要采用!因为它容易编写,容易调试,速度极快,并且节约空间。
几乎可以说,它是所有算法中最好的。
但是应该注意,别陷入证明不正确贪心性质的泥塘中无法自拔,因为贪心算法的适用范围并不大,而且有一部分极难证明,若是没有把握,最好还是不要冒险,因为还有其他算法会比它要保险。
类似问题:三值排序问题[IOI 1996]有一个由N个数值均为1、2或3的数构成的序列(N<= 1000),其值无序,现要求你用最少的交换次数将序列按升序顺序排列。
算法:排序后的序列分为三个部分:排序后应存储1的部分,排序后应存储2的部分和排序后应存储3的部分,贪心排序法应交换尽量多的交换后位置正确的(2,1)、(3,1)和(3,2)数对。
当这些数对交换完毕后,再交换进行两次交换后位置正确的(1,2,3)三个数。
分析:很明显,每一次交换都可以改变两个数的位置,若经过一次交换以后,两个数的位置都由错误变为了正确,那么它必定最优。
同时我们还可发现,经过两次交换后,我们可以随意改变3个数的位置。
那么如果存在三个数恰好为1,2和3,且位置都是错误的,那么进行两次交换使它们位置正确也必定最优。
有由于该题具有最优子结构性质,我们的贪心算法成立。
货币系统-- 一个反例[已删节]奶牛王国刚刚独立,王国中的奶牛们要求设立一个货币系统,使得这个货币系统最好。
现在告诉你一个货币系统所包含的货币面额种类(假设全为硬币)以及所需要找的钱的大小,请给出用该货币系统找出该钱数,并且要求硬币数尽量少。
算法:每次都选择面额不超过剩余钱数但却最大的一枚硬币。
例如:有货币系统为{1,2,5,10},要求找出16,那么第一次找出10,第二次找出5,第三次找出1,恰好为最优解。
错误分析: 其实可以发现,这种算法并不是每一次都能构成最优解。
反例如:货币系统{1,5,8,10},同样找16,贪心的结果是10,5,1三枚,但用两枚8的硬币才是最优解。
因为这样,贪心的性质不成立,如此解题也是错的。
拓扑排序给你一些物品的集合,然后给你一些这些物品的摆放顺序的约束,如"物品A应摆放在物品B前",请给出一个这些物品的摆放方案,使得所有约束都可以得到满足。
算法:对于给定的物品创建一个有向图,A到B的弧表示"物品A应摆放在物品B前”。
以任意顺序对每个物品进行遍历。
每当你找到一个物品,他的入度为0,那么贪心地将它放到当前序列的末尾,删除它所有的出弧,然后对它的出弧指向的所有结点进行递归,用同样的算法。
如果这个算法遍历了所有的物品,但却没有把所有的物品排序,那就意味着没有满足条件的解。
Search Techniques 搜索方式样例: n 皇后问题[经典问题]将n 个皇后摆放在一个n x n 的棋盘上,使得每一个皇后都无法攻击到其他皇后。
深度优先搜索(DFS)显而易见,最直接的方法就是把皇后一个一个地摆放在棋盘上的合法位置上,枚举所有可能寻找可行解。
可以发现在棋盘上的每一行(或列)都存在且仅存在一个皇后,所以,在递归的每一步中,只需要在当前行(或列)中寻找合法格,选择其中一个格摆放一个皇后。
1 search(col)2 if filled all columns3 print solution and exit4 for each row5 if board(row, col) is not attacked6 place queen at (row, col)7 search(col+1)8 remove queen at (row, col)从search(0)开始搜索,由于在每一步中可选择的节点较少,该方法可以较快地求解:当一定数量的皇后被摆放在棋盘上后那些不会被攻击到的节点的数量将迅速减少。
这是深度优先搜索的一个经典例题,该算法总是能尽可能快地抵达搜索树的底层:当k 个皇后被摆放到棋盘上时,可以马上确定如何在棋盘上摆放下一个皇后,而不需要去考虑其他的顺序摆放皇后可能造成的影响(如当前情况是否为最优情况),该方法有时可以在找到可行解之前避免复杂的计算,这是十分值得的。