NOIP2018提高组解题报告.doc

NOIP2018 解题报告南京师范大学附属中学 陈天2018/11/21（此前题目填数游戏算法五部分出现笔误，已更正由于公式编辑器问题，部分数学公式可能无法正常显示Day 1铺设道路road标签：贪心简化版题意：给定一个非负整数序列，每次操作可选择一段区间使其中的数全部减1，求全部减为0需要的最少操作次数。这题做法有很多主流大概这么几种：算法一RMQ：考场上怎么简单粗暴怎么来每次找到最小值然后分治，不交并总数是O(n)的时间复杂度O(nlogn)，空间复杂度O(n)算法二单调栈：头铁就是要写线性和算法一差不多，只不过使用了单调栈维护时间复杂度/空间复杂度O(n)算法三差分完正项的和就是答案。时间复杂度O(n)，空间复杂度O(1)作为一道送分题，算法三应该是比较正常的思路然而场上甚至有人写了线段树，不知道是不是现在的选手数据结构有点学傻了货币系统money标签：贪心，dp，背包简化版题意：给定n个不同的正整数，求最少需要几个正整数，使得与这n个整数在非负整数权线性组合下等价。这题也很显然吧首先给出的整数本身肯定是能被表示出来的，因此超过最大值的不用管，因为简化后肯定能用这些整数表示出来。然后从小到大考虑每个整数是否能被原系统表示，如果不能就不管，如果能但可以被之前加入的更小的数表示也不管，否则就将其加入答案。贪心的正确性是显然的，因为小于可被原系统表示的最小整数的数必然不能选，而该最小整数如果无法被此前选的数表示，就必须选。考虑完该数后，将递归地得到一个子问题。实现也很简单，就是一个裸的完全背包。在具体实现上的分歧给出了三种算法：算法一老老实实跑完全背包时间复杂度O(TnAi)，空间复杂度O(Ai)算法二考虑dp值只有0/1，可以利用压位加速转移，不过每次直接重复移位多遍效率很低，可以再考虑二进制分组，即每次分别移Ai,2Ai,4Ai位后与或原状态取或。时间复杂度O(TnAilogAi32 or 64 )（取决于压位用bitset或手写）空间复杂度O(Ai)这两种算法复杂度看上去比较极限，实际上并不会跑满，加之今年评测机性能极其优秀，完全没有压力。*进阶算法*背包问题本质上是卷积，可以使用多项式理论对其进行优化。这部分内容超出了NOIP的范畴，且在此题数据范围下没有明显优势，在此不多赘述。道路修建track标签：树，二分，贪心，dp简化版题意：给定一颗n个点的带边权树，在树上找出m条边不相交的简单路径，使得边权和最小的路径的边权和最大。这道题还是有一点难度的，我们来稍微分析一下算法一考虑m=1的情况，此时不需要考虑相交，只需要找出一条最长路径，即求树的直径即可。时间复杂度/空间复杂度O(n)可以获得20分算法二考虑n15的情况，可以记dp(S,k)表示使用的边的集合为S、已选择路径数为k的答案。每次枚举一条路径进行转移，只要边集不相交即可。时间复杂度O(2n-1n3)，空间复杂度O(2n-1n)结合算法一可以获得30分对于这类最大化最小或者最小化最大的问题，答案一般具有单调性，一个常见的思路是二分答案。因此在接下来的算法中，我们首先二分答案，并设当前二分的答案为curw。这样问题就转变为，求树上最多有几条边权和curw的路径。算法三对于一条链的情况，由于边权都为正，我们只需要从链的一端向另一端做，如果当前一段路径的权值和curw就加入该段，否则就开始新的一段路径。时间复杂度O(nlogw)，空间复杂度O(n)结合算法一、二可以获得45分。算法四对于菊花图（或者叫刺猬图），一条路径要么是一条边，要么是两条边。因此可以将所有边排序，先让所有curw的边自成一条路径，剩下的边贪心配对，具体方法是使用双指针，每次让当前最大的边尽量和小的边配。时间复杂度O(nlogn+nlogw)，空间复杂度O(n)结合算法一、二、三共可获得55分算法五考虑将算法四扩展到一般树上的情况。任取一点为根，类比算法四容易发现，树上一条路径要么是一条自上而下的链，要么是从两端点lca向下的两条链。一个很自然的想法是，对于每条路径，我们在其lca处进行统计。如果给定某点x在其各子树内向下的链的长度，使用算法四即可求出以x为lca最多能得到的合法路径条数。然而我们面临的问题不是计算是构造，我们并不知道这些链的长度为多少时可以取得全局最优解。为了得到这些信息，以下性质是必需的：全局最优解必然建立在各子树最优解的基础上这很容易理解，因为我们不会将一条子树内本可以配出来的路径拆掉，交给其父亲节点去配；这明显不如保留这条路径，再换另外一条链向上配。接下来注意到一条从x向下的链必然是一条从其某子节点v向下的链加上(x,v)这条父边，即可以从v的子问题得到。因此我们可以使用类似树dp的思想，自底向上贪心，每一层优先使配出的路径数尽可能多，在此前提下尽可能保留一条最长的向下的链留给其父亲节点。如果恰好配完了，那么留给父亲节点的链长就是0。对于分支不超过3的测试点，直接暴力枚举或者手动讨论每一层配对及保留链的情况即可，时间复杂度O(nlogw)，空间复杂度O(n)；对于n1000的测试点，暴力枚举保留哪一条链之后直接套用算法四即可，时间复杂度O(n2logw )，空间复杂度O(n)。至此可以获得的暴力分已经达到85分。算法五已经比较接近正解了，在此基础上稍微优化一下就得到了三种主流算法：算法6.1配对的过程中使用multiset维护，不断尝试用较小数替换较大数。笔者写的并不是这种做法，所以具体实现不是很清楚。时间复杂度O(nlognlogw)，空间复杂度O(n)，然而由于set常数较大，似乎并不能通过此题。算法6.2考虑我们保留的链越长，可以配出的路径数就越少，因此可以先求出最多可以配的对数pair，接着二分保留的链的长度，每次判断一下保留这条链后是否还能配出pair对即可。时间复杂度O(nlognlogw)，空间复杂度O(n)常数虽然比算法6.1小，但比算法6.3还是大不少的。不过由于今年评测机性能优秀，可以通过此题。算法6.3同样考虑先进行一次贪心求出最多可以配的对数pair。贪心的过程中顺带记录一下每个数是否被使用了，如果第pair+1大的数被使用了，那么能保留的就是没有被使用过的最大数。否则由于我们只需要保留一条链，只需要考虑最大的2pair+1个数。考虑使用第pair+1大的数替换第pair大的数，如果可以替换就继续考虑用第pair大的数替换第pair-1大的数直到无法替换，或者第1大的数已经被替换出来为止。此时被替换出来的数就是可以保留的最大值。这个过程实际上就是枚举留下哪一个数，将剩下的数按最大配最小贪心匹配了，只不过每次只需要判断被替换的那一对数，因为其它配对并没有被改变。时间复杂度O(nlognlogw)，空间复杂度O(n)虽然理论复杂度和算法6.2是一样的，不过这个复杂度主要来自sort，除sort以外复杂度是一个log的，而sort的常数非常小，可以无压力通过此题。笔者场上使用的是这种做法，然而由于对第pair+1大的数必须使用的情况特判失误，直接挂成了85分。从考场策略的角度来说，也许使用算法6.2这种无脑二分比一味追求算法效率更妥当一些吧Day2旅行travel标签：树，基环树，dfs，贪心简化版题意：给定一颗树或一颗基环树，求其字典序最小的dfs序。算法一对于树的情况，显然最优解应该从1号点开始遍历，并且每次应该访问未访问过的点中编号最小的。只需要将各点邻接点预先排序，然后贪心地dfs一遍即可。时间复杂度/空间复杂度O(n)可以获得60分算法二对于基环树的情况，同样预先将各点邻接点排序。和树的区别在于，基环树上有一条边是用不到的。由于数据范围比较小，可以暴力枚举删掉哪条边，之后用算法一求出dfs序，如果合法就更新答案。时间复杂度O(n2)，空间复杂度O(n)使用以上两种算法即可通过本题算法三其实基环树也可以直接dfs，不过讨论起来略麻烦一些。主要区别在于基环上点的访问顺序，可能会先沿某个方向访问若干点及其子树，然后反方向访问剩下的点。具体实现可以参考一下标算。时间复杂度/空间复杂度O(n)填数游戏game标签：组合计数，dp，搜索，打表简化版题意：nm方格表的每个格子可以填入0/1，求有多少种填数的方案，使得对于任意两条从(0,0)到(n,m)的NE-Lattice Path，都满足方向字符串字典序较大者的01数字串字典序较小。此题难度破格，某群给出的评价是“难度接近HNOI2017”，部分现役集训队选手都未能在现场AC此题。实际上看完题解后你也许会觉得这么easy的题为什么让那么多人都自闭了。其实这道题主要是思维难度比较高，发现性质和正确的思考方向后做起来还是比较轻松的。由于n,m是等价的，在接下来的分析中我们不妨假设nm。算法一大力暴搜时间复杂度O(2nm)，可以获得20分。算法二对于n=1，答案显然就是2m；对于n2，一个很明显的必要条件是满足如下性质：性质1. 设格子(i,j)中填的数为a(i,j)，则ai,j+1 a(i+1,j)否则任取两条第一次从(i,j)分歧的路径都不满足题意。同时容易证明，这个条件在n=2时是充分的。这一点非常重要，因为包括笔者在内的很多人一开始都低估了这道题的难度，发现这个性质后直接写了一发假的状压dp，然而事实上这个性质并不充分。不过n=2时这个做法是对的，可以按斜线或按列进行状压dp，转移时只需要判断一下是否满足斜线单调性即可。时间复杂度O(2nm )，当然也可以用矩阵乘法优化到O(8nlogm)。结合算法一可以获得50分（是不是有点太多了算法三考虑寻求新的性质。其实稍微考虑一下性质1的局限性很快就可以发现。如果一时缺少思路的话，一个可行的技巧是将小数据（比如n=3,m=3）满足斜线单调性的不合法方案打印出来进行观察，而观察后容易发现，这类方案都形如下图：即两条相交路径在相交前的数字序列完全相同，相交后走势发生了反转，而斜线单调性无法保证相交后的数字序列满足题意。于是容易得出另一条性质：性质2. 如果存在a(i,j+1)=a(i+1,j)，那么在以(i+1,j+1)为左上角的子矩阵中，每一条斜线上的数是相同的因为如果这个子矩阵中某条斜线上的数不同，我们总能找到类似上图的两条不满足题意的相交路径。另一方面，在增加了这条性质后，考虑任意两条的路径第一次产生分歧时，要么两个格子中数字不同分出了大小，由性质1可以保证满足题意；要么两个格子中数字相同，接下来无论怎么走，一旦相交，根据性质2都能满足题意，这就证明了充分性。得到了此题的充要条件后，我们就可以按斜线搜索，根据性质1每次枚举0/1的分界点，搜完所有斜线后判断是否满足性质2即可。时间复杂度O(n!2nm-nm)，根据实现的常数510分钟左右即可打出n,m8的答案表。实际上可以一边搜一边判断是否满足性质2，可以剪掉大量不合法的情况。优化后1s内可以跑完n,m8的情况。打出答案表后时间复杂度O(1)，空间复杂度O(nm)可以获得35分，结合算法二可以获得65分算法4.1通过算法一打表可以发现，当n=2或n=3时，似乎有：ansn,m=3m-nans(n,n) 于是只要打出33的答案表即可。时间复杂度O(logm)，可以获得65分。结合算法三可以获得80分。算法4.2算法一效率比较低，当n4时数据量不够，不足以验证规律。事实上，ans4,53ans(4,4)，笔者现场就是因为这个原因，误以为规律只对n=2,3适用，错失良机。通过算法三打表可以发现，算法4.1中的规律有一些偏差。实际上，对于所有n2，当mn+1时有：ans(n,m)=3m-n-1ans(n,n+1)。于是类似的，只需要打出89的答案表即可。笔者赛后使用算法三写的打表程序只需要3.8s就可以跑出这个答案表，基本上没什么压力。时间复杂度O(logm)，可以通过此题AC了本场比赛的神仙zzq场上使用的就是这种做法，不过以上规律为什么是对的，笔者不知道，出题人不知道，神仙zzq似乎也不知道。如果有同学会证的话欢迎与笔者联系。算法五考虑一些比较正经的、不需要投机取巧的做法。如果一个以(i,j)为左上角的子矩形内所有斜线上的数相等，称(i,j)满足性质2。一个格子(i,j)满足性质2等价于如下限制： a(i,j+1)=a(i+1,j) (i,j+1)和(i+1,j)分别满足性质2这样我们就可以按照斜线dp，因为等价变形后的限制允许我们只记录当前斜线上哪些格子满足性质2，并利用传递性对后续斜线进行限制，而不需要记录后续所有斜线的状态。记dp(i,S)表示处理了前i条斜线，第i条斜线上满足性质2的集合为S的方案数。根据性质1，我们每次只需要枚举下一条斜线的0/1分界点，对应转移即可。注意到第1行不可能受性质2限制，第n行是否满足性质2是毫无意义的，都不需要记录，因此s=2n-2而不必是2n时间复杂度O(2n-2nm)，可以获得80分。如果使用矩阵乘法优化，时间复杂度O(8n-2logm)，即可通过此题。算法六如果读者直觉足够敏锐，那么想必已经注意到了这一点算法五中实际有效的状态仍然相当有限。事实上，如果我们枚举了左起第2条和第3条斜线上填的数字，后续斜线上的大量格子就已经被限制好必须相同了。对这两条斜线上填的数为(00/11 , xxx)，(01 , 000/111)，(01 , 001/011)的几种情况分别进行讨论，接下来要做的就是在满足中间格子限制的前提下确定剩下的1n 或 1m 或 2n 或 2m的矩形中填数的方案，这部分可以通过dp或直接用组合方法进行计算。由于此处的讨论着实烦琐，写到这里时也已经是笔者写这篇报告的第五个晚上了，实在没有精力带着读者慢慢讨论。根据标算留下的数字注释，笔者推测算法六应该接近或者就是官方标算的做法了，所以剩下的具体讨论如果实在不会推，可以参考标算。时间复杂度O(n+m)，可以将n的数据规模扩大到和m同阶，在此题数据范围下已经足够优秀了。*进阶算法*对算法六中的dp使用矩阵乘法，或直接推出数学公式（如果存在的话），时间复杂度即可优化到O(logn+logm)，所以事实上此题n,m的数据规模是完全可以扩大到1018的。该算法应该是此题目前的最优解法了。保卫王国defense标签：树，dp，倍增，数据结构简化版题意：给定一颗带点权树，要求从中选择若干个点，使得任意两个相邻点至少有一个被选中。给出若干组询问，每组询问钦定两个点选择与否，求所有满足条件的方案中，被选中点的最小点权和是多少。询问之间相互独立。算法一非常基础的树dp，记f(x , 0/1)表示以x为根的子树是否选x时的最小点权和，那么显然有：fx,0=x,vE,vfa(x)fv,1fx,1=wx+x,vE,vfa(x)minfv,0,fv,1对于每组询问都进行一次dp，遇到受限制的点将违反限制的dp状态的值设为inf即可。时间复杂度O(nm)，空间复杂度O(n)可以获得44分算法二注意到如果预处理出不受限制情况下的dp值，那么对于每组询问，只需要重新计算受限制点到根路径上的dp值即可。时间复杂度O(n+depth)，空间复杂度O(n)可以获得52分算法三进一步优化算法二，我们并不需要重新计算a,b到根路径上所有点的dp值，只需要处理出这a-b路径上的dp值即可，因为在得到了其lca的dp值之后，只需要换根就能求出整棵树的dp值。至于如何实现换根dp，就是一个标准的两遍dfs，第一遍自下而上，第二遍自上而下即可。设g(x,0/1)分别表示点x取或不取时，整棵树去掉以x为根的子树后，剩下部分的答案。转移方程如下：gx,0=gfa,1+ffa,1-minfx,0,fx,1gx,1=mingfa,0+ffa,0-fx,1,g(x,0)时间复杂度O(n+m+dis(a,b)，空间复杂度O(n)可以获得68分算法四对于所有询问要求必须在1号点驻军的测试点，只需要以1号点为根，并且在第二遍dfs处理换根dp的时候强制1号点必须选即可。时间复杂度O(n+m)，空间复杂度O(n)结合算法三可以获得84分算法五到这里感觉似乎没有什么比较好的处理方法了，那么我们不妨先考虑一下比较简单的一条链的情况。对于这种情况，dp的转移方程会简单一些：fi,0=f(i+1,1)fi,1=wi+minfi+1,0,f(i+1,1)可以看出，转移的方式与需要的参数只和交界处的状态有关，类似SHOI2008 traffic。对于这种转移，只要按交界处状态维护所有可能的dp值，转移就可以满足结合律，进而可以快速进行修改与询问。具体来说，可以维护一颗线段树，对于一段区间l,r维护四个dp值f00,f01,f10,f11，分别表示左右端点选/不选情况下这一段区间的答案。合并两个区间的时候只需要枚举中间点的状态，对应转移一下就可以了。修改的话，只需按照普通线段树的操作修改，之后向上更新；询问的时候正常询问即可。此题中，我们相当于每次需要修改两个点的dp值，之后询问1,n的答案即可。时间复杂度O(n+mlogn)，空间复杂度O(n)结合算法一可以获得68分结合算法三可以获得80分结合算法四可以获得84分结合算法三、四可以获得88分。虽然看上去只多了4分，但算法五对一般情况有重要的启发意义。最后，我们将链上的做法推广到一般的树上的情况。参考算法三的想法，每次询问的时候，我们相当于要确定路径a-b上的点的状态，从中找出一组最优解。换言之，我们其实是把这条路径拉出来，从两端向中间分别进行dp。设dp(x,0/1)表示以路径上一点x为根的子树的答案，p=fa(x)，转移方程如下：dpp,0=fp,0-fx