NOIP2018乍矢记

NOIP2018乍矢记

陈述事实

这次NOIP，是我OI现役生涯中，可以说是最后一次了。
这次尽了力，就问心无愧了。

Day 1

今天的三道题目有很榜的葱鸡力，时尚又犀利。
浪我子看一眼，就想立刻去乍矢。
T1
打了对拍。
A n s = a [ n ] + ∑ i = 1 n − 1 m a x ( 0 , a [ i − 1 ] − a [ i ] ) Ans=a[n]+sum_{i=1}^{n-1} max(0,a[i-1]-a[i]) Ans=a[n]+∑i=1n−1​max(0,a[i−1]−a[i])
拍了很久都没错。
T2
最不该没AC的一道题目。丢了20分血亏。
题意：给出一堆数a[i]，一个数属于集合S，当且仅当这个数能够用a[]中若干个数的和来表示。（同一个a[i]可以选多次）
上年第一题，就是n=2的，然后求最大的没出现在S中的数是多少。
这题有一个结论。
如果a[]中一个数能够被a[]中其他的数的和（同个数可选多次）表示，那么这个数显然被踢掉。
直接bfs什么的暴力搞一波得了。
然而我只将倍数删掉了，然后跑暴力，加剪枝。
80分。
每个数要么选，要么不选。
然后扫一遍S数组。当然，值域开1000000即可。
如果最大的没出现在S’中的数≠最大的没出现在S中的数，则不合法。
这样子就可以跑过80了。
最后10分钟，捡回50分，数组差点开小了。
T3
不会用黑科技心态很崩。
菊花图提示了，要排序。
链提示了，要二分。
二叉树，并且n<=200这一档的，之前做过。
直接打75分。
100分？
二分答案mid，设f[x]表示以x为根的子树最多能有多少条>=mid的链。
由于，跨过x到fa[x]的只会贡献1条链，所以设g[x]表示x到y,y∈x的子树 的<mid的最长的链的长度。
对于x，如果f[son[x]]+weight[son[x]]>=mid，那么直接贡献1的答案。
否则加入一个set。然后直接贪心匹配。
时间复杂度： O ( n l o g 2 n ) O(n log^2 n) O(n log2 n)

Day1 小结

一出考场，就听到很多人说自己AK了，弄得我心态很崩。
当然，我尝试转移注意力，清一下0，准备好下一场考试。
Day1 255分，虽然说相对不高，但是按照原计划拿这个分数已经很不错了。
三题都考贪心，没AK也只能服气。
没到最后一刻，不能放弃。

Day 2

组题者将简单题全放到Day1，而难题全放到Day2。
T4
对于m=n-1，直接找最小的儿子走过去。
对于m=n，环套树。找出环，然后按照m=n-1的情况做。
太紧张没打tarjan，随便乱搞了一个东西。
n<=5000，所以 n 2 n^2 n2够了。
此时已经9:41了。
这个时候发现T6看错题了，以为只有一个点有贡献，所以以为自己AC T6了，很开心。
T5的DP很难写，肛了15分钟，过不了3 3
很想哭。
边打T5的对拍，边打T6，我也不知道自己在干嘛。
由于节奏乱了，所以只用了朴素的暴力去跑5 7跑不过。
其实可以跑过更多的点的。
最后打了个65分走人。
T6 浪费了很多时间。很可惜。
如果只有1个点有限制，那么这题就AC了。
设 f [ x ] [ 0 / 1 ] f[x][0/1] f[x][0/1]表示x不选/选的最大值。
44分 O ( n 2 ) O(n^2) O(n2)
对于A2/C2的，其实按照只有一个点受限制的做法就可以过了。
然而我只打了A2
B1也很简单， O ( 100 n ) O(100n) O(100n)即可。
A（链）怎么做？
分块。
每次修改，暴力重构，

最后想说的话

不管怎样，这次已经尽了力了。
提前准备好很多工作，到考试的时候，真正留给你想的时间其实非常少。
将这种训练的状态保持到最后吧。。。。