题目描述
暑假要到了。
可惜由于种种原因,小 $P$ 原本的出游计划取消。
失望的小 $P$ 只能留在西西艾弗岛上度过一个略显单调的假期……直到……
某天,小 $P$ 获得了一张神秘的藏宝图。
西西艾弗岛上种有 $n$ 棵树,这些树的具体位置记录在一张绿化图上。
简单地说,西西艾弗岛绿化图可以视作一个大小为 $(L+1) \\times (L+1)$ 的 $01$ 矩阵 $A$,地图左下角(坐标 $(0,0)$)和右上角(坐标 $(L,L)$)分别对应 $A\[0\]\[0\]$ 和 $A\[L\]\[L\]$。
其中 $A\[i\]\[j\]=1$ 表示坐标 $(i, j)$ 处种有一棵树,$A\[i\]\[j\]=0$ 则表示坐标 $(i, j)$ 处没有树。
换言之,矩阵 $A$ 中有且仅有的 $n$ 个 $1$ 展示了西西艾弗岛上 $n$ 棵树的具体位置。
传说,大冒险家顿顿的宝藏就埋藏在某棵树下。
并且,顿顿还从西西艾弗岛的绿化图上剪下了一小块,制作成藏宝图指示其位置。
具体来说,藏宝图可以看作一个大小为 $(S+1) \\times (S+1)$ 的 $01$ 矩阵 $B$($S$ 远小于 $L$),对应着 $A$ 中的某一部分。
理论上,绿化图 $A$ 中存在着一处坐标 $(x, y)$($0 \\le x, y \\le L-S$)与藏宝图 $B$ 左下角 $(0, 0)$ 相对应,即满足:
对 $B$ 上任意一处坐标 $(i, j)$($0 \\le i, j \\le S$),都有 $A\[x+i\]\[y+j\] = B\[i\]\[j\]$。
当上述条件满足时,我们就认为藏宝图 $B$ 对应着绿化图 $A$ 中左下角为 $(x, y)$、右上角为 $(x+S, y+S)$ 的区域。
实际上,考虑到藏宝图仅描绘了很小的一个范围,满足上述条件的坐标 $(x, y)$ 很可能存在多个。
请结合西西艾弗岛绿化图中 $n$ 棵树的位置,以及小 $P$ 手中的藏宝图,判断绿化图中有多少处坐标满足条件。
特别地,藏宝图左下角位置一定是一棵树,即 $A\[x\]\[y\] = B\[0\]\[0\] = 1$,表示了宝藏埋藏的位置。
输入格式
输入的第一行包含空格分隔的三个正整数 $n$、$L$ 和 $S$,分别表示西西艾弗岛上树的棵数、绿化图和藏宝图的大小。
由于绿化图尺寸过大,输入数据中仅包含 $n$ 棵树的坐标而非完整的地图;即接下来 $n$ 行每行包含空格分隔的两个整数 $x$ 和 $y$,表示一棵树的坐标,满足 $0 \\le x, y \\le L$ 且同一坐标不会重复出现。
最后 $(S+1)$ 行输入小 $P$ 手中完整的藏宝图,其中第 $i$ 行($0 \\le i \\le S$)包含空格分隔的 $(S+1)$ 个 $0$ 和 $1$,表示 $B\[S-i\]\[0\] \\cdots B\[S-i\]\[S\]$。
需要注意,最先输入的是 $B\[S\]\[0\] \\cdots B\[S\]\[S\]$ 一行,$B\[0\]\[0\] \\cdots B\[0\]\[S\]$ 一行最后输入。
输出格式
输出一个整数,表示绿化图中有多少处坐标可以与藏宝图左下角对应,即可能埋藏着顿顿的宝藏。
数据范围
$40\\%$ 的测试数据满足:$L \\le 50$;
$70\\%$ 的测试数据满足:$L \\le 2000$;
全部的测试数据满足:$n \\le 1000$、$L \\le 10^9$ 且 $S \\le 50$。
输入样例1:
5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0
输出样例1:
3
样例1解释
绿化图上 $(0,0)$、$(1,1)$ 和 $(2,2)$ 三处均可能埋有宝藏。
输入样例2:
5 4 2
0 0
1 1
2 2
3 3
4 4
0 0 0
0 1 0
1 0 0
输出样例2:
0
样例2解释
如果将藏宝图左下角与绿化图 $(3,3)$ 处对应,则藏宝图右上角会超出绿化图边界,对应不成功。
解题思路
既然藏宝图的左下角是一棵树且与绿化图对应,我们不妨枚举一下藏宝图左下角对应的到底是哪一棵树,再来判断以这棵树为藏宝图左下角是否可行。
首先,藏宝图的范围超出绿化图的范围肯定是不行的。所以我们枚举第 $i$ 棵树时,判断一下 $x _ i + S$ 和 $y _ i + S$ 是否超过了 $L$。如果超过肯定不行。
其次,我们遍历每一棵树,如果第 $j$ 棵树在藏宝图的范围内(即 $x _ i \le x _ j \le x _ i + S, y _ i \le y _ j \le y _ i + S$),那么我们对它进行如下讨论:
- 如果藏宝图对应位置(即 $(x _ j - x _ i, y _ j - y _ i)$ 的位置)为 $1$,也就是有种树,那么令一个变量 $cnt$ 加 $1$($cnt$ 刚开始为 $0$)。
- 如果藏宝图对应位置为 $0$,也就是没有种树,那么这个方案是不合法的,可以用一个
bool
型变量 $flag$ 标记并退出,也可以将 $cnt$ 设成一个非常小的数(如 $-10 ^ 5$)。
这样,如果最后 $cnt = k$ 且藏宝图符合绿化图范围(详见第二段内容),那么说明绿化图上有种树的位置藏宝图上对应位置也有种树,且绿化图上没有种树的位置藏宝图上对应位置也没有种树(否则会有 $cnt < k$),那么令答案 $ans$ 加 $1$。其中 $k$ 是藏宝图上 $1$ 的个数。
最后直接输出答案 $ans$ 即可。
AC Code
#include <cstdio>
#define N 1005
#define M 55
using namespace std;
int n, l, m, px, py, k, cnt, ans, x[N], y[N], a[M][M];
int main ()
{
scanf ("%d%d%d", &n, &l, &m);
for (int i = 1; i <= n; i ++)
{
scanf ("%d%d", &x[i], &y[i]);
}
for (int i = m; ~i; i --) // ~i 在这里相当于 i >= 0(原意是 i 不等于 -1)
{
for (int j = 0; j <= m; j ++)
{
scanf ("%d", &a[i][j]), k += a[i][j];
}
}
for (int i = 1; i <= n; i ++)
{
px = x[i], py = y[i], cnt = 0; // 枚举左下角,出现次数清零
for (int j = 1; j <= n; j ++)
{
if (x[j] >= px && x[j] <= px + m && y[j] >= py && y[j] <= py + m) // 如果这棵树在藏宝图范围内
{
a[x[j] - px][y[j] - py] ? cnt ++ : cnt = -114514;
// 如果藏宝图此位置是 1,那么出现次数加 1;否则不可能,将统计次数设为一个很小的数(0 不行,会 WA)
}
}
ans += px + m <= l && py + m <= l && cnt == k; // 答案加上是否是合法的方案
}
printf ("%d", ans);
return 0;
}
感谢观看!
密码碎片:Wing
$$\href {/blog/content/29204/} {\color {Lime} {【寒假每日一题】题解}}$$
怎么感觉有点像dp呢
qwq 这次实在是太惨了只拿到了一个 $1$ 月的,只好发一个 $1$ 月的了:AcWing【集日历瓜分10000AC币活动】赠送1月日历!
想要10呀大佬
差不多的思路,但官网100,acwing上tle了
看懂了感谢,终于弄明白了那个遍历的意思了
114514?
好臭的cnt`` o( ̄▽ ̄)ブ
玛雅,我离正解只差一个cnt啊,orz
一样的思路,但是只过了5个,能帮我看看哪里错了吗,谢谢~
也不知道为什么,把你这个内层 j 的循环改成 从 0 开始然后对应的改改里面的边界判断好像就对了
就把那一段改成这个样子就好啦
谢谢啦,等我搞懂会跟你说的。我看y总没排序,也许是排序的问题…
我想明白了,其余点要从0开始枚举,因为如果某个点x1不能作为起点,但是它可能是后面其它图x2里的点(当x1 == x2且y不同时,会出现遗漏x1点的情况)。