Process

fuck出题人，题目名称有问题，改了之后我的找不到源程序。。。50分就这样没了。。。 考得还行，第一题开始觉得是数学题太难了，打完暴力找几个数据试了下发现答案就是N * M % P，于是就这样兴高采烈地A了第一题，后来还是不放心，拍了1万组数据发现没问题就过了。第二题其实也是个简单的区间DP问题，考场上往这方面想过，但是没想出来。第三题t=0的50分很好写，直接按照右端点排序，贪心取就可以了。

Score

100 + 0 + 0(其实应该是50) = 100

Problems

0v0 [DONE]

printf("%lld\n", N * M % P)即可

OvO [TODO]

下午要上课，晚上回家再改 题目的要求就是不能同时取一对祖先和子孙。我们可以直接在dfs序上Dp，对于选择取W[i]的决策,即选择了DFS序上i号节点的子树所对应的区间。只要选择的区间不相交、不重复,那么就是一个合法的。这样,题目就成了一个区间覆盖 DP 问题

c [TODO]

第一问贪心跳即可 第二问,如果我们确定好了选择的ans1个整点,则一个区间 i,应该被划分到距离区间中点最近的一个所选点所对应的集合中。这样,我们只要以“到哪里为止,选择了多少个点”为状态,用线段树进行转移即可。