codevs 3945 完美拓印 (KMP)
2024-08-31 12:00:59
题目大意:给你一个神奇的印章,他左右下三个面都是直的,上面是凸凹不平的面(凸凹都平行于别的面)。然后给你一个轮廓线,如果一个面能与轮廓线完全重合,可以把印章的这个沿着轮廓线拓印,求所有的拓印方案。
把轮廓线和印章相邻两个高度打个查分,然后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 ;
}
最新文章
- 自己使用的一个.NET轻量开发结构
- Spring整合Ehcache管理缓存
- Javassist 字节码操作
- XiangBai——【AAAI2017】TextBoxes_A Fast Text Detector with a Single Deep Neural Network
- .NET C# 使用S22.Imap.dll接收邮件 并且指定收取的文件夹的未读邮件,并且更改未读准态
- Apache服务器访问过慢分析及解决
- StatusBar &; StatusBarItem
- CCF 认证4
- Linux下platform设备以及platform设备和驱动注册的先后顺序
- 总结:S5PV210时钟系统
- OSPF的基本配置及DR /BDR选举的实验
- Mysql中如何创建、删除授权用户
- html:常见行内标签,常见块级标签,常见自闭合标签
- 结对编程--四则运算(Java)萧英杰 夏浚杰
- Swift 学习- 03 -- 基本运算符
- 没有系列化导致错误:java.io.NotSerializableException: com.bjpowernode.bean.Team
- 将一台电脑上的虚拟机上的系统复制到另一台电脑的虚拟机上!!!and想询问大神们问题的解决办法??
- vim自动保存折叠
- create view in view
- 解决安装Apache中出现checking for APR... no configure: error: APR not found. Please read the documentation的问题
热门文章
- javascript事件列表解说
- N3-1 - 数组 - convert-sorted-array-to-binary-search-tree
- nyoj2-吝啬的国度
- [Libre 6282] 数列分块入门 6 (分块)
- 一个简单的 PC端与移动端的适配(通过UA)
- Centos如何安装 jdk 环境变量
- ajax提交数据遇到400异常,原因及解决方案
- HDU 4454
- HDU 5078 Revenge of LIS II(dp LIS)
- Ubuntu14.04编译WebRTC For Android代码 2014-07-24