P1028 [NOIP2001 普及组] 数的计算
时刻记住一句话:写递归,1画图,2大脑放空!!!
意思是,自己写递归题目,先用样例给的数据画图,然后想一个超级简单的思路,直接套上去就可以了。
上题干:
题目描述
给出正整数 n,要求按如下方式构造数列:
- 只有一个数字 n 的数列是一个合法的数列。
- 在一个合法的数列的末尾加入一个正整数,但是这个正整数不能超过该数列最后一项的一半,可以得到一个新的合法数列。
请你求出,一共有多少个合法的数列。
输入格式
输入只有一行一个整数,表示 n。
输出格式
输出一行一个整数,表示合法的数列个数。
输入输出样例
输入 #1复制
6输出 #1复制
6说明/提示
样例 1 解释
满足条件的数列为:
- 6
- 6,1
- 6,2
- 6,3
- 6,2,1
- 6,3,1
数据规模与约定
对于全部的测试点,保证 1≤n≤10^3。
说明
本题数据来源是 NOIP 2001 普及组第一题,但是原题的题面描述和数据不符,故对题面进行了修改,使之符合数据。原题面如下,谨供参考:
我们要求找出具有下列性质数的个数(包含输入的正整数 n)。
先输入一个正整数 n(n≤1000),然后对此正整数按照如下方法进行处理:
- 不作任何处理;
- 在它的左边拼接一个正整数,但该正整数不能超过原数,或者是上一个被拼接的数的一半;
- 加上数后,继续按此规则进行处理,直到不能再加正整数为止。
这道题,不要想那么复杂。
题目给的数字是6,并且帮我们分析了答案如何来的:
- 6
- 6,1
- 6,2
- 6,3
- 6,2,1
- 6,3,1
第一步:画图
我们可以画出一个简易的树状图:

第二步:大脑放空,想一个最简单的思路
从i=0开始枚举,一直枚举到 6/2,
用 f【i】表示,6后面直接跟的数字是 i 的种数。(如果i=0,就代表,没有跟任何数字)
所以答案就是 f【0】+ f【1】 +f【2】+f【3】
结束
写出代码:
const int N = 1e3 + 7;
int lxnb(int x) {int ans = 0;if (x == 1 or x == 0)return 1;for (int i = 0; i <= x / 2; i++) {ans += lxnb(i);}return ans;
}int main() {int n;cin >> n;cout << lxnb(n);
}
然后,这样的普通递归,无法,完成本题。
所以我们可以用到记忆化的方法,用一个数组记录f【i】的值,如果f【i】已经被记录了 ,那么我们就直接返回,它的值。
无脑塞进去就行了,哪里需要管这么多。。。。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
using namespace std;
const int N = 1e3 + 7;
int flag[N];
int lxnb(int x) {int ans = 0;if (flag[x])return flag[x];if (x == 1 or x == 0)return 1;for (int i = 0; i <= x / 2; i++) {ans += lxnb(i);}return flag[x]=ans;
}int main() {int n;cin >> n;cout << lxnb(n);
}
相关文章:
P1028 [NOIP2001 普及组] 数的计算
时刻记住一句话:写递归,1画图,2大脑放空!!! 意思是,自己写递归题目,先用样例给的数据画图,然后想一个超级简单的思路,直接套上去就可以了。 上题干ÿ…...
浅析三相异步电动机控制的电气保护
安科瑞 华楠 摘 要:要求三相异步电动机的控制系统不仅要保证电机正常启动和运行,完成制动操作,还要通过相关保护措施维护电动机的安全使用。基于此,本文以电动机电气保护作为研究对象,结合三相异步电动机的机械特点&…...
Java设计模式系列:单例设计模式
Java设计模式系列:单例设计模式 介绍 所谓类的单例设计模式,就是采取一定的方法保证在整个的软件系统中,对某个类只能存在一个对象实例,并且该类只提供一个取得其对象实例的方法(静态方法) 比如 Hiberna…...
开拓新天地:探讨数位行销对医药产业医病连结的影响
数字营销模式多元,主要围绕医生和患者。赛道各企业凭借各自优势(技术、学术、流量等)入局,提供各自差异化营销工具或服务。目前,围绕医生的数字营销旨在为医生提供全面学术解决方案从而提升对医药产品的认可࿰…...
[tsai.shen@mailfence.com].faust勒索病毒数据怎么处理|数据解密恢复
导言: [support2022cock.li].faust、[tsai.shenmailfence.com].faust、[Encrypteddmailfence.com].faust勒索病毒是一种具有恶意目的的勒索软件,其主要特点包括对受害者文件进行强力加密,然后勒索受害者支付赎金以获取解密密钥。攻击者通常通…...
Peter算法小课堂—前缀和数组的应用
桶 相当于计数排序,看一个视频 桶排序 太戈编程1620题 算法解析 #include <bits/stdc.h> using namespace std; const int R11; int cnt[R];//cnt[t]代表第t天新增几人 int s[R];//s[]数组是cnt[]数组的前缀和数组 int n,t; int main(){cin>>n;for(…...
线性表之链式表
文章目录 主要内容一.单链表1.头插法建立单链表代码如下(示例): 2.尾插法建立单链表代码如下(示例): 3.按序号查找结点值代码如下(示例): 4.按值查找表结点代码如下(示例): 5.插入节…...
[Docker]十.Docker Swarm讲解
一.Dokcer Swarm集群介绍 1.Dokcer Swarm 简介 Docker Swarm 是 Docker 公司推出的用来管理 docker 集群的工具, 使用 Docker Swarm 可以快速方便的实现 高可用集群 ,Docker Compose 只能编排单节点上的容器, Docker Swarm 可以让我们在单一主机上操作来完成对 整…...
相机机模组需求示例
产品需求名称摄像头采集图片数据补充说明产品需求描述 As:用户 I want to:通过相机模组获取到自定义格式图片数据,要求包括: 1、支持多种场景,如:手持相机拍摄舌苔 2、支持图片分辨率至少达到1920X1080 3、…...
Uniapp 微信登录流程解析
本文将介绍在 Uniapp 应用中实现微信登录的流程,包括准备工作、授权登录、获取用户信息等步骤。 内容大纲: 介绍Uniapp和微信登录: 简要介绍 Uniapp 框架以及微信登录的重要性和流行程度。 准备工作: 注册微信开发者账号创建应用…...
红旗Asianux Server Linux V8 安装万里数据库(GreatSQL)
红旗Asianux Server Linux V8 安装万里数据库(GreatSQL) 红旗Asianux介绍: 红旗Asianux Server Linux 8.0是为云时代重新设计的操作系统,为云时代的到来引入了大量新功能,包括用于配置管理、快速迁移框架、编程语言和…...
一文2000字使用JMeter进行接口测试教程!(建议收藏)
安装 使用JMeter的前提需要安装JDK,需要JDK1.7以上版本目前在用的是JMeter5.2版本,大家可自行下载解压使用 运行 进入解压路径如E: \apache-jmeter-5.2\bin,双击jmeter.bat启动运行 启动后默认为英文版本,可通过Options – Cho…...
Spark---介绍及安装
一、Spark介绍 1、什么是Spark Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark是UC Berkeley AMP lab (加州大学伯克利分校的AMP实验室)所开源的类Hadoop MapReduce的通用并行计算框架,Spark拥有Hadoop MapReduce所具有的优点;但…...
uni-app:实现request请求的递归(设置request请求的访问次数),并且调用自定义方法给出返回值
一、效果展示 失败效果 成功效果 二、写入后端请求部分 分析 ①自定义一个模块common.js主要用于封装所有的请求函数 ②核心代码 function requestWithRetry(cmd, username, password, retryCount) {return new Promise((resolve, reject) > {uni.request({url: ip sys…...
数据结构-归并排序+计数排序
1.归并排序 基本思想: 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个…...
Qml使用cpp文件的信号槽
文章目录 一、C文件Demo二、使用步骤1. 初始化C文件和QML文件,并建立信号槽2.在qml中调用 一、C文件Demo Q_INVOKABLE是一个Qt元对象系统中的宏,用于将C函数暴露给QML引擎。具体来说,它使得在QML代码中可以直接调用C类中被标记为Q_INVOKABLE的…...
聚类笔记:HDBSCAN
1 算法介绍 DBSCAN/OPTICS层次聚类主要由以下几步组成 空间变换构建最小生成树构建聚类层次结构(聚类树)压缩聚类树提取簇 2 空间变换 用互达距离来表示两个样本点之间的距离 ——>密集区域的样本距离不受影响——>稀疏区域的样本点与其他样本点的距离被放大——>…...
【Python】批量将PDG合成PDF,以及根据SS号重命名秒传的文件
目录 说明批量zip2pdf批量zip2pdf下载SS号重命名源代码SS号重命名源代码下载附录,水文年鉴 说明 1、zip2pdf是一个开源软件,支持自动化解压压缩包成PDG,PDG合成PDF,笔者在其基础上做了部分修改,支持批量转换。 2、秒…...
2023亚太杯数学建模A题思路 - 采果机器人的图像识别技术
# 1 赛题 问题A 采果机器人的图像识别技术 中国是世界上最大的苹果生产国,年产量约为3500万吨。与此同时,中国也是世 界上最大的苹果出口国,全球每两个苹果中就有一个,全球超过六分之一的苹果出口 自中国。中国提出了一带一路倡议…...
3、LeetCode之无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。转载: C常用语法——unordered_set 题目主要思想ÿ…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
土建施工员考试:建筑施工技术重点知识有哪些?
《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目,核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容,附学习方向和应试技巧: 一、施工组织与进度管理 核心目标: 规…...
Windows 下端口占用排查与释放全攻略
Windows 下端口占用排查与释放全攻略 在开发和运维过程中,经常会遇到端口被占用的问题(如 8080、3306 等常用端口)。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口,帮助你高效解决此类问题。 一、准…...
