NOIp06-15题解分析

NOIp20101.机器翻译：队列模拟，送分题2.乌龟棋：裸的dp，我在vijos上使用最裸的O(abcd)算法通过3.关押罪犯：我用的是二分答案+二分图染色判断。（宽搜时STL的queue常数巨大，换了手写队列就过了。）4.引水入城：FloodFill、搜索+动态规划。比较麻烦。NOIp20111.铺地毯：模拟，送分题2.选择客栈：枚举+优化3.Mayan游戏：搜索[+语文水平+心理素质]4.计算系数：组合数学题。5.聪明的质检员：二分+前缀和优化6.观光公交：贪心（或费用流）NOIp20121.Vigenère密码：字符串处理。送分题。2.国王游戏：贪心。证明并不非常简单（反证法+交换相邻元素）。（但是考场上可以猜、试出贪心规则）3.开车旅行：倍增+递推。4.同余方程：裸数学题5.借教室：二分（或线段树卡常）6.疫情控制：二分答案+倍增+递推NOIp20131.转圈游戏：快速幂2.火柴排序：贪心（同样也是证明稍烦，但结论很容易猜出）+求逆序对个数3.货车运输：最大生成树+树上求路径最小值（树剖或倍增之类的）（反证法证明）4.积木大赛：贪心5.花匠：离散化+DP求拐点+线段树优化（复杂度O(nlogn)，据说存在O(n)做法）6.华容道：最短路，通过一些奇异的方法转化NOIp20141.生活大爆炸版石头剪刀布：模拟即可2.联合权值：dfs+数学优化3.飞扬的小鸟：DP（类似背包问题）4.无线网路发射器选址：搜索，注意边界即可5.寻找道路：反向建图，两遍DFS或BFS即可6.解方程：数学题，方程取模+黑科技常数优化NOIp20151.神奇的幻方：模拟（听说有人手推打表233332.信息传递：限制出度为1的最小环，Tarjan或者BFS均可3.斗地主：30分很好骗。dfs和状压dp似乎（理论上）均可（常数原因需要一定优化）4.跳石头：二分答案5.字串：DP+滚存优化6.运输计划：二分答案+路径求交（事实上本题存在O(n)做法，本题又是卡常的题）noip2013day1题1:二分幂，没什么好讲的了。题2:如果看懂题意就很好办了，交换顺序就是求逆序对，记得哪年的初赛问题求解有类似问题，但那是一个数组。。归并复杂度（nlogn），三次即可求解，貌似有其他更高效的算法？？题3：之前写的解题报告的代码就是把别人的改了一下，自己都不知道原理，现在知道了，并查集+最大生成树+树上倍增，之前还不知道有树上倍增这个考点，现在看到真的很像最大流，就是起点终点那么多不知道怎么处理好，也就不去实现了。。博客上的思路就是记录每个点的LCA，就是把连接好的点建树，找的时候并查集，，不连通就-1，连就不断更新最小值的最大。。其实这些题解法很多。。看到有些人双向广搜也ACday2题1：模拟。。不讲题2：看上去就像DP，有点特别。。可以形象的说成是波动数组的最大长度。。之前说过在wikioi的别人代码上学到一种无论是空间还是时间都接近无敌的算法。。边读边比较。。考试应该想不到吧。。还是老实点用dp好。。也不会难写题3：最短路。。spfa方程。。不会太难写，就是剪枝有点复杂。。把空格当成起点。。接着就判重吧。。其实搜索也能过吧noip2012day1题1：字符串模拟题2：数学推导能力+恶心的高精度除法题3:这题让我告别链表盲，但是还不够熟。预处理就是记录每次的前一次和后一次能到的城市。。过一遍路程，输入逐一寻找答案day2题1：扩展欧几里得算法题2：二分答案+前缀和题3:其实就是尽量让军队往上，然后贪心最大的匹配最大的。。貌似是这样，反正自己打不出来。。noip2011day1题1：模拟，逆向思维，记录最上面的那块地毯题2：搜索+简单剪枝，以甲乙的选择为循环验证题3：dfs+特别判断+剪枝。。算是比较水的第三题吧，考了两道搜索day2题1：纯模拟。题2：线段树+二分答案题3：又是水题。。首先加速器必须用在到达时间比在此景点等候的人晚点才须加速，而且会影响后面的时间，只需逐一去计算，取减少时间最多的那段时间进行加速，并保证用时大于零即可。（ps.不想吐槽了，没有一道题是超过100+代码的）noip2010题1：模拟题2：dp，只有4种卡片，以卡片数为动态数组，注意第一张卡片会自动取题3：并查集经典题+排序轻松过题4：两遍bfs，第一次染色判断是否有解，第二次记录能到达最后一行的点，转换为经典得线段覆盖问题noip2009题1：字符串模拟题2：数论。。欧几里得+分解质因数题3：贪心+链表。。在低价买入，在高价卖出，注意判断是否为通路题4：搜索+优化。。有点水noip2008题1：字符串加质数判断题2：穷举秒过题3：dp，两条路同时进行，判断不重复即可题4：奇葩的模拟，貌似理解透了就是四个数组记录四个栈状态noip2007题1：快排统计输出，桶排会超的题2：字符串模拟题3：dp+高精度+压位题4：语文题，，floy求直径最小值noip2006题1：经典区间dp题2：带条件的背包问题题3：语文题，，一开始弄了好久都不懂，怪不得模拟也弄到第三题，相比之下前两题好理解的多题4：也是模拟。。带点数论吧搜索四题：例1：斗地主题目分析：这道题的话实际上是一道比较没有技术含量的复杂搜索题。其特点主要就是烦。看清楚细节这题应该是没有问题的。预处理：首先为了方便，肯定把3变1,4变2.。。。到13变11,1变12.但是这里有一个简单的优化，吧2变成14，双王变成15.因为这样的话在接下来判断顺子的时候就可以方便多了。搜索：这道题广度搜索明显不合适，因为要存下大量的信息。而这道题我们判断一下，发现其实可以比较简单地进行回溯（因为只有牌数的加减罢了）。还有，我们可以吧出牌的种类分成单张，一对，带牌，和顺子。因为其实每一类的性质是一样的。其中，单张和一对除了在四带二之中要判断之外，没有其他明显的区别。所以，可以何为一类来考虑。其中首先第一个认清的是，出单张一定是最差的选择，而其次的是一对。这两者在搜索之中不需要单独进行搜索。在最后一步一次性处理掉就可以了。因为他们的出牌方式只能单独出。没有带上啥啥之类的，也没有条件，是相对独立的出牌方式。那么剩下的就是带牌和顺子了。两种搜索应该都行。不过如果带牌的话要枚举所有的带牌方式，就是把对子和单张一起枚举。而顺子明显简单，只要从数量为5开始，顺次向下加数量，全部枚举就OK。而且回溯的时候也好回溯。所以选用枚举所有顺子。然后把能带牌的都全部先带掉。最后出单张or对子。难点分析：第一认清单张和对子不需要枚举。第二权衡带牌和顺子的利弊。例2：靶形数独当然，这道题如果直接枚举的话也不是不可以啦，就是O（9^（9*9-24））那么大而已。。。。额，这道题我一开始的想法是，模拟人做数独的方式，先把1~9可能存在的位置枚举一遍（存在九个图里）然后暴力，然而连样例都超时。。。。正解其实简单得不可思议，其实就是减小常数而已。先从可填的数少的地方开始搜索就可以了。但是还是有很多个优化的，以下列举出来：1.首先，并不是像我这样无脑存下9张图代表1~9的数字可填位置，而是利用数独的三个限制条件：（1）行（2）列（3）九宫格。来进行限制，即开启三个数组，然后分别代表第i个数在第j个横行是否可填。。。。然后的话，对于九宫格，这里有一个比较快捷的编号方法，下面贴代码，看看就懂intwz(inti,intj){return((i-1)/3)*3+((j-1)/3)+1;}2.然后自然就是每次搜索的时候，先把整个图暴力一遍，然后寻找一个可填数字数目最少的空格，枚举数字填上去。这样可以减少搜索的复杂度。3.最后一个优化。在改变数字的时候，加入位运算。怎么整，由于九宫格，横行，纵行的数组都是bool数组。所以把0-1或1-0直接用^1就OK。至于如果是要把九宫格填上一个数字或去掉一个数字，^a即可（初始化只要没有数字全部默认0），然后最后计算结果，输出Ok。4.搜索结束的标志：步数达到81.好咯，这题就是那个位运算比较难想到，储存数组的方式比较难想到。额。。算是一道考编程功底的题目吧。哎像我这种无脑存图的家伙，你们就不要学了。。下一道。。例3：Mayan游戏这道题是一道超级超级超级烦的搜索题目。额，，一开始完全不知道怎么入手。根本不知道怎么回溯。首先考虑一下，这道题广搜的话如果你写出来我服了你。深搜肯定要回溯。可是这个又是消方块的，又是掉落的，怎么回溯。所以我就卡在这里。最后看题解，它就直接把每张图都存下来了。。。太bt了。第一次看到如此暴力的搜索方式。。总之，把每次搜索的那张图存下来。然后直接强行暴搜咯。然后考虑优化。我们不难发现，方块移动的时候两种情况。第一种，交换方块，第二种，旁边是空白的。如果说是交换方块的话，从左往右和从右往左没区别。而右移答案的优先级更高，所以干脆把所有的交换移动都改右移。然后如果是空白的话，左移右移都需要考虑，就没啥好说的了。然后没回判断一下会不会掉下去啊，会不会消掉啊之类的都不难。而且这题明摆着就不想让你超时的节奏，所以大胆搜！如果不信的话，看看下面：不解释咯例4：华容道这道题其实主要是图论。就是spfa。但是其实最难的部分是在预处理里面的搜索。所以我就把他算到搜索题里面的。额，先来看看题目分析：稍微有点脑子的都知道这题肯定不是全搜索。这题给我灵感的是：题目说明里的一句话：要将指定块移入目标位置，必须先将空白块移入目标位置。这时我突然想到。如果要把指定块进行移动的话，那么必须做的一点就是将空白快移到指定块的旁边。唯有这样，才能实现方块的移动。这个时候，再次思考，指定块移动有4个方向。那么首先要做的一件事情就是要把空白块移动到指定块的旁边。这才能开始进行移动。这可以使用dfs来实现我们发现，它对于同一张图会发送多个请求。也就是说，我们的预处理处理得越多越好。那么，再次思考。如果指定块位于(x,y)位置，白块相对于指定块是dir（之后我们记录这种状态为（x，y，dir）），那么指定块一定可以从状态(x,y,dir)转移到(x+dx[dir],y+dy[dir],!dir)其中!dir指的是与dir相反的方向。但是如果我们想要让指定块不走dir方向的移动呢？那我们只能吧空白快移动到我们想要走的方向上，然后进行转移那么，联系之前对于图的预处理，我们要做的事情呼之欲出：枚举整张图，对于每一个点（x,y）记录一个数组，保存（x,y）从dir1方向到dir2，dir3，dir4分别所需的步数。预处理到这里，我们分析一下我们的工作是：要把指定块移动到目标位置。那么移动到目标位置时白块必定在指定块的旁边。至于在哪个方向上，无所谓。那么我们的事情就是吧状态(sx,sy,dir1~4)转移到(ex,ey,dir1~4)中最短的那条路径。而我们的每一种状态都具有唯一性。所以可以看成一个点，每一种状态转移都可以通过之前预处理的路径来实现，所以这题实质上是在找最短路！所以直接用spfa对于每次请求作出答案即可。