15.10.01【单调队列、二分答案、记忆化搜索】

  1. 1.为了和谐 (square)
    1. 方法一:
    2. 方法二:
    3. 方法三:
  2. 2.防守之道 (cover)
  3. 3.分蛋糕(separation)

学长黑学长系列

1.为了和谐 (square)

【问题背景】 在机房里,有两只小可爱,一只大可爱,一只小可爱。其中大可爱对大的东西感兴趣,小可爱对小的东西感兴趣。 现在有一个 \(a \times b\) 的矩阵,矩阵中每个位置都有一个非负整数\(i(0<=i<=2 000 000 000)\),两只小可爱要在这个矩阵中选择一个\(n\times n\)的正方形,大可爱要正方形中的最大数,小可爱要正方形中的最小数。 但是,如果两个人的数字差距过大的话,就会造成矛盾……为了机房人民的和谐相处,请你帮他们选择这个正方形,使得这个差距最小。 【问题描述】 有一个\(a\times b\)的整数组成的矩阵,现请你从中找出一个\(n\times n\) 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。

方法一:

\(20\)分水过。

方法二:

由RMQ问题,联想到ST算法,很好,能想到这个已经很不错了。自己随便搞一个二维的ST算法,\(O(AB lb n)\),卡着时限轻松飘过。

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001,MAXS=101,LG=6,INF=0x7FFFFFFF;
using namespace std;
int N,M,P,Ans;
int F[MAXN][MAXN][LG],G[MAXN][MAXN][LG];
void init()
{
int i,j;
freopen("square.in","r",stdin);
freopen("square.out","w",stdout);
scanf("%d%d%d",&N,&M,&P);
for (i=1;i<=N;i++)
for (j=1;j<=M;j++)
{
scanf("%d",&F[i][j][0]);
G[i][j][0]=F[i][j][0];
}
Ans=INF;
}
inline int Min(int a,int b){return a<b?a:b;}
inline int Max(int a,int b){return a>b?a:b;}
void SparseTable()
{
int i1,i2,j,jt,max,min;
for (j=jt=1;jt<=P;j++,jt=jt<<1)
{
for (i1=1;i1+jt<=N;i1++)
{
for (i2=1;i2+jt<=M;i2++)
{
max=0;min=INF;
max=Max(max,F[i1][i2][j-1]);
max=Max(max,F[i1][i2+jt][j-1]);
max=Max(max,F[i1+jt][i2][j-1]);
max=Max(max,F[i1+jt][i2+jt][j-1]);
F[i1][i2][j]=max;
min=Min(min,G[i1][i2][j-1]);
min=Min(min,G[i1][i2+jt][j-1]);
min=Min(min,G[i1+jt][i2][j-1]);
min=Min(min,G[i1+jt][i2+jt][j-1]);
G[i1][i2][j]=min;
}
}
}
}
int Log2(int a)
{
int r;
for (r=0;(1<<r)<=a;r++);
return r-1;
}
void solve()
{
int i,j,k,kt,min,max;
k=Log2(P);
kt=1<<k;
for (i=1;i+P-1<=N;i++)
{
for (j=1;j+P-1<=M;j++)
{
max=0;min=INF;
max=Max(max,F[i][j][k]);
max=Max(max,F[i][j+P-kt][k]);
max=Max(max,F[i+P-kt][j][k]);
max=Max(max,F[i+P-kt][j+P-kt][k]);
min=Min(min,G[i][j][k]);
min=Min(min,G[i][j+P-kt][k]);
min=Min(min,G[i+P-kt][j][k]);
min=Min(min,G[i+P-kt][j+P-kt][k]);
Ans=Min(Ans,max-min);
}
}
}
int main()
{
init();
SparseTable();
solve();
printf("%d\n",Ans);
return 0;
}

方法三:

看见这种区间移动的RMQ问题,相信大家都能想到“单调队列”吧?(想不到的自行面壁!……) 那么问题来了!二维的怎么搞?! 首先只看一层,可以用单调队列搞出来从每个点开始往后n个数的极值,如图。 用同样的方法将每一行都处理出来,并用数组\(w[i][j]\)记录第\(i\)行,从第\(j\)个开始往后\(n\)个数的最大值,\(ww[i][j]\)记录最小值。 接下来再来纵看,但看其中一列,也用同样的方法以\(w\)\(ww\)数组为依据来搞单调队列,如图 因为w已经将横向长为\(n\)的最大值存储在左边的\(4\)个点中了,纵向再求出这\(4\)个点的最大值,就是这\(4*4\)的矩阵的最大值。 最后再枚举一下正方形的左上定点,求出结果。\(O(ab+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
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N=1001;
struct node{
int pos,x;
}max[N],min[N];
int h1,t1,h2,t2;
int a[N][N],w[N][N],ww[N][N];
int main(){
freopen("square.in","r",stdin);
freopen("square.out","w",stdout);
int aa,bb,n;
scanf("%d%d%d",&aa,&bb,&n);
for(int i=1;i<=aa;i++)
for(int j=1;j<=bb;j++) scanf("%d",&a[i][j]);
for(int j=1;j<=aa;j++){
h1=h2=1; t1=t2=0;
for(int i=1;i<=bb;i++){
if(h1<=t1 && max[h1].pos<i-n+1) h1++;
if(h2<=t2 && min[h2].pos<i-n+1) h2++;
while(h1<=t1 && max[t1].x<a[j][i]) t1--;
max[++t1].pos=i; max[t1].x=a[j][i];
while(h2<=t2 && min[t2].x>a[j][i]) t2--;
min[++t2].pos=i; min[t2].x=a[j][i];
if(i-n+1>0) w[j][i-n+1]=max[h1].x,ww[j][i-n+1]=min[h2].x;
}
}
for(int j=1;j<=bb-n+1;j++){
h1=h2=1; t1=t2=0;
for(int i=1;i<=aa;i++){
if(h1<=t1 && max[h1].pos<i-n+1) h1++;
if(h2<=t2 && min[h2].pos<i-n+1) h2++;
while(h1<=t1 && max[t1].x<w[i][j]) t1--;
max[++t1].pos=i; max[t1].x=w[i][j];
while(h2<=t2 && min[t2].x>ww[i][j]) t2--;
min[++t2].pos=i; min[t2].x=ww[i][j];
if(i-n+1>0) w[i-n+1][j]=max[h1].x,ww[i-n+1][j]=min[h2].x;
}
}
int ans=0x7fffffff;
for(int i=1;i<=aa-n+1;i++)
for(int j=1;j<=bb-n+1;j++)
if(w[i][j]-ww[i][j]<ans) ans=w[i][j]-ww[i][j];
printf("%d\n",ans);
return 0;
}

2.防守之道 (cover)

【问题背景】 17班又要和AP1班踢足球了,为了吸取上次惨败的教训,王甫 王美男决定这次要好好加强一下防御。甫哥觉得,2个后卫防守实在不给力,决定变成3个防守后卫。 假定AP1班有n个前锋,每个前锋经常活动的区域是一个点,而3名后卫的防守区域都是一个边长为l的正方形。 甫哥想知道,l最小多大时,可以保证每名前锋都在防守区域内。 【问题描述】 给定n个点的坐标,求最小的l,使得3个边长为l的正方形可以将这n个点全部覆盖(每个正方形的各边平行于x轴和y轴)。

看见题目,应该就能想到是考察“二分答案”的吧?想不到的继续面壁!…… 问题的关键是,给定l,如何判断能否将n个点全覆盖? 先思考这样一个问题,根据n个点的坐标,可以处理出这n个点的外接矩形,那么,现在给你一个边长为l的正方形,如何放置?
答案是肯定的,一定是放在这个外接矩形的4个角!能想明白吗?为了全覆盖,只能放在4个角。 那么问题就好说了,先放一个正方形,没有覆盖的点再次处理出外接矩形,然后再放一个正方形,没有覆盖的点再处理出外接矩形,判断最后的外接矩形的长和正方形边长的大小关系,就知道是否可以覆盖了。 至于实现,由于每次放正方形都有4个位置,所以写DFS就行了,至于深度,由于只有2,所以完全不用担心。 最终效率 O(n lb L),轻松AC

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
#include<iostream>
#include<cstring>
#include<cstdio>
const int inf=2000000000;
int n,yes,l,r,mid;
int x[20001],y[20001];
bool b[20001];
using namespace std;
void dfs(int num,int len)
{
if(num>3)
{
for(int i=1;i<=n;i++)
if(!b[i]) return;
yes=1;return;
}
int maxx=-inf,maxy=-inf,minx=inf,miny=inf;
for(int i=1;i<=n;i++)
if(!b[i])
{
if(x[i]>maxx) maxx=x[i];if(x[i]<minx) minx=x[i];
if(y[i]>maxy) maxy=y[i];if(y[i]<miny) miny=y[i];
}
bool a[20001];
memcpy(a,b,sizeof(a));

for(int i=1;i<=n;i++)
if(x[i]>=maxx-len&&y[i]>=maxy-len) b[i]=1;
dfs(num+1,len);
memcpy(b,a,sizeof(b));

for(int i=1;i<=n;i++)
if(x[i]<=minx+len&&y[i]>=maxy-len) b[i]=1;
dfs(num+1,len);
memcpy(b,a,sizeof(b));

for(int i=1;i<=n;i++)
if(x[i]<=minx+len&&y[i]<=miny+len) b[i]=1;
dfs(num+1,len);
memcpy(b,a,sizeof(b));

for(int i=1;i<=n;i++)
if(x[i]>=maxx-len&&y[i]<=miny+len) b[i]=1;
dfs(num+1,len);
memcpy(b,a,sizeof(b));
}
int main()
{
freopen("cover.in","r",stdin);
freopen("cover.out","w",stdout);
scanf("%d",&n);
int maxx=-inf,maxy=-inf,minx=inf,miny=inf;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x[i],&y[i]);
if(x[i]>maxx) maxx=x[i];if(x[i]<minx) minx=x[i];
if(y[i]>maxy) maxy=y[i];if(y[i]<miny) miny=y[i];
}
l=0;r=max(maxx-minx,maxy-miny);
while(l!=r)
{
mid=(l+r)/2;
memset(b,0,sizeof(b));yes=0;
dfs(1,mid);
if(yes) r=mid;else l=mid+1;
}
printf("%d",l);
}

3.分蛋糕(separation)

【题目背景】 今天老师给机房的同志们买回a*b的蛋糕,蛋糕的每个位置都有 一个美味值。机房里有n位同学,现在要将整个蛋糕切n-1刀,分成n块,只能够沿着平行于蛋糕边缘的方向切割,每次切割将一块矩形蛋糕分成2块矩形蛋糕。对于切好的n块蛋糕,每块蛋糕都有一个美味值,等于内部所有美味值之和。为了尽可能的公平,希望这n块蛋糕美味值的标准差最小。 老师将切蛋糕的任务交给了楠哥,但是楠哥不会啊,快急哭了…… 现在他求助于你,希望你编写出一个程序,计算出这个最小的标准差值。 【题目描述】 对一个a*b的矩阵进行n-1次分割,使得分成的n个矩阵标准差最小,求出最小值(结果保留2位小数)

记忆化搜索 f[x1][y1][x2][y2][k]表示(x1,y1)到(x2,y2)的矩形分割成k个矩形的最优结果

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
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int a,b,n,x,tot;
int g[11][11],sum[11][11],f[11][11][11][11][11];
int search(int x1,int y1,int x2,int y2,int num)
{
if(f[x1][y1][x2][y2][num]!=-1) return f[x1][y1][x2][y2][num];
if(num==1)
{
int x=sum[y1][y2]+sum[x1-1][x2-1]-sum[x1-1][y2]-sum[y1][x2-1];
return x*x;
}
int x=0x7ffffff;
for(int i=x1;i<y1;i++)
for(int j=1;j<num;j++)
{
int y=search(x1,i,x2,y2,j)+search(i+1,y1,x2,y2,num-j);
if(y<x) x=y;
}
for(int i=x2;i<y2;i++)
for(int j=1;j<num;j++)
{
int y=search(x1,y1,x2,i,j)+search(x1,y1,i+1,y2,num-j);
if(y<x) x=y;
}
f[x1][y1][x2][y2][num]=x;
return x;
}
int main()
{
freopen("separation.in","r",stdin);
freopen("separation.out","w",stdout);
memset(f,-1,sizeof(f));
scanf("%d%d%d",&a,&b,&n);
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++)
scanf("%d",&g[i][j]),tot+=g[i][j];
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++)
sum[i][j]=g[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
float x=1.0*search(1,a,1,b,n)/n-1.0*tot*tot/n/n;
printf("%.2f",sqrt(x));
}