算法合集之《信息学中守恒法的应用》.ppt

信息学中守恒法的应用,两个质量相等的小球，速度分别为5m/s,4m/s，他们相向运动，碰撞之后速度分别变成多少？,动能动量守恒,10g C和10g O2在密闭容器中反应一个小时。最后的总质量是多少？,质量守恒,变化中的不变量,数列操作问题(1),问题描述：有一个数列a1,a2,a3,an。每次可以从中任意选3个相邻的数ai-1,ai,ai+1，进行如下操作(ai-1,ai,ai+1)(ai-1+ai,-ai,ai+ai+1),1 4 9 2 7 6,4+9-9 9+2,1 13-9 11 7 6,数列操作问题(2),问题：给定初始和目标序列，请判断能不能通过以上定义的操作，从初始变到目标状态。,1 6 9 4 2 0,1 6 13-4 6 0,1 6 13 2-6 6,7-6 19 2-6 6,Input.txt1 6 9 4 2 07 6 19 2 6 6Output.txtYES,数列操作问题(3),(ai-1,ai,ai+1)(ai-1+ai,-ai,ai+ai+1),S1=5S2=14S3=16,S1=14S2=5S3=16,S1和S2交换,数列操作问题(4),(ai-1,ai,ai+1)(ai-1+ai,-ai,ai+ai+1),S1=xS2=x+yS3=x+y+z,S1=x+yS2=xS3=x+y+z,S1和S2交换,数列操作问题(5),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),S1=xS2=x+yS3=x+y+z,S1=x+yS2=xS3=x+y+z,对(ai-1,ai,ai+1)的操作，相当于交换Si-1,Si,数列操作问题(7),对(ai-1,ai,ai+1)的操作，相当于交换Si-1,Si,Sn不可能被交换，所以初始和目标序列的Sn应该相等集合S1,S2,Sn-1始终不变经过若干操作后，序列S1,S2,Sn-1发生顺序的改变反之，如果两个Si和Si(1=i=n-1)完全相等，只是顺序不同。他们必然可以通过一系列操作互相转化(前提是Sn要相等),数列操作问题(8),输入数列Ai,Bi求出SAiSBi把SAn和SBn比较；再把SAiSBi（1=i=n-1）分别排序，然后直接比较。如果都相等输出“YES”，否则“NO”时间复杂度O(nlogn)（排序复杂度）,小结：数列变换的过程中，数字杂乱无章，没什么规律。但是他们的和是有规律的。抓住变化中的不变量，一切都变得很轻松。,棋子移动(1),问题描述：有一列无限长的格子里面。某些格子里面放了棋子如果某个格子里面有棋子，可以拿走这一颗，并且在这个格子的左边两个格子里面各放一颗。,棋子移动(2),问题描述：如果连续两个格子里面都有棋子，可以分别在两个格子里面各拿走一颗，并且在它们右边的格子里面放一颗。,棋子移动(3),问题：给定初始状态，要求用以上操作，使得：每个格子里面至多只有1个棋子（或者没有）。没有相邻的两个格子都有棋子。,简单的说：就是无法继续操作！,棋子移动(4),棋子移动(5),棋子变小,橡皮泥！,Wi第i个格子中橡皮泥的大小,Wi=Wi-1+Wi-2,棋子移动(6),Wi=Wi-1+Wi-2,Fibonacci数列,2*1+8*2+34*1=52,5*1+13*2+34*1=52,相等,棋子移动(7),棋子变小,橡皮泥！,操作的过程中橡皮泥的总量是保持不变的。,棋子移动(8),2*1+8*2+34*1=52,52-34=18,18-13=5,5-5=0,1,1,1,棋子移动(9),棋子移动的过程纷繁复杂，也没什么规律可寻。我们通过发现“橡皮泥质量守恒”，把复杂的移动规则，变成了简单的数字加减。“橡皮泥质量”就是变化中的不变量,还有一些细节：高精度，解的存在性的证明，解的唯一性的证明。格子有无穷多个，到底从什么地方开始标“质量”？这些大家可以自己研究。这里只想揭示最本质的东西：守恒。,总结,问题往往纷繁复杂，直接分析困难重重变化中往往存在一些不变量不变量或者明显，或者隐藏在幕后牢牢抓住不变量守恒，就能透过迷雾看到本质！,总结,给我一双慧眼吧！,信息学中最重要的慧眼，就是：“守恒”！,