论文国家队何林

《论文国家队何林》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、信息学中的守恒法K摘要】本文提出和总结了“守恒法”，以及它在信息学竞赛中的一些应用。守恒的本质是寻找变化中的不变量。守恒法能帮助我们跳过.避开纷繁复杂的细节，直接看透问题的本质。【关键字】守恒法不变量【正文】一、引言现实生活和实际问题是纷繁复杂的。问题］两个质量相等的小球,速度分别为5m/sf4n】/s,他们和向运动,完全弹性碰撞之后速度分别变成多少?问题210gC和10gO2在密闭容器屮反应一个小时。最后的总质量是多少?问题1我们大概耳熟能详：动量守恒、动能守恒，两个方程就能解出速度。实际上小球碰撞的过程是复杂的，究竟两对力如何互和作

2、用、互和影响、如何做功，思考起来是非常的复杂。如果忽略它们变化的具体过程，我们很容易发现“动量”和“动能”这两个变化屮的不变量，抓住不变量，就能跳过繁琐的细节，直达日标。问题2也是类似的题冃。C和02的反应同样是复杂的。在不同的局部，条件不同，可能产生C0,也可能产生CO2；C02和C还可能重新转化为C0……事实上不可能有人列出三个化学方程去分析——在一个密闭容器小，无论怎么变，总质量必然不变——也就是质量守恒。抓住这一点，我们在1秒钟内就能说岀答案：20go以上两个例子生动的说明守恒的作用。现实生活和实际问题如此纷繁复杂，条件和变化如

3、此之多，以至于我们考虑稍不周密就可能全盘皆错；抑或限于问题本身的复杂性，根本无法分析。但是如果能找到一两个守恒量——也就是变化屮的不变量，那么问题就能大大的简化了。忽略细节，抓住主要孑盾，这就是守恒法。二.一个简单的例子例题1有一个数列ai,a2,a?,……,ano每次可以从中任意选3个相邻的数ai-i,ai,ai+i,进行如下操作(此操作称为“对ai进行操作”)(ai-1,Hi,ai+1)(ai・i+ai,-ai,ai+ai+i)第1页共13页给定初始和忖标序列。问：能不能通过以上操作，将初始序列转换到忖标序列。比如初始(169420

4、),冃标(7-6192-66)。可以经过如下操作：(169420)9(1613-460)9(16132-66)9(7-6192-66)(加粗的是每次被操作的&丿如果初始序列是仃23),目标是(132)。那么无论如何都不能通过操作从初始序列转换到口标序列。Input,txt1694207-6192-66Input・txt123132Output,txtYesOutput.txtNo我们分析一下这个题目。操作是有先后顺序之分的。比如先对32操作，再操作H3；先对as操作，再操作a2,结果就有天壤之别。观察Sample：(169420)9(1

5、613-460)9(16132-66)9(7-6192-66)数字杂乱无章没有规律。仔细观察一下操作规则：(3i-i,ai,ai+i)T(aid+ai,ai+ai+i)直观的看，相当于把中间的数分别加到两边去，然后取反。容易发现，操作前后的总和是不变的！我们可能很激动的猜想：只耍两个序列和相等，他们就能通过操作互达。但是第二个sample很快否定了这个想法：(123),(132)是不可达的。因为(123)能进行的操作仅仅是：(3-25),再进行一次操作回到(123)。所以永远不能变成(132)o总和虽然不行，我们可以试着考察局部和。(a

6、i・i,ai,ai+i)Sl=Hi-lS2=ai-i+aiS3=ai・i+ai+ai+i(ai・i+ai,-di,ai+ai+i)Si9=ai-i+aiS2'=ai-iS3^=ai-i+ai+ai+i很容易看出Ss=S3,,(Si,S2)=(S『,S。。也就是说把(Si,S2,S3)屮的Si和S2交换位置就能得到(sr,s『,s『)。稍微推广一下：设Si=ai+a2+...+ai,对(an,ai,at+i)操作本质上和交换Sm,Si是等价的。比如第一个Sample：(169420)T仃613-460)9(16132-66)9(7-619

7、2-66)转化成和之后：(1716202222)9(1720162222)9(1720221622)9(7120221622)第2页共13页(加粗的是交换的两个数)比如第二个Sample:(123)TS(136)(132)TS(146)对(123)的操作实质上是不断的交换S(136)中的1,3o无论如何也不可能变成(146),因为4根本没在S(136)小出现过！另外还有一点，参与交换的只有S.^Sn-l,Sn是雷打不动的。所以我们算法出來了：1、判断So是否相等。2、判断｛Si,S2Sn-l｝是否相等。O(nlogn)的时间复杂度(排序

8、复杂度)。一个看似繁琐的题日被很轻松的解决了。如上文所言，操作的变化过程是纷繁复杂的，可以说没任何规律。如杲从每一次操作对总体的贡献入手研究，会碰得头破血流。但是我们把原來的数列进行了一个小小的转化：求和。