最大数字——蓝桥杯十三届2022国赛大学B组真题

](https://img-blog.csdnimg.cn/direct/7822beb2066b439f90d50069d3c004b6.png)

问题分析

这道题属于贪心加回溯。所有操作如果能使得高位的数字变大必定优先用在高位,因为对高位的影响永远大于对低位的影响。然后我们再来分析一下,如何使用这两种操作?对于加操作,如果能使这一位的数字加到9则变成9,否则使这个数字尽量大。对于减操作,如果能使这一位的数字减到9则变成9,否则不采用减操作。然后我们用回溯来分别对该位进行加操作和减操作,记录最大值。时间复杂度大概是 O ( 2 l g n ) O(2^{lg^{n}}) O(2lgn),不超过 1 0 4 10^{4} 104的数量级。因此回溯是可行的。

AC_Code

#include <bits/stdc++.h>
using namespace std;
string result;
void dfs(string str,int i,int a,int b){if(i==str.size()||a==0&&b==0){if(result<str){result=str;}return;}char ch=str[i];if('9'-ch<=a){//能加到9 str[i]='9';dfs(str,i+1,a-('9'-ch),b);}else{//不能加到9 str[i]=ch+a;dfs(str,i+1,0,b);}if((ch-'0'+1)<=b){//能减到9 str[i]='9';dfs(str,i+1,a,b-(ch-'0'+1));}else{//不能减到9 str[i]=ch;dfs(str,i+1,a,b); }
}
int main() {string str;int a,b;cin>>str>>a>>b;dfs(str,0,a,b);cout<<result<<endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/325625.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用socat做端口转发

最近买的云上mongo数据库但是数据库不支持外网访问&#xff0c;准备做iptables转发但是一直不成功&#xff0c;腾讯云官方给予的解释是受服务器内启动的docker影响 做iptables转发会冲突&#xff0c;所以只能另想办法&#xff0c;我发现使用socat做转发也很好用&#xff0c;所以…

.net 6.0 框架集成ef实战,步骤详解

一、代码框架搭建 搭建如下代码架构&#xff1a; 重点含EntityFrameworkCore工程&#xff0c;该工程中包含AppDbContext.cs和数据表实体AggregateObject 1、AppDbContext 代码案例 //AppDbContext 代码案例using Microsoft.EntityFrameworkCore;namespace EntityFrameworkCo…

OGG几何内核-网格化的改进

OGG社区于4月19日发布了OGG 1.0 preview版本。相对于OCCT 7.7.0有很多改进&#xff0c;目前在持续研究中。最近测试了一下网格化&#xff0c;确实有很好的改进。对比展示如下&#xff1a; 几何内核&#xff1a; OGG 1.0 preview 几何内核&#xff1a;OCCT 7.7.0 采用OCCT几何内…

栈与队列的实现

前言 本次博客将要实现一下栈和队列&#xff0c;好吧 他们两个既可以使用动态数组也可以使用链表来实现 本次会有详细的讲解 栈的实现 栈的基础知识 什么是栈呢&#xff1f; 栈的性质是后进先出 来画个图来理解 当然可不可以出一个进一个呢&#xff0c;当然可以了 比如…

BGP基础

1.BGP概述 &#xff08;1&#xff09;AS IANA&#xff08;Internet Assigned Numbers Authority&#xff0c;因特网地址分配组织&#xff09;&#xff1a;IAB&#xff08;Internet Architecture Board&#xff0c;因特网体系委员会&#xff09;的下设组织。IANA授权NIC&#x…

Web前端一套全部清晰 ⑧ day5 CSS.3 选择器、PxCook软件、盒子模型

谁不是一路荆棘而过呢 —— 24.5.12 CSS.3 选择器、PxCook软件、盒子模型 一、选择器 1.结构伪类选择器 1.作用: 根据元素的结构关系查找元素。 选择器 说明 E:first-child 查找第一个 E元素 E:last-child 查找最后一个E元素 E:nth-chil…

系统权限控制插件封装-实现系统权限控制插件化

背景&#xff1a;按照传统的开发方式方式&#xff0c;每次新开发一个系统&#xff0c;就需要花费大量时间精力去搭建权限控制模块&#xff0c;如果我们把权限控制这一整个模块都抽离成一个独立的权限控制插件&#xff0c;支持单命令安装&#xff0c;全面暴露参数与方法&#xf…

OpenCV下载安装教程(Windows)

一、什么是OpenCV OpenCV&#xff08;Open Source Computer Vision Library&#xff09;是一个广泛使用的开源计算机视觉库&#xff0c;旨在提供丰富的图像和视频处理功能。它最初由Intel于1999年开发&#xff0c;并演变成为一个全球性的开源项目&#xff0c;得到了众多开发者…

K8s源码分析(二)-K8s调度队列介绍

本文首发在个人博客上&#xff0c;欢迎来踩&#xff01; 本次分析参考的K8s版本是 文章目录 调度队列简介调度队列源代码分析队列初始化QueuedPodInfo元素介绍ActiveQ源代码介绍UnschedulableQ源代码介绍**BackoffQ**源代码介绍队列弹出待调度的Pod队列增加新的待调度的Podpod调…

cmd输入mysql -u root -p无法启动

问题分析&#xff1a;cmd输入mysql -u root -p无法启动 解决方法&#xff1a;配置系统环境变量 1.找到mysql安装文件下的bin文件&#xff1a;&#xff08;复制改文件地址,如下图所示&#xff09; 2.电脑桌面下方直接搜索环境变量并进入&#xff0c;如下图 3.点击环境变量&a…

Python 中的 Lambda 函数:简单、快速、高效

大家好&#xff0c;今天再给大家介绍一个python的一个强大工具Lambda 函数&#xff0c;它允许你快速定义简单的匿名函数。这种函数是“匿名的”&#xff0c;因为它们不需要像常规函数那样被明确命名。 在本文中&#xff0c;我们将通过清晰的解释和实用的示例&#xff0c;深入了…

GoF之代理模式(静态代理+动态代理(JDK动态代理+CGLIB动态代理带有一步一步详细步骤))

1. GoF之代理模式&#xff08;静态代理动态代理(JDK动态代理CGLIB动态代理带有一步一步详细步骤)&#xff09; 文章目录 1. GoF之代理模式&#xff08;静态代理动态代理(JDK动态代理CGLIB动态代理带有一步一步详细步骤)&#xff09;每博一文案2. 代理模式的理解3. 静态代理4. 动…

打印图形(C语言)

一、N-S流程图&#xff1b; 二、运行结果&#xff1b; 三、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int i, j;//循环打印&#xff1b;for (i 0; i < 5; i){//列&#xff1b;for (j 0; j &…

网络端口占用问题的综合调研与解决方案

原创 Randy 拍码场 问题背景 去年底信息安全团队进行网络权限治理&#xff0c;要求所有应用实例使用静态IP&#xff0c;公网访问策略与静态IP绑定&#xff1b;之后实例重启时偶现“端口被占用”错误。通过分析总结应用日志&#xff0c;共有以下4种错误类型&#xff0c;实质都是…

1-02-02:虚拟化与容器化Docker环境搭建

1.02.02 虚拟化与容器化Docker环境搭建 一. 虚拟化与容器化技术简介1. 虚拟机环境2. docker环境 二. Docker 架构与隔离机制2.1 Docker 架构2.2 Docker 隔离机制2.3 资源限制2.4 Docker应用场景 三. 实战:Docker在Centos7安装与镜像加速 ❤❤❤3.1 docker安装3.2 设置镜像加速 …

AI回答总不满意?你的提问方式可能完全错误!

大家好&#xff0c;我是卷福同学&#xff0c;一个专注AI大模型整活的前阿里程序员&#xff0c;腾讯云社区2023新秀突破作者 向AI提问想写一篇论文&#xff0c;结果AI就生成2000字左右的文章后就完了。小伙伴们是不是也会遇到这类情况呢。今天来教大家AI提示词的技巧&#xff0c…

Kubernetes基础理论介绍

前言 随着企业数字化转型的深入&#xff0c;为云而生的云原生架构和思想已被大量企业所接受。容器云、微服务、DevOps、 Serverless 已成为企业落地云原生的关键技术&#xff0c;而 Kubernetes 作为容器云的核心基础和事实标准&#xff0c;已成为当今互联网企业和传统 IT 企业…

DHCP原理

什么是DHCP DHCP (Dynamic Host Configuration Protocol,动态主机配置协议&#xff09;是由Internet工作任务小组设计开发的&#xff0c;专门用于为TCP/IP网络中的计算机自动分配TCP/IP参数的协议&#xff0c;是一个应用层协议&#xff0c;使用UDP的67和68端口。 DHCP的前身是B…

发布GPT-5的方式可能会与以往不同;开源vocode使用 AI 自动拨打电话;开源gpt智能对话客服工具;AI自动写提示词

✨ 1: vocode 用AI通过声音与用户进行实时交流 Vocode是一个旨在帮助开发者快速构建基于声音的大型语言模型&#xff08;LLM&#xff09;应用程序的开源库。简单来说&#xff0c;如果你想要开发一个能够通过声音与用户进行实时交流的应用&#xff0c;比如电话机器人、语音助手…

一套MySQL读写分离分库分表的架构,被秀到了!

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 作者&#xff1a;IT邦德 中国DBA联盟(ACDU)成员&#xff0c;10余年DBA工作经验&#xff0c; Oracle、PostgreSQL ACE CSDN博客专家及B站知名UP主&#xff0c;全网粉丝10万 擅长主流Oracle、My…