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

Codeforces Round 863 (Div. 3) E. Living Sequence

题目链接

头一回用不是正解的方法做出来,也是比较极限,直接说做法就是二分+数位dp
数位 d p dp dp 1 − n 1-n 1n出现多少含 4 4 4的数字个数 这纯纯板子了 \sout{这纯纯板子了} 这纯纯板子了
f ( x ) f(x) f(x) 1 − x 1-x 1x 中含有4的个数, f f f 关于 x x x 单调递增(并非严格) ,题目要找的其实是 x − f ( x ) = k x-f(x)=k xf(x)=k这样一个解,我们去二分 x x x,检查 x − f ( x ) x-f(x) xf(x) k k k 的大小关系
Specially ,我们需要注意 x − f ( x ) x-f(x) xf(x) 是一个一会儿单调递增,一会儿没有增量的一个函数,所以我们要找最小的符合上述方程的解

#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
i64 k;
int len,a[20];
i64 dp[20][2][2];i64 dfs(int pos,int limit,int flag){if(pos==len) return flag;if(dp[pos][limit][flag]!=-1) return dp[pos][limit][flag];int rg = limit?a[pos]:9;i64 ans = 0;for(int i = 0;i<=rg;++i){if(i==4) ans+=dfs(pos+1,limit&&i==rg,1);else ans+=dfs(pos+1,limit&&i==rg,flag);}return dp[pos][limit][flag] = ans;
}void solve(){cin>>k;i64 l = k,r = 2e18;while(l<=r){i64 mid= (l+r)>>1;len = 0;i64 tmp = mid;while(tmp){a[len++] = tmp%10;tmp/=10;}reverse(a,a+len);for(int i = 0;i<20;++i){for(int j = 0;j<2;++j){dp[i][j][0]=dp[i][j][1]=-1;}}i64 t = dfs(0,1,0);if(mid-t>=k) r = mid-1;else l = mid+1;}cout<<l<<"\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t;cin>>t;while(t--) solve();return 0;
}

相关文章:

Codeforces Round 863 (Div. 3) E. Living Sequence

题目链接 头一回用不是正解的方法做出来&#xff0c;也是比较极限&#xff0c;直接说做法就是二分数位dp 数位 d p dp dp 求 1 − n 1-n 1−n出现多少含 4 4 4的数字个数 这纯纯板子了 \sout{这纯纯板子了} 这纯纯板子了 设 f ( x ) f(x) f(x) 为 1 − x 1-x 1−x 中含有4的…...

一文讲解HashMap线程安全相关问题(上)

HashMap不是线程安全的&#xff0c;主要有以下几个问题&#xff1a; ①、多线程下扩容会死循环。JDK1.7 中的 HashMap 使用的是头插法插入元素&#xff0c;在多线程的环境下&#xff0c;扩容的时候就有可能导致出现环形链表&#xff0c;造成死循环。 JDK 8 时已经修复了这个问…...

MFC 创建Ribbon样式窗口

然后点击下一步直到完成即可...

uv 安装包

是的&#xff0c;你可以使用 uv 来安装 Python 包。uv 是一个高性能的 Python 包安装器和解析器&#xff0c;由 astral.sh 团队开发&#xff0c;旨在替代 pip 和 pip-tools&#xff0c;提供更快的包安装体验。 ### 如何使用 uv 安装包 1. **安装 uv**&#xff1a; 如果你还…...

IELTS口语练习题库

IELTS口语1-4月题库 Part 1 Gifts Have you ever sent handmade gifts to others? Yes, I have. I once made a scrapbook for my best friend’s birthday. It included photos of our memories together and some handwritten notes. She loved it because it was personal…...

图书管理系统 Axios 源码__获取图书列表

目录 核心功能 源码介绍 1. 获取图书列表 技术要点 适用人群 本项目是一个基于 HTML Bootstrap JavaScript Axios 开发的图书管理系统&#xff0c;可用于 添加、编辑、删除和管理图书信息&#xff0c;适合前端开发者学习 前端交互设计、Axios 数据请求 以及 Bootstrap 样…...

基于OSAL的嵌入式裸机事件驱动框架——整体架构调度机制

参考B站up主【架构分析】嵌入式祼机事件驱动框架 感谢大佬分享 任务ID &#xff1a; TASK_XXX TASK_XXX 在系统中每个任务的ID是唯一的&#xff0c;范围是 0 to 0xFFFE&#xff0c;0xFFFF保留为SYS_TSK_INIT。 同时任务ID的大小也充当任务调度的优先级&#xff0c;ID越大&#…...

c++ string类 +底层模拟实现

提醒: 本片博客只是小编的听课笔记&#xff0c;介意勿看。 基础 包含在头文件<string>&#xff0c;才能使用string类似函数接口。 string常见构造类 string s1; cin>>s1;//无参构造 string s2(s1);//拷贝构造 string s1("jfksa");//传参构造 三种…...

六十分之三十七——一转眼、时光飞逝

一、目标 明确可落地&#xff0c;对于自身执行完成需要一定的努力才可以完成的 1.第三版分组、激励、立体化权限、智能设备、AIPPT做课 2.8本书 3.得到&#xff1a;头条、吴军来信2、卓克科技参考3 4.总结思考 二、计划 科学规律的&#xff0c;要结合番茄工作法、快速阅读、…...

Shell基础:中括号的使用

在Shell脚本中&#xff0c;中括号&#xff08;[ ... ] 和 [[ ... ]]&#xff09;是一种常见的条件测试结构。它们用于进行文件类型检查、值比较以及逻辑判断。通过了解它们的不同特点和用法&#xff0c;能够帮助你编写更加高效、安全且易读的脚本。本文将详细介绍Shell中单中括…...

《基于Scapy的综合性网络扫描与通信工具集解析》

在网络管理和安全评估中&#xff0c;网络扫描和通信是两个至关重要的环节。Python 的 Scapy 库因其强大的网络数据包处理能力&#xff0c;成为开发和实现这些功能的理想工具。本文将介绍一个基于 Scapy 编写的 Python 脚本&#xff0c;该脚本集成了 ARP 扫描、端口扫描以及 TCP…...

面经--C语言——sizeof和strlen,数组和链表,#include <>和 #include ““ #define 和typedef 内存对齐概述

文章目录 sizeof 和 strlen数组和链表总结 #include <>和 #include ""#define 和typedef内存对齐概述对齐规则示例&#xff1a;结构体的内存对齐分析&#xff1a; 内存对齐的常见规则&#xff1a;填充字节的计算对齐影响的实际例子 sizeof 和 strlen 特性size…...

使用 Kotlin 将 Vertx 和 Springboot 整合

本篇文章目的是将 Springboot 和 Vertx 进行简单整合。整合目的仅仅是为了整活&#xff0c;因为两个不同的东西整合在一起提升的性能并没有只使用 Vertx 性能高&#xff0c;因此追求高性能的话这是在我来说不推荐。而且他们不仅没有提高很多性能甚至增加了学习成本 一、整合流…...

线性回归算法-01

线性回归简介 学习目标 了解线性回归的应用场景知道线性回归的定义 1 线性回归应用场景 房价预测销售额度预测贷款额度预测 2 什么是线性回归 2.1 定义与公式 线性回归(Linear regression)是利用 回归方程(函数)对 一个或多个自变量(特征值)和因变量(目标值)之间关系进行建模…...

洛谷 P1130 红牌 C语言

题目描述 某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂&#xff0c;一共包括 N 个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程&#xff0c;每一步政府都派了 M 个工作人员来检查材料。不幸的是&…...

虚幻UE5手机安卓Android Studio开发设置2025

一、下载Android Studio历史版本 步骤1&#xff1a;虚幻4.27、5.0、5.1、5.2官方要求Andrd Studio 4.0版本&#xff1b; 5.3、5.4、5.5官方要求的版本为Android Studio Flamingo | 2022.2.1 Patch 2 May 24, 2023 虚幻官网查看对应Andrd Studiob下载版本&#xff1a; https:/…...

线性代数复习笔记

1. 课程学习 1.1 3Blue1Brown 线性代数 2. 基本术语 eigenvector&#xff08;特征向量&#xff09;&#xff1a;线性变换中方向保持不变的向量 可以视作3D旋转矩阵形成的旋转的轴...

你需要更深层次的解放

先谈一谈理性认知中的属性替换原则。简单来说&#xff0c;属性替换就是用简单的问题取代难题。 当人们需要评估属性A时&#xff0c;却发现评估属性B更容易一些&#xff08;A与B之间存在一定的关系&#xff09;&#xff0c;于是就改为评估属性B。这叫做属性替换。 作为一种认知…...

机器学习算法在网络安全中的实践

机器学习算法在网络安全中的实践 本文将深入探讨机器学习算法在网络安全领域的应用实践&#xff0c;包括基本概念、常见算法及其应用案例&#xff0c;从而帮助程序员更好地理解和应用这一领域的技术。"> 序言 网络安全一直是信息技术领域的重要议题&#xff0c;随着互联…...

Qt事件处理:理解处理器、过滤器与事件系统

1. 事件 事件 是一个描述应用程序中、发生的某些事情的对象。 在 Qt 中&#xff0c;所有事件都继承自 QEvent &#xff0c;并且每个事件都有特定的标识符&#xff0c;如&#xff1a;Qt::MouseButtonPress 代表鼠标按下事件。 每个事件对象包含该事件的所有相关信息&#xff…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...