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

数列操作问题(1) 数列操作问题(2) 数列操作问题(3) 数列操作问题(4) 数列操作问题(5) 数列操作问题(6) 数列操作问题(7) 数列操作问题(8) 棋子移动(1) 棋子移动(2) 棋子移动(3) 棋子移动(4) 棋子移动(5) 棋子移动(6) 棋子移动(7) 棋子移动(8) 棋子移动(9) 总结 问题往往纷繁复杂，直接分析困难重重 变化中往往存在一些不变量 不变量或者明显，或者隐藏在幕后 牢牢抓住不变量守恒，就能透过迷雾看到本质！ 总结 * * 信息学中守恒法的应用 两个质量相等的小球，速度分别为5m/s, 4m/s，他们相向运动，碰撞之后速度分别变成多少？ 动能动量守恒 10g C和10g O2在密闭容器中反应一个小时。最后的总质量是多少？ 质量守恒 变化中的不变量 问题描述： 有一个数列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 问题：给定初始和目标序列，请判断能不能通过以上定义的操作，从初始变到目标状态。 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.txt 1 6 9 4 2 0 7 –6 19 2 –6 6 Output.txt YES (ai-1, ai, ai+1)?(ai-1+ai, -ai, ai+ai+1) 5 9 2 14 -9 11 S1=5 S2=14 S3=16 S1=14 S2=5 S3=16 S1和S2交换 (ai-1, ai, ai+1)?(ai-1+ai, -ai, ai+ai+1) x y z x+y -y y+z S1=x S2=x+y S3=x+y+z S1=x+y S2=x S3=x+y+z S1和S2交换 1 6 9 4 2 0 S1=1 S2=7 S3=16 S4=20 S5=22 S6=22 7 -6 19 2 -6 6 S1=7 S2=1 S3=20 S4=22 S5=16 S6=22 {1,7,16,20,22,22} {1,7,16,20,22,22} 相等 (ai-1, ai, ai+1)?(ai-1+ai, -ai, ai+ai+1) x y z x+y -y y+z S1=x S2=x+y S3=x+y+z S1=x+y S2=x S3=x+y+z 对(ai-1,ai,ai+1)的操作，相当于交换Si-1, Si 对(ai-1,ai,ai+1)的操作，相当于交换Si-1, Si Sn不可能被交换，所以初始和目标序列的Sn应该相等 集合{S1, S2, …, Sn-1}始终不变 经过若干操作后，序列S1, S2, …, Sn-1发生顺序的改变 反之，如果两个{Si}和{S’i}(1=i=n-1)完全相等，只是顺序不同。他们必然可以通过一系列操作互相转化(前提是Sn要相等) 输入数列{Ai}, {Bi} 求出{SAi}{SBi} 把SAn和SBn比较；再把{SAi}{SBi}（1=i=n-1）分别排序，然后直接比较。 如果都相等输出“YES”，否则“NO” 时间复杂度O(nlogn)（排序复杂度） 小结： 数列变换的过程中，数字杂乱无章，没什么规律。 但是他们的和是有规律的。 抓住变化中的不变量，一切都变得很轻松。 问题描述： 有一列无限长的格子里面。某些格子里面放了棋子 如果某个格子里面有棋子，可以拿走这一颗，并且在这个格子的左边两个格子里面各放一颗。 2 6 3 2 1 1 5 3 问题描述： 如果连续两个格子里面都有棋子，可以分别在两个格子里面各拿走一颗，并且在它们右边的格子里面放一颗。 2 6 3 2 1 1 5 3 问题： 给定初始状态，要求用以上操作，使得： 每个格子里面至多只有1个棋子（或者没有）。 没有相邻的两个格子都有棋子。 简单的说：就是无法继续操作！ 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 棋子变小 橡皮泥！ Wi第i个格子中橡皮泥的大小 Wi=Wi-1+Wi-2 Wi=Wi-1+Wi-2 Fibonacci数列 1 1 2 3 5 8 13 21 34 55 89 1 1 1 1 2 1 2*1+8*2+34*1=52 1 1 2