Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


alien解题报告

题目描述

给你一个R*C的地图,现在其中某些点已经有障碍物了,现在有一个大小为A+B的飞船需要降落在地图中的某个位置,要求飞船降落区域没有障碍物,请问有多少种降落区域选择的方案?


输入格式

第一行是四个整数,R C P Q
接下来的P 行每行两个整数x,y表示(x,y)这个点为障碍物
接下来的Q行每行两个整数A,B,表示询问大小为A*B的飞船降落有几种方案。


输出格式

输出Q行,每行只有一个整数,表示答案。


解题思路。

二维前缀和,f[i][j]表示到i,j这个点,共有x个障碍点;然后枚举i,j;检查A*B范围内障碍是否为零。因为飞船可以旋转,只需要把A和B交换就好。

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
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
using namespace std;
int f[1005][1005],map[1005][1005],n,m,p,q,a,b;
int main(){
freopen("alien.in","r",stdin);
freopen("alien.out","w",stdout);

scanf("%d%d%d%d",&n,&m,&p,&q);
for(int i = 1;i <= p;i++){
scanf("%d%d",&a,&b);
map[a][b] = 1;
}

for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
f[i][j] = f[i][j-1]+f[i-1][j]-f[i-1][j-1]+map[i][j];

while(q--){
int cnt = 0;
scanf("%d%d",&a,&b);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
if(i+a-1 <= n && j+b-1 <= m && map[i][j] == 0)
if(f[i+a-1][j+b-1] - f[i+a-1][j-1] - f[i-1][j+b-1] + f[i-1][j-1] == 0)
cnt++;
swap(a,b);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
if(i+a-1 <= n && j+b-1 <= m && map[i][j] == 0)
if(f[i+a-1][j+b-1] - f[i+a-1][j-1] - f[i-1][j+b-1] + f[i-1][j-1] == 0)
cnt++;
printf("%d\n",cnt);
}
return 0;
}

Markdown

最近的文章

lowbit解题报告

题目描述 这天,LYK在学习树状数组。 当它遇到一个叫lowbit的函数时有点懵逼。lowbit(x)的意思是将x分解成二进制,它的值就是2𝑘,其中k是最小的满足(x &amp; 2𝑘)&gt;0的数。(&amp;是二进制中的and运算)  LYK甚至知道lowbit(x)=(x&amp;-x) …

于  数学 继续阅读
更早的文章

stick解题报告

题目描述 LYK有很多木棍,具体的,总共有n根,且每根木棍都有一个长度。为了方便起见,我们可以用一个正整数ai表示第i根木棍的长度。LYK有一把小刀,但这把小刀由于削木棍很不方便,对于一根木棍而言,它只能用这把小刀削掉恰好1的长度。LYK觉得如果4根木棍头尾相连能恰好拼成长方形,说明这4根木棍是可以 …

于  模拟 继续阅读