NOIP2018提高组解题报告

《NOIP2018提高组解题报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、NOIP2018解题报告南京师范大学附属中学陈天2018/11/21（此前题目填数游戏算法五部分出现笔误，已更正由于公式编辑器问题，部分数学公式可能无法正常显示Day1铺设道路road标签：贪心简化版题意：给定一个非负整数序列，每次操作可选择一段区间使其中的数全部减1，求全部减为0需要的最少操作次数。这题做法有很多……主流大概这么几种：算法一RMQ：考场上怎么简单粗暴怎么来每次找到最小值然后分治，不交并总数是O(n)的时间复杂度O(nlogn)，空间复杂度O(n)算法二单调栈：头铁就是要写线性和算法一差不多，只不过使

2、用了单调栈维护时间复杂度/空间复杂度O(n)算法三差分完正项的和就是答案。时间复杂度O(n)，空间复杂度O(1)作为一道送分题，算法三应该是比较正常的思路然而场上甚至有人写了线段树，不知道是不是现在的选手数据结构有点学傻了……货币系统money标签：贪心，dp，背包简化版题意：给定n个不同的正整数，求最少需要几个正整数，使得与这n个整数在非负整数权线性组合下等价。这题也很显然吧……首先给出的整数本身肯定是能被表示出来的，因此超过最大值的不用管，因为简化后肯定能用这些整数表示出来。然后从小到大考虑每个整数是否能被原系统

3、表示，如果不能就不管，如果能但可以被之前加入的更小的数表示也不管，否则就将其加入答案。贪心的正确性是显然的，因为小于可被原系统表示的最小整数的数必然不能选，而该最小整数如果无法被此前选的数表示，就必须选。考虑完该数后，将递归地得到一个子问题。实现也很简单，就是一个裸的完全背包。在具体实现上的分歧给出了三种算法：算法一老老实实跑完全背包时间复杂度O(T·n·Ai)，空间复杂度O(Ai)算法二考虑dp值只有0/1，可以利用压位加速转移，不过每次直接重复移位多遍效率很低，可以再考虑二进制分组，即每次分别移Ai,2Ai,4A

4、i⋯位后与或原状态取或。时间复杂度O(T·n·AilogAi32or64)（取决于压位用bitset或手写）空间复杂度O(Ai)这两种算法复杂度看上去比较极限，实际上并不会跑满，加之今年评测机性能极其优秀，完全没有压力。**进阶算法**背包问题本质上是卷积，可以使用多项式理论对其进行优化。这部分内容超出了NOIP的范畴，且在此题数据范围下没有明显优势，在此不多赘述。道路修建track标签：树，二分，贪心，dp简化版题意：给定一颗n个点的带边权树，在树上找出m条边不相交的简单路径，使得边权和最小的路径的边权和最大。这道

5、题还是有一点难度的，我们来稍微分析一下算法一考虑m=1的情况，此时不需要考虑相交，只需要找出一条最长路径，即求树的直径即可。时间复杂度/空间复杂度O(n)可以获得20分算法二考虑n≤15的情况，可以记dp(S,k)表示使用的边的集合为S、已选择路径数为k的答案。每次枚举一条路径进行转移，只要边集不相交即可。时间复杂度O(2n-1n3)，空间复杂度O(2n-1n)结合算法一可以获得30分对于这类最大化最小或者最小化最大的问题，答案一般具有单调性，一个常见的思路是二分答案。因此在接下来的算法中，我们首先二分答案，并设当前

6、二分的答案为curw。这样问题就转变为，求树上最多有几条边权和≥curw的路径。算法三对于一条链的情况，由于边权都为正，我们只需要从链的一端向另一端做，如果当前一段路径的权值和

7、n+nlogw)，空间复杂度O(n)结合算法一、二、三共可获得55分算法五考虑将算法四扩展到一般树上的情况。任取一点为根，类比算法四容易发现，树上一条路径要么是一条自上而下的链，要么是从两端点lca向下的两条链。一个很自然的想法是，对于每条路径，我们在其lca处进行统计。如果给定某点x在其各子树内向下的链的长度，使用算法四即可求出以x为lca最多能得到的合法路径条数。然而我们面临的问题不是计算是构造，我们并不知道这些链的长度为多少时可以取得全局最优解。为了得到这些信息，以下性质是必需的：全局最优解必然建立在各子树最优

8、解的基础上这很容易理解，因为我们不会将一条子树内本可以配出来的路径拆掉，交给其父亲节点去配；这明显不如保留这条路径，再换另外一条链向上配。接下来注意到一条从x向下的链必然是一条从其某子节点v向下的链加上(x,v)这条父边，即可以从v的子问题得到。因此我们可以使用类似树dp的思想，自底向上贪心，每一层优先使配出的路径数尽可能多，在此前提下尽可能保