当前位置: 首页 > news >正文

CF1995D Cases

CF1995D Cases

题意:

给定一个长为 \(n\),字符集大小 \(c=18\) 的字符串,给定一个整数 \(m\) ,你需要求出一个字符集合 \(S\) 满足在原串中每 \(m\) 个字符中至少有一个被包含在集合 \(S\) 中。

其中 \(m\le n\le 2^{18}=262144\)

思路:

最暴力的想法:\(dp_{i,S}\) 表示已钦定 \(S\) 内的点都选取,当前推到了字符串的第 \(i\) 位,是否可行。时间复杂度 \(O(n2^{18})\) 。进一步找性质发现对于一个位置 \(i\) ,只会往后转移 \(c\) 个位置,所以我们能否尝试根据这个性质 bitset 优化?显然无法操作,因为一是无法分割 bitset 成若干位置,二是 \(n\) 过大导致 bitset 时间复杂度无法接受。

更换思路,我们考虑什么样的 \(S\) 是一定无法成立的。可以发现,若连续 \(k\) 个字符所形成的字符集 \(T\) 满足 \(T\cap S=\empty\) ,一定无法成立。但是我们这样的 \(T\) 的数量 \(=n-k+1\) ,暴力判断仍然不行,因为这样的 \(S\) 之间没有相关性,即无法相互推导(考虑到两个不相等的集合 \(S_1,S_2\cap T=0\),他们形成的并集也一定与 \(T\) 的交集为空)。考虑优化。直接找到满足这种性质的 \(S\) 显然不好找,由于 \(T\cap S=\empty\) ,所以 \(T\cap \overline{S}=T\) ,并且对于任意字符 \(c\notin \overline{S} ,(\{c\}\cup\overline S)\cap T=T\),所以我们不妨尝试寻找这样的 \(\overline{S}\)

这是简单的,先标记所有的 \(dp_T=1\) ,然后按照上面的性质以此遍历所有的集合。

http://www.hskmm.com/?act=detail&tid=18317

相关文章:

  • 日志| 编辑距离 | 最长有效括号 |
  • day5
  • 《etcd库——键值存储系统》 - 教程
  • 有一个函数只会返回0和1,且返回0和返回1的概率不等。要求只能通过这个函数生成一个等概率返回0和1的函数
  • AI智能体开发实战:17种核心架构模式详解与Python代码实现
  • 代码随想录算法训练营第十天 | 232. 用栈实现队列、225. 用队列实现栈、20. 有效的括号、删除字符串中的所有相邻重复项
  • 2025.9.26总结 - A
  • MySQL性能优化
  • 关于“悬荡悟空”决策机制的简要技术说明
  • 最小二乘问题详解1:线性最小二乘
  • 9月26日
  • 工程监理行业多模态视觉​​​​​​​大模型系统,打造工地行业全场景的监理智能生态
  • 完整教程:【鸿蒙心迹】摸蓝图,打地基
  • 正则表达式
  • LuatOS Air780EPM 实现 HTTP 通信:从原理到代码实践
  • 搜维尔科技:Senseglove Nova 2触觉手套:虚拟训练、VR/AR模拟和研究中的触觉反馈
  • 深入解析:盟接之桥EDI软件:中国制造全球化进程中的连接挑战与路径探索
  • 【STM32H7】基于CubeMX从零开始搭建的HAL库工程模板(包含串口重定向和DSP库)
  • 在Windows架构中安装Miniforge及python环境变量配置
  • 搜维尔科技:Force Dimension Omega力反馈设备遥操作工业机器人
  • 3. Ollama 安装,流式输出,多模态,思考模型 - Rainbow
  • C++程序练习(部分未完全完成)
  • C#性能优化基础:垃圾回收机制
  • 实验报告1
  • 2025.9.26——1蓝
  • 根号
  • 【A】杂题选将
  • 有一个[1,5]的等概率随机函数fx(),在不改变fx()函数的情况下,利用fx()函数做出一个[1,7]的等概率随机函数。
  • WSL2 磁盘清理
  • 质因数分解