Codeforces Round #737 Ezzat and Grid 题解 (Java/C++)

题解

这个题大概分为四个部分。


第一部分:Hash

由于最多只有m段1,因此我们很自然的想到将$1\leq l \leq r \leq 10^9$的hash到$1\leq l \leq r \leq 2\cdot 3\cdot 10^5$。将原先的线段的两端离散后排序,按照大小顺序依次hash即可。
代码中对应的函数为:map_point。

同时,这里我们把这m段,分散到对应的行中,以便后续使用方便。
代码中对应的函数为:group


第二部分:DP

我们发现,于其寻找最少删多少行,不如寻找最多能构造出多少行。于是我们能够自然的想到一种$O(n^2)$的DP。

我们令$dp[i]$表示前行,最多能构造出多少行。于是很自然的$dp[i]=\max(dp[j]+1)$,其中$0<j<i$且第i行和第j行能相通。

但是显然,这个是$O(n^2)$的时间复杂度,且每次判断第i行和第j行是否相通的最朴素的做法是$O(m)$的。


第三部分:线段树

首先我们思考,判断第i行和第j行是否相通的标准是什么?如果i行和j行相通,那么至少有一个位置都是1。因此,如果我们把j中的所有区间在i中查询区间最大值,如果某一个区间的查询结果不为0,则i和j必有相通之处。
以下图为例:

j会在i中查询[0,1]以及[5,6],其中[0,1]的查询结果为1,[5,6]的查询结果为0。因此j和i至少有一处同为1。

进一步,我们结合上面的DP部分,我们发现可以用类似的方法。

对于$dp[i]$,我们的核心问题是,要往前找到某一行j,使得其$dp[i]$尽可能大,且i和j有共同的1。
于是每当我们求出一个新的dp[i],我们都将i为1的位置更新到线段树中,更新的值为dp[i]。其中这颗线段树要维护的是区间最大值。
至于如何求出新的dp[i]就很明显了。我们只需要查询i行所有为1的区间,取其中最大的值即可。
以样例2为例:

当我们求dp[3]的时候,我们可以在i=2中查询,发现可以查询到的最大值为1。于是dp[3]=1+1,接着将[2-3]更新为dp[3]。


第四部分:记录路径

在线段树维护最大值时,同时维护是哪一行更新了当前区间的最大值。这样,在更新dp[i]时,可以记录下其前置的j到底是谁。这样我们就能依次找出最长的列,剩下的元素都是要被删除的。

代码

Java

Submission #125679861 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #125681799 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论