【NOIP2018】游记

Day0

lxx老仙果然毒奶,说不考dp确实变成了dp专场

晚上试机时一位大佬看我打线段树,一脸不屑,二话不说写起FHQ Treap,本蒟蒻瑟瑟发抖,,,

试机感觉机器还是挺好用的(比lqyz的好多了)

Day1

  • T1

一眼看出原来自己做过,但是就是忘了是哪里的题了,只是记得一个O(n^2)做法,本来想试试线段树优化一下就OK了,结果没调出来,然后就弃了

T1就弃了我还是真菜呢

  • T2

一开始一脸茫然

后来看到时感觉直接消掉可以用其他货币组成的大货币,然后加了个标记数组,如果这个金额可以组成,就从这个金额基础上再加上各种货币的金额,把所有再次组成的金额标记上就是了,如果单个货币的金额上有标记就把ans--(ans初始是n)

似乎对?不太清楚,反正我是不会什么背包做法

  • T3

这是个啥外意???

管他什么正解,直接看暴力

m = 1 ? 这个不是树的直径吗?直接写上。

bi = ai + 1 就是个链吧,写二分呗。(可是我怎么调也调不对,很无奈)

ai = 1 菊花图?没时间了,XJB贪心一下吧

Day2

  • T1

m = n - 1不就是按一定顺序dfs嘛,直接搞定

m = n就茫然了,我直接写的一个错误的想法(鬼知道考场上我怎么想的)

  • T2

啥东西?状压吗?

不会,打暴力!

但是我自己把自己坑了,我特判了(n == 1 || m == 1)时ans = 0,实际好像直接用2的n次方就好QAQ

  • T3

树的最大独立集?好办啊!

等等,怎么还有固定的?还要变啊。不太会呢。

先打dfs暴力,去想T1的剩下40分去了。(最后也没想出来)

最后预计(luogu)得分 100 + 100 + 25 + 60 + 15 + 16 = 316

别问我为什么O(n^2)能过T1,我也不清楚为什么,反正洛谷数据就过了。T3的XJB贪心忘了自己怎么贪的了,T5被自己坑了,所以不太可能拿到多少分了啊

总体体验

Day1诸位老仙都260+,我打算Day2翻身,却被Day2的神仙题目吊打。体验极差诶。

原文地址:https://www.cnblogs.com/yizimi/p/10056329.html