Noi2001全国分区联赛解题报告
Noi2001全国分区联赛解题报告
一．一元三次方程求解：
【问题描述】
求一个一元三次方程ax3+bx2+cx+d=0的三个解，其中：任意两根之差的绝对值不小于1，根的范围是[-100,100]。
【解题思路】
初看是要解方程，我们便会联想到一元二次方程的求根公式，但是三次方程是否有求根公式呢?答案是有的。但是公式较为复杂，而且要分情况讨论，在考场上也很难推导出来，我们只有另寻方法。
我们先来考虑一元三次方程的根的特点：
容易联想到：一个一元三次方程一定可以写成 (x-x1) * (x-x2) * (x-x3)=0的形式，其中：x1，x2，x3为这个方程的三个根。
表现在数轴上就是
|
y |
|
x |
|
x1 |
|
x2 |
|
x3 |
|
O |
|
k1 |
|
k2 |
若设f(x)= ax3+bx2+cx+d.
可以看到，若区间（k1，k2）之间有一个根，则
f(k1) *f(k2)<0。这也是我们解题的关键。有了这一个理论，又根据题目的条件“任意两根之差的绝对值不小于1”,
|
y |
|
x |
|
x1 |
|
X2 |
|
x3 |
|
O |
|
k1 |
|
k2 |
二分的原则是：在
f(k1) *f(k2)<0的前提下，缩小根的范围，
程序是：
repeat
e:= (k1+k2)/2;
if f(e) *f(k1)>0 then k1:=e
else k2:=e;
until abs(k1-k2)<1e-4;
此时的e就是一个解，同理可以求出另外两个解，然后按照升序输出即可。
【时空复杂度】
时间上: O(100)以内，可以忽略不计。
空间上:100Byte以内，可以忽略不计。
二．数的划分：
【问题描述】
将一个数n划分成本质不同的k份，每份不能为空，求有多少中划分法。
1≤n≤200，2≤k≤6
【解题思路】
这个题目的数据是比较小(1≤n≤200，2≤k≤6)的，而且也可以用const数组，对于搜索可以讲是天时地利人和了，所以可以考虑搜索。
因为题目是要求本质不同的有多少种，也就是说：{1，1，5}和{1，5，1}是一样的，这就要求搜索时要有一定的顺序。例如：我们可以规定后一个所总不能小于前一个数。这样编程就很容易了。
Procedure Search(u,last,deep： integer);
Var
I: integer;
Begin
If deep = k then
Begin
Inc(Total);
Exit;
End;
For I := last to U div 2 do {i不可能大于u div 2,否则就会比下一个数大}
Search(u – I, I, deep + 1);
End;
这个程序虽然短小，确十分的高效，当n=200，k=6时，也可以在0.38s内出解，当n或k稍小的时候，几乎不要时间。做成const数组后复杂度是O(0)。为什么如此之快？应为for循环时卡了界，i:=last to u div 2。按照我们的规定，后一个所总不能小于前一个数，所以，i最小为last{上一个数}，最大为u div 2{再大的话后一个数就会比他小了，也不行}，其实，为了更加高效，我们可以卡上下界，但是，并没有太大的用，原因是搜索层数较小，又加了对i的限制，卡上下界能剪掉的枝，这样也基本上都剪掉了。虽然说这样的题目适应为数据小才能用搜索做，但是对于搜索的剪枝也体现了一些搜索的技巧。
此外，这个题目也可以用动态规划做：
用f[i,j,k]表示:将I划分为j份,其中最小的一个是k的划分数，然后，由于将一个数划分为j部分的方案只与将一个数划分为j-1部分的方案有关，于是可以只用两个数组，交替使用就可以了。具体实现略。
【时空复杂度】
这里只讨论用搜索求解的时空复杂度。
时间上:0.38s以内
空间上:100Byte以内,忽略不计。
当然，这个题目如果生成了const数组，则时空复杂度约为O(0)，5k(200*6*4Byte).
三．统计单词个数：
【问题描述】略
【解题思路】
显然这个题目适合用动态规划解决，为什么？因为一旦分好段后能找到的单词的个数是确定的，关键是怎么分段，而分段的时候是满足最优化原理的。我们可以用f[i,j]表示将从第i个字母开始的串划分为k段能够得到的最多的单词数，用words来表示单词，s表示串，len表示单词的长度，match（a，b）表示串中第a个字母结束的连续若干个单词可以和第b个单词匹配。
动态规划方程是：
f[i,j] := f[i+1,j];
{第i个字母没有用}
若match(a,p)那么:
begin
if i+1后的字母还可以分成j段{至少要j个字母} then
f[i,j] := max{f[i,j],f[i+1,j]+1}
{可以得到f[i+1,j]+1个单词;第i个字母开始的单词有一个}
if i+len[p]后的字母还可以分成j-1段{至少要j-1个字母} then
f[i,j] := max{f[i,j],f[i+len[p],j-1]+1}
{从第p各结尾处划分开,得到一个新的段}
end;
程序为:
for j := 1 to k to
for i := length(S) downto 1 do
begin
f[i,j]=max{f[i,j],f[i+1,j]}
for p := 1 to TotWords do
if match(i,p) then
begin
if length(S) - (j + Len[p]) + 1 >= I then
f[i,j] := max{f[i,j],f[i+1,j]+1}
if length(S) - (j + Len[p]) + 1 >= i – 1 then
f[i,j] := max{f[i,j],f[i+len[p],j-1]+1}
end;
end;
【时空复杂度】
时间上:不会超过O(200*6*40)= O(480000)
空间上:约为8K(200*40Byte)，若用两个数组交替使用，可以达到800Byte，或者更少。
四．Car的旅行路线：
【问题描述】略
【解题思路】
这是一个求最短路径的问题，我们很容易想到dijkstra算法。是否可以用dijkstra算法呢？
答案是可以的，只要我们把一个城市里的四个机场拆开成四个节点，这样的图就变成了一个标准的求最短路径的网络了，于是可以用dijkstra来求从起点城市到终点城市的最短路径。
但在这之前，我们必须解决一个问题，就是得到一个城市的四个机场的坐标。
|
（x1,y1） |
|
（x2,y2） |
|
（x3,y3） |
|
（x4,y4） |
|
（xm,ym） |
由于每一个城市的四个机场都能构成矩形，这也就肯定了当其中三个点坐标确定后第四个点的坐标也是确定的。然而，这个坐标要怎样求呢？
如图：假设矩形的四个点坐标分别为(x1,y1), (x2,y2), (x3,y3), (x4,y4),中心点为：(xm,ym)。
我们先讨论中心点的坐标与顶点坐标之间的关系：
当连接对角线后，中心点即是对角线的交点，而根据矩形的性质，这个交点也是两对角线的中点。又由解析几何知识可知：一条线段的中点坐标是这条线段两端坐标的平均值。
例如上图中：
xm=(x1+x3)/2
ym=(y1+y3)/2
同理:
xm=(x2+x4)/2
ym=(y2+y4)/2
将上面的几式联立得：
x1+x3=x2+x4；y1+y3=y2+y4；
也就是说：一个矩形中，将在同一条对角线上的两个顶点坐标之和减去第三个顶点坐标就是第四个点的坐标。
然而怎么确定哪两个顶点是在同一条对角线上的呢？很简单：这三个点之间距离最远的两个点便是了。
有了上面的方法，各个顶点可以很容易求出来了。剩下的工作便是dijkstra。我们是否要保留所有的边呢？显然不要。因为对于任何一个点来说，和他相连的节点是已经确定了的：
1． 处于同一个城市里的点只能通过铁路来联系，
2． 而处于不同城市里的点则只能用空中航线来联系。
这些只要在for循环里判断一下就可以了。
【时空间复杂度】
时间上：约为O((4*城市个数)2)
空间上：小于3K。
用户登录
还没有账号？
立即注册