Dream-解题报告.doc

NOIP2004长郡中学模拟试题解题报告一 骑士精神(Knight)问题简述 在一个55的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。给定一个初始的棋盘，求最少移动得到目标棋盘。算法分析 一看就知道这是一道搜索题，解决此题的关键是如何搜。1） 广搜：该题需要求出最少步数，而广搜显然是一种求最优解的可行方法。但盲目地广搜效率肯定太低了，那么可以对其进行优化。优化显然有两条思路：首先由于初始状态和目标状态都已经给定，所以双向广搜是一种不错的选择，它能节省大约一半的时间，但还是不能令人满意。再来看A*算法，可以得到一个估价函数f 为初始状态中所有骑士所站的位置与目标状态不相符的数目，这些骑士显然至少要走一步才能到达可行格子，这样及时删去明显无用状态，效率有大幅度提高。2） 深搜：盲目地深搜很有可能会陷入过深的子树而难以得到最优解。我们可以考虑将深搜和广搜结合起来得到限界深搜算法。枚举最少步数，即限定搜索树的层次，每次只在规定层次类搜索，找到的第一个解就是最优解，而如果没找到则将步数加1，直到找到解。如果再利用A*算法的思想，用估价函数f来剪枝，即是IDA*算法，效果很好，所有数据都能迅速出解。二 王室联邦(Royal)问题简述 将一棵n个结点的树分成若干个部分，使得每一部分包含的结点个数属于B，3B，且连通或者添加某个结点后连通。算法分析 深度优先遍历该树，并且统计以每个结点为根的子树中未划分的结点数。回溯的时候如果发现某个结点为根子树中已经有大于等于B个未划分结点，则将其划分成一个部分，且该根结点则为中心点。如果某次划分后剩下的结点个数已经不超过3B，则可以把剩下的结点划分成一个部分，树根结点为中心点。1 33 8 6 5 2 4 7 9 如上图中，b = 2，我们深度优先遍历的过程如下：（其中Search(x)表示遍历以x为根的子树，Return(x)表示回溯到遍历以x为根的子树过程）Search(1)Search(2)Search(3)Return(2) 可以将结点2和3划分为一个省，省会为2Return(1) Search(8) Search(7) Return(8) Search(6) Search(4) Return(6) Search(5) Return(6) 可以将结点4和5划分为一个省，省会为6 发现此时剩下5个结点，那么把剩下的结点1，8，7，6，9划分为一个省，省会为根结点1 Return(8)Return(1)这样一共分成如下3个省：城市：1， 6， 7， 8， 9 省会： 1城市：2， 3 省会： 2城市：4， 5 省会： 6三 互不侵犯(King)问题简述 在NN的棋盘里面放M个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。算法分析用01来表示状态，0表示该位置没有放King，1则表示放了一个King。将每行状态的01串用一个十进制数来表示，并且去掉无用的状态（即在某行中出现两个相邻的1），用Vi表示状态i中1的个数。如果两行状态可以相邻（即任意相邻的两行两列4个格子至多只有一个1），则将其用邻接表保存下来。这样我们抽象出了数学模型，有n个阶段，每个阶段有一些状态可选，且状态i的权值为Vi，相邻两行状态的选取有限制，现在要求得到权值和恰为M的方案数，显然可以用动态规划解决。Fi,j,k表示前i行，第i行为状态j，得到了权值和为k的方案数。方程： 边界：目标：四 扫雷 (Mine)问题简述 有一个长度为n的格子，其中某些格子中有一个地雷。给定一个长度为n的非负整数序列，序列中的第i个元素表示第i-1格，第i格，第i+1格（如果存在）中雷的个数。求出地雷的分布方案数。算法分析 按照我们平时玩扫雷的心得，我们往往可以通过某个位置周围的数字以及已经得到的雷的分布推出其是不是雷。该题同样可以这样做，如果已知第i-1格和i-2格是否有雷(i2)，则可以通过序列中第i-1个数推出第i格是否有雷。而第2格的状态则只需要由第一格的雷和序列第一个数推出。 设Ai表示序列中第i个元素，Fi表示第I格的雷数,我们可以递推求解。方程： 但是F1的值还是未知的，由于每一格就是有雷和无雷两种状态，显然我们可以枚举第一格雷的状态，即F1的值为0或者1，这样就