Summary, 未分类【Day -4】11-6模拟赛 Summary

【Day -4】11-6模拟赛 Summary

Process

今天分数还看得,但是排名掉到好后面去了。今天一上午基本上都在淦第一题,一道非常简单的树形Dp我因为设错了状态变得非常复杂,短短十行左右的dfs我硬生生地写了三四十行。。。不过幸好最后30min调出来了(我自己都不信),然后最后5min打了第二题40pts的暴力,以至于分数还是没有那么难看。这次考试其实检验出我的树形Dp的能力还是太弱了,这几天要多刷一点树形Dp的题,而且以前做题对题解的依赖太大,以后做题也要改掉这个习惯,加强独立思考的能力,这样考场上才能快速切掉比较简单的题。此外,今天时间安排也不是很合理,开始认为第一题好像有点思路就一直在做第一题,调到下考前30min才调出来,但是如果仔细想一下第二题的话会发现60pts的做法是很好想的,正解也其实就是在60pts的做法上用线段树进行了优化。
离NOIP只有4days了,这几天的模拟考难度好像会降低,所以这几次考试都要当成正式的NOIP,一套题如果没思路的话,一定先把暴力都打出来,不能想着暴力分太少就懒得去打,这样就会损失很多不该丢的分。

Score

100 + 50 + 0 = 150

Problems

tree[DONE]

由题意可知一条边由两个点覆盖,而这样的点对越多越好
因此题目可以转化为求这样的点对的个数
正解是设Dp[i][0/1]表示以i为根的子树中能够两两配对的最大点数, 0/1表示选不选节点i
然后Dp[i][0] = \\sum Dp[j][1](j为i的儿子)
Dp[i][1] = max(Dp[i][1], Dp[i][0] – Dp[j][1] + Dp[j][0] + 2)
然后就做完了

queue[DONE]

记ci表示比ai大的数的个数,那么若ci < bi,则无解
我们考虑按照ai从小到大插入序列
那么有两种放法:使得ai前面有bi个比它大或后面有bi个比它大
这两种放法分别是从左到右放第(bi + 1)个空位或第(ci – bi + 1)个空位。因为我们是从小到大插入的,因此这个做法的正确性是显然的。
要使字典序最小,只需对这两个位置取min即可
但是这样做的复杂度是O(N ^ 2)的,我们用一个线段树记录对应区间剩余空位的个数(初始值为区间长度),如果一个点被选,那么它所在位置就减少了一个空位,直接更新即可。如果我们要查找第k个空位,只需要递归的时候判断如果左子树剩余空位个数>=k的话,就递归到左子树,否则用k减去左子树的空位个数,再递归到右子树。最后递归到叶子节点时便找出来了第k个空位。
这样做的复杂度是O(N log N)

necklace[TODO]

群论、数论内容还不会

Categories: Summary, 未分类 Tags:

Comments

  1. xunzhen

    2017年12月28日 下午2:18

    学习学习

Post a comment