【NOIP2018】题解报告

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

D1T1 铺设道路

题面

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

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

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

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

D1T2 货币系统

题面

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

发表评论

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