bzoj 1127 [POI2008]KUP——思路(悬线法)

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1127

大于2*K的视为不能选的“坏点”。有单个格子满足的就直接输出。

剩下的都是<K的格子，求面积大于等于K的一个矩形；若还<=2*K就直接输出，否则一列一列删；

删去一列后若仍>=2*K，继续；若>=K&&<=2*K，就输出；若<K，则删去的那一列满足>=K，在那列上一格一格删，因为格子<K，所以不能从>2*K跳到<K，一定有解了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=;

int n,K,D,a[N][N],l[N][N],r[N][N],u[N][N],p0,p1;

ll s[N][N];

bool b[N][N],flag;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return fx?ret:-ret;

}

ll calc(int h1,int l1,int h2,int l2)

{

  return s[h2][l2]-s[h2][l1-]-s[h1-][l2]+s[h1-][l1-];

}

void solve2(int h1,int h2,int j)

{

  int sm=calc(h1,j,h2,j);

  if(sm>=K&&sm<=D){printf("%d %d %d %d\n",j,h1,j,h2);return;}

  for(int i=h2;i>=h1;i--)

    {

      sm-=a[i][j];

      if(sm>=K&&sm<=D){printf("%d %d %d %d\n",j,h1,j,i-);return;}

    }

}

void solve(int h1,int l1,int h2,int l2)

{

  ll sm=calc(h1,l1,h2,l2);

  if(sm<K)return;

  if(sm>=K&&sm<=D){printf("%d %d %d %d\n",l1,h1,l2,h2);flag=;return;}

  for(int i=l2;i>=l1;i--)

    {

      sm=calc(h1,l1,h2,i-);

      if(sm>=K&&sm<=D)

    {

      printf("%d %d %d %d\n",l1,h1,i-,h2);

      flag=;return;

    }

      if(sm<K)

    {

      solve2(h1,h2,i);flag=;return;

    }

    }

}

int main()

{

  K=rdn(); n=rdn(); D=(K<<);

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

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

      {

    a[i][j]=rdn(); if(a[i][j]>D)b[i][j]=;

    if(a[i][j]>=K&&a[i][j]<=D)p0=j,p1=i;

    s[i][j]=s[i][j-]+a[i][j];

      }

  if(p0){printf("%d %d %d %d\n",p0,p1,p0,p1);return ;}

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

    for(int j=;j<=n;j++)s[i][j]+=s[i-][j];

  for(int i=,k;i<=n;i++)

    for(int j=,k=;j<=n;j++)

      {

    if(!b[i-][j]) u[i][j]=u[i-][j]+;

    else u[i][j]=;

    if(!b[i][j])l[i][j]=max(k,l[i-][j]);

    else k=j+;

      }

  for(int j=;j<=n;j++)r[][j]=n;//!

  for(int i=,k;i<=n;i++)

    for(int j=n,k=n;j>=;j--)

      {

    if(!b[i][j])r[i][j]=min(k,r[i-][j]);

    else k=j-,r[i][j]=n;//for don't influence i+1,j

    if(!b[i][j])solve(i-u[i][j]+,l[i][j],i,r[i][j]);

    if(flag)return ;

      }

  puts("NIE");

  return ;

}