今年的提高组还是一如既往的出锅。

Day1三题原题,三题贪心,无数人AK。

Day2难度远超Day1,甚至达到noi难度,无数人心态爆炸。

Day1

铺设道路

noip2013原题。送分贪心。

直接考虑相邻的两个深度\(x\)和\(y\)。

如果\(x\ge y\),显然在填\(x\)的时候已经把\(y\)填满了,无代价;

如果\(x<y\),显然,还需要在\(y\)的时候再填\(y-x\)次。

扫一遍,直接计算代价即可。

 


货币系统

要把货币系统中的货币减少,显然就是要把所有重复的货币去掉。

那么,什么是重复的,如果已经有了两种货币\(x\)和\(y\),可以用自然数\(a,b\)表示\(ax+by=z\),那么显然\(z\)是重复的,我们不需要他。显然\(z\ge x,y\)

我们将输入的货币排序,然后直接跑完全背包就行了。如果\(z\)已经能够取到了,显然是不需要的。

 


赛道修建

一道比较套路题目。

先看到题目,“使得长度最小的赛道长度最大”,那自然就考虑到二分答案。

剩下的问题就是怎么验证答案。

考虑在树上贪心。

\(f[x]\)表示以\(x\)为根的子树中最多能找出几个长度\(\ge k\)的路径。\(g[x]\)表示去掉已经满足的路径,从\(x\)子树内往上连的最长的路径有多长。

为什么只需要存下最长的路径。因为从一个节点向上最多只有一条路径,那我们肯定希望最大化这条路径。

转移时将所有子结点的贡献\(g[y]+dist(x,y)\)排序。若贡献已经\(\ge k\),那么就直接计入答案。

否则对于当前最大,贪心地找到能与其配对的最小的贡献,计入答案。

如果找不到能与之配对的贡献,那么就用它来更新\(g[x]\)

最后就只需要知道\(f[x]>=m\)是否成立就好了。

时间复杂度是\(O(n*log^2n)\)

 


Day2

旅行

观察数据范围,发现只有两种情况:一种是树,另一种是基环树。

我们考虑树上的怎么来做。

显然我们会从节点\(1\)开始扩展,在树上,一旦向下拓展了就一定会拓展完,那么,我们从\(1\)开始,贪心的从小到大做就好了。

接下来就是考虑不是树上的怎么做了。

显然我们找到的合法路径所组成的一定是一棵树,也就是说,有一条边是没有用的。

那我们就枚举去掉每一条所得到的访问序号,取其中的最小值即可。

时间复杂度\(O(n^2logn)\)

 


填数游戏

这题目怎么推啊。根本无从下手。

用最纯的暴力打表,多跑一会儿,\(n\le 8\)的表还是能跑出来的。

然后肉眼找规律。\(n\le 3\)的规律还是好看出来的。

首先,行和列是等价的,把\(n\)作为较小的,方便处理。

  • \(n=1\),显然都成立,\(ans=2^m\)。
  • \(n=2\),\(ans=4*3^{m-1}\)。
  • \(n=3\),\(ans=112*3^{m-3}\)。

然后的规律。肉眼看不出来了。

不过直观上感觉,除了\(n=1\)是特例,别的应该都是和\(3\)的次幂相关的(本来想直接OEIS的,发现根本没有)。

  • \(n=4\),\(ans=2688*3^{m-5}\)。
  • \(n=5\),\(ans=21321*3^{m-6}\)。
  • \(n=6\),\(ans=170112*3^{m-7}\)。
  • \(n=7\),\(ans=1360128*3^{m-8}\)。
  • \(n=8\),\(ans=10879488*3^{m-9}\)。

然后还要处理\(n\ge 4,n=m\)的情况,幸亏这部分表已经打出来了。

 


保卫王国

好难啊。好难啊。

这道题目显然超纲了啊。

不过部分分很多,至少链的部分还是好处理的,有60分呢。

具体的解析看独立的另一篇文章吧。

【Noip2018】保卫王国


 


发表评论

电子邮件地址不会被公开。 必填项已用*标注