题目大意:给你一个神奇的印章,他左右下三个面都是直的,上面是凸凹不平的面(凸凹都平行于别的面)。然后给你一个轮廓线,如果一个面能与轮廓线完全重合,可以把印章的这个沿着轮廓线拓印,求所有的拓印方案。

把轮廓线和印章相邻两个高度打个查分,然后KMP匹配一下就行了。

 #include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define N 10010
#define mod 1000000007
#define ui unsigned int
#define ll long long
#define dd double
#define idx(x) x-'a'+1
using namespace std;
//re
int T,n,m,cnt;
int nxt[][N];
ui f[N];
int a[N],b[N],s[N],t[][N];
void get_kmp(int s1[],int p)
{
int i=,j=;
nxt[p][]=;
while(i<m)
{
if(j==||s1[i]==s1[j])
{
i++;
j++;
nxt[p][i]=j;
}else{
j=nxt[p][j];
}
}
}
int KMP(int s1[],int s2[],int p)
{
int i=,j=,cnt=;
while(i<n)
{
if(j==||s1[i]==s2[j])
{
i++;
j++;
}else{
j=nxt[p][j];
}
if(j==m)
{
cnt++;
j=nxt[p][j];
}
}
return cnt;
} int main()
{
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++) scanf("%d",&b[i]);
for(int j=;j<=n;j++) scanf("%d",&a[j]);
if(m==) {printf("%d\n",n*);return ;}
for(int i=;i<m;i++) t[][i]=b[i+]-b[i],t[][i]=;
for(int i=;i<m;i++) t[][i]=t[][m-i];
for(int i=;i<n;i++) s[i]=a[i+]-a[i];
get_kmp(t[],),get_kmp(t[],),get_kmp(t[],);
int ans=;
ans+=KMP(s,t[],);
ans+=KMP(s,t[],);
ans+=*KMP(s,t[],);
printf("%d\n",ans);
return ;
}

最新文章

  1. 自己使用的一个.NET轻量开发结构
  2. Spring整合Ehcache管理缓存
  3. Javassist 字节码操作
  4. XiangBai——【AAAI2017】TextBoxes_A Fast Text Detector with a Single Deep Neural Network
  5. .NET C# 使用S22.Imap.dll接收邮件 并且指定收取的文件夹的未读邮件,并且更改未读准态
  6. Apache服务器访问过慢分析及解决
  7. StatusBar &amp; StatusBarItem
  8. CCF 认证4
  9. Linux下platform设备以及platform设备和驱动注册的先后顺序
  10. 总结:S5PV210时钟系统
  11. OSPF的基本配置及DR /BDR选举的实验
  12. Mysql中如何创建、删除授权用户
  13. html:常见行内标签,常见块级标签,常见自闭合标签
  14. 结对编程--四则运算(Java)萧英杰 夏浚杰
  15. Swift 学习- 03 -- 基本运算符
  16. 没有系列化导致错误:java.io.NotSerializableException: com.bjpowernode.bean.Team
  17. 将一台电脑上的虚拟机上的系统复制到另一台电脑的虚拟机上!!!and想询问大神们问题的解决办法??
  18. vim自动保存折叠
  19. create view in view
  20. 解决安装Apache中出现checking for APR... no configure: error: APR not found. Please read the documentation的问题

热门文章

  1. javascript事件列表解说
  2. N3-1 - 数组 - convert-sorted-array-to-binary-search-tree
  3. nyoj2-吝啬的国度
  4. [Libre 6282] 数列分块入门 6 (分块)
  5. 一个简单的 PC端与移动端的适配(通过UA)
  6. Centos如何安装 jdk 环境变量
  7. ajax提交数据遇到400异常,原因及解决方案
  8. HDU 4454
  9. HDU 5078 Revenge of LIS II(dp LIS)
  10. Ubuntu14.04编译WebRTC For Android代码 2014-07-24