CF471D MUH and Cube Walls

Link

一句话题意：

给两堵墙。问 \(a\) 墙中与 \(b\) 墙顶部形状相同的区间有多少个.

这生草翻译不想多说了。

我们先来转化一下问题。对于一堵墙他的向下延伸的高度，我们是不用管的。

我们只需要考虑的是上边延伸的高度，那我们可以求出相邻的两个块之间的高度差。

我们要求的是 \(a\) 中连续的一段与 \(b\) 完全相同的数量。

其实就是 \(kmp\) 匹配啦。

注意特判一下 \(m=1\) 的情况。

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define int long long

const int inf = 2147483647;

const int N = 3e5+10;

int n,m,ans,h[N],t[N],a[N],b[N],net[N];

inline int read()

{

	int s = 0,w = 1; char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

	while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}

	return s * w;

}

signed main()

{

	n = read(); m = read();

	if(m == 1) {printf("%d\n",n); return 0;}

	for(int i = 1; i <= n; i++) h[i] = read();

	for(int i = 1; i <= m; i++) t[i] = read();

	for(int i = 1; i <= n-1; i++) a[i] = h[i] - h[i+1];//求一下相邻的两个的高度差

	for(int i = 1; i <= m-1; i++) b[i] = t[i] - t[i+1];

	b[m] = -inf;

	int j = 0;

	for(int i = 2; i < m; i++)//kmp

	{

		while(j && b[i] != b[j+1]) j = net[j];

		if(b[i] == b[j+1]) j++;

		net[i] = j;

	}

	j = 0;

	for(int i = 1; i < n; i++)

	{

		while(j && a[i] != b[j+1]) j = net[j];

		if(a[i] == b[j+1]) j++;

		if(j == m-1) ans++;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

CF471D MUH and Cube Walls

最新文章

热门文章