这题做法还算比较明显,\(500\) 的数据范围也暗示了做法。
考虑直接二分所求答案,在 \(\mathcal{O}(n^2)\) 的时间内进行验证。如何验证 \(x\) 的合法性?
可以逐行操作。比如先考虑把第一行分成 \(\geq x\) 的 \(b\) 块。如果不可以,那么就加上第二行再分,一直叠加直到可以分出这样的 \(b\) 块为止,假设叠加到了第 \(p\) 行,那么 \([1,p]\) 就作为横向切的第一刀(即切在 \(p\) 行处),然后再对 \(p+1\) 行进行同样的操作。最后判断能否切到 \(a\) 刀即可。这个过程做 \(n\) 次。
如何验证能否把若干行分成 \(\geq x\) 的 \(b\) 块?要求线性做法,你有可能会想到再次二分?那 \(2\) 个 \(\text{log}\) 当然也可以。但不如考虑直接 \(1 - n\) 枚举列的切法,维护二维前缀和,扫到当前和 \(\geq x\) 那么就清空和,扫到最后一列看有没有 \(b\) 块。这个过程也要做 \(n\) 次。
其实说白了,就是先操作列切,合法了再操作行切,行列枚举法。加上二分,复杂度没炸,这题就轻松过了。
时间复杂度:\(\mathcal{O}(n^2 \log \sum a_{i,j})\).
注意:二分不知道怎么写 l<r
和 r=mid
的写法炸了,只能换了一种。
#include<bits/stdc++.h>
using namespace std;
const int N=5e2+1;
inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}
inline void write(int x) {
if(x<0) {putchar('-');write(-x);return;}
if(x<10) {putchar(char(x%10+'0'));return;}
write(x/10);putchar(char(x%10+'0'));
}
int r,c,a,b,s[N][N];
inline int Sum(int a,int b,int c,int d) {return s[c][d]-s[a-1][d]-s[c][b-1]+s[a-1][b-1];}
inline bool check(int x) {
int ans=0,st=1;
for(int i=1;i<=r;i++) {
int p=0,q=1;
for(int j=1;j<=c;j++)
if(Sum(st,q,i,j)>=x) p++,q=j+1;
if(p>=b) st=i+1,ans++;
} return ans>=a;
}
int main() {
r=read(),c=read(),a=read(),b=read();
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+read();
int l=1,r=4000*500*500;
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
} printf("%d\n",l-1);
return 0;
}