当前位置: 首页 > 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;我们属于大三&…...

手把手教你用TI F28P65X开发板实现LED定时闪烁(基于CPU Timer2,含完整源码)

从零玩转TI F28P65X开发板&#xff1a;CPU Timer2实现可调频LED闪烁实战指南 刚拿到TI F28P65X开发板时&#xff0c;面对密密麻麻的引脚和复杂的开发环境&#xff0c;很多嵌入式新手会感到无从下手。本文将带你用最直观的方式&#xff0c;通过控制LED闪烁这个经典入门项目&…...

Unity 6升级后频繁闪退?别慌,这8个D3D11崩溃的修复方法亲测有效

Unity 6升级后D3D11崩溃全攻略&#xff1a;从快速修复到深度优化 刚升级到Unity 6的开发者们&#xff0c;是否正被突如其来的编辑器崩溃搞得焦头烂额&#xff1f;那些令人抓狂的"D3D11设备丢失"弹窗&#xff0c;不仅打断工作流&#xff0c;还可能让宝贵项目进度陷入停…...

只要一行代码,瞬间搭建 Web 服务器 python -m http.server 8000

只要一行代码,瞬间搭建 Web 服务器 python -m http.server 8000 目录 只要一行代码,瞬间搭建 Web 服务器 python -m http.server 8000 1. 核心机制:内置的 `http.server` 模块 2. 为什么它能“求生”,但不能“生产”? 🚀 并发处理能力 (Concurrency) 🛡️ 安全性 (Se…...

GTX1650也能跑!Windows11上OLLAMA+AnythingLLM本地部署Llama3保姆级教程

GTX1650也能跑&#xff01;Windows11上OLLAMAAnythingLLM本地部署Llama3保姆级教程 老旧硬件也能玩转大模型&#xff1f;当GTX1650这样的入门级显卡遇上Llama3这类前沿AI模型&#xff0c;很多人第一反应可能是"跑不动"。但经过实测&#xff0c;只要合理配置和优化&am…...

鸿蒙应用开发实战:手把手教你封装一个可复用的音乐播放器管理类(ArkTS版)

鸿蒙应用开发实战&#xff1a;构建高可复用的音乐播放器管理类&#xff08;ArkTS版&#xff09; 在鸿蒙应用开发中&#xff0c;音频播放功能是许多应用的核心需求。本文将深入探讨如何设计一个健壮、可复用的音乐播放器管理类&#xff0c;采用ArkTS语言实现&#xff0c;帮助开发…...

主体代码分析

一、整体架构分析这个程序是一个图片管理工具&#xff0c;采用MVC模式的变体&#xff0c;分为&#xff1a;UI层&#xff1a;界面定义&#xff08;ui_image_manager.py&#xff0c;由Qt Designer生成&#xff09;逻辑层&#xff1a;当前文件的业务逻辑业务层&#xff1a;busines…...

pybind11进阶指南:如何高效封装C++类供Python调用(附常见问题解决方案)

pybind11进阶指南&#xff1a;如何高效封装C类供Python调用&#xff08;附常见问题解决方案&#xff09; 在当今高性能计算和科学计算领域&#xff0c;C与Python的结合已成为开发者工具箱中不可或缺的组合。C提供底层性能优势&#xff0c;而Python则以其简洁语法和丰富生态著称…...

QuickSnap:Blender三维建模效率革命,快速对齐插件让精准建模变得简单

QuickSnap&#xff1a;Blender三维建模效率革命&#xff0c;快速对齐插件让精准建模变得简单 【免费下载链接】quicksnap Blender addon to quickly snap objects/vertices/points to object origins/vertices/points 项目地址: https://gitcode.com/gh_mirrors/qu/quicksnap…...

OpenClaw 深度研究报告:从开源框架到企业级智能体平台的演进之路

一、核心定位&#xff1a;突破"对话天花板"的执行中枢 OpenClaw&#xff08;外号"龙虾"&#xff09; 是由奥地利工程师 Peter Steinberger 于 2025 年底开发的本地优先、模型无关的 AI 智能体运行框架。其核心价值主张极为鲜明&#xff1a; “The AI that …...

Python MCP服务端框架源码剖析(2024最新LTS版内核解密)

第一章&#xff1a;Python MCP服务端框架源码剖析&#xff08;2024最新LTS版内核解密&#xff09;Python MCP&#xff08;Modular Control Protocol&#xff09;服务端框架2024 LTS版标志着其架构从单体调度向轻量级异步模块总线的重大演进。该版本基于 Python 3.11 构建&#…...