NOIP2018复盘(终于不咕咕啦!)

先占个坑,突然发现可以把发布时间调早一点

D1T1 铺设道路

题面

虽然很多人在喊是原题,但是还是写下放下三种写法吧。
很容易想到解法,就是维护区间最小值,达到\(O(nlogn)\)的复杂度。
但是这样子的写法无论是时间上还是代码复杂度上都比不过正解。

考场上炸了(具体看我的退役记orz)写了一个\(O(nm)\)的复杂度的算法,m是数字的种类。(其实这个复杂度我也不是很确定)
然后测了4组数据,学军的和牛客的只有70,另外两组是100跑的还挺快,希望官方数据不要把我卡掉啊QAQ

正解只有12行,很容易想到,前面的如果比后面的高,肯定需要额外的操作来消除,记录入cnt即可

还是想说下ccf这种恶劣的行为,又不是没有更好的题目,这样子真的是没意思……

D1T2 货币系统

题面

居然没有看出是完全背包!!!,一开始还用着自己智障的数学推论,结果最后还是打的深搜,60pt到85pt左右

正解其实有点像数论里面的筛法

考虑 $f[i]$ 表示价格 $i$ 能被出示, $f[0]=1$

由于大面值的钱不能表示小面值的,但小面值可能可以表示大面值的钱
我们对面值进行升序排序,对于每一个面值 $a[i]$ 它能表示的钱为 $x\times a[i] , x\in N $
于是我们遇到一个数 $a[i]$ 先判断 $a[i]$ 是否能被表示(即 $f[a[i]]$ 是否为1 ),如果能被表示,则答案减一,否则更新 $f$

这么简单没拿100真的很后悔

D1T3 赛道修建

题面

考场40pt,实际上有55pt的部分分是很好拿的,这里只介绍AC做法,我被卡常了!!

看到最小的最大值,马上想到二分答案,但是如何判断这个答案是否可行呢?

虽然它图画的是方方正正的,但是它任然是一棵树,我们可以考虑自下向上的统计答案

显然一个子节点到父节点的道路只有一条,为了最优,我们希望子节点拿一条最长的路贡献给父节点

假设子节点能给父节点提供的长度为 $val_i$ (其中已经包含子节点到父节点路径长度)

该父节点首先要考虑能否选出满足二分答案k的赛道。

  1. $k\leq val_i$ 这时这条赛道符合
  2. $k\leq val_a+val_b $ 这时这两条路径组合成的道路符合

对于第一种情况我们很容易就能判断出,但是对于第二种情况,我们如果希望答案最优,就要从最小的 $val_a$ 考虑,为此,我们需要找到一个最小的 $val_b$ 使得 $k\leq val_a+val_b $

这个可以用 $multiset$ 来处理。

注意被选中的路径不能再贡献给当前节点的父节点了。

可以考虑找出树的直径优化二分上界。

在loj上最慢的点也才200ms,但是洛谷上T了两个点(怕不是要手写平衡树)

D2T1 旅行

又是一道本该拿满分的题,考场上打开题目->一眼看出基环树->只听过名字不会写->拿60pt愉快走人吧~

结果我完全忽视了8700k和n<=5000的存在,明显有一种平方的做法啊,就是暴力删边,然后就是一棵树了……mdzz

点赞

发表评论

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