继续刷题
Monitor
#include<bits/stdc++.h>
using namespace std
;
#define in Read()
int in
{
int i
=0;bool f
=true;char ch
=0;
while(!isdigit(ch
)&&ch
!='-') ch
=getchar();
if(ch
=='-') ch
=getchar(),f
^=1;
while(isdigit(ch
)) i
=(i
<<1)+(i
<<3)+ch
-48,ch
=getchar();
return f
?i
:-i
;
}
const int N
=1e7+5;
int n
,m
,p
,q
;
typedef vector
<int> poly
;
int main(){
while(scanf("%d%d",&n
,&m
)!=EOF){
vector
<poly
> f(n
+2,poly(m
+2)),g(n
+2,poly(m
+2));
p
=in
;
for(int i
=1;i
<=p
;++i
){
int x1
=in
,y1
=in
,x2
=in
,y2
=in
;
++f
[x1
][y1
];
--f
[x1
][y2
+1];
--f
[x2
+1][y1
];
++f
[x2
+1][y2
+1];
}
for(int i
=1;i
<=n
;++i
)
for(int j
=1;j
<=m
;++j
)
f
[i
][j
]+=f
[i
-1][j
]+f
[i
][j
-1]-f
[i
-1][j
-1];
for(int i
=1;i
<=n
;++i
)
for(int j
=1;j
<=m
;++j
)
g
[i
][j
]=(f
[i
][j
]>0)+g
[i
][j
-1]+g
[i
-1][j
]-g
[i
-1][j
-1];
q
=in
;
for(int i
=1;i
<=q
;++i
){
int x1
=in
,y1
=in
,x2
=in
,y2
=in
;
int S
=g
[x2
][y2
]-g
[x2
][y1
-1]-g
[x1
-1][y2
]+g
[x1
-1][y1
-1];
if(S
==(x2
-x1
+1)*(y2
-y1
+1)) puts("YES");
else puts("NO");
}
}
return 0;
}
二位差分有点烧脑 旁边@wssstc piapia打脸
最大正方形
#include<bits/stdc++.h>
using namespace std
;
#define in Read()
int in
{
int i
=0;bool f
=true;char ch
=0;
while(!isdigit(ch
)&&ch
!='-') ch
=getchar();
if(ch
=='-') ch
=getchar(),f
^=1;
while(isdigit(ch
)) i
=(i
<<1)+(i
<<3)+ch
-48,ch
=getchar();
return f
?i
:-i
;
}
int n
,m
,a
[200][200];
int main(){
n
=in
,m
=in
;
for(int i
=1;i
<=n
;++i
)
for(int j
=1;j
<=m
;++j
)
a
[i
][j
]=in
+a
[i
-1][j
]+a
[i
][j
-1]-a
[i
-1][j
-1];
for(int l
=min(n
,m
),s
=l
*l
;l
>=1;--l
,s
=l
*l
)
for(int i
=l
;i
<=n
;++i
)
for(int j
=l
;j
<=m
;++j
)
if(a
[i
][j
]+a
[i
-l
][j
-l
]-a
[i
][j
-l
]-a
[i
-l
][j
]==s
){
printf("%d\n",l
);
return 0;
}
puts("0");
return 0;
}
[HNOI2003]激光炸弹
边界条件想清楚 数组越界会造成和MLE一样的惨剧
#include<bits/stdc++.h>
using namespace std
;
#define in Read()
int in
{
int i
=0;bool f
=true;char ch
=0;
while(!isdigit(ch
)&&ch
!='-') ch
=getchar();
if(ch
=='-') ch
=getchar(),f
^=1;
while(isdigit(ch
)) i
=(i
<<1)+(i
<<3)+ch
-48,ch
=getchar();
return f
?i
:-i
;
}
const int N
=5e3+7;
int n
,m
,a
[N
][N
],ans
;
int main(){
n
=in
,m
=in
;
for(int i
=1;i
<=n
;++i
){
int x
=in
+1,y
=in
+1;
a
[x
][y
]=in
;
}
for(int i
=1;i
<=5005;++i
)
for(int j
=1;j
<=5005;++j
)
a
[i
][j
]+=a
[i
][j
-1]+a
[i
-1][j
]-a
[i
-1][j
-1];
for(int i
=m
;i
<=5005;++i
)
for(int j
=m
;j
<=5005;++j
)
ans
=max(ans
,a
[i
][j
]-a
[i
-m
][j
]-a
[i
][j
-m
]+a
[i
-m
][j
-m
]);
printf("%d\n",ans
);
return 0;
}
