1127: [POI2008]KUP

Time Limit:?10 Sec??Memory Limit:?162 MBSec??Special Judge
Submit:?317??Solved:?111
[Submit][Status][Discuss]

Description

給一個(gè)n*n的地圖，每個(gè)格子有一個(gè)價(jià)格，找一個(gè)矩形區(qū)域，使其價(jià)格總和位于[k,2k]

Input

輸入k n（n<2000)和一個(gè)n*n的地圖

Output

輸出矩形的左上和右下的列-行坐標(biāo)或NIE

Sample Input

inputdata1
4 3
1 1 1
1 9 1
1 1 1
inputdata2
8 4
1 2 1 3
25 1 2 1
4 20 3 3
3 30 12 2

Sample Output

outputdata1
NIE
outputdata2
2 1 4 2

HINT

1<=k<=10^9 每個(gè)價(jià)格都是不大于2*10^9的非負(fù)整數(shù)

Source

感謝vfleaking提供SPJ

Solution

這個(gè)題需要思路....

首先假設(shè)有一個(gè)一維的區(qū)間$[l,r]$，那么假設(shè)這個(gè)區(qū)間中滿足$\forall x,x<K$，那么且這個(gè)區(qū)間的和$>=K$，那么答案肯定存在在這個(gè)區(qū)間中。

?

證明：

因?yàn)檫@個(gè)區(qū)間中滿足$\forall x,x<K$，所以區(qū)間和每加上一個(gè)數(shù)，區(qū)間和的變化量一定是$<K$的;

所以，并不會(huì)存在一個(gè)數(shù)使得一個(gè)子區(qū)間（連續(xù)的）和加上他得到的新區(qū)間和直接從$(-\infty,K]$跳過(guò)$[K,2*K]$變成$[2*K,+\infty)$.

所以，只要從這個(gè)一維的區(qū)間的左/右端開(kāi)始一一刪除，就可以得到滿足條件的區(qū)間。

?

但是這里的$N*N$的矩陣，所以要利用這個(gè)結(jié)論就必須擴(kuò)展到多維區(qū)間塊上面，但是這個(gè)結(jié)論是可以拓展的。

這樣就是一個(gè)子矩陣滿足$\forall x,x<K$，且子矩陣和$>=K$，那么這個(gè)子矩陣中存在答案。

證明類比上面的證明，這里分類討論一下，可以利用上面的方法，先一行一行的刪除，刪成滿足條件的，或者只剩一行，轉(zhuǎn)成上述，再一個(gè)一個(gè)刪.

然后就是找出這些需要搞得子矩形的方法了,把$x>2*K$的點(diǎn)認(rèn)為是障礙，做一遍懸線法，就可以得到所有的極大子矩形，然后一一判斷。

當(dāng)然一開(kāi)始讀入的時(shí)候，如果存在一個(gè)$1*1$的位置$x$直接滿足$x \in [K,2*K]$那么可以直接輸出。

Code

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define LL long long inline int read() {int x=0,f=1; char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f; } int K,N,l[2010][2010],r[2010][2010],h[2010][2010]; LL sum[2010][2010],a[2010][2010]; inline LL Sum(int x1,int y1,int x2,int y2) {return sum[x2][y2]+sum[x1-1][y1-1]-sum[x2][y1-1]-sum[x1-1][y2];} inline void Cut(int x1,int y1,int x2,int y2) {while (Sum(x1,y1,x2,y2)>2*K){if (x1==x2) {y2--; continue;}if (Sum(x1,y1,x2-1,y2)>=K) {x2--; continue;}if (Sum(x1+1,y1,x2,y2)>=K) {x1++; continue;}}printf("%d %d %d %d\n",y1,x1,y2,x2);exit(0); } int main() {K=read(),N=read();for (int i=1; i<=N; i++)for (int j=1; j<=N; j++)a[i][j]=read(),sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];for (int i=1; i<=N; i++)for (int j=1; j<=N; j++)if (a[i][j]>=K && a[i][j]<=2*K) {printf("%d %d %d %d\n",j,i,j,i); return 0;}for (int i=1; i<=N; i++){for (int j=1,x=0; j<=N; j++)if (a[i][j]<=2*K) l[i][j]=x; else l[i][j]=0,x=j;for (int j=N,x=N+1; j>=1; j--)if (a[i][j]<=2*K) r[i][j]=x; else r[i][j]=N+1,x=j;}for (int i=1; i<=N+1; i++) r[0][i]=N+1;for (int i=1; i<=N; i++)for (int j=1; j<=N; j++)if (a[i][j]<=2*K)h[i][j]=h[i-1][j]+1,l[i][j]=max(l[i][j]+1,l[i-1][j]),r[i][j]=min(r[i][j]-1,r[i-1][j]);// puts("=========================="); // for (int i=1; i<=N; i++,puts("")) // for (int j=1; j<=N; j++) // printf("%d ",h[i][j]); // puts("=========================="); // for (int i=1; i<=N; i++,puts("")) // for (int j=1; j<=N; j++) // printf("%d ",l[i][j]); // puts("=========================="); // for (int i=1; i<=N; i++,puts("")) // for (int j=1; j<=N; j++) // printf("%d ",r[i][j]); // puts("==========================");for (int i=1; i<=N; i++)for (int j=1; j<=N; j++)if (a[i][j]<=2*K){ // printf("%d %d %d %d\n",i-h[i][j]+1,l[i][j],i,r[i][j]);if (Sum(i-h[i][j]+1,l[i][j],i,r[i][j])>=K) Cut(i-h[i][j]+1,l[i][j],i,r[i][j]);}puts("NIE");return 0; } /* 2 3 3 25 7 6 1 2 16 11 20 */

?

轉(zhuǎn)載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5997325.html

超強(qiáng)干貨來(lái)襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的【BZOJ-1127】KUP 悬线法 + 贪心的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。