MX Day3

· · 生活·游记

T1：

做法：

1、我们可以首先发现，我们的路程可以简化为 0--->A--->0--->B--->0--->C--->.....

2、所以我们要提取出一个0--->A--->0的循环节，我们对于每个A--->0，都找一个截止时间不超过T且最晚的0--->A，组成一个连续段；

3、之后，我们得到了若干个[l, r]，每个这样的段我们对其进行排序，规则是先排左端点，左边一样按照右边从小到大排序

4、取出若干个不重叠的子序列，得到的总数最大值就是答案

T2：

做法：

1、首先我们可以发现它这个环可以将其转化为在一棵最小生成树上加边，从而试下下面的功能；

2、我们将最小生成树建出来，然后，我们找出那些不在树上的边，进行从小到大的排序；

3、我们一个个加边（尽管加完后就删除），但是我们做完第一步，我们就要从这里往上寻找点，将他们的答案记录为当前的边权，因为我们知道我们是一个环，而且这个环能得到的答案是在不断递增的，这个性质很容易满足；

4、每次爬完一次就要用并查集缩点，下次直接跳过，因为答案已经不会变了。

T3：

做法：

1、我们可以发现，答案要么是LIS+LCS，要么是在此基础上减一；

2、我们先用DP找出以每个点为交点，这个点结尾的LIS、LCS，和以这个点开头的LIS、LCS，可以用BIT在nlog的时间复杂度解决；

3、同时我们可以统计LIS、LCS的个数，这个也可以用BIT解决，LIS的方案数是C1×C3，LCS的方案数C2×C4，每个点的方案数是C1×C2×C3×C4；

4、如果，所有点的方案数的和得到的结果等于整个序列的方案数，也就是LIS的个数×LCS的个数，那么答案就是LIS+LCS-1，否则只要不等于就是LIS+LCS。