國家集訓(xùn)隊(duì)2004論文集 何林

《國家集訓(xùn)隊(duì)2004論文集 何林》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、信息學(xué)中守恒法的應(yīng)用兩個(gè)質(zhì)量相等的小球，速度分別為5m/s,4m/s，他們相向運(yùn)動，碰撞之后速度分別變成多少？動能動量守恒10gC和10gO2在密閉容器中反應(yīng)一個(gè)小時(shí)。最后的總質(zhì)量是多少？質(zhì)量守恒變化中的不變量數(shù)列操作問題(1)問題描述：有一個(gè)數(shù)列a1,a2,a3,……,an。每次可以從中任意選3個(gè)相鄰的數(shù)ai-1,ai,ai+1，進(jìn)行如下操作(ai-1,ai,ai+1)?(ai-1+ai,-ai,ai+ai+1)1492764+9-99+2113-91176數(shù)列操作問題(2)問題：給定初始和目標(biāo)序列，請判斷能不

2、能通過以上定義的操作，從初始變到目標(biāo)狀態(tài)。1694201613-46016132-667-6192-66Input.txt1694207–6192–66Output.txtYES數(shù)列操作問題(3)(ai-1,ai,ai+1)?(ai-1+ai,-ai,ai+ai+1)59214-911S1=5S2=14S3=16S1=14S2=5S3=16S1和S2交換數(shù)列操作問題(4)(ai-1,ai,ai+1)?(ai-1+ai,-ai,ai+ai+1)xyzx+y-yy+zS1=xS2=x+yS3=x+y+zS1=x+yS

3、2=xS3=x+y+zS1和S2交換數(shù)列操作問題(5)169420S1=1S2=7S3=16S4=20S5=22S6=227-6192-66S1=7S2=1S3=20S4=22S5=16S6=22{1,7,16,20,22,22}{1,7,16,20,22,22}相等數(shù)列操作問題(6)(ai-1,ai,ai+1)?(ai-1+ai,-ai,ai+ai+1)xyzx+y-yy+zS1=xS2=x+yS3=x+y+zS1=x+yS2=xS3=x+y+z對(ai-1,ai,ai+1)的操作，相當(dāng)于交換Si-1,Si數(shù)列

4、操作問題(7)對(ai-1,ai,ai+1)的操作，相當(dāng)于交換Si-1,SiSn不可能被交換，所以初始和目標(biāo)序列的Sn應(yīng)該相等集合{S1,S2,…,Sn-1}始終不變經(jīng)過若干操作后，序列S1,S2,…,Sn-1發(fā)生順序的改變反之，如果兩個(gè){Si}和{S’i}(1<=i<=n-1)完全相等，只是順序不同。他們必然可以通過一系列操作互相轉(zhuǎn)化(前提是Sn要相等)數(shù)列操作問題(8)輸入數(shù)列{Ai},{Bi}求出{SAi}{SBi}把SAn和SBn比較；再把{SAi}{SBi}（1<=i<=n-1）分別排序，然后直接比較。

5、如果都相等輸出“YES”，否則“NO”時(shí)間復(fù)雜度O(nlogn)（排序復(fù)雜度）小結(jié)：數(shù)列變換的過程中，數(shù)字雜亂無章，沒什么規(guī)律。但是他們的和是有規(guī)律的。抓住變化中的不變量，一切都變得很輕松。棋子移動(1)問題描述：有一列無限長的格子里面。某些格子里面放了棋子如果某個(gè)格子里面有棋子，可以拿走這一顆，并且在這個(gè)格子的左邊兩個(gè)格子里面各放一顆。26321153棋子移動(2)問題描述：如果連續(xù)兩個(gè)格子里面都有棋子，可以分別在兩個(gè)格子里面各拿走一顆，并且在它們右邊的格子里面放一顆。26321153棋子移動(3)問題：給定初

6、始狀態(tài)，要求用以上操作，使得：每個(gè)格子里面至多只有1個(gè)棋子（或者沒有）。沒有相鄰的兩個(gè)格子都有棋子。簡單的說：就是無法繼續(xù)操作！棋子移動(4)121111111111111棋子移動(5)棋子變小橡皮泥！Wi第i個(gè)格子中橡皮泥的大小Wi=Wi-1+Wi-2棋子移動(6)Wi=Wi-1+Wi-2Fibonacci數(shù)列11235813213455891111212*1+8*2+34*1=5211235813213455895*1+13*2+34*1=52相等棋子移動(7)棋子變小橡皮泥！操作的過程中橡皮泥的總量是保持不

7、變的。棋子移動(8)112358132134558912111235813213455892*1+8*2+34*1=5252-34=1818-13=55-5=0111棋子移動(9)棋子移動的過程紛繁復(fù)雜，也沒什么規(guī)律可尋。我們通過發(fā)現(xiàn)“橡皮泥質(zhì)量守恒”，把復(fù)雜的移動規(guī)則，變成了簡單的數(shù)字加減?！跋鹌つ噘|(zhì)量”就是變化中的不變量還有一些細(xì)節(jié)：高精度，解的存在性的證明，解的唯一性的證明。格子有無窮多個(gè)，到底從什么地方開始標(biāo)“質(zhì)量”？這些大家可以自己研究。這里只想揭示最本質(zhì)的東西：守恒?？偨Y(jié)問題往往紛繁復(fù)雜，直接分析困難

8、重重變化中往往存在一些不變量不變量或者明顯，或者隱藏在幕后牢牢抓住不變量守恒，就能透過迷霧看到本質(zhì)！總結(jié)給我一雙慧眼吧！信息學(xué)中最重要的慧眼，就是：“守恒”！