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

1、第七届（2001）分区联赛复赛解题报告（提高组）俞玮 赵爽第一题：一元三次方程求解给出一个三次方程 ，试求它所有的三个根。这里所有的根都32()0fxabcxd在区间 中，并保证方程具有三个实根，且它们之间的差不小于 1。10,分析：如果是一般的求三次方程根的问题，那么只能直接使用求根公式，但这是非常复杂的。由于题目要求只精确到 0.01，故我们考虑一下是否可以应用数值方法进行计算。由题目给出的方程在区间内存在根的条件可知，我们可以用一个变量 从-100.000 到 100.000 以i步长 0.001 做循环。若 ，则可知在区间 内存在方程的()0.1)fi(,0.1)解。这样无论这个区间内

2、的解是什么，在取两位小数的精度后都与 取两位小数的结果是i一样的。故我们就可以把取两位小数精度的 作为问题的解。另外还有可能方程的根在区i间端点 的情况，我们可以通过判断 是否为 0 来获得。i ()f但这种方法由于用到了题目所要求的数值精度小的特殊性，故无法扩展。而在用数值方法求方程根的时候，我们最常用的方法就是二分法。该方法的应用在于如果确定了方程在区间 内如果存在且只存在一个根，那么我们可以用逐次缩小根可能存在()0fx(,)ab范围的方法确定出根的某精度的数值。该方法主要利用的就是题目所给的若在区间内存在一个方程的根，则 这个事实，并重复执行如下的过程：(,)ab()0fab 取当前可

3、能存在解的区间 ；, 若 或 ，则可确定根为 并退出过程；0.1b2abf2ab 若 ，则由题目给出的定理可知根在区间 中，故对区间2()af2,ab重复该过程；2,ab 若 ，则必然有 ，也就是说根在 中，应该对2()0abf2()0abff2,ab此区间重复该过程。最后，就可以得到精确到 0.001 的根。再考虑什么样的区间内会有根 1。由于题目给出了所有的根都在-100 到 100 之间，且根与根之间差不小于 1 的限制条件，故我们可知，在 、 、10,9),8)、 这 201 个区间内，每个区间内至多只能存在一个根。这样对除去区9,10),0间 外 2的其他的区间 ，要么 ，要么 时这

4、个,)a()fa()1)0fa方程在此区间内才有解。若 ，显然 为解；若 ，则可以利用(0ff上面所说的方法球出解来。这样就可求出这个方程的所有解。最后是输出的解要求排序。我们既可以在求出来之后排序，也可以从小到大的顺序求解，就可以按照升序求出所有解。数据：输入 输出1 1 -2 -1 2 -1.00 1.00 2.002 1 -4.65 2.25 1.4 -0.35 1.00 4.003 1 10 -1 -10 -10.00 -1.00 1.004 1 -1.8 -8.59 -0.84 -2.10 -0.10 4.00第二题：数的划分求把一个整数 无序划分成 份互不相同的正整数之和的方法总数

5、。nk分析：这是一道整数剖分的问题。这类问题的数学性很强，方法也很多。这里介绍一种较为巧妙的办法。我们不必拘泥于原问题如何求解，而把思维转换一个角度来考虑一个与原问题等价的问题。我们可以形象的把 n 的 k-自然数剖分看作把 n 块积木堆成 k 列，且每列的积木个数依次递增，也就是这 n 块积木被从左到右积木被堆成了 “楼梯状” 。比如，下图是 10 的几种 4-剖分。1 更确切地说是只有一个根。2 该区间显然只有一个数，可以用用判断 是否为 0 的方法来求出该区间内方程的根。对此，我们特(1)f殊处理。现在，我们不妨把这三个图顺时针旋转 90 度，成为 3：不难发现，旋转之后的模型还是 10

6、 的剖分，不过约束条件有所不同。很明显，由于原来是 k 剖分，因此新的模型中最大的一个元素必然是 k。而其余的元素大小不限，但都不能大于 k。因此问题转化成了求 n 的任意无序剖分，其中最大的元素是 k4。当然，我们可以把 n 减去 k，成为 ，剩下的问题就是求 的任意剖分，且其中每个元素都不大于 k 的方案总数了。求解这个新的模型可以用递推的方法。用 表示把 b 做任意剖分，其中最大的一af,个部分恰好是 a 的方案总数。用 表示把 b 做任意剖分，其中最大的一个部分不大g,于 a 的方案总数。那么，有：。aibfgf1,消去 ，有： 。我们可fabgaibgifaiai ,1,11以按照

7、a、b 递增的顺序计算 的值，这样在在计算 的时候， 和(,)g,1都已经得到，故我们只用进行一次简单的加法运算即可。最后的g,即为所求。knk,3 该图为数学上的一个著名图示（Ferrer 图） ，对此有兴趣的读者可以自己参看一些数学书。4 由于篇幅有限，这里就不严格证明这两个问题的等价性了。这种方法的时间复杂度为 。空间复杂度为 21321knOknOO(nk)，或者我们可以用滚动数组的方法降到 O(n)。该题中模型转化的思想，是很值得借鉴的。数据：输入 输出1 7 2 32 20 4 643 100 5 382254 200 5 5834645 200 6 4132096第三题：统计单词

8、个数给出一个长度不超过 200 的由小写英文字母组成的字符串（约定：该字符串以每行20 个字母的方式输入，且保证每行一定 20 个） 。要求将此字符串分成 k 份（1k40 ） ，且每份中包含的单词个数加起来最大（每份中包含的单词可以重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可以包含 this 和 is，但是选用 this 之后就不能再选 th） 。分析：这一题应该算是一道比较原创的题目。注意到题目中有一个非常特殊的地方，就是以串中某个位置的字母为首字母，最多只能分出一个单词。由于在拆分字符串的过程中，如果以某位置为首某个较短单词被截断，那么以该位置为首的较长单词

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

10、x,1,ilflkfikgli5 当然前提是在这个位置可以匹配上一个单词。6 这里 为该字串的长度。l7 这里 为单词的个数。w这里有初值 为：,1fl ,1,flgl这个式子中， 表示把字串前 个字符分成 段时所形成的最多单词的数目，,flkk表示字串的第 个字符开始的 个字符形成的字串中所能形成的单词数。这里,gpipi由于过于庞大，不能用预计算的方法加快速度，只能现用现算。计算的方法为对于所有 的 ，如果 存在（也就是有单词可以在位置 匹配上） ，且1qiqmlenqq，则该位置必然可以匹配上一个单词。把所有这样位置的数目加mlenp起来就可以得到 的值了。这样算法的复杂度为 O(kl3

11、)。,gi但这里计算还有一个技巧，就是我们可以依次按照 增加， 增加， 增加的顺序计算kli的值。这样在 由 增加到 的时候，由于在计算 所对应的 值时可以用fi1i1ig,1gpgpmlenpii这个方程进行复杂度为 O(1)的递推计算，故总复杂度可以降到 O(kl2+wl2)。这种被称作双重动态规划的方法，请读者自己好好体会。数据：输入 输出12 1thisisappleisthistheoopbooktheisurrtoywe4isofthebook824 4dfhfghgdfksgdflsdsdssdsdsddfsdffssddsfdfasasassasdsdsdsdsdsdsadad

12、adasdsdsdsdssdd4dssd13dfdfdfsdsdjkjjk310 4aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa1aaaaa193410 4sdfsdsassdasdddsasddsdasdsasdsadasdasdsaassa

13、saasadassadsaaddssasdasdasdssddsassaasdasdasdasdasddsadsdsadasdasdasadssdssaasssdasdsasdassdssaadsaddsasdasdsadsaasaadsadsasddsadsadsssaadsdsaasddsaadsdsasa6aasadsdasasd125510 4sdfsdsassdasdddsasddsdasddassdsaadaasdsaassasaasadassadsaaddssasdsaasdassddsassasaddssassasdsaasssdsdsasdasdsddasdasdssaass

14、sdasdsasdassdssaasadsassdssassdsasssasasdsasdsasdsasdsssa65sdsasdsasdsassdasdsa6asddsaadsdassadsda第四题：CAR 的旅行路线又到暑假了，住在城市 A 的 Car 想和朋友一起去城市 B 旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市的两个机场之间有一条笔直的高速铁路，第 i 个城市高速铁路的单位里程价格为 Ti。任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为 t。那么 Car 应如何安排到 B 的路线才能尽可能的节省花费呢？她发现这并不是一个简单的问题

15、，于是她来向你请教。分析：我们换一种对题目描述的方法，就是给出一张地图，求出某人从某点到另一点的最短距离。这是一个图论中的标准问题，就是在一个无向图中求最短路径的问题。首先，这个人在从起点到终点所可能停下的点都是确定的，就是一个城市的四个机场（其他的时候是没有更换交通工具的自由的） 。所以我们可以以所有的机场为顶点，而机场与机场之间的交通路线 8为边建立一个图。该图的边权值为机场之间相互通行所需的时间。至于求最短路，我们可以使用一个被称为 Dijkstra 的算法。该算法的主要思想就是模拟液体等速的在管子内流动，先流到的位置就是离起点较近的位置。在使用算法实现的时候，我们可以把顶点划分为已流到

16、的和未流到的两个部分。依次找出液体从已流到的部分最少还需经过多少时间才能流到未流到的部分，并模拟流的过程。有关该算法的具体内容，请读者自行参见有关图论的算法书籍，这里不赘述。最后，还需注意的是题目中对于一个城市只给出了三个机场的坐标。但我们知道这四个机场是成矩形排列的，而矩形的对角线互相平分。故我们可以先找出这三个机场中相对的两个机场，易知这样的机场就是距离最大的两个机场。然后通过对这两个机场求平均数求出该矩形的中心，再把另一个机场按矩形的中心作对称就可以得出第四个机场的坐标。还有题目中最多可能有 400 个节点，也就是说可能有 80000 条边。这些边显然是无法事先计算并保存下来的。但由于在

17、求最短路径的过程中，每一条边最多只会访问两遍，故我们可以采用现用现算的办法。其他在计算点与点之间距离时也要注意对整数取平方时的运算有可能引发整数越界的问题，我们应该先转换成实数再进行计算。该算法的时间复杂度为 ，空间复杂度为 O(n)。23nO8 可能为铁路或航线。数据：输入 输出111 10 1 11 1 2 2 2 1 100.00213 10 1 32 2 2 1 1 2 102 12 12 2 22 12 122 22 22 32 32 22 10214.14313 10 1 310 1 1 10 1 1 1020 1 30 1 30 111 110 110 10 111 1 111

18、10310.004110 10 1 227 27 194 105 194 27 10366 290 381 290 366 305 1080 158 196 245 196 158 1289 154 358 154 358 86 217 284 84 350 84 284 1175 289 292 289 175 362 3450 371 420 371 420 32 2241 29 270 29 270 43 4251 182 347 270 251 270 5347 341 410 341 347 369 11885.035115 50 1 151 2 3 1 4 3 71 12 3 11 4 13 361 22 3 21 4 23 51 32 3 31 4 33 191 42 3 41 4 43 4711 2 13 1 14 3 211 12 13 11 14 13 611 22 13 21 14 23 111 32 13 31 14 33 2711 42 13 41 14 43 2921 2 23 1 24 3 3421 12 23 11 24 13 1621 22 23 21 24 23 141924.2321 32 23 31 24 33 4121 42 23 41 24 43 3