====== 2020/01/01 -- 2020/02/02 周报 ======

===== 团队训练 =====

[[2020-2021:teams:tle233:Niuke05|2020牛客暑期多校第五场]]

[[2020-2021:teams:tle233:Niuke06|2020牛客暑期多校第六场]]

===== Marvolo =====

==== 专题 ====

无

==== 比赛 ====

Codeforces: [[https://codeforces.com/contest/1389|Educational Codeforces Round 92]]

AtCoder: [[https://atcoder.jp/contests/m-solutions2020|M-SOLUTIONS Programming Contest 2020]]

==== 题目 ====

AtCoder:

[[https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_f|Air Safety]]

具体见本周推荐.

===== Kevin =====

==== 专题 ====

无

==== 比赛 ====

Codeforces: [[https://codeforces.com/contest/1389|Educational Codeforces Round 92]]

==== 题目 ====

[[https://leetcode.com/problems/median-of-two-sorted-arrays|LeetCode 4.]]

具体见本周推荐

===== TownYan =====

==== 专题 ====

无

==== 比赛 ====

Codeforces: [[https://codeforces.com/contest/1389|Educational Codeforces Round 92]]

AtCoder: [[https://atcoder.jp/contests/m-solutions2020|M-SOLUTIONS Programming Contest 2020]]

==== 题目 ====

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

具体见本周推荐

===== 本周推荐 =====

==== Marvolo ====

AtCoder:

[[https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_f|Air Safety]]

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

tag: set

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

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

牛客OJ:

[[https://ac.nowcoder.com/acm/contest/5670/B|Graph]]

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

题意与题解参考[[2020-2021:teams:tle233:niuke05|这里]]

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

==== Kevin ====

[[https://leetcode.com/problems/median-of-two-sorted-arrays|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$。

==== TownYan ====
[[https://ac.nowcoder.com/acm/contest/5670/D]]

**题意**

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

**tag**

LIS，排序

**题解**

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

**comment**

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