解题报告_魏大刚.txt

这个压缩包全部是在VC6.0下的开发程序！

 
1031 Transportation

	本题很难用动规求解，因为有后效，难以建立状态转移方程。所以提交的同学都使用的是
搜索，但是同样是搜索，速度差距确非常大。直接穷举搜索费时约5s，而优化后可以达到20ms。
下面介绍nealzane大牛的做法：建立订单order数据结构：
	struct order
	{
		int from; /* from station */
		int to; /* to station */
		int passangers; /* no of passangers */
		int price; /* price */
		int remaining; /* sum of prices of this and all remainings orders 
				in the sequence */
	}
	对每一订单先算出price,price = (from - to)*passengers；然后，对订单按price递减
排序。搜索过程就是按这个顺序进行。值得一提的是在剪枝问题上，容易想到建立全局最优值best。如果剩
下的订单已经不能超过最优值则剪枝。这是这样实现的：对已经排好需的订单，用remaining表示从当前订
单到最后一张订单的price的累加。在递归搜索中，设已经接下的订单的价值和记为earning，若earning＋
remaining[i]<=best就直接退出。
经测试：
不对订单按price排序耗时：110ms，排序后可以减少到20ms。

1078 BlueEyes' Schedule 

	贪心动规都可以做。

1070 Arbitrage (II)

	找是否存在这样的回路：回路上边的权值的乘积大于1。我用的floyd算法。

1071 The Tower of Babylon

	典型动规题目。先一个block变3个，再对block按地面积递减排序。建一个一维数组height[];
height[i]表示：把第i个block(已经排序的)作为放在面上时达到的最多高度。由于第i个block是放在
第j(0<=j<i)个block上的显然这样就建立了最优子结构了。

1091 指环王 

	双广+HASH效率很高。双广适用于：起始状态和目标状态确定的情况。

1111 Gnome Tetravex

	本题关键是判重，相同的数据项应该归为一类。搜索时按类来扩展。

1128 控 制 棋

	典型的博弈树问题。最好翻翻教科书，一看就明白了。

1131 麻将游戏

	题目说：“允许路径暂时离开平板”，于是可以将平板扩展一圈。然后就是DFS了，我采用的
减枝策略是记录到达每一点所需要的最小线段数，在扩展过程中比较记录值和扩展后的值决定是否扩展
该点。

1139 Flip Game

	这是一个规模不大的搜索题，完全搜索2^16种情况也可以过。但是有一个较好的搜索方法
：搜索第1行的翻转情况，共16种。第2行翻转情况由第1行决定（第2行的翻转必须保证第一行为全b
或全w），第3行又由第2行决定，第4行由第3行决定。最后检查第4行是否全b或全w即可。

1140 Buffer Manager

	模拟题没太多说的，关键是输入的处理

1141 Domino Puzzle

	思路：搜索加Euler道路判断条件:没有奇点或者有两个奇点。把一个domino看成一条边，
domino的数字代表结点，在原来的基础上加入N个domino后可以形成Euler道路。可以证明N<=5，
所以最多搜索5层就够了。

1142 Binary Search

	出乎意料，直接搜索N居然很快出结果。

1143 Frontier

	两Tower间的连线如果所有Monument都在其内侧，则可能是最后的被采用的边。我们先
把这样的边记录下了，然后在这些边中搜索。需要特别注意的是在Monument为0的情况下，要保证
3条边不在同一直线上(3点叉积不为0)。

1144 Garland

	本题可以搜索高度为0的点来做，也可以先找出关系直接递推，搜索的效率并不比直接推
慢。

1147 Equipment Box

	简单的计算几何，计算时注意精度。

1148 Secret Code
	
	搜索题。先搜索a0，使得X在减去a0后可以被B整除。再将(X-a0)除以B，作为中间数仍然用X
表示，再搜索a1，使得(X－a1)可以被B整除。这样一直到X为0停止。

1150 Labyrinth
	
	本题利用了一个结论：可以这样得到树中距离最远的两个结点A和B－－任选树的一结点为起点做
一次遍历，与它距离最远的结点(若有多个，可以任选其一)必然是我们的两个目标结点之一记为A；同样的
我们这次选A作为起点做一次遍历，与它距离最远的点(若有多个，任选其一)就是B了。结论的证明比较简单，
用反证法并添加辅助线容易证明。

1151 Piggy-Bank

	比较典型的动规题目。由小规模问题推上去。

1153 Play on Words

	考察有向图的欧拉道路判断条件：1.图是连通的；2.出度等于入度的点的个数为0，或者有且仅有
一个点的出度比入度大一和另一个点的入度比出度大一。本题将一个单词看做一条有向边，起点是首字母，
终点是末字母。

1162 I-Keyboard

	动规。建二维数组price, price[n][g]表示用g个格子放n个字符的最小代价(n >= g)。对于n和g
要计算price[n][g]可以这样做:搜索最后一格放的字符数k(范围：1 ~ n-(g-1))。这样就找到了最优子结构
。假设用price(k)表示最后一格的代价，那么(非边界情况):
	price[n][g] = min{ price[n-k][g-1]+price(k); 1 <= k <= n-(g-1) }；
边界情况直接计算。

1194 Round and Round We Go

	大数乘法。

1197 Multiplication Puzzle

	动规。与一个经典的爬台阶问题分析类似：每次可以上的阶数为n1，n2，n3，若上K阶，
最少用几次（或有多少种方法）。分析这个问题是从最后一步入手的：即通过上K－n1阶，K－n2阶，
K－n3阶的次数推K阶的次数。这样就建立了最优子结构。Multiplication Puzzle也可以从最后
一步取哪个数这一点将问题分为若干个最优子结构。有了子结构动规就很方便了。

1193 Robot Contest

	若任意两机器人可以找到某条长度为偶数的路径相连就YES，否则NO。但是，可以证明只需要
判断是否机器人1和其他机器人均可找到偶数长路径即可保证任意两机器人有偶数长路径相连。
	在判断两点A和B能否通过偶数长路径相连时我采用的方法：若二者为同一点则YES，否则，判断与B直
接相连的点中，是否有与A通过奇数长路径相连的点，若有则YES，否则NO。
	在判断两点A和B能否通过奇数长路径相连时我采用的方法：若二者为同一点则NO，否则，判断与B直接
相连的点中，是否有与A通过偶数长路径相连的点，若有则YES，否则NO。
	这样好像有点博弈树的味道。

1200 The Alphabet Game

	我们先计算出每种字母的坐标范围minx,maxx,miny,maxy.如果可以找到适合的分割线分隔各个字母
区域的话，显然可以只用各个字母区域的边界线来实现。所以，我们找出每个字母区域的边界线：x=minx;
x = maxx; y = miny; y = maxy。这时对于每条边界线我们判断它是否会分割别的区域，若会，则必然不是
最后要找的分割线，否则将其记录下来。经过这个过程就得到了若干边界线，我们用这些线把整个区域分割
成若干小的区域，这时只需要判断每个小区域内是否只有一种字母。若是，YES；否则NO。
	本题与1143 Frontier 做法有相似之处：对所有的线先进行预先判断，保留可行的线，再进行后面
的操作。从而使效率大大提高。

1203 Pass-Muraille

	贪心。和1078 BlueEyes' Schedule是基本一样的。可以证明这种贪心策略是正确的：将
墙按右边界递增排序，再依次去。
------=_1062063425_55651--