Bzoj1127 [POI2008] KUP-Plot Purchase

, ,

Description

https://www.luogu.com.cn/problem/P3474

Solution

这题的关键在于用到 $[k,2k]$ 和 $<k$ 的关系。

显然如果一个点：

  • $>2k$，那么这个点一定不能被选。
  • $k\le a_{i,j}\le 2k$，这个点就可以作为答案。
  • $<k$。

把上面两种判掉，那么转化为我们要选一个只有 $<k$ 的点组成的矩阵，满足矩阵元素之和在 $[k,2k]$ 之间。

观察到如果一个矩阵仅有 $<k$ 的组成，如果这个矩阵的和 $\ge k$，那么一定有解。

  • 如果矩阵的和 $\le 2k$，它就是答案。
  • 否则如果矩阵的第一行 $<k$，那么删掉这一行。
  • 如果矩阵的第一行 $\ge k$，那么只保留这一行，并不断删数删到这一行的和 $\le 2k$ 为止。

因为我们选出的这个矩阵中的所有元素都 $<k$，所以一定可以删到 $[k,2k]$ 之间。

要找一个满足条件且 $\ge k$ 的矩阵，等价于找一个只包含 $<k$ 元素的最大子矩阵。悬线法即可。复杂度 $O(n^2)$。

我写的比较丑陋。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 2005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,k;
int a[maxn][maxn],s[maxn][maxn];
int Up[maxn][maxn],L[maxn][maxn],R[maxn][maxn],stac[maxn];
int calc(int x,int y,int xx,int yy) {
	return s[xx][yy]-s[x-1][yy]-s[xx][y-1]+s[x-1][y-1];
}
int tot;
void print(int x,int y,int xx,int yy) {
	int i,j;
	for (i=x;i<=xx;i++) {
		if (calc(i,y,xx,yy)<=2*k) {
			printf("%d %d %d %d\n",y,i,yy,xx);
			return ;
		}
		if (calc(i,y,i,yy)<k) continue;
		while (calc(i,y,i,yy)>2*k) y++;
		printf("%d %d %d %d\n",y,i,yy,i);
		return ;
	}
}
signed main(void){
	int i,j;
	read(k);read(n);
	for (i=1;i<=n;i++) for (j=1;j<=n;j++) read(a[i][j]),s[i][j]=a[i][j];
	for (i=1;i<=n;i++) for (j=1;j<=n;j++) s[i][j]+=s[i][j-1];
	for (i=1;i<=n;i++) for (j=1;j<=n;j++) s[i][j]+=s[i-1][j];
	for (i=1;i<=n;i++) for (j=1;j<=n;j++) {
		if (a[i][j]>=k) {
			// gdb(i,j,a[i][j],k);
			if (a[i][j]>2*k) Up[i][j]=0;
			else {
				printf("%d %d %d %d\n",j,i,j,i);
				return 0;
			} 
			continue;
		}
		Up[i][j]=1;
		if (i>=1&&a[i-1][j]<k) Up[i][j]+=Up[i-1][j];
	}
	for (i=1;i<=n;i++) {
		tot=0;stac[0]=0;
		for (j=1;j<=n;j++) {
			while (tot&&Up[i][stac[tot]]>=Up[i][j]) tot--;
			L[i][j]=stac[tot]+1;stac[++tot]=j;
		}
		tot=0;stac[0]=n+1;
		for (j=n;j>=1;j--) {
			while (tot&&Up[i][stac[tot]]>=Up[i][j]) tot--;
			R[i][j]=stac[tot]-1;stac[++tot]=j;
		}
		// for (j=1;j<=n;j++) gdb(i,j,Up[i][j],L[i][j],R[i][j]);
		for (j=1;j<=n;j++) if (Up[i][j]&&calc(i-Up[i][j]+1,L[i][j],i,R[i][j])>k) {
			assert(L[i][j]>=1&&R[i][j]<=n);
			print(i-Up[i][j]+1,L[i][j],i,R[i][j]);
			return 0;
		}
	}
	puts("NIE");
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i