NOI提高组解题报告

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

俞玮

赵爽

第一题：一元三次方程求解

给出一个三次方程f(x)?ax3?bx2?cx?d?0，试求它所有的三个根。这里所有的根都在区间[?100,100]中，并保证方程具有三个实根，且它们之间的差不小于1。

分析：

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

i的情况，我们可以通过判断f(i)是否为0来获得。

但这种方法由于用到了题目所要求的数值精度小的特殊性，故无法扩展。而在用数值方法求方程根的时候，我们最常用的方法就是二分法。该方法的应用在于如果确定了方程f(x)?0在区间(a,b)内如果存在且只存在一个根，那么我们可以用逐次缩小根可能存在范围的方法确定出根的某精度的数值。该方法主要利用的就是题目所给的若在区间(a,b)内存在一个方程的根，则f(a)?f(b)?0这个事实，并重复执行如下的过程： ? 取当前可能存在解的区间(a,b)； ? 若a?0.001?b或f? 若f(a)?fb，则可确定根为?a?2??0a?b并退出过程； 2bbb，则由题目给出的定理可知根在区间?a,a?中，故对区间?a,a??a?2??02?2?重复该过程；

1 / 9

? 若f(a)?fbbb，则必然有f?a?，也就是说根在?a?中，应该对?a?2??02??f(b)?02,b?此区间重复该过程。

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

再考虑什么样的区间内会有根①。由于题目给出了所有的根都在-100到100之间，且根与根之间差不小于1的限制条件，故我们可知，在[?100,?99)、[?99,?98)、……、

[99,100)、[100,100]这201个区间内，每个区间内至多只能存在一个根。这样对除去区

间[100,100]外②的其他的区间[a,a?1)，要么f(a)?0，要么f(a)?f(a?1)?0时这个方程在此区间内才有解。若f(a)?0，显然a为解；若f(a)?f(a?1)?0，则可以利用上面所说的方法球出解来。这样就可求出这个方程的所有解。

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

数据：

输入

输出

-1.00 1.00 2.00 -0.35 1.00 4.00 -10.00 -1.00 1.00 -2.10 -0.10 4.00

1 1 -2 -1 2 2 1 -4.65 2.25 1.4 3 1 10 -1 -10 4 1 -1.8 -8.59 -0.84

第二题：数的划分

求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。

分析：

这是一道整数剖分的问题。这类问题的数学性很强，方法也很多。这里介绍一种较为巧妙的办法。

我们不必拘泥于原问题如何求解，而把思维转换一个角度来考虑一个与原问题等价的问题。

我们可以形象的把n的k-自然数剖分看作把n块积木堆成k列，且每列的积木个数依次递增，也就是这n块积木被从左到右积木被堆成了“楼梯状”。比如，下图是10的几种4-剖分。

①②

更确切地说是只有一个根。

该区间显然只有一个数，可以用用判断f(100)是否为0的方法来求出该区间内方程的根。对此，我们特殊处理。

2 / 9

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

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

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

?f?a,b??g?a,b?a??a。 ?????ga,b?fi,b??i?1?消去f，有：g?a,b???f?i,b???g?i,b?i??g?a?1,b??g?a,b?a?。我们可以

i?1i?1aa按照a、b递增的顺序计算g(a,b)的值，这样在在计算g?a,b?的时候，g?a?1,b?和

g?a,b?a?都已经得到，故我们只用进行一次简单的加法运算即可。最后的g?n,k???g?k,n?k?即为所求。

③④

该图为数学上的一个著名图示（Ferrer图），对此有兴趣的读者可以自己参看一些数学书。

由于篇幅有限，这里就不严格证明这两个问题的等价性了。

3 / 9

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

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

数据：

1 7 2 2 20 4 3 100 5 4 200 5 5 200 6

输入

3 64 38225 583464 4132096

输出

第三题：统计单词个数

给出一个长度不超过200的由小写英文字母组成的字符串（约定：该字符串以每行20个字母的方式输入，且保证每行一定20个）。要求将此字符串分成k份（1

分析：

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

f[l,k]?max?f[l?i,k?1]?g[l?i?1,i]?

1?i?l?1 ⑤⑥

当然前提是在这个位置可以匹配上一个单词。

这里l为该字串的长度。 ⑦

这里w为单词的个数。

4 / 9