算法艺术与信息学竞赛习题部分提示(2)

1.5.19

本题最大的迷惑点在于佳佳的篮子，如果你在记录当前糖果堆的同时记录篮子内的糖果，那么你就上当了。佳佳很聪明，他只记录当前糖果堆的情况，从而推知哪些糖果曾被拿到篮子里，并标记编号为i的糖果总共被拿出来Ai颗。

本着将尽可能多的糖果放入口袋的原则，佳佳将能配对的糖果统统从篮子内取出，于是令Ai =Ai mod 2，则当前篮子里糖果的数量Tot=sum{Ai}就求出了。

我们用P1,P2,P3,P4分别表示当前4堆糖果剩余的糖果数量，用数组元素a[P1,P2,P3,P4]表示状态P1,P2,P3,P4相应的Tot值。显然，根据a[P1,P2,P3,P4+1]的值，我们可以推得a[P1,P2,P3,P4]的值。如果Tot≤5，那么状态P1,P2,P3,P4是合法的，记为d[P1,P2,P3,P4] = true；否则，这是导致游戏结束的非法状态，记为d[P1,P2,P3,P4] = false。根据这个布尔型状态定义，我们不难写出状态转移方程，请读者自己完成。

1.5.21

本题也是利用匹配点的稀疏性。

1.5.22

只需求原串和逆序串的LCS

1.5.23

标准的LIS问题

1.6节习题

1.6.1

按照拓扑顺序来搜索，即先搜最里层子天平，再次里层...可以用后文提到的极端法剪枝（估计天平两边的最大、最小可能取值）

1.6.7

仔细分析一下状态空间，你会发现它其实非常少，用简单的启发函数（例如只考虑档住的纵向车移动的最小步数和与Car0步数之和）就可以取得非常好的效果。

1.6.8

此题比较难。可以利用IDA*搜索，忽略湖泊后用网络流的方法求出的割点数目（事实上还不完全是割点，因为有些点被屏蔽掉了）作为h函数，加上可行性剪枝：如果可以加石头的地方都加了石头还是能相互看见，则剪枝。h函数和可行性剪枝的作用都非常明显，读者不妨一试。

1.6.16

对于大多数数据来说，预处理合并掉相同的块并事先保存好每个块右方和下方可能的块集合后速度将会非常快。

算法艺术与信息学竞赛习题部分提示

2.1节习题

2.1.2

先考虑n=2^k的情况，构造完成后任意n都能处理了。

2.1.3

先展开m^k - (m-1)^k = A(m) = a[k-1]*m^(k-1) + a[k-2]*m^(k-2) + ...，其中A(m)为m的k-1次多项式。代入m=1,2,3...n后左右相加得到n^k = a[k-1]*s(k-1,n) + a[k-2]*s(k-2,n) + ... 其中a[k]为A(m)的k次项系数。可用此法从s(1,n), s(2,n) ... s(k-1,n)计算s(k,n)。

2.1.6

解方程组。

2.1.9

列出方程组以后发现可以直接递推计算而不需高斯消元。

2.1.10

解方程组。

2.1.11

解方程组。注意特殊情况的处理。建议读者自己分析。

2.1.14

n<=50时可以用递推法得到解；n>=50时不管m为几一定有解。

2.2节习题

2.2.6

提示：2^k步以后的情形很有规律。利用这个规律可以用二分法逐步用2^k逼近n。

2.3节习题

2.3.3

类似15数码问题的处理方法，参见书p190页

2.4节习题

缺少的提示：

2.4.1; 2.4.2; 2.4.7; 2.4.9

2.4.3 Gridland

其实这道题目只需要考虑两种情况。

情况一：两个边长至少有一个是偶数

算法艺术与信息学竞赛习题部分提示

长度为：

2*(height-1)+2*(width-1)+(height-2)*(width-2)

= 2*height-2+2*width-2+height*width-2*height-2*width+4

= height*width

情况二：两个边长都是奇数

长度为：Height*width –1 + sqrt(2)

因为少一条直边但是多一个斜边。

2.4.4邮递员

首先让我们把报酬的问题理清楚。如果期望值为Wi的村子是邮递员第Ki个经过的不同村子，那么他会得到报酬Wi-Ki元；同时在邮递员走过所有M条路后，他会从邮局那里得到m元，所以无论邮递员怎么走，只要他完成了任务，报酬都是 Wi i m。这样

i 1i 1nn

报酬的问题就不用考虑了，需要解决的只剩如何完成任务。

或者四条路的米子路口上，或者一条路的中因为每个村子只可能处于两条路的十子路口上，

央，所以与每个村子相连的路的条数为偶数。这个村落的构造符合一笔画的充要条件，剩下的问题唯有求欧拉回路。

2.4.5城市观光

如果这个兴趣值小于0则必然不能满足要求， 首先，完成所有旅程后的兴趣值为一定的。

也就是说总的兴趣值大于0是路径存在的必要条件。那么是否有满足题意的充分条件呢？实际上，总的兴趣值大于0就是路径存在的充分必要条件，构造如下：

1. 由于每个点的度都为4，所以图中必然存在欧拉回路，找出一条这样的欧拉回路。

2. 从任意一点出发，找到权最小的一个位置。如果这个位置的权是正的，则这条路经已经

满足要求。

3. 因为这个权是最小的负权，设为-a(a>0)。所以从这个点出发，回到起点的权至少为a。

而由于是最小负权，所以在从起点到这个点的这段路径中所有点的权都大于-a。换句话说，如果将这个权最小的点作为新起点，则从原起点到这个点的路径上的所有点的权均大于0。同时，由于这个点的权最小，所以在从这个点到起点的路径中所有的点的权也都大于0。满足题目要求。

所以，只要构造出一条回路，就总能在这条回路上找到一个点作为起点，满足题目要求。

算法艺术与信息学竞赛习题部分提示

2.4.6 赌博机

我们来分析一下机器失败的苛刻条件。首先抽象模型：赌博机是图（称为图T1）中的顶点，如果赌博机x的集合中有一个数y，那么向图中添加一条从x指向y的有向边。仅当此图构成一个顶点1出度比入度大一，顶点n入度比出度大一，其余顶点入度等于出度的欧拉路时，机器才有可能失败。所以下面我们只针对此种情况进行讨论：

如果机器没有失败，那么图中剩余边构成残留图T3，机器运作路径构成图T2，T2是一个顶点1出度比入度大一，顶点n入度比出度大一，其余顶点入度等于出度的欧拉路。因为T1-T2=T3，所以T3是顶点n入度出度皆为0其余所有顶点入度等于出度的欧拉回路。既然是回路就必然包含圈，事实上，只要残留图T3是个圈而非没有边的空图，机器就不会失败。我们从每个顶点出发，找寻不包含顶点n的圈。如果找不到，那么机器失败；如果找到了，那么把这个圈从图T1中删除，剩下的图便是使得机器获胜的路径，而这个路径仍然是个顶点1出度比入度大一，顶点n入度比出度大一，其余顶点入度等于出度的欧拉路。

2.4.8 远程通信

对于Bornholm端口2、Gotland 例子给出的方案是怎样找到的呢？我们可以这样来分析：

端口1、 Gotland端口4，由于没有其它端口以它们为目的端口，所以它们必须被设置成发送模式，因此一一对应的Gotland端口5、Bornholm端口4、Bornholm端口1必须为接收模式。删除由Gotland端口5、Bornholm端口4、Bornholm端口1发出的有向边。结果发现，由于边的删除，Gotland端口3、 Bornholm端口3也成为只有发送模式没有接受模式的端口，所以它们必须被设置成发送模式，相应的Gotland端口2为接受模式。

参照样例的解题方法，对于任意待匹配的通讯图，我们不断找出只有发送（接受）模式的端口x，确定它们以及相应接受（发送）端口y的运行方式，将点x、y及相关边从图中删除。如此迭代，直至无点、边可删。考虑当前剩余通讯图，图中共有a+b个点，a+b条有向边，每个点入度出度皆为1。这样的图只能由若干个有向环构成。倘若某个有向环顶点个数为奇数，那么 …… 此处隐藏：3007字，全部文档内容请下载后查看。喜欢就下载吧 ……