NOI提高组解题报告.docVIP

第七届（2001）分区联赛复赛解题报告（提高组） 俞玮赵爽 第一题：一元三次方程求解 给出一个三次方程，试求它所有的三个根。这里所有的根都在区间中，并保证方程具有三个实根，且它们之间的差不小于1。 分析： 如果是一般的求三次方程根的问题，那么只能直接使用求根公式，但这是非常复杂的。由于题目要求只精确到0.01，故我们考虑一下是否可以应用数值方法进行计算。由题目给出的在区间内存在根的条件可知，我们可以用一个变量从-100.000到100.000以步长0.001做循环。若，则可知在区间内存在方程的解。这样无论这个区间内的解是什么，在取两位小数的精度后都与取两位小数的结果是一样的。故我们就可以把取两位小数精度的作为问题的解。另外还有可能方程的根在区间端点的情况，我们可以通过判断是否为0来获得。 但这种方法由于用到了要求数值精度小的特殊性，故无法扩展。而在用数值方法求方程根的时候，我们最常用的方法就是二分法。该方法的应用在于如果确定了方程在区间内如果存在且只存在一个根，那么我们可以用逐次缩小根可能存在范围的方法确定出根的某精度的数值。该方法主要利用的就是题目所给的若在区间内存在一个方程的根，则这个事实，并重复执行如下的过程： 取当前可能存在解的区间； 若或，则可确定根为并退出过程； 若，则由题目给出的定理可知根在区间中，故对区间重复该过程； 若，则必然有，也就是说根在中，应该对此区间重复该过程。 最后，就可以得到精确到0.001的根。 再考虑什么样的区间内会有根。由于题目给出了所有的根都在-100到100之间，且根与根之间差不小于1的限制，故我们可知，在、、……、、这201个区间内，每个区间内至多只能存在一个根。这样对除去区间外的其他的区间，要么，要么时这个方程在此区间内才有解。若，显然为解；若，则可以利用上面所说的方法球出解来。这样就可求出这个方程的所有解。 最后是输出的解要求排序。我们既可以在求出来之后排序，也可以从小到大的顺序求解，就可以按照升序求出所有解。 数据： 输入 输出 1 1 -2 -1 2 -1.00 1.00 2.00 2 1 -4.65 2.25 1.4 -0.35 1.00 4.00 3 1 10 -1 -10 -10.00 -1.00 1.00 4 1 -1.8 -8.59 -0.84 -2.10 -0.10 4.00 第二题：数的划分 求把一个整数划分成份互不相同的正整数之和的方法总数。 分析： 这是一道整数剖分的问题。这类问题的数学性很强，方法也很多。这里介绍一种较为巧妙的办法。 思维转换一个角度我们形象的把n的k-自然数剖分看作n块积木k列，从左到右积木被堆成了楼梯状。比如，下图是10的几种4-剖分。 现在，我们不妨把这三个图顺时针旋转90度，成为： 不难发现，旋转之后的模型还是10的剖分，不过约束条件有所不同。很明显，由于原来是k剖分，因此新的模型中最大的一个元素必然是k。而其余的元素不限，都不能大于k。因此问题转化成了求n的任意无序剖分，其中最大的元素是k。当然，我们可以把n减去k，成为，剩下的问题就是求的任意剖分，其中每个元素都不大于k的方案总数了。 求解这个新的模型可以用递推的方法。用表示把b做任意剖分，其中最大的一个部分恰好是a的方案总数。用表示把b做任意剖分，其中最大的一个部分不大于a的方案总数。那么，有：。 消去，有：。的值，这样在在的时候，和都已经得到，我们简单即可。最后的即为所求。这种方法的时间复杂度为。 数据： 输入 输出 1 7 2 3 2 20 4 64 3 100 5 38225 4 200 5 583464 5 200 6 4132096 第三题：统计单词个数 1k≤40），且每份中包含的单词个数加起来最大（每份中包含的单词可以重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is，但是选用this之后就不能再选th）。 分析： 这一题应该算是一道比较原创的题目。注意到题目中有一个非常特殊的地方，就是以串中某个位置的字母为首字母，最多只能分出一个单词。由于在拆分字符串的过程中，如果以某位置为首某个较短单词被截断，那么以该位置为首的较长单词必然也会被截断。也就是说，对于各个位置来说我们选取较短的单词总不会比选取较长的单词所形成的单词少。这样我们可以定义一个在位置的参数表示以位置的字母为首字母，所能形成的最短单词的长度。这样如果在这个位置加上这个单词的长度之内截断，则以该位置为首字母就不能形成单词，否则就可能形成一个单词。这样对于所有的不同个首位置，我们只要在各个位置依次对各个单词进行匹配就以得出所对应的的值，这一部分的复杂度为O(wl2)。然后是计算把字串分为多个部分的过程中有什么单词可以留下。由于是把字串分为多个部分