論文國(guó)家隊(duì)何林

《論文國(guó)家隊(duì)何林》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、信息學(xué)中的守恒法K摘要】本文提出和總結(jié)了“守恒法”，以及它在信息學(xué)競(jìng)賽中的一些應(yīng)用。守恒的本質(zhì)是尋找變化中的不變量。守恒法能幫助我們跳過(guò).避開(kāi)紛繁復(fù)雜的細(xì)節(jié)，直接看透問(wèn)題的本質(zhì)?！娟P(guān)鍵字】守恒法不變量【正文】一、引言現(xiàn)實(shí)生活和實(shí)際問(wèn)題是紛繁復(fù)雜的。問(wèn)題］兩個(gè)質(zhì)量相等的小球,速度分別為5m/sf4n】/s,他們和向運(yùn)動(dòng),完全彈性碰撞之后速度分別變成多少?問(wèn)題210gC和10gO2在密閉容器屮反應(yīng)一個(gè)小時(shí)。最后的總質(zhì)量是多少?問(wèn)題1我們大概耳熟能詳：動(dòng)量守恒、動(dòng)能守恒，兩個(gè)方程就能解出速度。實(shí)際上小球碰撞的過(guò)程是復(fù)雜的，究竟兩對(duì)力如何互和作

2、用、互和影響、如何做功，思考起來(lái)是非常的復(fù)雜。如果忽略它們變化的具體過(guò)程，我們很容易發(fā)現(xiàn)“動(dòng)量”和“動(dòng)能”這兩個(gè)變化屮的不變量，抓住不變量，就能跳過(guò)繁瑣的細(xì)節(jié)，直達(dá)日標(biāo)。問(wèn)題2也是類(lèi)似的題冃。C和02的反應(yīng)同樣是復(fù)雜的。在不同的局部，條件不同，可能產(chǎn)生C0,也可能產(chǎn)生CO2；C02和C還可能重新轉(zhuǎn)化為C0……事實(shí)上不可能有人列出三個(gè)化學(xué)方程去分析——在一個(gè)密閉容器小，無(wú)論怎么變，總質(zhì)量必然不變——也就是質(zhì)量守恒。抓住這一點(diǎn)，我們?cè)?秒鐘內(nèi)就能說(shuō)岀答案：20go以上兩個(gè)例子生動(dòng)的說(shuō)明守恒的作用?，F(xiàn)實(shí)生活和實(shí)際問(wèn)題如此紛繁復(fù)雜，條件和變化如

3、此之多，以至于我們考慮稍不周密就可能全盤(pán)皆錯(cuò)；抑或限于問(wèn)題本身的復(fù)雜性，根本無(wú)法分析。但是如果能找到一兩個(gè)守恒量——也就是變化屮的不變量，那么問(wèn)題就能大大的簡(jiǎn)化了。忽略細(xì)節(jié)，抓住主要孑盾，這就是守恒法。二.一個(gè)簡(jiǎn)單的例子例題1有一個(gè)數(shù)列ai,a2,a?,……,ano每次可以從中任意選3個(gè)相鄰的數(shù)ai-i,ai,ai+i,進(jìn)行如下操作(此操作稱(chēng)為“對(duì)ai進(jìn)行操作”)(ai-1,Hi,ai+1)(ai?i+ai,-ai,ai+ai+i)第1頁(yè)共13頁(yè)給定初始和忖標(biāo)序列。問(wèn)：能不能通過(guò)以上操作，將初始序列轉(zhuǎn)換到忖標(biāo)序列。比如初始(169420

4、),冃標(biāo)(7-6192-66)。可以經(jīng)過(guò)如下操作：(169420)9(1613-460)9(16132-66)9(7-6192-66)(加粗的是每次被操作的&丿如果初始序列是仃23),目標(biāo)是(132)。那么無(wú)論如何都不能通過(guò)操作從初始序列轉(zhuǎn)換到口標(biāo)序列。Input,txt1694207-6192-66Input?txt123132Output,txtYesOutput.txtNo我們分析一下這個(gè)題目。操作是有先后順序之分的。比如先對(duì)32操作，再操作H3；先對(duì)as操作，再操作a2,結(jié)果就有天壤之別。觀察Sample：(169420)9(1

5、613-460)9(16132-66)9(7-6192-66)數(shù)字雜亂無(wú)章沒(méi)有規(guī)律。仔細(xì)觀察一下操作規(guī)則：(3i-i,ai,ai+i)T(aid+ai,ai+ai+i)直觀的看，相當(dāng)于把中間的數(shù)分別加到兩邊去，然后取反。容易發(fā)現(xiàn)，操作前后的總和是不變的！我們可能很激動(dòng)的猜想：只耍兩個(gè)序列和相等，他們就能通過(guò)操作互達(dá)。但是第二個(gè)sample很快否定了這個(gè)想法：(123),(132)是不可達(dá)的。因?yàn)?123)能進(jìn)行的操作僅僅是：(3-25),再進(jìn)行一次操作回到(123)。所以永遠(yuǎn)不能變成(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。。也就是說(shuō)把(Si,S2,S3)屮的Si和S2交換位置就能得到(sr,s『,s『)。稍微推廣一下：設(shè)Si=ai+a2+...+ai,對(duì)(an,ai,at+i)操作本質(zhì)上和交換Sm,Si是等價(jià)的。比如第一個(gè)Sample：(169420)T仃613-460)9(16132-66)9(7-619

7、2-66)轉(zhuǎn)化成和之后：(1716202222)9(1720162222)9(1720221622)9(7120221622)第2頁(yè)共13頁(yè)(加粗的是交換的兩個(gè)數(shù))比如第二個(gè)Sample:(123)TS(136)(132)TS(146)對(duì)(123)的操作實(shí)質(zhì)上是不斷的交換S(136)中的1,3o無(wú)論如何也不可能變成(146),因?yàn)?根本沒(méi)在S(136)小出現(xiàn)過(guò)！另外還有一點(diǎn)，參與交換的只有S.^Sn-l,Sn是雷打不動(dòng)的。所以我們算法出來(lái)了：1、判斷So是否相等。2、判斷｛Si,S2Sn-l｝是否相等。O(nlogn)的時(shí)間復(fù)雜度(排序

8、復(fù)雜度)。一個(gè)看似繁瑣的題日被很輕松的解決了。如上文所言，操作的變化過(guò)程是紛繁復(fù)雜的，可以說(shuō)沒(méi)任何規(guī)律。如杲從每一次操作對(duì)總體的貢獻(xiàn)入手研究，會(huì)碰得頭破血流。但是我們把原來(lái)的數(shù)列進(jìn)行了一個(gè)小小的轉(zhuǎn)化：求和。