国家集训队2004论文集 何林

《国家集训队2004论文集 何林》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息学中守恒法的应用两个质量相等的小球，速度分别为5m/s,4m/s，他们相向运动，碰撞之后速度分别变成多少？动能动量守恒10gC和10gO2在密闭容器中反应一个小时。最后的总质量是多少？质量守恒变化中的不变量数列操作问题(1)问题描述：有一个数列a1,a2,a3,……,an。每次可以从中任意选3个相邻的数ai-1,ai,ai+1，进行如下操作(ai-1,ai,ai+1)(ai-1+ai,-ai,ai+ai+1)1492764+9-99+2113-91176数列操作问题(2)问题：给定初始和目标序列，请判断能不

2、能通过以上定义的操作，从初始变到目标状态。1694201613-46016132-667-6192-66Input.txt1694207–6192–66Output.txtYES数列操作问题(3)(ai-1,ai,ai+1)(ai-1+ai,-ai,ai+ai+1)59214-911S1=5S2=14S3=16S1=14S2=5S3=16S1和S2交换数列操作问题(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交换数列操作问题(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}相等数列操作问题(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)的操作，相当于交换Si-1,Si数列

4、操作问题(7)对(ai-1,ai,ai+1)的操作，相当于交换Si-1,SiSn不可能被交换，所以初始和目标序列的Sn应该相等集合{S1,S2,…,Sn-1}始终不变经过若干操作后，序列S1,S2,…,Sn-1发生顺序的改变反之，如果两个{Si}和{S’i}(1<=i<=n-1)完全相等，只是顺序不同。他们必然可以通过一系列操作互相转化(前提是Sn要相等)数列操作问题(8)输入数列{Ai},{Bi}求出{SAi}{SBi}把SAn和SBn比较；再把{SAi}{SBi}（1<=i<=n-1）分别排序，然后直接比较。

5、如果都相等输出“YES”，否则“NO”时间复杂度O(nlogn)（排序复杂度）小结：数列变换的过程中，数字杂乱无章，没什么规律。但是他们的和是有规律的。抓住变化中的不变量，一切都变得很轻松。棋子移动(1)问题描述：有一列无限长的格子里面。某些格子里面放了棋子如果某个格子里面有棋子，可以拿走这一颗，并且在这个格子的左边两个格子里面各放一颗。26321153棋子移动(2)问题描述：如果连续两个格子里面都有棋子，可以分别在两个格子里面各拿走一颗，并且在它们右边的格子里面放一颗。26321153棋子移动(3)问题：给定初

6、始状态，要求用以上操作，使得：每个格子里面至多只有1个棋子（或者没有）。没有相邻的两个格子都有棋子。简单的说：就是无法继续操作！棋子移动(4)121111111111111棋子移动(5)棋子变小橡皮泥！Wi第i个格子中橡皮泥的大小Wi=Wi-1+Wi-2棋子移动(6)Wi=Wi-1+Wi-2Fibonacci数列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)棋子移动的过程纷繁复杂，也没什么规律可寻。我们通过发现“橡皮泥质量守恒”，把复杂的移动规则，变成了简单的数字加减。“橡皮泥质量”就是变化中的不变量还有一些细节：高精度，解的存在性的证明，解的唯一性的证明。格子有无穷多个，到底从什么地方开始标“质量”？这些大家可以自己研究。这里只想揭示最本质的东西：守恒。总结问题往往纷繁复杂，直接分析困难

8、重重变化中往往存在一些不变量不变量或者明显，或者隐藏在幕后牢牢抓住不变量守恒，就能透过迷雾看到本质！总结给我一双慧眼吧！信息学中最重要的慧眼，就是：“守恒”！