85问答库 > c++ n*n的矩阵中只有0或1,先求m*m的区域内,最多有多少个1.(n>=m,n=1~10的8次方)

c++ nn的矩阵中只有0或1,先求mm的区域内,最多有多少个1.(n>=m,n=1~10的8次方)

如题，有人告诉我用map去解，但是没想通怎么做。

2024-11-28 16:45:11

推荐回答（1个）

回答1：

简单地说就是，用扫描线，和一棵区间加减、求最大值的线段树。似乎就可以了？

不知道你会不会，具体说就是：
枚举一个正方形的左边界，每次就只数从这个边界到右边距离m之内的点，就是把所有值为1点加到线段树中去。每当你枚举的左边界+1时，就会把一些点加进来，把一些点删掉，每个点最多被增删一次。

线段树的操作是，把这个点的位置到它上面m的距离的线段+1。意思就是说以以你枚举的那个左边界和线段树上的位置为高度的坐标为左上角的正方形中包含多少个1。求全树的最大值就可以了。

。。。如果算法伪了就回复吧，让我再想一想。