CF471D MUH and Cube Walls

简要题意

题目传送门

平面上有两堵墙 \(a,b\)。长度分别为 \(n,w\)。求 \(a\) 墙顶端有多少个区间与 \(b\) 墙顶端一样。

\(1\le n,w \le 2 \times 10^5,1 \leq a_i,b_i \leq 10^9\)

代码

先用一下样例的图进行分析:

image

可以发现,顶端的形状取决于从 \(i\)\(i+1\) 上升或下降了多少格,而不取决于每一个地方的具体高度。自然想到差分数组。

我们求出 \(a,b\) 两堵墙的差分数组后,就可以 \(b\) 为模式串在 \(a\) 上跑 KMP 了。

注意这个做法有一个缺陷,就是在 \(w=1\) 的时候答案是 \(n\),我们会输出 \(n-1\)。这是因为差分数组比原数组少一个元素导致的。我们特判一下即可。

时间复杂度 \(O(n+w)\)

代码

这里给出的是传统实现,看不懂题解的拼接两个数组的写法。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
int A[1000005],B[1000005];
int fail[1000005];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>A[i];
    for(int i=1;i<=m;i++) cin>>B[i];
    for(int i=1;i<n;i++) A[i]-=A[i+1];
    for(int i=1;i<m;i++) B[i]-=B[i+1];
    n--;m--;
    for(int i=2,j=0;i<=m;i++){
        while(j&&B[i]!=B[j+1]) j=fail[j];
        if(B[j+1]==B[i]) j++;
        fail[i]=j;
    }
    int ans=0;
    for(int i=1,j=0;i<=n;i++){
        while(j&&B[j+1]!=A[i]) j=fail[j];
        if(A[i]==B[j+1]) j++;
        if(j==m){ans++;j=fail[j];}
    }
    cout<<ans;
    return 0;
}
如果文章有问题,静待斧正,建议向我(@xiezheyuan)发送洛谷私信并指出博文地址 http://www.cnblogs.com/zheyuanxie/p/cf417d.html !
本文转载于网络 如有侵权请联系删除

相关文章

  • Node.js 基础入门

    一、Node.js简介Node.js是一个基于ChromeV8引擎的JavaScript运行时环境安装与运行下载https://nodejs.org/zh-cn/download/复制下载创建项目mkdirnode cdnode npminit-y复制新建index.js文件const{readFile}=require('fs') readFile('./package.json',{encoding:'utf-8'},(err,data)=>{ if(err){ throwerr; } console.log(data) })复制输入package.json文件nodeindex.js复制版本管理在同一个设备上如何快速切换Node.js版本?版本管理工具:n:一个npm全局的开源包,是依赖npm来全局安装、使用的fnm:快速简单,兼容性支持.node-version和.nvmrc文件nvm:独立的软件包,NodeVersionManager特点特点异步I/O当Node.js执行I/O操作时,会在响应返回并恢复操作,

  • 使用webpack和rollup打包组件库

    前言之前做了一个loading的样式组件,为了实现代码的可重用性,将这个小项目打包并且发布在了npm上。在一次次的打包发包过程中经历了一个又一个报错,@buzuosheng/loading这个组件已经到了2.7.0版本,虽然还有一些要调整的地方,但总算是可以用了。包体的大小webpack和rollup对比webpack算是使用程序员使用最多的打包工具,面试中往往会问到webpack的相关问题,而rollup被问到的要少很多。导致这种现象的一个原因是,「应用开发使用webpack,库开发使用rollup」的说法。但是两个打包工具都有很强大的插件开发功能,功能差异越来越模糊,但是rollup使用起来更加简洁,而且能打出能小体积的文件。但当我们做前端应用时,性能分析往往要求更小的库,所以rollup更符合开发库的要求。这次算是一个打包的实验,我们使用两个工具都对这个项目打一次包。使用webpack打包在打包之前,需要给package.json文件中添加或更改一些字段。{ //程序主入口模块,用户引用的就是该模块的导出 "main":"dist/bundle.js

  • 使用 Kustomize 配置 Kubernetes 应用

    如果你经常使用Kubernetes,那么你肯定就有定制资源清单文件的需求,但是貌似现在大家都比较喜欢使用Helm,Helm很好用,但也有很多缺点,比如需要一个tiller服务端,需要超高的权限,最重要的是如果你要想自己做一个HelmChart包的话,则不是那么容易的,需要你了解一些gotemplate的相关知识,它抛弃了我们在Docker和Kubernetes上面学到的一些知识点,今天我们将为大家介绍另外一种名为Kustomize的替代工具。 实际上Kustomize并不是一个新的工具,而且现在已经被集成在了kubectl1.14版本的子命令中了,是不是非常方便了,免去了安装第三方工具的麻烦,因为kubectl工具基本上是我们天天都在使用的,所以......你可以把Helm命令扔掉了?。Kustomize和Kubernetes一样,它完全就是声明式的,你说你想要什么,系统就提供给你什么,不需要遵循命令方式来描述你希望构建的对象。其次,它和Docker比较类似,有很多层组成,每个层都是修改以前的层,正因为有这个理念存在,所以我们可以不断在其他人至上写东西,而不会增加配置的复杂性,构建的最

  • 简易数据分析 04 | Web Scraper 初尝:抓取豆瓣高分电影

    这是简易数据分析系列的第4篇文章今天我们开始数据抓取的第一课,完成我们的第一个爬虫。因为是刚刚开始,操作我会讲的非常详细,可能会有些啰嗦,希望各位不要嫌弃啊:)有人之前可能学过一些爬虫知识,总觉得这是个复杂的东西,什么HTTP、HTML、IP池,在这里我们都不考虑这些东西。一是小的数据量根本不需要考虑,二是这些乱七八糟的东西根本没有说到爬虫的本质。爬虫的本质是什么?其实就是找规律。而且爬虫的找规律难度,大部分都是小学三年级的数学题水平。 我们下面拿个例子说明一下。下图历史文章的一个截图,我们可以很清晰的看到,每一条推文可以分为三大部分:标题、图片和作者,我们只要找到这个规律,就可以批量的抓取这类数据。好了,理论的地方我们讲完了,下面我们开始进行实操。但凡做爬虫练手,第一个爬取的网站一般都是豆瓣电影TOP250,网址链接是https://movie.douban.com/top250?start=0&filter=。第一次上手,我们爬取的内容尽量简单,所以我们只爬取第一页的电影标题。浏览器按F12打开控制台,并把控制台放在网页的下方(具体操作可以看上一篇文章),然后找到WebSc

  • 微服务模式系列之二:微服务架构

    译者评论:微服务架构大家已经耳熟能详,但是我认为这篇文章最有价值的是这段:但这类解决方案中也存在着以下弊端:开发者必须应对创建分布式系统所产生的额外的复杂因素。现有开发者工具/IDE主要面向单体应用程序,因此无法显式支持分布式应用的开发。 测试工作更加困难。开发者必须采取服务间通信机制。很难在不使用分布式事务机制的情况下跨服务实现功能。跨服务实现功能要求各团队进行密切协作。 部署复杂。在生产环境下,对这类多种服务类型构建而成的系统进行部署与管理十分困难。内存占用量更高。微服务架构使用N*M个服务实例替代N个单体应用实例,如果每项服务运行自己的JVM(或者其它类似机制),且各实例之间需要进行隔离,那将导致M倍JVM运行时的额外开销。另外,如果每项服务都在自己的虚拟机(例如EC2实例)上运行,如同Netflix一样,那么额外开销会更高。微服务架构带来的这些复杂性正是普元数字化企业云平台着力解决的。译者自序:熟悉我的朋友都知道,我很不喜欢翻译东西,因为在两种语言的思维方式之间做频繁切换对我来说是件很痛苦的事情。但是这次不一样,公司和同事的大力支持降低了我的痛苦指数,让我能够坚持把Chri

  • 揭秘:从内部源码看Facebook技术(第一集)

    Warning本文中所有代码都是通过合法途径获得。写在前面我是一名铁杆Facebook粉丝。Facebook为开源社区贡献了许多力量,经常开放他们内部的软件。比如Phabricator,libphutil,以及XHP都是不错的好东西。Phabricator是Facebook开发的可视化代码审查工具。工程师可以在页面上非常方便的针对每一段(单行或者多行)代码进行交互讨论。负责审查的工程师可以接受代码改变,可以提出疑问要求原作者继续修改。曾经有段时间我对Phabricator和XHP(一个PHP扩展)进行了优化研究,却意外发现了许多有关Facebook的内部资料。意外的发现大概是2013年6月份左右,那时我已经在使用Phabricator修复bug了。如果我没有记错的话,Phabricator程序当时是返回了一个PhutilBootloaderException错误信息。当时我并不知道Phabricator是怎么运行的,于是就Google查询了下错误信息……就跟你想的一样,我获得了源代码以及一些参考链接,其中有一个链接十分抢眼——一个Pastebin(一个轻量级的文本分享工具)分享链接,里

  • Django基础

    1.Django安装 pipinstalldjango==2.1.5   2.修改配置 settings.py--> LANGUAGE_CODE='zh-Hans'TIME_ZONE='Asia/Shanghai'USE_I18N=TrueUSE_L10N=TrueUSE_TZ=False   3.Django默认的数据库是sqlite,如果想用mysql settings.py-->   'default': {        'ENGINE': 'django.db.backends.mysql',        'NAME': 'db1',        'USER': 'user1',     &nbs

  • 本地缓存方式

    iOS本地缓存数据方式有五种: 1.直接写文件方式:可以存储的对象有NSString、NSArray、NSDictionary、NSData、NSNumber,数据全部存放在一个属性列表文件(*.plist文件)中。 2.NSUserDefaults(偏好设置),用来存储应用设置信息,文件放在perference目录下。 3.归档操作(NSkeyedArchiver),不同于前面两种,它可以把自定义对象存放在文件中。 4.coreData:coreData是苹果官方iOS5之后推出的综合型数据库,其使用了ORM(ObjectRelationalMapping)对象关系映射技术,将对象转换成数据,存储在本地数据库中。coreData为了提高效率,甚至将数据存储在不同的数据库中,且在使用的时候将本地数据放到内存中使得访问速度更快。我们可以选择coreData的数据存储方式,包括sqlite、xml等格式。但也正是coreData是完全面向对象的,其在执行效率上比不上原生的数据库。除此之外,coreData拥有数据验证、undo等其他功能,在功能上是几种持久化方案最多的。 5.FMDB:FM

  • Oracle 时间差计算

    GPS平台、网站建设、软件开发、系统运维,找森大网络科技!https://cnsendnet.taobao.com来自森大科技官方博客http://www.cnsendblog.com/index.php/?p=2193   Oracle时间差计算 两个Date类型字段:START_DATE,END_DATE,计算这两个日期的时间差(分别以天,小时,分钟,秒,毫秒): 天: ROUND(TO_NUMBER(END_DATE-START_DATE)) 小时: ROUND(TO_NUMBER(END_DATE-START_DATE)*24) 分钟: ROUND(TO_NUMBER(END_DATE-START_DATE)*24*60) 秒: ROUND(TO_NUMBER(END_DATE-START_DATE)*24*60*60) 毫秒: ROUND(TO_NUMBER(END_DATE-START_DATE)*24*60*60*1000)   Oracle计算时间差函数2008-08-2010:00两个Date类型字段:START_DATE,END_DATE,计算这

  • 流程控制之条件语句if

    1.1go语言条件语句:    条件语句需要开发者通过指定一个或多个条件,并通过测试条件是否为true来决定是否执行指定语句,并在条件为false的情况在执行另外的语句。   Go语言提供了以下几种条件判断语句: 1.1.2if语句if语句由一个不二表达式后紧跟一个或多个语句组成 Go编程语言中if语句的语法如下: •可省略条件表达式括号。 •持初始化语句,可定义代码块局部变量。 •代码块左括号必须在条件表达式尾部。 if布尔表达式{ /*在布尔表达式为true时执行*/ }复制 if在布尔表达式为true时,其后紧跟的语句块执行,如果为false则不执行。   x:=0 //ifx>10//Error:missingconditioninifstatement //{ //} ifn:="abc";x>0{//初始化语句未必就是定义变量,如println("init")也是可以的。 println(n[2]) }elseifx<0{//注意elseif和else左大括号位置。 println(n[1]) }else{ println(n[0])

  • Django 之缓存

    Django之缓存 一、缓存 由于Django是动态网站,所有每次请求均会去数据进行相应的操作,当程序访问量大时,耗时必然会更加明显,最简单解决方式是使用:缓存,缓存将一个某个views的返回值保存至内存或者memcache中,5分钟内再有人来访问时,则不再去执行view中的操作,而是直接从内存或者Redis中之前缓存的内容拿到,并返回。 Django中提供了6种缓存方式: 开发调试 内存 文件 数据库 Memcache缓存(python-memcached模块) Memcache缓存(pylibmc模块) 1、配置 a、开发调试 1#此为开始调试用,实际内部不做任何操作 2#配置: 3CACHES={ 4'default':{ 5'BACKEND':'django.core.cache.backends.dummy.DummyCache',#引擎 6'TIMEOUT':300,#缓存超时时间(默认300,None表示永不过期,0表示立即过期) 7'OPTIONS':{ 8'MAX_ENTRIES':300,#最大缓存个数(默认300) 9'CULL_FREQUENCY'

  • frp代理工具

    frps.ini的配置文件如下: [common] bind_port=7000 [common]部分是必须有的配置,其中bind_port是自己设定的frp服务端端口,用于和frp服务器端进行通信。 复制 frpc.ini配置文件如下: [common] server_addr=VPSIP server_port=7000 [ssh] type=tcp local_ip=127.0.0.1 local_port=22 remote_port=6000 [common]部分是必须有的配置 其中serveraddr是VPS的IP serverport是用来和frp客户端通信的端口,必须和frp服务器端端口一致,默认是7000。 [ssh]可以修改成任意名称,localip是本地的IP,localport是本地进行监听的端口, remoteport是访问VPS时需要使用的端口,也就是说访问到这个remoteport端口时才能访问到内网。 复制 启动frp客户端: ./frpc-c./frpc.ini 启动frp服务器端 ./frps-c./frps.ini frpc.i

  • 期末成绩计算方法

    综合作业验收时间: 12月15日(周日)的课程作业验收,定在教室F121,时间是14:00开始 综合作业分数30分   期末成绩构成:9次作业+4次课堂作业+GoldNum锦标赛成绩 9次作业:8次10分的,最后1次综合的30分 4次课堂作业:每次5分 GoldNum锦标赛:5分 9次作业中一直未交的扣掉本次作业满分 上述成绩加起来后得到每位同学的原始得分[S1...Sn] [S1...Sn]映射到期末成绩[65...100] 映射方法通过映射到90分数以上的人数来决定   附加作业每次5分,最高可附加10分,不影响其它同学成绩,做的同学单独在自己的期末成绩(映射前)上加  附加题可选题目: 1、用 windbg 以及其它工具如何debug  程序,  以及如何下载 windowsSDK(这个工具包包括了 windbg 以及其它工具) http://msdn.microsoft.com/en-US/windows/desktop/bg162891 

  • Java 高级技术 —— 专栏总集篇

    此篇博文是为了本人将本人认为有必要的、实现过程十分巧妙的技术博文总集在此篇之中 第一节-------------------------------------------------《ORM技术》 第二节-------------------------------------------------《easySwing》 第三节-------------------------------------------------《Betty》 第四节-------------------------------------------------《NetFramwork》 第五节-------------------------------------------------《IoC/DI技术的实现》 第六节-------------------------------------------------《AOP技术的基本实现》 第七节-------------------------------------------------《RMI技术的基本实现》 第八节-----------

  • 自学Java HashMap源码

    自学JavaHashMap源码# 参考:http://zhangshixi.iteye.com/blog/672697 HashMap概述   HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键,存储的对象是一个键值对对象(Entry<K,V>)。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。   注意这里研究的是JDK7之前的版本,JDK8HashMap采用的是数组+链表+红黑树的形式。 HashMap的数据结构   基于数组和链表实现,内部维护着一个数组table,该数组保存着每个链表的表头结点;查找时,先通过hash函数计算key的hash值,再根据key的hash值计算数组索引(取余法),然后根据索引找到链表表头结点,然后遍历查找该链表。   示意图如下,左边的数组索引是根据key的hash值计算得到,不同hash值有可能产生一样的索引,即哈希冲突,此时采用链地址法处理哈希冲突,即将所有索引一致的节点构成一个单链表; HashMap继承的类与实现的接口 源码如下: /** *Thetable,

  • IDEA修改选中行背景色 - mac电脑 - 2022年7月

    第一步:IntellijIDEA -> Preferences: 第二步: 左边菜单选中:Editor -> ColorScheme -> General  右边内容选中:Editor -> Caretrow -> (勾选)Background -> 设置勾选框后面的颜色     end. 支付宝扫一扫,为女程序员打赏! 作者:梦幻朵颜 版权:本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

  • Block详解二(底层分析)

    本人已迁移博客至掘进,以后会在掘进平台更新最新的文章也会有更多的干货,欢迎大家关注!!!https://juejin.im/user/588993965333309   Block专辑: Block讲解一 MRC-block与ARC-block Block详解一(底层分析) 今天讲述Block的最后一篇,后两篇仅仅是加深1,2篇的理解,废话少说,开始讲解! __block细节 __block内存管理 循环引用问题   一:__block细节 大家可能会遇到下面的问题,block的内部想要修改外部的auto变量,但是编译器会报问题!如下 如果block内部想要修改外部的auto变量,可以在intage前面加入static修饰词,变为静态局部变量(会一直存在内存中,反而不好),以及可以将intage代码移植到函数外面变为全局变量!除此之外还有没有其他的做法了呢,显然是有的,通过__block修饰,如下: 发现__block修改外面变量是可以达到目的的!小结论 __block可以用于解决block内部无法修饰auto变量值的问题 __block不能修饰全局变量、

  • binlog文件恢复数据

    占位符! 学习中,博客都是自己学习用的笔记,持续更新改正。。。

  • 排序

    (1)冒泡排序 冒泡排序(BubbleSort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。 作为最简单的排序算法之一,冒泡排序给我的感觉就像Abandon在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。冒泡排序还有一种优化算法,就是立一个flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来 说并没有什么太大作用。 1.算法步骤 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 2.动图演示 3.什么时候最快 当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。 4.什么时候最慢 当输入的

  • ubuntu下如何用命令行运行deb安装包

    如果ubuntu要安装新软件,已有deb安装包(例如:iptux.deb),但是无法登录到桌面环境。那该怎么安装?答案是:使用dpkg命令。dpkg命令常用格式如下:sudodpkg-Iiptux.deb#查看iptux.deb软件包的详细信息,包括软件名称、版本以及大小等(其中-I等价于--info)sudodpkg-ciptux.deb#查看iptux.deb软件包中包含的文件结构(其中-c等价于--contents)sudodpkg-iiptux.deb#安装iptux.deb软件包(其中-i等价于--install)sudodpkg-liptux#查看iptux软件包的信息(软件名称可通过dpkg-I命令查看,其中-l等价于--list)sudodpkg-Liptux#查看iptux软件包安装的所有文件(软件名称可通过dpkg-I命令查看,其中-L等价于--listfiles)sudodpkg-siptux#查看iptux软件包的详细信息(软件名称可通过dpkg-I命令查看,其中-s等价于--status)sudodpkg-riptux#卸载iptux软件包(软件名称可通过dp

  • 7.测试与调试

    测试概要 测试内容 实际测试内容 预先设计内容 说明 登录系统 不同用户输入用户名和密码后,进入各自的界面 普通用户登录后进入查询界面,管理员登录后进入管理界面   线路查询 用户输入线路名后,点击查询,结果框出现该线路进过的站点数,起点站和终点站,并显示沿途的站点 用户进入查询界面后,输入要查询的线路,结果框显示该线路上所有站点,起点和终点站   站点查询 输入要查询的占站点,结果框显示经过该站点的线路条数,并分别显示每条线路具体走向 将要查询的站点点击后出现经过该站点的线路及线路的信息   线路选择 选择出发的起点站和要到达的终点站,分别显示直达方案和换乘方案 输入起点站和终点站,结果框显示乘车路线   删除站点 首先选择路线上的站点,点击删除,返回后站点列表上不再显示该站点 选择要删除的站点后站点列表里和数据库里不再显示该站点   增加站点 选择在哪条路线上增加站点,然后点击增加 在选定的线路上增

相关推荐

推荐阅读