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

P1028 [NOIP2001 普及组] 数的计算

时刻记住一句话:写递归,1画图,2大脑放空!!!

意思是,自己写递归题目,先用样例给的数据画图,然后想一个超级简单的思路,直接套上去就可以了。

上题干:

题目描述

给出正整数 n,要求按如下方式构造数列:

  1. 只有一个数字 n 的数列是一个合法的数列。
  2. 在一个合法的数列的末尾加入一个正整数,但是这个正整数不能超过该数列最后一项的一半,可以得到一个新的合法数列。

请你求出,一共有多少个合法的数列。

输入格式

输入只有一行一个整数,表示 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),然后对此正整数按照如下方法进行处理:

  1. 不作任何处理;
  2. 在它的左边拼接一个正整数,但该正整数不能超过原数,或者是上一个被拼接的数的一半;
  3. 加上数后,继续按此规则进行处理,直到不能再加正整数为止。

 这道题,不要想那么复杂。

题目给的数字是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 普及组] 数的计算

时刻记住一句话&#xff1a;写递归&#xff0c;1画图&#xff0c;2大脑放空&#xff01;&#xff01;&#xff01; 意思是&#xff0c;自己写递归题目&#xff0c;先用样例给的数据画图&#xff0c;然后想一个超级简单的思路&#xff0c;直接套上去就可以了。 上题干&#xff…...

浅析三相异步电动机控制的电气保护

安科瑞 华楠 摘 要&#xff1a;要求三相异步电动机的控制系统不仅要保证电机正常启动和运行&#xff0c;完成制动操作&#xff0c;还要通过相关保护措施维护电动机的安全使用。基于此&#xff0c;本文以电动机电气保护作为研究对象&#xff0c;结合三相异步电动机的机械特点&…...

Java设计模式系列:单例设计模式

Java设计模式系列&#xff1a;单例设计模式 介绍 所谓类的单例设计模式&#xff0c;就是采取一定的方法保证在整个的软件系统中&#xff0c;对某个类只能存在一个对象实例&#xff0c;并且该类只提供一个取得其对象实例的方法&#xff08;静态方法&#xff09; 比如 Hiberna…...

开拓新天地:探讨数位行销对医药产业医病连结的影响

数字营销模式多元&#xff0c;主要围绕医生和患者。赛道各企业凭借各自优势&#xff08;技术、学术、流量等&#xff09;入局&#xff0c;提供各自差异化营销工具或服务。目前&#xff0c;围绕医生的数字营销旨在为医生提供全面学术解决方案从而提升对医药产品的认可&#xff0…...

[tsai.shen@mailfence.com].faust勒索病毒数据怎么处理|数据解密恢复

导言&#xff1a; [support2022cock.li].faust、[tsai.shenmailfence.com].faust、[Encrypteddmailfence.com].faust勒索病毒是一种具有恶意目的的勒索软件&#xff0c;其主要特点包括对受害者文件进行强力加密&#xff0c;然后勒索受害者支付赎金以获取解密密钥。攻击者通常通…...

Peter算法小课堂—前缀和数组的应用

桶 相当于计数排序&#xff0c;看一个视频 桶排序 太戈编程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.头插法建立单链表代码如下&#xff08;示例&#xff09;: 2.尾插法建立单链表代码如下&#xff08;示例&#xff09;: 3.按序号查找结点值代码如下&#xff08;示例&#xff09;: 4.按值查找表结点代码如下&#xff08;示例&#xff09;: 5.插入节…...

[Docker]十.Docker Swarm讲解

一.Dokcer Swarm集群介绍 1.Dokcer Swarm 简介 Docker Swarm 是 Docker 公司推出的用来管理 docker 集群的工具&#xff0c; 使用 Docker Swarm 可以快速方便的实现 高可用集群 ,Docker Compose 只能编排单节点上的容器, Docker Swarm 可以让我们在单一主机上操作来完成对 整…...

相机机模组需求示例

产品需求名称摄像头采集图片数据补充说明产品需求描述 As&#xff1a;用户 I want to&#xff1a;通过相机模组获取到自定义格式图片数据&#xff0c;要求包括&#xff1a; 1、支持多种场景&#xff0c;如&#xff1a;手持相机拍摄舌苔 2、支持图片分辨率至少达到1920X1080 3、…...

Uniapp 微信登录流程解析

本文将介绍在 Uniapp 应用中实现微信登录的流程&#xff0c;包括准备工作、授权登录、获取用户信息等步骤。 内容大纲&#xff1a; 介绍Uniapp和微信登录&#xff1a; 简要介绍 Uniapp 框架以及微信登录的重要性和流行程度。 准备工作&#xff1a; 注册微信开发者账号创建应用…...

红旗Asianux Server Linux V8 安装万里数据库(GreatSQL)

红旗Asianux Server Linux V8 安装万里数据库&#xff08;GreatSQL&#xff09; 红旗Asianux介绍&#xff1a; 红旗Asianux Server Linux 8.0是为云时代重新设计的操作系统&#xff0c;为云时代的到来引入了大量新功能&#xff0c;包括用于配置管理、快速迁移框架、编程语言和…...

一文2000字使用JMeter进行接口测试教程!(建议收藏)

安装 使用JMeter的前提需要安装JDK&#xff0c;需要JDK1.7以上版本目前在用的是JMeter5.2版本&#xff0c;大家可自行下载解压使用 运行 进入解压路径如E: \apache-jmeter-5.2\bin&#xff0c;双击jmeter.bat启动运行 启动后默认为英文版本&#xff0c;可通过Options – Cho…...

Spark---介绍及安装

一、Spark介绍 1、什么是Spark Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark是UC Berkeley AMP lab (加州大学伯克利分校的AMP实验室)所开源的类Hadoop MapReduce的通用并行计算框架&#xff0c;Spark拥有Hadoop MapReduce所具有的优点&#xff1b;但…...

uni-app:实现request请求的递归(设置request请求的访问次数),并且调用自定义方法给出返回值

一、效果展示 失败效果 成功效果 二、写入后端请求部分 分析 ①自定义一个模块common.js主要用于封装所有的请求函数 ②核心代码 function requestWithRetry(cmd, username, password, retryCount) {return new Promise((resolve, reject) > {uni.request({url: ip sys…...

数据结构-归并排序+计数排序

1.归并排序 基本思想&#xff1a; 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并&#xff0c;得到完全有序的序列&#xff1b;即先使每个子序列有序&#xff0c;再使子序列段间有序。若将两个有序表合并成一个…...

Qml使用cpp文件的信号槽

文章目录 一、C文件Demo二、使用步骤1. 初始化C文件和QML文件&#xff0c;并建立信号槽2.在qml中调用 一、C文件Demo Q_INVOKABLE是一个Qt元对象系统中的宏&#xff0c;用于将C函数暴露给QML引擎。具体来说&#xff0c;它使得在QML代码中可以直接调用C类中被标记为Q_INVOKABLE的…...

聚类笔记:HDBSCAN

1 算法介绍 DBSCAN/OPTICS层次聚类主要由以下几步组成 空间变换构建最小生成树构建聚类层次结构(聚类树)压缩聚类树提取簇 2 空间变换 用互达距离来表示两个样本点之间的距离 ——>密集区域的样本距离不受影响——>稀疏区域的样本点与其他样本点的距离被放大——>…...

【Python】批量将PDG合成PDF,以及根据SS号重命名秒传的文件

目录 说明批量zip2pdf批量zip2pdf下载SS号重命名源代码SS号重命名源代码下载附录&#xff0c;水文年鉴 说明 1、zip2pdf是一个开源软件&#xff0c;支持自动化解压压缩包成PDG&#xff0c;PDG合成PDF&#xff0c;笔者在其基础上做了部分修改&#xff0c;支持批量转换。 2、秒…...

2023亚太杯数学建模A题思路 - 采果机器人的图像识别技术

# 1 赛题 问题A 采果机器人的图像识别技术 中国是世界上最大的苹果生产国&#xff0c;年产量约为3500万吨。与此同时&#xff0c;中国也是世 界上最大的苹果出口国&#xff0c;全球每两个苹果中就有一个&#xff0c;全球超过六分之一的苹果出口 自中国。中国提出了一带一路倡议…...

3、LeetCode之无重复字符的最长子串

给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长子串 的长度 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"&#xff0c;所以其长度为 3。转载&#xff1a; C常用语法——unordered_set 题目主要思想&#xff…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...