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

C++笔试强训day36

目录

1.提取不重复的整数

2.【模板】哈夫曼编码

3.abb


1.提取不重复的整数

链接icon-default.png?t=N7T8https://www.nowcoder.com/practice/253986e66d114d378ae8de2e6c4577c1?tpId=37&tqId=21232&ru=/exam/oj

按照题意模拟就行,记得从右往左遍历

#include <iostream>
using namespace std;int a[10];
int main() {string s;cin >> s;for (int i = s.size() - 1; i >= 0; --i)if (a[s[i] - '0']++ == 0)cout << s[i] - '0';cout << endl;return 0;
}

2.【模板】哈夫曼编码

链接icon-default.png?t=N7T8https://www.nowcoder.com/practice/4c0419eb07c840ca8402e4f2a52cfd49?tpId=308&tqId=40489&ru=/exam/oj

做这题前首先需要去了解哈夫曼编码。

因为题中已经给出了每个字符的频次,因此可以直接用优先队列(堆)解决,但别忘了用小根堆。

3.abb

链接icon-default.png?t=N7T8https://www.nowcoder.com/practice/0a8bbf8b9b5b4280957849ef4f240f07?tpId=230&tqId=38957&ru=/exam/oj

一道动态规划题,同样是去找出它的状态表示:

dp[x] : 以 x 元素结尾的所有子序列中,_xx的个数

要想拿到dp[x],则需要找到以 x 元素结尾的所有子序列中,_x的个数。

将其(以 x 元素结尾的所有子序列中,_x的个数)定义为 f[x] ,要想拿到 f[x] ,则需要找到区间[0, i - 1]中非 x 的个数,(这里我们转化为 x 的个数,最后用 i {区间总数} 减去 x 个数即可),(定义为g[x])

然后就是状态转移方程:

dp[x] = f[x], (因为这时候遍历到的数就是 x, _x 加上x即为_xx)

f[x] = f[x] + (i - g[x])

g[x] = g[x] + 1

注意状态转移方程顺序,要先更新 f[x] 后才能更新 g[x]。

最后是返回值:

返回的是所有字母为结尾的个数的和。即所有的dp[x]。因为dp[x] = f[x]。

所以可以不需要dp[x]。

#include <iostream>
#define int long long
using namespace std;int f[26];
int g[26];
char s[100010];
int n;signed main() {cin >> n;for(int i = 0; i < n; ++i)cin >> s[i];int ret = 0;for(int i = 0; i < n; ++i){int x = s[i] - 'a';        ret += f[x];f[x] = f[x] + i - g[x];g[x] = g[x] + 1;}cout << ret << endl;return 0;
}

相关文章:

C++笔试强训day36

目录 1.提取不重复的整数 2.【模板】哈夫曼编码 3.abb 1.提取不重复的整数 链接https://www.nowcoder.com/practice/253986e66d114d378ae8de2e6c4577c1?tpId37&tqId21232&ru/exam/oj 按照题意模拟就行&#xff0c;记得从右往左遍历 #include <iostream> usi…...

网络通信过程的技术分析

网络通信过程的技术分析 目录 网络通信过程的技术分析 一、引言 二、网络通信基础 三、通信协议 四、数据传输过程 五、网络设备与通信 六、网络安全与通信 七、高级网络通信概念 八、结论 一、引言 网络通信是现代计算机网络中的核心活动&#xff0c;它涉及多个层面的…...

一篇文章搞懂二叉树

文章目录 DP 树叶的度树的度节点的层次节点的祖先节点的子孙双亲节点或父节点 树的表示孩子兄弟表示法双亲表示法树和非树树的应用 二叉树满二叉树完全二叉树推论二叉树的存储以数组的方式以链表的方式堆(Heap)堆的分类大根堆和小根堆的作用 二叉树的遍历DFS和BFS DP 动态规划…...

python——__future__模块

__future__模块是Python的一个特殊内建模块&#xff0c;它提供了一种方式来让程序员在当前版本的Python中使用未来版本的语言特性&#xff0c;从而帮助代码实现向前兼容。这意味着&#xff0c;即使你正在使用的是旧版本的Python&#xff0c;也可以通过导入__future__模块中的某…...

开源一个工厂常用的LIMS系统

Senaite是一款强大且可靠的基于Web的LIMS/LIS系统&#xff0c;采用Python编写&#xff0c;构建在Plone CMS基础架构之上。该系统处于积极开发阶段&#xff0c;在灵活的定制空间中为开发人员提供了丰富的功能。其中&#xff0c;Senaite在处理REST的JSON API上做得出色&#xff0…...

SpringBoot项目中redis序列化和反序列化LocalDateTime失败

实体类中包含了LocalDateTime 类型的属性&#xff0c;把实体类数据存入Redis后变成这样&#xff1a; 此时&#xff0c;存入redis不会报错&#xff0c;但是从redis获取的时候&#xff0c;会报错&#xff1a; com.fasterxml.jackson.databind.exc.InvalidDefinitionException: Ca…...

linux怎么查询远程管理卡型号

在Linux中&#xff0c;要查询远程管理卡&#xff08;通常是服务器主板上的集成芯片&#xff0c;如iDRAC、iLO、BMC等&#xff09;的型号&#xff0c;可以使用一些特定厂商的工具&#xff0c;或者通过IPMI&#xff08;Intelligent Platform Management Interface&#xff09;来实…...

西储大学数据集学习

数据集下载地址&#xff1a;CWRU凯斯西储大学轴承数据数据集——附&#xff1a;下载链接_西储大学轴承数据集下载-CSDN博客 最近研究故障诊断&#xff0c;先对使用比较多的西储大学数据集研究。以资料【1】中的内容展开研究。 1、轴承的结构 轴承分为外圈、内圈、保持架和滚珠…...

《web应用技术》第九次作业

一、将前面的代码继续完善功能 1.采用XML映射文件的形式来映射sql语句&#xff1b; <?xml version"1.0" encoding"UTF-8" ?> <!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" "http://mybatis.org/dtd/mybatis…...

dockerfile关键字

参考&#xff1a;59_Dockerfile保留字简介_哔哩哔哩_bilibili FROM 作用&#xff1a;指定基础镜像&#xff0c;即在这个基础镜像上构建新镜像&#xff0c;如下所示&#xff0c;表示在ubuntu20.04镜像的基础上构建新镜像 FROM ubuntu:20.04 MAINTAINER 作用&#xff1a;镜像…...

MATLAB分类与判别模型算法: 快速近邻法(FastNN)分类程序【含Matlab源码 MX_005期】

算法思路介绍&#xff1a; 1. 数据准备阶段&#xff1a; 生成一个合成数据集 X&#xff0c;其中包含三个簇&#xff0c;每个簇分布在不同的区域。 定义聚类层数 L 和每个层次的子集数量 l。 2. 聚类阶段&#xff1a; 使用K均值聚类算法将初始数据集 X 分成 l 个簇。…...

css卡片翻转 父元素翻转子元素不翻转效果

css卡片翻转 父元素翻转子元素不翻转效果 vue <div class"moduleBox"><div class"headTitle"><span class"headName">大额案例</span></div><div class"moduleItem"><span class"module…...

解决文件传输难题:如何绕过Gitee的100MB上传限制

引言 在版本控制和代码托管领域&#xff0c;Gitee作为一个流行的平台&#xff0c;为用户提供了便捷的服务。然而&#xff0c;其对单个文件大小设定的100MB限制有时会造成一些不便。 使用云存储服务 推荐理由&#xff1a; 便捷性&#xff1a;多数云存储服务如&#xff1a; Dro…...

零基础学Java第二十三天之网络编程Ⅱ

1. InetAddress类 用来表示主机的信息 练习&#xff1a; C:\Windows\system32\drivers\etc\ hosts 一个主机可以放多个个人网站 www.baidu.com/14.215.177.37 www.baidu.com/14.215.177.38 www.taobao.com/183.61.241.252 www.taobao.com/121.14.89.253 2. Socket 3.…...

【HarmonyOS尝鲜课】- 前言

面向人群 本课程适用于HarmonyOS应用开发的初学者。 有无经验的开发者都可以轻松掌握ArkTS语言声明式开发范式&#xff0c;体验更简洁、更友好的HarmonyOS应用开发旅程。 什么是HarmonyOS HarmonyOS&#xff08;鸿蒙操作系统&#xff09;是由华为技术有限公司开发的全场景分…...

phpstudy配置网站伪静态

apache的伪静态写法&#xff1a; RewriteEngine On RewriteCond % {REQUEST_FILENAME} !-f RewriteCond % (REQUEST_FILENAME) !-d RewriteRule ^(.*)$ indexp?/$1 [QSA, PT,L] nginx写法&#xff1a; location / { index index.html index.php; #autoindex on; if(!…...

浅谈traceroute网络诊断工具

traceroute 是一个网络诊断工具&#xff0c;用于跟踪和显示数据包从源主机到目标主机所经过的每一跳&#xff08;路由器&#xff09;的路径。它能够帮助用户识别网络路径中的瓶颈和故障点。traceroute 的工作原理主要基于 ICMP&#xff08;Internet Control Message Protocol&a…...

Java数据结构与算法(红黑树)

前言 红黑树是一种自平衡二叉搜索树&#xff0c;确保在插入和删除操作后&#xff0c;树的高度保持平衡&#xff0c;从而保证基本操作&#xff08;插入、删除、查找&#xff09;的时间复杂度为O(log n)。 实现原理 红黑树具有以下性质&#xff1a; 每个节点要么是红色&#…...

SpringBoot RPM制作

安装依赖 [root20240423-instance4 ~]# yum install rpmdevtools2.初始化目录 [root20240423-instance4 ~]# rpmdev-setuptree [root20240423-instance4 ~]# tree rpmbuild/ rpmbuild/ ├── BUILD ├── RPMS ├── SOURCES ├── SPECS └── SRPMS5 directories, 0 …...

专转本上岸别太老实做这三件事

如果你专转本上岸&#xff0c;千万不要当老实人去做这三件事&#xff0c;真的没有必要&#xff0c;不但浪费时间&#xff0c;还会让你提前进入对未来的迷茫期。建议转本人们一定要知道&#xff0c;首先就是不要过度关注学分。因为转本上岸只有两年&#xff0c;我们属于大三&…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

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

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

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...