首页 > 其他分享 >The 2024 ICPC Asia East Continent Online Contest (II)

The 2024 ICPC Asia East Continent Online Contest (II)

时间:2024-09-25 18:00:53浏览次数:6  
标签:前缀 Contest sum Asia II kmp 集合 border 复杂度

C. Prefix of Suffixes

比赛的时候调E,调的心态爆炸,最后一点时间写C,又没冲出来

题目大意

给三个数组\(\{S_n\},\{a_n\},\{b_n\}\),对于每个\(i\)求\(\sum_{j=1}^i\sum_{k=j}^{j+z_j-1}A_kB_j\),其中\(z_i\)表示\(S_{[1,i]}\)和\(S_{[j,i]}\)的最长公共前缀的长度,\(S\)数组强制在线

\[n\le100000 \]

题解

设\(f_i\)表示\(i\)的答案
可以把式子转化成\(f_i=f_{i-1}+A_i\sum_{j=1}^iB_j[S_{[j,i]}是S_{[1,i]}的前缀]\)
那么关键就是要求\(\sum_{j=1}^iB_j[S_{[j,i]}是S_{[1,i]}的前缀]\)
相当于要对\(S_{[1,i]}\)的求所有\(border\)的\(B\)之和
设\(g_i=\sum_{j=1}^iB_j[S_{[j,i]}是S_{[1,i]}的前缀]\)
考虑从\(g_{i-1}\)来求\(g_i\),那么要把在\(i-1\)上是\(border\)的,但在\(i\)上不是\(border\)的减去,然后再把\(i\)上长度为\(1\)的\(border\)加上
对于一个\(i\),它的\(border\)集合,就是\(kmp_{i}\)连出来的链,\(i-1\)的\(border\)集合,就是\(kmp_{i-1}\)连出来的链
一个在\(i-1\)的长度为\(l\)的\(border\),在\(i\)中如果还存在,它的长度将变为\(l+1\),也就是\(i\)中的\(border\)集合中应该存在\(l+1\),否则这个\(border\)就是要被删去的\(border\)
这个第一个想法就是用\(bitset\)来实现,但这太暴力了,再考虑其他性质,就是\(i\)的\(border\)集合除去\(1\)后一定是\(i-1\)的集合的子集,于是又有第二个想法,暴力的跳\(kmp\)数组,如果我们的复杂度可以控制在\(O(不同的border)\),那么复杂度就是对的,只有\(kmp_{i}=kmp_{i-1}+1\)的情况会影响复杂度,于是可以预处理一下,让条链的时候,直接跳过\(kmp_{i}=kmp_{i-1}+1\)的情况,这样复杂度就对了,每个\(border\)最多被删一次,所以复杂度是\(O(n)\)的

标签:前缀,Contest,sum,Asia,II,kmp,集合,border,复杂度
From: https://www.cnblogs.com/the-blog-of-doctorZ/p/18431910

相关文章

  • IIS Web服务器安装配置教程(图文)---IIS安装(win10)
    IIS是一种Web(网页)服务组件,其中包括Web服务器、FTP服务器、NNTP服务器和SMTP服务器,分别用于网页浏览、文件传输、新闻服务和邮件发送等方面,它使得在网络(包括互联网和局域网)上发布信息成了一件很容易的事。IIS是什么很多朋友都不知道IIS是什么?其实IIS是InternetInformation......
  • IIS部署前端代码和后端api
    环境准备:安装net8运行时 https://dotnet.microsoft.com/zh-cn/download/dotnet/8.0 第一步:安装IIS 第二步:安装完成后,打开IIS管理器 第三步:部署后端api服务1.选择网站右键"添加网站"  2,点击确定添加3.添加完成后,选中刚刚添加的网站,点击预览网站4:如......
  • STM32驱动1.3寸(0.96寸)OLED显示屏 #基于HAL库#软件IIC通讯
    前言  本文用作记录基于HAL库搭建起来的软件IIC驱动OLED显示器。一、软件IIC原理  只需理解两点:1.IIC是一种通信总线,物理层面用于单片机与OLED的通信。2.软件IIC即模拟硬件IIC的引脚时序,可以灵活配置引脚。IC物理接口:IIC串行总线有两根信号线,一根是双向的数据线SDA,另......
  • 【Linux】多线程:线程池的创建、日志类、RAII互斥锁、单例模式:饿汉方式与懒汉方式
    目录一、线程池概念二、线程的封装及线程池类成员变量的介绍 三、单例模式饿汉方式(EagerInitialization)懒汉方式(LazyInitialization)四、RAII类型的互斥锁 五、日志类的实现六、简单的任务类创建七、线程池的创建 一、线程池概念线程池(ThreadPool)是一种基于......
  • The 2024 ICPC Asia EC Regionals Online Contest (II)
    A-GamblingonChoosingRegionals题意\(k\)场比赛,每场比赛每个大学至多\(c_i\)个队;总\(n\)个队伍,每队有分数与所属大学两个属性,每只队伍至多参加\(2\)场比赛。求各个队在最坏情况下的最优排名。思路最坏情况就是你打哪场,强队都去哪场,就选\(c_i\)小的场次,能让排名更靠......
  • Java项目实战II基于Java+Spring Boot+MySQL的大学生入学审核系统(文档+源码+数据库)
    目录一、前言二、技术介绍三、系统实现四、文档参考五、核心代码六、源码获取全栈码农以及毕业设计实战开发,CSDN平台Java领域新星创作者一、前言二、技术介绍语言:Java使用框架:SpringBoot前端技术:JS、Vue、css3开发工具:IDEA/Eclipse数据库:MySQL5.7/8.0数......
  • AtCoder Beginner Contest 372(4/7)
    比赛链接:https://atcoder.jp/contests/abc372开头:过去一个多月了,虽然暑假就上了蓝,但感觉自已一直还没达到蓝的水准,网络赛也打了两场,打的一般,开学之后一直比较忙,现在稳定了下来,接下来打算尽量每周3-4篇atcoder的题解吧,这是这周第一篇,虽然有点水(A.delete.思路:签......
  • SP1825 FTOUR2 - Free tour II 题解
    题目传送门前置知识点分治|树状数组解法维护点对信息,考虑点分治。本题比luoguP4149[IOI2011]Race多了个前缀查询\(\max\)。套个支持单点修改、区间查询\(\max\)的数据结构即可。直接线段树维护区间\(\max\)貌似会TLE,换成树状数组维护前缀\(\max\)即可。注......
  • The 2024 ICPC Asia East Continent Online Contest (II)
    Preface被徐神带飞咯,全程睡觉看队友卡卡过题,最变态的是K我上去乱写了个假做法就下机睡觉了,后面徐神反手就改了个正解出来这场主要是周五晚上无来由地发烧了,第二天比赛的时候头痛的一批,几乎没法集中精力想代码和写题但没想到这场最后打的还挺好,开局1h不到就把6个签过了,然......
  • The 2024 ICPC Asia East Continent Online Contest (I)
    Preface打的一坨,直接被Div.2学弟吊起来打这场主要是中期的Easy~mid写的太慢,导致中后期题没时间写同时封榜后的决策也有点问题,没有全队All-in一个题而是让徐神去写当时1/27的K,虽然可能徐神来想H我们也出不来但感觉还是跟榜适合我们队的level赛后发现H反着填右括......