《国家集训队论文集浅谈信息学中状态的合》由会员分享，可在线阅读，更多相关《国家集训队论文集浅谈信息学中状态的合（15页珍藏版）》请在金锄头文库上搜索。
1、浅谈信息学中状态的合理设计与应用福建省福州第三中学 刘弈 引言l在日常生活中，工作时间与工作数量、在日常生活中，工作时间与工作数量、单位效率的关系可以用下面的这个式子单位效率的关系可以用下面的这个式子来表达：来表达：工作时间工作时间=工作数量工作数量*单位效率单位效率引言l在信息学中，程序的运行时间是由两个在信息学中，程序的运行时间是由两个因素决定的，程序中所处理的状态的总因素决定的，程序中所处理的状态的总数目和处理每个状态所花费的时间。数目和处理每个状态所花费的时间。程序运行时间程序运行时间=状态总数状态总数*单位效率单位效率 引言l信息学中的状态总数有时隐藏着许多冗信息学中的状态总数有时隐
2、藏着许多冗余状态。我们对状态的合理设计与应用余状态。我们对状态的合理设计与应用不仅能优化的算法效率，还能够帮助编不仅能优化的算法效率，还能够帮助编程人员理清思路，降低思维难度。程人员理清思路，降低思维难度。例一 Square Root状态分析合理地分析状态数目例二 Banal Tickets状态优化对状态进行优化例三 Shoot Your Gun状态设计重新设计状态例三Shoot Your Gunl定义边平行于坐标轴的简单多边形为定义边平行于坐标轴的简单多边形为矩形多边形。l已知在一个大的已知在一个大的矩形多边形M中有两个小的中有两个小的矩形多边形G和和T。G边上的任意一点可以向其左边上的任意
3、一点可以向其左上、左下、右上、右下四个方向发射出射线。上、左下、右上、右下四个方向发射出射线。射线在遇到射线在遇到M的边时会发生光的镜面反射。的边时会发生光的镜面反射。l求从求从G边上的任意一点发出一条射线到边上的任意一点发出一条射线到T所需要所需要的最少反射次数。的最少反射次数。l矩形多边形最多包含最多包含50条边，顶点坐标为整数条边，顶点坐标为整数在在0，4000之内。之内。下图左描绘出了一个例子，下图中描述了在特殊点时的反射规则。射线方向如下图右。l题目中题目中G边上的任意一点都可以发射出射边上的任意一点都可以发射出射线。线。枚举？l只需要处理整点和只需要处理整点和1/2点即可。点即可。
4、题目分析l使用普通的状态表示法，将每个点发射出的4个方向分别做为4个点，进行构图并使用最短路算法进行求解。l这样的状态数是O(n2)级别的，不能很好的解决此题。分析条件l题目条件：路线轨迹遵循光的传播路线 光是沿直线传播的，只有在遇到障碍物时才会发生反射 l只有发生反射时，路线方向才会发生改变。也就是说，只有在边上才可能使方向发生变化。如下图，图中加粗的边为射线的轨迹。设计状态l因此我们不妨将边上的点作为状态因此我们不妨将边上的点作为状态l使用使用spfa算法则可以满足题目时间和空算法则可以满足题目时间和空间的要求。间的要求。l用用spfa算法解决此题效果并不好。算法解决此题效果并不好。深入思
5、考l光路是不会部分重叠的，要么完全不重光路是不会部分重叠的，要么完全不重叠，要么完全重叠。叠，要么完全重叠。l只需要枚举起点，然后每次遇到多边形只需要枚举起点，然后每次遇到多边形的边的时候模拟反射，直到到达的边的时候模拟反射，直到到达T集合。集合。 l这样做之后，程序实现起来十分简单，这样做之后，程序实现起来十分简单，运行效率也很高。至此，我们很好地解运行效率也很高。至此，我们很好地解决了此题。决了此题。总结l对状态优化的方法是基于对状态的表示对状态优化的方法是基于对状态的表示和对题目条件的深入分析而设计的。和对题目条件的深入分析而设计的。 l在很多时候，对单位效率进行优化难以在很多时候，对单位效率进行优化难以奏效，对状态进行合理地优化与设计却奏效，对状态进行合理地优化与设计却能大显身手，取得良好的效果。能大显身手，取得良好的效果。l对状态进行合理地分析及设计能帮助我对状态进行合理地分析及设计能帮助我们更好的理清头绪并设计出简洁的算法。们更好的理清头绪并设计出简洁的算法。谢谢 谢谢
