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