算法艺术与信息学竞赛题解例题报告

1、POI VI Stage 3 Problem 5遗传基因题意分析首先，抓住问题的两个关键因素：“特征”和“基因段”。一个“特征”是由两个有序整数组成的，例如有“特征”(2,3)，那么，在对应的“基因段”中必然存在连续的两个数ai=2和ai+1=3。不妨将“基因段”中的自然数看成点，如果两点之间存在一条有向边，那么该边就是这段基因的一个“特征”。如图一所示，假设基因段是(1,2,3,4,3,5,6,2,5)。123546123546图 一而对“基因段”来说，可以从图一中的1点出发，画出一条路径，每条边经过且只经过一次。题目要求的是：给定一些“特征”，求最短的可行“基因段”。对应到图中，就是：给定

2、一些有向边，要求画出一条路径，经过这些有向边，并且路径长度尽量短。路径是：路径是：1,2,3,2,4 图 二1234假设给定的特征是(1,2),(2,3),(2,4)。如图二所示，我们自然希望每一条边都走过，而尽量不走不需要的边这样可以减少路径长度。但是，在图二中，我们不得不走一条不属于给定特征的边虚线所示，也就是说，我们分两笔才画出图二，而不是一气呵成。因此，我们面临的问题求路径长度尽量短，也可以转化成如何用最少的笔画来画出给定图。现在，已经将原问题转化到图中，得到了一个模型。下面，就在这个模型上，考虑设计算法。算法设计问题转化成上述的模型后，我们不由的联想到了经典的“一笔画”问题。不过在本

3、题中，我们需要求的是“至少”要几笔才能“画”完。1234123456图 三下面，先从简单的开始，假设给出的特征如图三所示。显然，图中每个点的入度等于出度，我们可以“一笔画完”：1,2,3,4,5,2,6,1。这也就是我们要求的最短基因段。图 四12345稍微变化点，假设有两个点的入度不等于出度 图 四12345 不可能只有一个点的入度不等于出度，这点是可以轻易证明的。图 五1图 五123因为1点没有入度，却有2个出度，必然有两笔会从1点画出，至少需要两笔画。再复杂一点的呢？四个、五个回顾先前对简单例子的分析，我们发现如下规律：所有点的入度等于出度，一笔画只有一个点的入度比出度大一，一笔画只有一

4、个点的入度比出度大二，二笔画难道问题与入度和出度的差值有关？不妨再拿一个略微复杂的实例分析。如图六所示：对每个点，求其出度减入度的值，如下：1：1-0 = 1 4：0-1 = -1对每个点，求其出度减入度的值，如下：1：1-0 = 1 4：0-1 = -12：2-1 = 1 5：1-2 = -13：2-1 = 1 6：0-1 = -1123456图 六我们不禁猜想：所有出度大于入度的点，将出度减去入度，得到的值累加起来就是问题的解。哦，还有一个特殊情况，图三中，所有出度等于入度，值加起来为0，但是需要一笔画。一般地，设点集Vi，入度为Ai，出度为Bi，之差Ci=Bi-Ai。那么，最少需要笔才能

5、画完。特别地，当所有Ci=0时，需要一笔画。下面，就让我们来尝试证明这个猜想，分两步：首先证明该数值是下界，再证明能构造出一种方案，只需要画这几笔。先证明，该数值是下界证：假设对一个点Vi，入度为Ai，出度为Bi，且BiAi。由于在一笔画的过程中，一个点如果进一次，只能出一次，进两次，出两次。所以，至少要从Vi点画出Bi-Ai笔这Bi-Ai笔是互不相干的。那么对于每个Bj大于Aj的点Vj，我们都至少要画Bj-Aj笔，因此，画出整个图至少需要笔，这是下界。再证明，能构造出这样一种方案证：只有一条边的图，是成立的假设有1K条边的任意图是成立的，下面证明有K+1条边的图也可以构造出这样的方案如果该图

6、中，所有点出度等于入度，则可以“一笔画”，符合特殊情况结论；如果该图中，有点Vi的出度大于入度，则从Vi开始，随意画一笔，直到不能画下去为止，显然，结束点是在另一点Vj。再在这一笔所经过的点上不断的找环，并添加到该笔中，直到没有环为止。将这一笔所经过的边从图中去掉，得到了一个新的图，则有Ci=Ci-1、Cj=Cj+1，其他Ck=Ck。新的图可能被划分成几个单独的部分，但是可以肯定，没有任何一个部分是一个环（即特殊情况），否则它会被事先添加入先前的一笔中的。对新图，边数减少了，根据假设，其需要的笔画数为，那么原图需要1+笔才能画出，又有Ci=Ci-1，Cj=Cj+1，其他Ck=Ck，所以原图用笔

7、即可画出。证明了这个猜想，大致的算法已经呈现：先将图分成几个独立的部分，每个独立部分之间没有边对每个独立部分求解，求出至少需要几笔才能画出将所求的笔画数加起来，再加上点数N，就是问题的解第二、三部分很容易解决。第一部分则有些麻烦：图的规模可能达到1000个点，如果我们按照常规去保存这幅图，显然在空间上存在问题，看来只能一边读入数据，一边处理了。不过，第一部分所要求的仅仅是将图划分成独立部分，也就是要知道每个点属于哪个部分。我们可以用合并等价类的方法求解 关于等价类和并查集的算法实现和复杂度，详细参见NOI2001食物链一题，以及周咏基同学的论文。 关于等价类和并查集的算法实现和复杂度，详细参见NOI2001食物链一题，以及周咏基同学的论文。思考小结任何想法都不是凭空而出的。在遗传基因一题中，我们从最最简单的情况入手，从易到