栗师 转化目标 在解题中的应用.pptVIP

转化目标在解题中的应用 概述 在解题时，总是觉得 题目——超级马(1) 题目——超级马(2) 确定算法(1) 广搜？ 确定算法(2) 确定算法(3) 只要求当(x,y)=(0,1),(0,-1),(1,0),(-1,0)的情况 放大目标—— 放大目标——求整数解(2) 目标仍然很复杂 放大目标——求整数解(3) c1x1+c2x2=0 放大目标——求整数解(4) 定义Si,j：y∈Si ,j当且仅当存在整数k1,k2满足k1Pi+k2Pj=(0,y) 放大目标——求整数解(5) 定义S： 放大目标——求整数解(6) 如果1属于集合S，那么，方程①就有整数解了！ 放大目标——求整数解(7) 结论①： 放大目标——求整数解(8) 放大目标——求整数解(9) 放大目标——求整数解(10) 证明了结论①后，有下面结论： 求非负整数解(1) 求非负整数解(2) 定义T i,j: y∈Ti,j当且仅当存在非负整数k1,k2满足k1Pi+k2Pj=(0,y)) 求非负整数解(3) 用同样的方式定义T： 求非负整数解(4) 因为需要证明下面的结论： 求非负整数解(5) 构造方法： 求非负整数解(6) 接下来看下面的结论： 求非负整数解(7) 同时考虑两个位置：(0, 1)，(0, -1)。 算法 得到了问题的算法： 总结(1) 题目首先是要求方程的非负整数解，而方程求整数解比求非负整数解要简单。所以首先把目标放大成了求解整数解。求完整数解后，就站在了一个新的高度上，由整数解得出非负整数解变得简单。 总结(2) 转化目标 * * 湖南省长沙市长郡中学 栗师 限制太多 范围太窄 关系错综复杂 目标太远 困难需要解决！ 减少限制 放宽范围 简化关系 解题遇到困难 转化目标 解决某些题目，在算法设计中需要转化目标 在一个无限的棋盘上有一个超级马，它占据一个正方形单位格，可以完成各种移动动作。每一种移动动作由两个整数来描述——第一个数说明动作左右移动多少格(正数向右，负数向左)，第二个数说明动作上下移动多少格(正数向上，负数向下)。已知一个超级马能够完成的动作，要判断它是否能够到达棋盘上的所有位置。 SUP.IN 2 5 2 4 2 2 -3 -3 4 3 1 3 5 1 -3 2 1 4 1 4 -2 2 -2 超级马个数k(1=k=100) 动作数n(1=n=100) 每一个动作(xi,yi)，(-100=xi,yi=100) TAK表示超级马能够到达所有的位置 NIE表示超级马不能够到达所有的位置 SUP.OUT TAK NIE 数学方法 Time Limit Exceeded! 动态规划? 在某种意义上等价于广搜 否定了上面的算法后，似乎只有一条出路了： 每一个动作（xi，yi)用一个平面向量Pi表示，Pi=(xi,yi) 要判断的就是对于任意的x,y，是否都存在着一个非负整数序列c，使得下面的等式成立： 确定了数学模型： 解方程 由于对称性，只需要求(x,y)=(0,1)的情况 所以最终目标： ………………方程① 方程只有一个 但是，未知数很多 如果有解，解的个数应该比较多，有可能有无限个。 尝试着构造解。 构造出现了两个困难: A、方程右边y值要等于1。 B、方程左边系数要非负。 所以先解决困难A 太重了 先求出问题的整数解! 两个一起搬 先搬A 再搬B 求 整 数 解 再退一步 先考虑n=2的情况 假设x1,y1,x2,y2≠0 那么，两个向量能够到达纵坐标的哪些地方？ c1=Lcm(x1,x2)/x1; c2=-Lcm(x1,x2)/x2 W=c1P1+c2P2可以由P1、P2完成。 任意整数k,kW都可以由P1, P2来完成。 P2=(x2,y2) P1=(x1,y1) c1x1 -c2x2 c1P1+c2P2 {9k|k∈Z} 4 {6k|k∈Z} {3k|k∈Z} 3 {4k|k∈Z} {k|k∈Z} {0} 2 {2k|k∈Z} {5k|k∈Z} {6k|k∈Z} {2k|k∈Z} 1 5 4 3 2 j i Si,j n=5 P1=(2,4) P2=(2,2) P3=(-3,-3) P4=(4,3) P5=(1,3) P1-P2=(0,2) 3P1+2P3=(0,6) 2P1-P4=(0,5) -P1+2P5=(0,2) a、如果存在i,j使得y∈Si,j，那么y∈S; b、如果y1∈S, y2∈S，y=k1y1+k2y2，(k1∈Z,k2∈Z),那么y∈S。 c、其余的数都不属于S。 由模的知识不难得出，S集合也是形如{ky|k∈Z}的形式。 S是用所有的Si,j通过加减运算得出的闭形式。 S中最小的正数(上面的y)就是所有Si,j中的最小正数的最大公约数！ 找到方程①有整数解的充分条件了！ 上面