[BZOJ] 1127: [POI2008]KUP

似曾相识的感觉

考虑另一个判断问题，给定一个k，问这个k是否可行

存在矩形和\(sum>2k\)，则该矩阵不对判定做出贡献
存在矩形和\(sum\in [k,2k]\)，则我们找到了一个解

于是判掉这两种情况，专心讨论\(sum<k\)的矩形

找到\(sum<k\)的极大矩形，按它的和\(S\)讨论

\(S<k\)，则无解
\(S\in [k,2k]\)，则我们找到了一个解
\(S>2k\)，递归成小矩形继续求解

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define int long long

using namespace std;

const int MAXN = 2005;

int n,m;

signed l[MAXN][MAXN],a[MAXN][MAXN],r[MAXN][MAXN],h[MAXN][MAXN];

int sum[MAXN][MAXN];

int Sum(int x,int y,int u,int v){return sum[u][v]+sum[x-1][y-1]-sum[x-1][v]-sum[u][y-1];}

inline void print(int x,int y,int u,int v){

    while(Sum(x,y,u,v)>2*m){

        if(x==u)

            v--;

        else if(Sum(x+1,y,u,v)>=m)

            x++;

        else

            u--;

    }

    printf("%lld %lld %lld %lld\n",y,x,v,u);exit(0);

}

signed main(){

    scanf("%lld%lld",&m,&n);

    for(int i=1;i<=n;i++){

      for(int j=1;j<=n;j++){

        scanf("%lld",&a[i][j]);

        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

        if(a[i][j]>=m&&a[i][j]<=m*2){

          printf("%lld %lld %lld %lld\n",j,i,j,i);

          return 0;

        }

        a[i][j]=(a[i][j]<=m*2);

      }

    }

    for(int i=1;i<=n;i++){

      for(int j=1;j<=n;j++){

        if(!a[i][j])continue;

        l[i][j]=r[i][j]=h[i][j]=1;

      }

    }

    for(int i=1;i<=n;i++){

      for(int j=1;j<=n;j++){

        if(!a[i][j])continue;

        if(a[i-1][j])h[i][j]+=h[i-1][j];

        if(a[i][j-1])l[i][j]+=l[i][j-1];

      }

      for(int j=n;j>=1;j--){

        if(!a[i][j])continue;

        if(a[i][j+1])r[i][j]+=r[i][j+1];

      }

    }

    for(int i=1;i<=n;i++){

      for(int j=1;j<=n;j++){

        if(!a[i][j])continue;

        if(h[i][j]<=1)continue;

        l[i][j]=min(l[i-1][j],l[i][j]);

        r[i][j]=min(r[i-1][j],r[i][j]);

        int x=i-h[i][j]+1,u=i;

        int y=j-l[i][j]+1,v=j+r[i][j]-1;

        if(Sum(x,y,u,v)>=m)print(x,y,u,v);

      }

    }

    puts("NIE");

}

巴特西

[BZOJ] 1127: [POI2008]KUP

最新文章

热门文章