CF1383E 题解
2024-09-08 17:44:07
题意
给定一个长度为 \(n\) 的 01 串 \(a\)。在一次操作中,你可以选择任意一个 \(i\in[1,|a|)\),令 \(a_i=\max(a_i,a_{i+1})\),然后将 \(a_{i+1}\) 删除。你可以进行不超过 \(n-1\) 次操作,问一共能得到多少种 01 串,答案对 \(10^9+7\) 取模。
\(1\le n\le 10^6\)。
题解
若对操作的序列计数,此题难以处理。我们通过一些转换,对可以得到的串计数。
利用 \(1\) 将串划分,记录每段 \(0\) 的数量。如 \(001010011\) 就是 \(\{2,1,2,0,0\}\)。那么可行的操作就是将一个大于 \(0\) 的数减 \(1\),或删除一个不在头尾的 \(0\)。于是一个串与一个序列一一对应。下面我们对序列计数。
头尾不删,则可以扔掉,最后乘上系数 \((a_{1}+1)(a_n+1)\)。此时可知一个长为 \(m\) 的序列 \(b\) 可行的充要条件:存在 \(i_1<i_2<\dots<i_m\) 满足 \(\forall j\in[1,m],b_j\le a_{i_j}\)。用类似子序列自动机的方式判断。每次向后找到第一个大于等于 \(b_j\) 的位置并移动指针。
然后可以 \(\text{dp}\)。设 \(f_i\) 表示指针在 \(i\),每次枚举下一个放的数。则有 \(f_i=\sum\limits_{j<i}f_j+\max(0,a_i-\max\limits_{k=j+1}^{i-1}a_k)\)。单调栈可做到 \(O(n)\)。
最新文章
- Python for Informatics 第11章 正则表达式三(译)
- Cordova开发环境的搭建
- HAProxy安装及初步使用
- 【转】vim - tab变空格
- RCP学习笔记
- Java中到底有没有指针;同时注意引用和指针的区别
- Socket,非阻塞,fcntl
- 如何去除configure的默认选择-g O2
- 如何在VS2013中显示代码行号
- createNewFile()与createTempFile()的不同
- Java 架构师之路(1)
- Linux系统zookeeper环境搭建(单机、伪分布式、分布式)
- CF700E E. Cool Slogans
- python3 dict(字典)
- JSON格式字符串作为存储过程参数解析
- 元类实现ORM
- HDU 1003 Max Sum 求区间最大值 (尺取法)
- Lua游戏开发之时区问题
- Django Rest Framework源码剖析(六)-----序列化(serializers)
- 多线程学习笔记七之信号量Semaphore
热门文章
- if多条件判断
- 学会了selenium 模拟鼠标操作,你就可以偷懒点点点了
- Python实验报告(第7章)
- 对Asp.net WebApi中异步(async+await)接口实际使用及相关思考(示例给出了get,post,提交文件,异步接口等实践).
- .NET 6配置EF Core数据库链接字符串
- .Net开发的系统安装或更新时如何避免覆盖用户自定义的配置
- 数据结构与算法 ->; 大顶堆与小顶堆
- ElasticSearch必知必会-进阶篇
- ActiveMQ 常见集群模式
- Linux之ssh远程连接