1127: [POI2008]KUP

https://lydsy.com/JudgeOnline/problem.php?id=1127

分析：

　　如果存在一个点大于等于k，小于等于2k的话，直接输出。

　　否则把点分成两类，一类是<k的，另一类是大于2k的，大于2k的一定没用。

　　然后找一个全部由小于2k的点中组成一个的矩形（悬线法），这个矩形有三种情况：1、<k，没用；2、大于等于k，小于等于2k，输出；3、大于2k，它的子矩阵中一定存在一个合法的矩阵（因为每个元素都是<k的，所以增加一个元素不可能直接使面积从小于k变成大于等于2k）。

　　考虑如何对一个大于等于2k的矩形找到它的合法的子矩阵。每次删掉一行或者一列一定可以找到。

　　

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #include<cctype>

 #include<set>

 #include<queue>

 #include<vector>

 #include<map>

 #include<cstdlib>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 LL sum[N][N], k;

 int a[N][N], U[N][N], L[N], R[N], n;

 void pd(int u,int d,int l,int r) {

     if (u > d || l > r) return ;

     LL now = sum[d][r] - sum[d][l - ] - sum[u - ][r] + sum[u - ][l - ];

     if (now < k) return ;

     if (now >= k && now <= k + k) {

         printf("%d %d %d %d",l, u, r, d); exit();

     }

     if (d - u > r - l) {

         pd(u + , d, l, r); pd(u, d - , l, r);

         pd(u, d, l + , r); pd(u, d, l, r - );

     }

     else {

         pd(u, d, l + , r); pd(u, d, l, r - );

         pd(u + , d, l, r); pd(u, d - , l, r);

     }

 }

 int main() {

     k = read(), n = read();

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

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

             a[i][j] = read();

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

             if (a[i][j] >= k && a[i][j] <= k + k) { printf("%d %d %d %d\n",j, i, j, i); return ; }

         }

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

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

              U[i][j] = a[i][j] <= k + k ? U[i - ][j] +  : ;

     for (int i = ; i <= n; ++i) L[i] = , R[i] = n + ;

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

         int last = ;

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

              if (a[i][j] <= k + k) L[j] = max(L[j], last + );

              else last = j, L[j] = ;

         }

         last = n + ;

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

             if (a[i][j] <= k + k) R[j] = min(R[j], last - );

             else last = j, R[j] = n + ;

         }

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

             if (U[i][j] && L[j] >=  && R[j] <= n) pd(i - U[i][j] + , i, L[j], R[j]);

     }

     puts("NIE");

     return ;

 }