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

浅谈信息学中状态的合理设计与应用1浅谈信息学中状态的合理设计与应用福建省福州第三中学刘弈目录浅谈信息学中状态的合理设计与应用.......................................................................1摘要...............................................................................................................................2关键字...........................................................................................................................2正文...............................................................................................................................2一、引言..........................................................................................................2二、状态设计与应用的相关应用及例题分析..............................................31、合理分析状态...........................................................................................3例一、squareroot.................................................................................3问题描述:..........................................................................................4问题分析:..........................................................................................4初步优化:..........................................................................................4深入分析:..........................................................................................5小结:..................................................................................................52、合理改进状态...........................................................................................6例二、banaltickets...............................................................................6题目描述:.........................................................................................6问题分析:.........................................................................................7初步分析:..........................................................................................8进一步分析：.................................................................................10小结：.............................................................................................103、合理设计状态.........................................................................................11例三、shootyourgun.........................................................................11问题描述:........................................................................................11题目分析:........................................................................................12进一步分析：.................................................................................14深入思考：.....................................................................................16小结：.............................................................................................16三、总结........................................................................................................17附录.............................................................................................................................18浅谈信息学中状态的合理设计与应用2浅谈信息学中状态的合理设计与应用摘要状态分析与设计是信息学中一个重要的部分，在动态规划、搜索、枚举等众多算法中均有很多应用。对状态本身的分析与研究也是十分重要的，而本文就针对这个方面进行了探讨研究。本文通过三个例题阐述了对于状态的合理设计在解题中所发挥的重要作用。关键字状态、分析、优化、改进正文一、引言在日常生活中，工作时间与工作数量、单位效率的关系可以用下面的这个式子来表达：工作时间=工作数量*单位效率……①（上式中的单位效率是指完成一个工作所需花费的时间）在信息学中，程序的运行时间是由两个因素决定的：程序中所处理的状态总数和处理每个状态所花费的时间，因此程序运行的总时间可以用下面的式子来表示：程序运行时间=状态总数*单位效率……②众所周知，①式中的工作数量是无法减少的，因此大多数人选择了减少对每一个工作所花费的时间，即提高单位效率，从而减少工作总时间，达到优化的目的。从表面上看，式①与式②并没有什么本质区别，然而在信息学中，式②中的状态总数不完全等同于式①中的工作数量，因为不同的状态表示可能产生不同的状态量。合理的状态设计有时能有效地减少冗余，从而通过减少状态总数而达到优化的目的。此外，好的的状态表示还能够帮助编程人员理清思路，为我们的浅谈信息学中状态的合理设计与应用3解题带来崭新的思维方式，降低了解题难度。而对单位效率进行优化有时则无法达到这样的效果。二、状态分析与设计的相关应用本文将重点介绍三道例题：《squareroot》、《banaltickets》、《shootyourgun》，从三个方面描述了如何根据问题的核心要求分析出问题的本质，并合理改进状态的设计与表示方法，由此带来解题新思路。其中，例题一《SquareRoot》，通过合理地分析，减少状态总数，用朴素算法解决问题。例题二《BanalTickets》，改进状态表示方法，通过对状态进行优化，取得良好的效果。例题三《ShootYourGun》，在常规状态表示法无法奏效时，重新设计了状态表示，极大的减少了状态总数。并由此得出了更为简洁的算法，成功的降低了编程复杂度及时间复杂度。1、合理分析状态人们在解决问题时，往往要先分析算法的复杂度是否能够满足题目的空间及时间的限制，之后才进行编程。如果在分析复杂度时出现错误，过高或过低地估计了算法的复杂度，都会直接影响问题的解决。复杂度估计过低，往往使得编程人员盲目下手，就算最后恍然大悟，发现算法不可行，也已经浪费了不少编程时间。如果不能及时找到有效的改进，往往就只能选择放弃该算法而另起炉灶。这样的错误在严格限定时间编程的信息学赛场上导致的后果是很严重的，甚至会直接影响选手的心理及比赛的结果；反之，如果复杂度估计过高，可能会使选手放弃本来可行的解法而另寻出路。由于这样一点分析上的失误而与正确的算法失之交臂，难道不是很可惜吗？下面的例子就是讲述如何通过分析状态总数做相应优化，消除其中的冗余，并正确判断与运用算法，减少程序运行总时间，提高效率，使问题得以解决。例一、squareroot11题目来源acm.timus.ru/problem.aspx?space=1&num=1132浅谈信息学中状态的合理设计与应用4问题描述:若整数x满足x2≡a(modn)，则称x是以n为模时a的平方根，记(,)rootan为满足以上条件的x的集合。题目包含k个询问(1100000)k，每次询问给出a和n(1,32767)an，其中n为质数，且a与n互质，要求出所有在(0,n-1)区间内的(,)rootan。问题分析:这题是一道模平方根(ModularSquareRoots)的问题，有专门的数学方法来解决此类问题，如有兴趣，可以参考相关资料。但是，解决模平方根的问题需要学习和掌握较高深的数学知识，若想在竞赛时推导数学公式，需要花费不少的时间。假如在推公式时遇到了阻碍，我们就会考虑用其他替代方法来解决这样的问题。首先考虑最普通的方法——枚举。枚举的基本思路是穷举x，计算2()(mod)valuexxn，如果()valuex等于a，那么就称这个(,)xrootan。对于一个询问，枚举的复杂度为()On，则整体复杂度为()Okn，在极限数据时，总枚举量可高达30多亿，显然无法在要求的时限内出解。经过上述分析，枚举法似乎很难满足题目要求。但枚举法是否就真的不可行呢？我们需要对状态进行合理的分析。初步优化:枚举法虽然无法直接解决这个问题，但是我们注意到这样一个信息：每次对一个询问(,)an使用枚举法处理，实际上可以得到所有的询问),(nm的答案，)0(nm。对一个询问花费了()On的时间去枚举，却只利用了这中间的一小部分，浪费严重。那么，应该如何合理利用这些“冗余”操作呢？再次回顾题目，可以看到k（即询问数）最多有100000个，但是n的取值只有32767个。显然，根据简单的鸽笼原理可得知，这些询问中最多出现32767浅