[SOJ]若干题目解题报告

 
SOJ
SOJ1031 Transportation
SOJ
SOJ
SOJ
SOJ 本题很难用动规求解，因为有后效，难以建立状态转移方程。所以提交的同学都使用的是
SOJ
SOJ搜索，但是同样是搜索，速度差距确非常大。直接穷举搜索费时约5s，而优化后可以达到20ms。
SOJ
SOJ下面介绍nealzane大牛的做法：建立订单order数据结构：
SOJ
SOJ struct order
SOJ
SOJ {
SOJ
SOJ  int from; /* from station */
SOJ
SOJ  int to; /* to station */
SOJ
SOJ  int passangers; /* no of passangers */
SOJ
SOJ  int price; /* price */
SOJ
SOJ  int remaining; /* sum of prices of this and all remainings orders
SOJ
SOJ    in the sequence */
SOJ
SOJ }
SOJ
SOJ 对每一订单先算出price,price = (from - to)*passengers；然后，对订单按price递减
SOJ
SOJ排序。搜索过程就是按这个顺序进行。值得一提的是在剪枝问题上，容易想到建立全局最优值best。如果剩
SOJ
SOJ下的订单已经不能超过最优值则剪枝。这是这样实现的：对已经排好需的订单，用remaining表示从当前订
SOJ
SOJ单到最后一张订单的price的累加。在递归搜索中，设已经接下的订单的价值和记为earning，若earning＋
SOJ
SOJremaining[i]<=best就直接退出。
SOJ
SOJ经测试：
SOJ
SOJ不对订单按price排序耗时：110ms，排序后可以减少到20ms。
SOJ
SOJ
SOJ
SOJ1078 BlueEyes' Schedule
SOJ
SOJ
SOJ
SOJ 贪心动规都可以做。
SOJ
SOJ
SOJ
SOJ1070 Arbitrage (II)
SOJ
SOJ
SOJ
SOJ 找是否存在这样的回路：回路上边的权值的乘积大于1。我用的floyd算法。
SOJ
SOJ
SOJ
SOJ1071 The Tower of Babylon
SOJ
SOJ
SOJ
SOJ 典型动规题目。先一个block变3个，再对block按地面积递减排序。建一个一维数组height[];
SOJ
SOJheight[i]表示：把第i个block(已经排序的)作为放在面上时达到的最多高度。由于第i个block是放在
SOJ
SOJ第j(0<=j<i)个block上的显然这样就建立了最优子结构了。
SOJ
SOJ
SOJ
SOJ1091 指环王
SOJ
SOJ
SOJ
SOJ 双广+HASH效率很高。双广适用于：起始状态和目标状态确定的情况。
SOJ
SOJ
SOJ
SOJ1111 Gnome Tetravex
SOJ
SOJ
SOJ
SOJ 本题关键是判重，相同的数据项应该归为一类。搜索时按类来扩展。
SOJ
SOJ
SOJ
SOJ1128 控 制 棋
SOJ
SOJ
SOJ
SOJ 典型的博弈树问题。最好翻翻教科书，一看就明白了。
SOJ
SOJ
SOJ
SOJ1131 麻将游戏
SOJ
SOJ
SOJ
SOJ 题目说：“允许路径暂时离开平板”，于是可以将平板扩展一圈。然后就是DFS了，我采用的
SOJ
SOJ减枝策略是记录到达每一点所需要的最小线段数，在扩展过程中比较记录值和扩展后的值决定是否扩展
SOJ
SOJ该点。
SOJ
SOJ
SOJ
SOJ1139 Flip Game
SOJ
SOJ
SOJ
SOJ 这是一个规模不大的搜索题，完全搜索2^16种情况也可以过。但是有一个较好的搜索方法
SOJ
SOJ：搜索第1行的翻转情况，共16种。第2行翻转情况由第1行决定（第2行的翻转必须保证第一行为全b
SOJ
SOJ或全w），第3行又由第2行决定，第4行由第3行决定。最后检查第4行是否全b或全w即可。
SOJ
SOJ
SOJ
SOJ1140 Buffer Manager
SOJ
SOJ
SOJ
SOJ 模拟题没太多说的，关键是输入的处理
SOJ
SOJ
SOJ
SOJ1141 Domino Puzzle
SOJ
SOJ
SOJ
SOJ 思路：搜索加Euler道路判断条件:没有奇点或者有两个奇点。把一个domino看成一条边，
SOJ
SOJdomino的数字代表结点，在原来的基础上加入N个domino后可以形成Euler道路。可以证明N<=5，
SOJ
SOJ所以最多搜索5层就够了。
SOJ
SOJ
SOJ
SOJ1142 Binary Search
SOJ
SOJ
SOJ
SOJ 出乎意料，直接搜索N居然很快出结果。
SOJ
SOJ
SOJ
SOJ1143 Frontier
SOJ
SOJ
SOJ
SOJ 两Tower间的连线如果所有Monument都在其内侧，则可能是最后的被采用的边。我们先
SOJ
SOJ把这样的边记录下了，然后在这些边中搜索。需要特别注意的是在Monument为0的情况下，要保证
SOJ
SOJ3条边不在同一直线上(3点叉积不为0)。
SOJ
SOJ
SOJ
SOJ1144 Garland
SOJ
SOJ
SOJ
SOJ 本题可以搜索高度为0的点来做，也可以先找出关系直接递推，搜索的效率并不比直接推
SOJ
SOJ慢。
SOJ
SOJ
SOJ
SOJ1147 Equipment Box
SOJ
SOJ
SOJ
SOJ 简单的计算几何，计算时注意精度。
SOJ
SOJ
SOJ
SOJ1148 Secret Code
SOJ
SOJ 
SOJ
SOJ 搜索题。先搜索a0，使得X在减去a0后可以被B整除。再将(X-a0)除以B，作为中间数仍然用X
SOJ
SOJ表示，再搜索a1，使得(X－a1)可以被B整除。这样一直到X为0停止。
SOJ
SOJ
SOJ
SOJ1150 Labyrinth
SOJ
SOJ 
SOJ
SOJ 本题利用了一个结论：可以这样得到树中距离最远的两个结点A和B－－任选树的一结点为起点做
SOJ
SOJ一次遍历，与它距离最远的结点(若有多个，可以任选其一)必然是我们的两个目标结点之一记为A；同样的
SOJ
SOJ我们这次选A作为起点做一次遍历，与它距离最远的点(若有多个，任选其一)就是B了。结论的证明比较简单，
SOJ
SOJ用反证法并添加辅助线容易证明。
SOJ
SOJ
SOJ
SOJ1151 Piggy-Bank
SOJ
SOJ
SOJ
SOJ 比较典型的动规题目。由小规模问题推上去。
SOJ
SOJ
SOJ
SOJ1153 Play on Words
SOJ
SOJ
SOJ
SOJ 考察有向图的欧拉道路判断条件：1.图是连通的；2.出度等于入度的点的个数为0，或者有且仅有
SOJ
SOJ一个点的出度比入度大一和另一个点的入度比出度大一。本题将一个单词看做一条有向边，起点是首字母，
SOJ
SOJ终点是末字母。
SOJ
SOJ
SOJ
SOJ1162 I-Keyboard
SOJ
SOJ
SOJ
SOJ 动规。建二维数组price, price[n][g]表示用g个格子放n个字符的最小代价(n >= g)。对于n和g
SOJ
SOJ要计算price[n][g]可以这样做:搜索最后一格放的字符数k(范围：1 ~ n-(g-1))。这样就找到了最优子结构
SOJ
SOJ。假设用price(k)表示最后一格的代价，那么(非边界情况):
SOJ
SOJ price[n][g] = min{ price[n-k][g-1]+price(k); 1 <= k <= n-(g-1) }；
SOJ
SOJ边界情况直接计算。
SOJ
SOJ
SOJ
SOJ1194 Round and Round We Go
SOJ
SOJ
SOJ
SOJ 大数乘法。
SOJ
SOJ
SOJ
SOJ1197 Multiplication Puzzle
SOJ
SOJ
SOJ
SOJ 动规。与一个经典的爬台阶问题分析类似：每次可以上的阶数为n1，n2，n3，若上K阶，
SOJ
SOJ最少用几次（或有多少种方法）。分析这个问题是从最后一步入手的：即通过上K－n1阶，K－n2阶，
SOJ
SOJK－n3阶的次数推K阶的次数。这样就建立了最优子结构。Multiplication Puzzle也可以从最后
SOJ
SOJ一步取哪个数这一点将问题分为若干个最优子结构。有了子结构动规就很方便了。
SOJ
SOJ
SOJ
SOJ1193 Robot Contest
SOJ
SOJ
SOJ
SOJ 若任意两机器人可以找到某条长度为偶数的路径相连就YES，否则NO。但是，可以证明只需要
SOJ
SOJ判断是否机器人1和其他机器人均可找到偶数长路径即可保证任意两机器人有偶数长路径相连。
SOJ
SOJ 在判断两点A和B能否通过偶数长路径相连时我采用的方法：若二者为同一点则YES，否则，判断与B直
SOJ
SOJ接相连的点中，是否有与A通过奇数长路径相连的点，若有则YES，否则NO。
SOJ
SOJ 在判断两点A和B能否通过奇数长路径相连时我采用的方法：若二者为同一点则NO，否则，判断与B直接
SOJ
SOJ相连的点中，是否有与A通过偶数长路径相连的点，若有则YES，否则NO。
SOJ
SOJ 这样好像有点博弈树的味道。
SOJ
SOJ
SOJ
SOJ1200 The Alphabet Game
SOJ
SOJ
SOJ
SOJ 我们先计算出每种字母的坐标范围minx,maxx,miny,maxy.如果可以找到适合的分割线分隔各个字母
SOJ
SOJ区域的话，显然可以只用各个字母区域的边界线来实现。所以，我们找出每个字母区域的边界线：x=minx;
SOJ
SOJx = maxx; y = miny; y = maxy。这时对于每条边界线我们判断它是否会分割别的区域，若会，则必然不是
SOJ
SOJ最后要找的分割线，否则将其记录下来。经过这个过程就得到了若干边界线，我们用这些线把整个区域分割
SOJ
SOJ成若干小的区域，这时只需要判断每个小区域内是否只有一种字母。若是，YES；否则NO。
SOJ
SOJ 本题与1143 Frontier 做法有相似之处：对所有的线先进行预先判断，保留可行的线，再进行后面
SOJ
SOJ的操作。从而使效率大大提高。
SOJ
SOJ
SOJ
SOJ1203 Pass-Muraille
SOJ
SOJ
SOJ
SOJ 贪心。和1078 BlueEyes' Schedule是基本一样的。可以证明这种贪心策略是正确的：将
SOJ
SOJ墙按右边界递增排序，再依次去。
SOJ------=_1062063425_55651--
SOJ
SOJ
SOJ