算法合集之《浅谈信息学中状态的合理设计及应用》.ppt

浅谈信息学中状态的合理设计与应用福建省福州第三中学 刘弈  引言 在日常生活中，工作时间与工作数量、单位效率的关系可以用下面的这个式子来表达： 工作时间=工作数量*单位效率 引言 在信息学中，程序的运行时间是由两个因素决定的，程序中所处理的状态的总数目和处理每个状态所花费的时间。 程序运行时间=状态总数*单位效率 引言 信息学中的状态总数有时隐藏着许多冗余状态。我们对状态的合理设计与应用不仅能优化的算法效率，还能够帮助编程人员理清思路，降低思维难度。 例一 Square Root 状态分析 合理地分析状态数目 例二 Banal Tickets 状态优化 对状态进行优化 例三 Shoot Your Gun 状态设计 重新设计状态 例三 Shoot Your Gun 定义边平行于坐标轴的简单多边形为矩形多边形。 已知在一个大的矩形多边形M中有两个小的矩形多边形G和T。G边上的任意一点可以向其左上、左下、右上、右下四个方向发射出射线。射线在遇到M的边时会发生光的镜面反射。 求从G边上的任意一点发出一条射线到T所需要的最少反射次数。 矩形多边形最多包含50条边，顶点坐标为整数在[0，4000]之内。 下图左描绘出了一个例子，下图中描述了在特 殊点时的反射规则。射线方向如下图右。 题目中G边上的任意一点都可以发射出射线。 枚举？ 只需要处理整点和1/2点即可。 题目分析 使用普通的状态表示法，将每个点发射出的4个方向分别做为4个点，进行构图并使用最短路算法进行求解。 这样的状态数是O(n2)级别的，不能很好的解决此题。 分析条件 题目条件： 路线轨迹遵循光的传播路线 光是沿直线传播的，只有在遇到障碍物时才会发生反射 只有发生反射时，路线方向才会发生改变。也就是说，只有在边上才可能使方向发生变化。 如下图，图中加粗的边为射线的轨迹。 设计状态 因此我们不妨将边上的点作为状态 使用spfa算法则可以满足题目时间和空间的要求。 用spfa算法解决此题效果并不好。 深入思考 光路是不会部分重叠的，要么完全不重叠，要么完全重叠。 只需要枚举起点，然后每次遇到多边形的边的时候模拟反射，直到到达T集合。 这样做之后，程序实现起来十分简单，运行效率也很高。至此，我们很好地解决了此题。 总结 对状态优化的方法是基于对状态的表示和对题目条件的深入分析而设计的。 在很多时候，对单位效率进行优化难以奏效，对状态进行合理地优化与设计却能大显身手，取得良好的效果。 对状态进行合理地分析及设计能帮助我们更好的理清头绪并设计出简洁的算法。 谢 谢 例一 Square Root 若整数x满足 x2 ≡ a (mod n)，则称x 是以n为模时a的平方根，记root(a,n)为满足以上条件的x的集合。题目包含k个询问，每次询问给出a和n，其中n为质数，且a与n互质，要求出所有在(0,n-1)区间内的root(a,n)。 数据范围 1=a,n=32767，n为质数，a与n互质 1=k=100000 初步设计 不难想到如下算法： 枚举x，然后算出value(x)=x^2 mod n，如果value(x)等于a，那么就称这个x∈Root(a,n)。 每次枚举复杂度为O(N)，总复杂度为O(KN)，因此这个算法是十分低效的。 重要条件 n为质数，a与n互质 如何利用？ 状态分析 K最多为100000 N最多为32767 根据鸽巢原理即可知N不同的询问最多只有32767个。 事实上，由于n为质数，因此当N为32767时最多只有3500多个取值。 我们在使用枚举法的时候，是对x进行枚举，然后判断x是否∈Root(a,n)。 仔细分析，不难发现，在求Root(a,n)的同时，我们可以顺便求出Root(m,n) （0=mn) 因此，我们可以在对询问进行分类后，对于n相同的询问，花O(N)的时间对第1个询问进行枚举，这样剩下的询问就可以用O(1)的时间得出结果了。 时间复杂度变成O(prime(n)*n+klogk) 例二 Banal Tickets 给定一个长度为2n(n=18)的数字串，数字串中有的位置的数字是已知的，以[0,9]的数字表示；有的位置的数字是未知的，以?表示。 当且仅当一个数字串满足以下条件时，称这个数字串interesting，否则为banal: 要求求出所有interesting串和所有banal串的个数。 初步分析 求interesting串的个数和求banal串的个数这两个问题是等价的，两者为互补关系。这样，就可以通过求其中的一个命题，来直接得到另一命题的解。而求interesting串的个数明显比求banal串的个数简单，因此只考虑求interesting串的个数的命题。 初步设计 不难得出这