第七届（2001）分区联赛复赛解题报告（提高组）

俞玮      赵爽

第一题：一元三次方程求解 [源程序]

给出一个三次方程 ，试求它所有的三个根。这里所有的根都在区间 中，并保证方程具有三个实根，且它们之间的差不小于1。

分析：

如果是一般的求三次方程根的问题，那么只能直接使用求根公式，但这是非常复杂的。由于题目要求只精确到0.01，故我们考虑一下是否可以应用数值方法进行计算。由题目给出的方程在区间内存在根的条件可知，我们可以用一个变量 从-100.000到100.000以步长0.001做循环。若 ，则可知在区间 内存在方程的解。这样无论这个区间内的解是什么，在取两位小数的精度后都与 取两位小数的结果是一样的。故我们就可以把取两位小数精度的 作为问题的解。另外还有可能方程的根在区间端点 的情况，我们可以通过判断 是否为0来获得。

但这种方法由于用到了题目所要求的数值精度小的特殊性，故无法扩展。而在用数值方法求方程根的时候，我们最常用的方法就是二分法。该方法的应用在于如果确定了方程 在区间 内如果存在且只存在一个根，那么我们可以用逐次缩小根可能存在范围的方法确定出根的某精度的数值。该方法主要利用的就是题目所给的若在区间 内存在一个方程的根，则 这个事实，并重复执行如下的过程：

l         取当前可能存在解的区间 ；

l         若 或 ，则可确定根为 并退出过程；

l         若 ，则由题目给出的定理可知根在区间 中，故对区间 重复该过程；

l         若 ，则必然有 ，也就是说根在 中，应该对此区间重复该过程。

最后，就可以得到精确到0.001的根。

再考虑什么样的区间内会有根[1]。由于题目给出了所有的根都在-100到100之间，且根与根之间差不小于1的限制条件，故我们可知，在 、 、……、 、 这201个区间内，每个区间内至多只能存在一个根。这样对除去区间 外[2]的其他的区间 ，要么 ，要么 时这个方程在此区间内才有解。若 ，显然 为解；若 ，则可以利用上面所说的方法球出解来。这样就可求出这个方程的所有解。

最后是输出的解要求排序。我们既可以在求出来之后排序，也可以从小到大的顺序求解，就可以按照升序求出所有解。

数据：

	输入	输出
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列，且每列的积木个数依次递增，也就是这n块积木被从左到右积木被堆成了“楼梯状”。比如，下图是10的几种4-剖分。

现在，我们不妨把这三个图顺时针旋转90度，成为[3]：

不难发现，旋转之后的模型还是10的剖分，不过约束条件有所不同。很明显，由于原来是k剖分，因此新的模型中最大的一个元素必然是k。而其余的元素大小不限，但都不能大于k。因此问题转化成了求n的任意无序剖分，其中最大的元素是k[4]。当然，我们可以把n减去k，成为 ，剩下的问题就是求 的任意剖分，且其中每个元素都不大于k的方案总数了。

求解这个新的模型可以用递推的方法。用 表示把b做任意剖分，其中最大的一个部分恰好是a的方案总数。用 表示把b做任意剖分，其中最大的一个部分不大于a的方案总数。那么，有：

。

消去 ，有： 。我们可以按照a、b递增的顺序计算 的值，这样在在计算 的时候， 和 都已经得到，故我们只用进行一次简单的加法运算即可。最后的 即为所求。

这种方法的时间复杂度为 。空间复杂度为O(nk)，或者我们可以用滚动数组的方法降到O(n)。

该题中模型转化的思想，是很值得借鉴的。

数据：

	输入	输出
1	7 2	3
2	20 4	64
3	100 5	38225
4	200 5	583464
5	200 6	4132096

第三题：统计单词个数 [源程序]

给出一个长度不超过200的由小写英文字母组成的字符串（约定：该字符串以每行20个字母的方式输入，且保证每行一定20个）。要求将此字符串分成k份（1<k≤40），且每份中包含的单词个数加起来最大（每份中包含的单词可以重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is，但是选用this之后就不能再选th）。

分析：

这一题应该算是一道比较原创的题目。注意到题目中有一个非常特殊的地方，就是以串中某个位置的字母为首字母，最多只能分出一个单词。由于在拆分字符串的过程中，如果以某位置为首某个较短单词被截断，那么以该位置为首的较长单词必然也会被截断。也就是说，对于各个位置来说我们选取较短的单词总不会比选取较长的单词所形成的单词少。这样我们可以定义一个在位置 的参数 表示以位置 的字母为首字母，所能形成的最短单词的长度。这样如果在这个位置加上这个单词的长度之内截断，则以该位置为首字母就不能形成单词，否则就可能形成一个单词[5]。这样对于所有的不同 [6]个首位置，我们只要在各个位置依次对各个单词进行匹配就以得出所对应的 的值，这一部分的复杂度为O(wl²)[7]。然后是计算把字串分为多个部分的过程中有什么单词可以留下。由于是把字串分为多个部分，故我们类比其他的分割字串的问题，列出动态规划的方程如下：

                            

这里有初值 为：

                                             

这个式子中， 表示把字串前 个字符分成 段时所形成的最多单词的数目， 表示字串的第 个字符开始的 个字符形成的字串中所能形成的单词数。这里 由于过于庞大，不能用预计算的方法加快速度，只能现用现算。计算的方法为对于所有 的 ，如果 存在（也就是有单词可以在位置 匹配上），且 ，则该位置必然可以匹配上一个单词。把所有这样位置的数目加起来就可以得到 的值了。这样算法的复杂度为O(kl³)。

但这里计算还有一个技巧，就是我们可以依次按照 增加， 增加， 增加的顺序计算 的值。这样在 由 增加到 的时候，由于在计算 所对应的 值时可以用

               

这个方程进行复杂度为O(1)的递推计算，故总复杂度可以降到O(kl²+wl²)。

这种被称作双重动态规划的方法，请读者自己好好体会。

数据：

	输入	输出
1	2 1 thisisappleisthisthe oopbooktheisurrtoywe 4 is of the book	8
2	4 4 dfhfghgdfksgdflsdsds sdsdsddfsdffssddsfdf asasassasdsdsdsdsdsd sadadadasdsdsdsdssdd 4 dssd dfdfdf sdsd jkjjk	13
3	10 4 aaaaaaaaaaaaaaaaaaaa