2016 Multi-University Training Contest 5 总结

这次依旧是 5 题,发挥挺好,在湖南的名次也还可以。主要是罚时越来越少,许多题都是一遍过。当然这次又手残交错了一发 T^T 。这场我还是放一下官方题解吧。

 

1001 ATM Mechine

这题题意需要好好理解,提问版里 admin 也挺傲娇的。我的做法主要是 DP ,每次选取中间要试探的数进行 DP ,并且先离线都预处理好。复杂度是 O(k^2w) 的,但是我每次都是选取中间点,然后左右试探更优点,这样复杂度会大大降低,接近 O(kw)。 看了题解后发现如果选取二分的话,最多只要警告15次, 所以复杂度接近 O(k) .

 

1003 Divide the Sequence

水题。首先负数不应该出现在最开始,其次用尽量少的正数去中和负数,因为正数可以单独算一个。做法直接倒着扫一遍。复杂度 O(n) .
 

 

1011 Two

一个比较典型的 DP。 加上前缀和优化就可以在 O(nm) 的时间内跑出来。

 

1012 World is Exploding

这题意思是找到一个四元组,使得一对升序一对降序,且不能重复。答案可以又升序的个数乘降序的个数再减去重复的个数。首先把所有的数离散化,再用树状数组做两遍逆序对。处理出以 a_i 开头,结尾的升序,逆序对数。在通过这个算出最后的答案。复杂度 O(n\ logn) .

2 thoughts on “2016 Multi-University Training Contest 5 总结

发表评论

电子邮件地址不会被公开。 必填项已用*标注