2020牛客暑期多校第五场

2020牛客暑期多校第六场

无

Codeforces: Educational Codeforces Round 92

AtCoder: M-SOLUTIONS Programming Contest 2020

AtCoder:

Air Safety

具体见本周推荐.

无

Codeforces: Educational Codeforces Round 92

LeetCode 4.

具体见本周推荐

无

Codeforces: Educational Codeforces Round 92

AtCoder: M-SOLUTIONS Programming Contest 2020

https://ac.nowcoder.com/acm/contest/5670/D

具体见本周推荐

AtCoder:

Air Safety

题意:给出一个二维平面上一些飞机的坐标和它们飞行的方向(上下左右之一),飞机会沿着飞行方向一直移动.问最近的一次碰撞将会发生在什么时候.

tag: set

题解:分类讨论,首先是上下碰与左右碰的情况,以及两架飞机在y=x+a或y=a-x上时,发生的四种直角碰撞.对于单一的碰撞方式,例如上下碰,可以先把所有向下走的飞机的纵坐标扔到set里,然后枚举所有向上走的飞机,求它的纵坐标在set里的前驱,算一个答案并维护最小值即可.不用set应该也可以,只不过判断时可能麻烦一点.

comment:set的良好练手题.之前看一篇辣鸡博客说set的lower_bound是求小于等于一个值的最后一个元素的,实际上人家是求大于等于一个值的第一个元素的,也就是lower_bound返回的迭代器再往前一个才是前驱,导致浪费了很多调试的时间.

牛客OJ:

Graph

tag:Trie树,DP,启发式合并

题意与题解参考这里

comment:赛后讲题的时候,大家都是用的Trie树与DP.但是是从上往下算的,其实这道题可以从下往上算,合并两个分支就代表着在两个连通块间连边,如何选择两个数使得他们的异或值最小可以通过暴力走Trie树解决,辅以启发式合并就可以顺利解决时间复杂度的问题.

LeetCode 4.

题意

求两个非递减序列 $A, B$ 有序合并后的中位数（偶数个数则输出中间两个的均值）。

tag

分治

题解

似乎是比较经典的一道题。merge 做法、快排 partition 都是线性的，但这道题还有一种巧妙的 $\log$ 做法。

首先不论奇偶，找到第 $k=\lfloor\frac{m+n+1}{2}\rfloor$ 小的数就行。假设这个数在 $A$ 中，显然，这个数的位置 $p$ 满足 $p = \max\{p \mid B[k-p] \le A[p]\ \text{and}\ B[k-p+1] \ge A[p]\}$。因为 $B$ 是单调不减所以可以直接二分 $p$，得到答案，复杂度 $\log$。

https://ac.nowcoder.com/acm/contest/5670/D

题意

给定一个排列，有两种操作，每种操作可以连续使用若干次：（1）将第一位的数放到最后，其他数向前补。（2）将倒数第二个数放到第一位，除最后一位不动以外其他数向后补。问最多需要使用多少轮第二种操作才能把这个排列改成单调的（每一轮可以使用任意次）。

tag

LIS，排序

题解

可以理解成用最后一位进行插入排序，问题转化为求原序列拿出多少位以后变成循环条件下单调的（比如3412就是单调的）。题里也没有为难这一点，最长给500，可以直接暴力枚举“最长上升子序列”的最小数的位置，复杂度n^2logn。然后答案就是n-最长的LIS的长度。

comment

yysy，赛场上很快想到还是挺爽的