首页 > itarticle > luogu2216 [haoi2007]理想的正方形

luogu2216 [haoi2007]理想的正方形

admin 11月 13, 2020 0 

1
 
裸题

st有两种
讲得很清楚的博客
O(nmlogm) - O(n)
O(nmlognlogm) - O(1)
这题是求正方形，可以O(nmlogt) - O(1)

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
 
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL ()
{
	LL 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<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1008;
int n,m,t;
int a[N][N],maxi[N][N][8],mini[N][N][8];
int len,ans=INT_MAX;
int main()
{
	n=read();m=read();t=read();
	memset(mini,0x3f,sizeof(maxi));
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			maxi[i][j][0]=mini[i][j][0]=a[i][j]=read();
		}
	}
	for(int k=1;(1<<k)<=t;++k){
		for(int i=1;i+(1<<k)-1<=n;++i){
			for(int j=1;j+(1<<k)-1<=m;++j){
				maxi[i][j][k]=max(max(maxi[i][j][k-1],maxi[i+(1<<(k-1))][j][k-1]),
								  max(maxi[i][j+(1<<(k-1))][k-1],maxi[i+(1<<(k-1))][j+(1<<(k-1))][k-1]));
				mini[i][j][k]=min(min(mini[i][j][k-1],mini[i+(1<<(k-1))][j][k-1]),
								  min(mini[i][j+(1<<(k-1))][k-1],mini[i+(1<<(k-1))][j+(1<<(k-1))][k-1])); 
			}
		}
	}
	
	//while((1<<(len+1))<t)	++len;
	len=log2(t);
	for(int i=1;i+t-1<=n;++i){
		for(int j=1;j+t-1<=m;++j){
			ans=min(ans,max(max(maxi[i][j][len],maxi[i+t-(1<<len)][j][len]),max(maxi[i][j+t-(1<<len)][len],maxi[i+t-(1<<len)][j+t-(1<<len)][len]))
						-min(min(mini[i][j][len],mini[i+t-(1<<len)][j][len]),min(mini[i][j+t-(1<<len)][len],mini[i+t-(1<<len)][j+t-(1<<len)][len])));
		}
	}
	printf("%d",ans);
	return 0;
}

O(nm)的单调队列
写错是因为变量名打错！！

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL ()
{
	LL 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<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1008;
int n,m,t;
int a[N][N],maxi[N][N],mini[N][N];
int q[N],pos[N],he,ta; 
int main()
{
	n=read();m=read();t=read();
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			a[i][j]=read();
		}
	}
	//----------------
	for(int i=1;i<=n;++i){
		he=1;ta=0;
		for(int j=1;j<t;++j){
			while(he<=ta&&a[i][j]>=q[ta])	--ta;		
			q[++ta]=a[i][j];
			pos[ta]=j;
		}
		for(int j=t;j<=m;++j){
			while(he<=ta&&pos[he]<=j-t)	++he;
			while(he<=ta&&a[i][j]>=q[ta])	--ta;		
			q[++ta]=a[i][j];
			pos[ta]=j;
			maxi[i][j]=q[he];
		}
	}/*
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cout<<maxi[i][j]<<' ';
		}cout<<'n';
	}
	puts("");*/
	for(int j=t;j<=m;++j){
		he=1;ta=0;
		for(int i=1;i<t;++i){
			while(he<=ta&&maxi[i][j]>=q[ta])	--ta;
			q[++ta]=maxi[i][j];
			pos[ta]=i;
		}
		for(int i=t;i<=n;++i){
			while(he<=ta&&pos[he]<=i-t)	++he;
			while(he<=ta&&maxi[i][j]>=q[ta])	--ta;
			q[++ta]=maxi[i][j];
			pos[ta]=i;
			maxi[i][j]=q[he];
		}
	}/*
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cout<<maxi[i][j]<<' ';
		}cout<<'n';
	}
	puts("");*/
	//--------------------------
	for(int i=1;i<=n;++i){
		he=1;ta=0;
		for(int j=1;j<t;++j){
			while(he<=ta&&a[i][j]<=q[ta])	--ta;		
			q[++ta]=a[i][j];
			pos[ta]=j;
		}
		for(int j=t;j<=m;++j){
			while(he<=ta&&pos[he]<=j-t)	++he;
			while(he<=ta&&a[i][j]<=q[ta])	--ta;		
			q[++ta]=a[i][j];
			pos[ta]=j;
			mini[i][j]=q[he];
		}
	}/*
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cout<<mini[i][j]<<' ';
		}cout<<'n';
	}
	puts("");*/
	for(int j=t;j<=m;++j){
		he=1;ta=0;
		for(int i=1;i<t;++i){
			while(he<=ta&&mini[i][j]<=q[ta])	--ta;
			q[++ta]=mini[i][j];
			pos[ta]=i;
		}
		for(int i=t;i<=n;++i){
			while(he<=ta&&pos[he]<=i-t)	++he;
			while(he<=ta&&mini[i][j]<=q[ta])	--ta;
			q[++ta]=mini[i][j];
			pos[ta]=i;
			mini[i][j]=q[he];
		}
	}
	/*for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cout<<mini[i][j]<<' ';
		}cout<<'n';
	}
	puts("");*/
	int ans=INT_MAX;
	for(int i=t;i<=n;++i){
		for(int j=t;j<=m;++j){
			ans=min(ans,maxi[i][j]-mini[i][j]);
		}
	}
	printf("%d",ans);
	return 0;
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能