1
3
2018
0

O(time)->O(ans)

http://www.lydsy.com/JudgeOnline/problem.php?id=4716

正解是用个堆,然而有个非常高明的”暴力“。

#pragma GCC optimize("O2")
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for (register int i=a; i<=b; i++)
#define per(i,a,b) for (int i=a; i>=b; i--)
typedef long long ll;
using namespace std;
typedef pair<int,int> Pii;
typedef vector<int> vec;
inline void read(int &x) {
    x=0; char c=getchar(); int f=1;
    while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
    while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
const int N = 1050;
int n,m,xmn,ymn,k;
int a[N][N];
ll s[N][N];
inline ll getsum(int x0, int y0, int x1, int y1) {
    x0--; y0--;
    return s[x1][y1]-s[x0][y1]-s[x1][y0]+s[x0][y0];
}
inline int getans(int val) { //"<=val"
    int res=0; //if (res>=k) return res;
    rep(i,1,n-xmn+1) rep(j,1,m-ymn+1) {
        register int x=i+xmn-1,y=j+ymn-1;
        for (;x<=n;x++) {
            if (getsum(i,j,x,y)>val) break;
            rep(Y,y,m) {
                if (getsum(i,j,x,Y)>val) break;
                res++; if (res>=k) return res;
            }
        }
    }
    return res;
}
int main() {
    read(n); read(m); read(xmn); read(ymn); read(k);
    rep(i,1,n) rep(j,1,m) read(a[i][j]);
    rep(i,1,n) rep(j,1,m) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    int l=0,r=n*m*2000;
    while (l<r) {
        register int mid=(1LL*l+r)>>1;
        if (getans(mid)<k) l=mid+1; else r=mid;
    }
    printf("%d",l+1);
    return 0;
}

可以证明,每次getans函数,里面有用的解只有O(k)个,没用的解(多余的复杂度)也只有O(k+nm)个,所以复杂度是O(nm+k)。

Category: 技巧 | Tags: | Read Count: 50

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com