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

Codeforces Round 961 D. Cases 【SOS DP、思维】

D. Cases

1
2

题意

有一个长度为 n n n 且仅由前 c c c 个大写字母组成的字符串,问最少选取多少种字母为每个单词的结尾,使得每个单词长度不超过 k k k

思路

首先注意到最后一个字母一定要选择,接下来我们给出一个断言:如果一个字母被选上了,那么对于这个字母在字符串中所有出现的位置,用这些位置作为结尾是最优的
这是因为如果最优的答案存在一个单词横跨了所选的这个字母,因为这个单词长度本身小于等于 k k k,所以我们把他划分成两段,一段以所选的字母结尾,另一段以原先单词自己的字母结尾,这样子并不会使得答案更劣,所以我们一旦选择了某个字母,一定是选择其在字符串中出现的所有位置

进一步观察发现:对于每 k k k连续的字符,我们一定至少选择 1 1 1 个字母作为结尾
简化一下单词长度不超过 k k k 的这个条件,我们如果对于每一个长度恰好为 k k k 的一个窗口,把这个窗口里所有出现的字母记录一下,形成一个 m a s k mask mask,那么对于所有的 O ( n ) O(n) O(n) m a s k mask mask,我们等价于要满足每个 m a s k mask mask 都至少有 1 1 1 位被选作最终的答案集合

至此,问题便转化为了:对于 O ( n ) O(n) O(n) m a s k mask mask,我们要选择一个含 1 1 1 数量最少的,且与每个 m a s k mask mask 有交,且 a n s ans ans 必须包含最后一个字母

直接枚举 a n s ans ans 并与 O ( n ) O(n) O(n) m a s k mask mask 求交太慢,我们可以先把全部不合法的 a n s ans ans 筛出来,再从剩下的所有合法的 a n s ans ans 中选一个最少的即可

接下来我们将 O ( n ) O(n) O(n) m a s k mask mask 放入数组 a a a 中,注意到一个答案 b b b 如果不合法,那么一定有 b & a i = 0 b \; \& \; a_i = 0 b&ai=0,即一定存在至少一个 m a s k mask mask,使得 b b b 与其没有任何的交集,那么这个 b b b 不合法
剩下的一定是合法的。
注意到: a & b = 0 ⇔ b ⊂ a ˜ ( a 的补集 ) a \; \& b \; = 0 \Lrarr b \subset \~a (a 的补集) a&b=0ba˜(a的补集),即 b b b a a a 的补集的子集
现在我们有了 O ( n ) O(n) O(n) 个母集 a i a_i ai,我们需要筛出其所有的子集 b ⊂ a i b \subset a_i bai,这个过程我们可以使用 S O S D P SOS \; DP SOSDP

时间复杂度: O ( c n + c 2 c ) O(cn + c2^c) O(cn+c2c)

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;std::cin >> t;while(t--){int n, c, k;std::cin >> n >> c >> k;std::string s;std::cin >> s;s = '0' + s;std::vector<std::vector<int>> sum(n + 1, std::vector<int>(26, 0));std::vector<int> a;fore(i, 1, n + 1){int ch = s[i] - 'A';fore(j, 0, c) sum[i][j] = sum[i - 1][j];++sum[i][ch];if(i >= k){int mask = 0;fore(j, 0, c)if(sum[i][j] - sum[i - k][j])mask |= 1 << j;a.push_back(mask);}}for(int& mask : a) mask = (~mask & ((1 << c) - 1));std::vector<int> dp(1 << c, 1);for(auto mask : a) dp[mask] = 0;fore(i, 0, c)fore(mask, 0, 1 << c)if(!(mask >> i & 1))dp[mask] &= dp[mask ^ (1 << i)];int last = s.back() - 'A';int ans = c;fore(mask, 0, 1 << c)if(dp[mask] && (mask >> last & 1))ans = std::min(ans, __builtin_popcount(mask));std::cout << ans << endl;}return 0;
}

相关文章:

Codeforces Round 961 D. Cases 【SOS DP、思维】

D. Cases 题意 有一个长度为 n n n 且仅由前 c c c 个大写字母组成的字符串&#xff0c;问最少选取多少种字母为每个单词的结尾&#xff0c;使得每个单词长度不超过 k k k 思路 首先注意到最后一个字母一定要选择&#xff0c;接下来我们给出一个断言&#xff1a;如果一个…...

VirtualBox上的Oracle Linux虚拟机安装Docker全流程

1.安装docker依赖 yum install -y yum-utils device-mapper-persistent-data lvm2 2.安装docker仓库 yum-config-manager --add-repo https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo 生成docker的yum源配置到在 /etc/yum.repos.d/docker-ce.repo 3.安装D…...

LNMP安装部署

目录 一、Nginx安装部署 1.安装包下载 2.下载相关依赖工具 3. 创建运行用户 4.编译安装 5.优化路径 6.将nginx添加至系统服务 7.文件赋权 二、MySQL部署安装 1.解压 2.安装相关工具 3.创建运行用户 4.编译安装 5.修改配置文件 6.更改mysql安装目录和配置文件的属…...

django之自定义序列化器用法

在Django中&#xff0c;自定义序列化器方法通常用于处理复杂的数据转换逻辑&#xff0c;特别是在使用Django REST framework&#xff08;DRF&#xff09;时。自定义序列化器方法可以帮助你在序列化和反序列化过程中执行特定的逻辑&#xff0c;比如格式化日期、计算字段值、或者…...

20240821给飞凌OK3588-C的核心板刷Rockchip原厂的Buildroot并挂载1TB的exFAT格式的TF卡

fdisk -l df -h df -t df -T mount 20240821给飞凌OK3588-C的核心板刷Rockchip原厂的Buildroot并挂载1TB的exFAT格式的TF卡 2024/8/21 18:06 【切记&#xff0c;对于Rockchip原厂的Buildroot&#xff0c;如果你没有针对性的适配DTS&#xff1a;修改其中的GPIO口供电&#xff0c…...

多模态学习Multimodal Learning:人工智能中的多模态原理与技术介绍初步了解

多模态学习&#xff08;Multimodal Learning&#xff09;是机器学习中的一个前沿领域&#xff0c;旨在综合处理和理解来自不同模态的数据。模态可以包括文本、图像、音频、视频等。随着数据多样性和复杂性增加&#xff0c;多模态学习在自然语言处理、计算机视觉、语音识别等领域…...

外部环境连接kafka

修改配置文件外部环境连接kafka 1、kafka的docker官方镜像地址2、kafka官方介绍的三种连接方式3、方式一&#xff1a;Default configs默认配置4、方式二&#xff1a;File input&#xff08;文件输入&#xff1a;外部配置文件替换docker容器内的配置文件&#xff09;4.1、首先查…...

结合了MySQL数据库、Elasticsearch和Redis,构建一个产品搜索和推荐系统

1. 数据库设置&#xff08;MySQL&#xff09; 首先&#xff0c;我们需要创建两个表来存储产品信息和产品类别信息。 CREATE DATABASE product_system;USE product_system;CREATE TABLE categories (id INT AUTO_INCREMENT PRIMARY KEY,name VARCHAR(255) NOT NULL,created_at…...

白酒与素食:健康与美味的双重享受

在美食的世界里&#xff0c;白酒与素食的搭配仿佛是一场跨界的盛宴。豪迈白酒&#xff08;HOMANLISM&#xff09;的醇香与精致素食的清新&#xff0c;在不经意间交织出了一幅美妙的画卷&#xff0c;让人在品味中感受到健康与美味的双重享受。 素食&#xff0c;以其清淡、自然的…...

工厂现场多功能帮手,三防平板改善管理体验

随着制造业的智能化变革&#xff0c;信息化、自动化和智能化逐渐成为工厂管理的新常态。在这一波技术浪潮中&#xff0c;三防平板作为一种多功能的工作工具&#xff0c;正在逐步改善工厂现场的管理体验。 一、三防平板的定义与特点 三防平板&#xff0c;顾名思义&#xff0c;是…...

【git】问题解决---Failed to connect to github.com

场景 最近运行命令git push,git pull或者git clone的时候总会报如下错误 fatal: unable to access https://github.com/xxxxx/xxxxxx.git/: **Failed to connect to github.com** port 443 after 21052 ms: Couldnt connect to server原因 一般是网络配置原因造成的, 如果能…...

Java 中 String 类型的特点

在 Java 中&#xff0c;String 是一种常用且重要的数据类型&#xff0c;用于表示和处理字符序列。它有一些独特的特性和用法&#xff0c;使得它在开发中非常灵活和高效。以下是关于 String 类型的一些特点、特殊性、使用技巧以及注意事项。 1. String 的特点 1.1 不可变性 定…...

AddressUtils 、RegionUtils IP地址工具类

一、类展示 AddressUtils &#xff1a; /*** 获取地址类**/ Slf4j NoArgsConstructor(access AccessLevel.PRIVATE) public class AddressUtils {// 未知地址public static final String UNKNOWN "XX XX";public static String getRealAddressByIP(String ip) {i…...

牛客网SQL进阶134: 满足条件的用户的试卷总完成次数和题目总练习次数

满足条件的用户的试卷完成数和题目练习数_牛客题霸_牛客网 0 问题描述 基于用户信息表user_info、试卷信息表examination_info、试卷作答记录表exam_record、题目练习记录表practice_record&#xff0c;筛选出 高难度SQL试卷得分平均值大于80并且是7级的用户&#xff0c;统计他…...

机器学习:逻辑回归处理手写数字的识别

1、获取数据, 图像分割该数据有50行100列&#xff0c;每个数字占据20*20个像素点&#xff0c;可以进行切分,划分出训练集和测试集。 import numpy as np import pandas as pd import cv2 imgcv2.imread("digits.png")#读取文件 graycv2.cvtColor(img,cv2.COLOR_BGR2G…...

文件上传真hard

一、SpringMVC实现文件上传 1.1.项目结构 1.1.2 控制器方法 RequestMapping("/upload1.do")public ModelAndView upload1(RequestParam("file1") MultipartFile f1) throws IOException {//获取文件名称String originalFilename f1.getOriginalFilename(…...

精益管理|介绍一本专门研究防错法(Poka-Yoke)的书

在现代制造业中&#xff0c;如何确保产品在每个生产环节中不出现错误是企业追求的目标之一。而实现这一目标的关键技术之一就是防错法&#xff08;Poka-Yoke&#xff09;。作为一种简单而有效的精益管理、六西格玛管理工具&#xff0c;防错法帮助企业避免因人为错误或工艺不当导…...

面试题目:(4)给表达式添加运算符

目录 题目 代码 思路解析 例子 题目 题目 给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target &#xff0c;在 num 的数字之间添加 二元 运算符&#xff08;不是一元&#xff09;、- 或 * &#xff0c;返回 所有能够得到 target 的表达式。1 < num.length &…...

[C#]将opencvsharp的Mat对象转成onnxruntime的inputtensor的3种方法

第一种方法&#xff1a;在创建tensor时候直接赋值改变每个tensor的值&#xff0c;以下是伪代码&#xff1a; var image new Mat(image_path);inpWidth image.Width;inpHeight image.Height;//将图片转为RGB通道Mat image_rgb new Mat();Cv2.CvtColor(image, image_rgb, Col…...

CTF入门教程(非常详细)从零基础入门到竞赛,看这一篇就够了!

一、CTF简介 CTF&#xff08;Capture The Flag&#xff09;中文一般译作夺旗赛&#xff0c;在网络安全领域中指的是网络安全技术人员之间进行技术竞技的一种比赛形式。CTF起源于1996年DEFCON全球黑客大会&#xff0c;以代替之前黑客们通过互相发起真实攻击进行技术比拼的方式。…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...