Noip考前冲刺-搜索枚举2

NOIP考前冲刺

--枚举、搜索武森MAZE现在有一个6×6的迷宫。每个格子可能是空地或者是洞穴。每个格子的四周有可能是墙，如果一个格子的左边有墙，那么它不能从这个格子往左面的格子走。迷宫中有且只有一个起点〔圆点〕和重点〔星型〕，起点和重点有可能是属于同一个格子。现在可以往上〔U〕、下〔D〕、左〔L〕和右(R)四个方向走。先要求用最短的步数从起点走到终点〔当走洞穴是，那么算失败〕。解法BFS状态表示DIST[X,Y]状态转移DIST[X,Y]=MIN{DIST[X+DIRX[I],Y+DIRY[I]]}+1转移条件：转到格子是否在范围内转移格子是否有墙转移格子是否似乎洞穴DOUBLE

MAZE现在有两个6×6的迷宫每个格子可能是空地或者是洞穴。每个格子的四周有可能是墙，如果一个格子的左边有墙，那么它不能从这个格子往左面的格子走。迷宫中有且只有一个起点〔圆点〕和重点〔星型〕，起点和重点有可能是属于同一个格子。现在可以往上〔U〕、下〔D〕、左〔L〕和右(R)四个方向走。现在同时控制两个格子的走法〔一个命令两个迷宫同时走〕，如果有个一个迷宫走到了洞穴，那么失败。如果有一个格子的要走的方向有墙，那么待在原位置的不动。先要求用最短的步数〔步数相同要求字典序最小〕从起点走到终点〔当走洞穴是，那么算失败〕。解法BFS？解法BFS状态表示DIST[X1,Y1,X2,Y2]状态表示DIST[X1Y1,X2Y2]哪个比较好？解法BFS状态表示DIST[X1Y1,X2Y2]状态转移DIST[X1Y1,X2Y2]

=MIN{DIST[X1Y1+WAYX[I],X2Y2+WAYY[I]]}+1DIST[X1Y1+WAYX[I],X2Y2+WAYY[I]]表示

能到达[X1Y1,X2Y2]的格子转移条件：转到格子是否在范围内转移格子是否有墙转移格子是否似乎洞穴注意那些有一个格子的路上有墙，留在原地的格解法求出了最短距离。怎么求得字典序最小的方案？方法1每次按字典序有小到大的走路方式〔D,L,R,U〕枚举走路的格子，判断DIST’是否等于当前格子的DIST-1.方法特点优点：容易想到，简单易写不容犯错.缺点：算法复杂度高，方法2根据上面的方法，我们易知枚举是否要走路的格子，如果是，那么DIST’是否等于当前格子的DIST-1.那个能否从终点到起点进行BFS,直接计算出路径最短并且字典序最小的方案？算法实现本卷须知：在倒向BFS的时候，我们要注意的是现在的BFS是对原本实践的回放，和原本的BFS方式不同。对于一个左边有墙格子，如果他在原本的BFS的过程当中是向左走的，那么我们现在就要向右走，这点毋庸置疑！但是，他有可能是向左走的时候，发现左边有墙而停留在原味的结果，所以对于这种情况，我们要考虑两种不同的情况，当然如果两个迷宫同时出像这种情况，那么要考虑2×2=4种情况。方法特点优点：便于根据题目要求，得到最短且字典序最小的解。时间复杂度低缺点：细节考虑较多编程复杂度高不易实现考点选手的正向思维和逆向思维思维的严谨性智慧珠游戏智慧珠游戏拼盘由一个三角形盘件和12个形态各异的零件组成。12个零件按珠子数分3大类第1大类：有三个珠子符号为A第2大类：有四个珠子符号为B符号为C符号为D第3大类：有五个珠子符号为E 符号为I符号为F 符号为J符号为G 符号为K符号为H 符号为L举例说明字符化B

BK

BKK

BJKK

JJJDD

GJGDDC

GGGCCCI

EEEHHIIA

ELHHHIAAF

ELLLLIFFFF条件&要求对于由珠子构成的零件，可以放到盘件的任一位置，条件是能有地方放，且尺寸适宜，所有的零件都允许旋转(0º、90º、180º、270º)和翻转(水平、竖直)。

现给出一个盘件的初始布局，求一种可行的智慧珠摆放方案，使所有的零件都能放进盘件中。样例输入文件一共有10行，第i行有i个字符。如果第i行的第j个字符是字母”A”至”L”中的一个，那么表示第i行第j列的格子上已经放了零件，零件的编号为对应的字母。如果第i行的第j个字符是”.”，那么表示第i行第j列的格子上没有放零件。输入保证预放的零件已摆放在盘件中。。

。。

。。。

。。。。

。。。。。

。。。。。C

。。。CCC。

EEEHH。。。

E。HHH。。。。

E。。。。。。。。。输出样例如果能找到解，输出10行，为放完全部12个零件后的布局。其中，第i行应包含i个字符，第i行的第j个字符表示第i行第j列的格子上放的是哪个零件。如果无解，输出单独的一个字符串”Nosolution”(不要引号，请注意大小写)。所有的数据保证最多只有一组解。B

BK

BKK

BJKK

JJJDD

GJGDDC

GGGCCCI

EEEHHIIA

ELHHHIAAF

ELLLLIFFFF解法BFSorDFS解法BFS不好记录状态，解最多为一个，不存在深度较浅的解DFSNOSOLUTION输入数据中“.”的个数与实际需要填的形状的柱子总数不符。。。预处理对于每个珠子，将其的构造形式量化，便于搜索时使用方法1最简单的思路从第一行的第一个位置开始搜索，尝试将当前情况下的没有放过的珠子，放在个这个位置上〔这个位置为珠子的某一个角而不是其中任意一个点〕依次搜索每一个没有放东西的位置，直至最终没有格子没有放下并且所有的珠子都已经放完了如果满足要求，那么输出解如果不满足要求，那么属于Nosolution方法特点优点：思路简单，清晰代码易写缺点：根本没有优化的可能性时间复杂度较高方法2通过观察题目中的不同珠子我们发现，对有有些珠子，如：G,J,K等珠子，由于形状比较特殊，所以可能与其有连接的珠子的形式比较单一，可以预处理出来，在搜索的时候，可以从这里入手。观察输入文件为一个三角形，那么对于斜边上的位置，会造成有一些格子不能被放置，这一点也可以预先处理出来，可以有效地进行优化算法特点优点：改变搜索的顺序，可以有效的减少搜索的次数对于一些特殊的情况，事先预处理出来，可以有效的减枝时间复杂度较方法1有一定的优势缺点：算法要预处理的内容有些复杂编程复杂度较高BFSORDFS探险队得到了一张古老藏宝的地图，图中包含n神秘的地点，并且知道这些神秘的地点之间是有一些隧道连接的，并且探险队知道藏宝图中包含了m条隧道，〔m<n〕，经过探险的观察这个藏宝图中不包含什么回路〔即任意两点之间最多存在一条路径使其相连〕，藏宝图中当中可能包含很多区域，任意两个区域是不相通的，现在藏宝图和探险队走过藏宝图中的某些神秘的地点，又知道探险队只能采取深度优先搜索或者宽度优先搜索的方式来对藏宝地点进行探险，请问探险队可能使用哪种方式进行探险的？输入数据第一行两个数字n、m和k表示藏宝图中有多少个神秘地点由1到n表示这个n个神秘地点和藏宝图中的道路和探险队已经探过的神秘地点数目。接下来的m行每行两个数ai,bi表示神秘地点ai和神秘地点bi有道路相连。在接下来的k行每行一个数字表示那些神秘地点被探过。输出数据输出有种情况DFS 表示是深度优先搜索的BFS 表示是宽度优先搜索的BOTH 表示两种情况都有可能NEITHER 表示两种情况都不可能题目模型抽象给定一个无向图，并且其中一些点被遍历，现在询问你这些点是怎么遍历的？思路首先对于图进行遍历。由于不同的联通分支之间互不影响所以进行处理。判断是哪种方法？思路什么情况下无解？

如果有两个或两个以上联通分支没有被完全遍历到对于这种情况是不不可能存在某一种算法，能便利成那个样子的。

所以Nosolution思路那么这道题目，就简化成了对以某一联通分支进行检查，判断其遍历方式。思路BFS: 一直对于某一联通分支〔题目中已经给出图中没有环〕，所以这是一棵树，如果我们确定了这棵树的树根，那么就很好判断这棵树是否是用BFS遍历得了。 怎么求得这棵树的树根呢？思路不妨枚举树根易知宽度优先搜索的最深深度与最浅深度相差为一那么对于图中的各个不同的遍历路径，我们都可以计算深度，从而判断，是否为BFS思路DFS: 白板聪明的火车司机一辆有n个门的火车驶进了一座长len的火车站，火车的n个门在火车上的位置分别为di(1≤i≤n，且d1=0，di≤len)。火车站有m个乘客，第i个乘客位于火车站的pi(pi≤len)位置，一个乘客会选择离他最近的门上车。火车的每个门都必须停在火车站内，为了让所有乘客上车时走的距离和最长，火车司机应该让火车的第一个门停在火车站的什么位置，最长距离和又是多少。输入样例第一行一个数len第二行一个数m第三行m个递增的非负整数p1，p2，……pm第四行一个数n第五行n-1个递增的正整数d2，d3，……dn45012344123输出数据一行两个数分别表示最优位置和最长距离和，答案保存3位小数0.5002.500思路枚举枚举什么？车停靠的位置？？？思路最简单的方法是以0.001为步长枚举时间复杂度为O(1000l(n+m))优化策略用反证法容易证明最优情况下至少有一个人位于两个门的中点，以此为根据可将步长调整为0.5再枚举复杂度为O(l(n+m))误差曲线小红是个聪明的女孩，最近沉迷于机器学习。她非常喜欢的方法称为线性判别分析，其中有许多有趣的性质。为了检验该算法的效率，她收集很多的数据集。更重要的是，每个数据分为两局部：训练数据和测试数据。她得到的训练数据模型的参数和测试的测试数据模型。令她惊讶的是，她发现每个数据集的测试误差曲线只是一个抛物曲线。一个抛物曲线对应一个二次函数。在数学中，二次函数的形式是多项式函数f(x)=ax^2+bx+c.如果只有一个测试误差曲线的最小误差值很容易计算。然而，有几个数据集，这意味着小红将获得许多抛物曲线。小红希望得到，使所有数据集上的最正确性能优化的参数。所以她应该考虑到，即所有误差曲线，她要面对许多二次函数，并作出新的错误定义，将其总误差。现在，她着重于以下新的功能的最小二次其中涉及到多个职能。新的函数F〔x〕的定义如下： F(x)=max(Si(x)),i=1...n.,xis[0,1000].Si(x)isaquadricfunction现在小红想要知道函数F〔x〕的最小值是多少？输入数据输入数据包含两局部。第一局部是一个整数n表示有多少个测试误差曲线第二局部由n行组成，每行有三个数字a，b，c，表示测试误差曲线的三个参数a(0≤a≤100),b(|b|≤5000),c(|c|≤5000)。2200

2-42输出数据输出小红想要的最小值0.5000思路对于这道题目，我们可以看到这个曲线有一下特殊情况：直线顶点这些情况要特殊处理。方法1由于我们要寻找一个点，使得函数F〔x〕的最小，我们最初的想法和上一道题目一样，能不能枚举我们选取的那个点，然后以此计算这个点上的函数F〔x〕的值。最终得到答案。算法特点有点：思路简单，通俗易懂缺点：算法时间复杂度很高

方法2既然枚举选取的值不行，那么这道题是不是不是枚举呢？枚举答案？方法2如果枚举答案，我们就要怎么计算这个答案，能不能在答案范围内找到呢？见白板有趣的楼道小明在漆黑的光棍节晚上还要悲催的去上一节政治课，他心里越想越