P1028 [NOIP2001 普及组] 数的计算题解

时间:2024-02-11 23:53:54 标签:  题解  

题目

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

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

请你求出,一共有多少个合法的数列。两个合法数列a,b不同当且仅当两数列长度不同或存在一个正整数i≤∣a∣,使得a_{i}\neq b_{i}​。

输入输出格式

输入格式

输入只有一行一个整数,表示n。

输出格式

输出一行一个整数,表示合法的数列个数。

输入输出样例

输入样例

6

输出样例

6

解析

对于一个整数n,如果只考虑变换一次,那么问题就很简单了,答案就是n/2+1,但是还需要对变换后的继续变换。比如说,数列中最开始只有一个元素8,在末尾加入一个新元素,列表就可以变成[8 4]、[8 3]、[8 2]、[8 1],算上[8]一共有五种情况,之后的变换只需要按照上面的这种方法,分别是计算[4]、[3]、[2]、[1]按照这样的操作能有几种情况,然后累加统计即可。

原来是要解决n=8的问题,现在分解成了4个规模更小但本质上同样的子问题;如果要解决n=4的问题,基于同样的思想还可以分解成两个规模更小的单质相同的子问题;当需要解决n=2的问题时,可以分解成n=1的问题(只有n=1的情况了);直到n=1时,没法继续分解,根据题目说的“不作任何处理就直接统计为一种合法的数列”,可以直接返回只有唯一一种数列,即[1]。然后返回上一层接受到所有小规模问题的答案,合并统计处理获得这个规模下的答案,再继续返回上一层……直到求得问题的解。

像这样构造函数,这个函数在运行过程中调用自己,从而解决问题的思路就称为递归思想。

#include<iostream>
#include<cstring>
using namespace std;
int n,count,f[1010];
int sol(int x){int count=1;if(f[x]!=-1){return f[x];}for(int i=1;i<=x/2;i++){count+=sol(i);}return f[x]=count;
}
int main(){cin>>n;memset(f,-1,sizeof(f));f[1]=1;cout<<sol(n)<<endl;return 0;
}

直接使用递归运行效率很低,为了防止做很多无用功,可以定义一个数组f,其每一项f[i]就是当问题规模为i的时候的答案,首先将数组初始化为-1,说明f[i]还没有被计算过。依然使用同样的方法去求解,只是如果发现已经计算过就直接返回f[i],而不必进行接下来的计算了,否则还是按照刚才递归的方式计算,然后将结果存入数组中以便之后再次调用。

这样,每个数字最多只计算一次,因为一旦计算完成就会被存下来,便于日后使用,这样的思想称为“记忆化搜索”。

来源:分享自作者个人站点/博客

智能推荐

题目 给出正整数n&#xff0c;要求按如下方式构造数列&#xff1a; 只有一个数字n的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数&#xff0c;但是这个正整数不能超过该数列最后一项的一半&#xff0c;可以得到一个新的合法数列。 请你求出&#xff0c;一共有多少个合法的数列。两个合法数列a,b不同当且仅当两数列长度不同或存在一个正整数i≤∣a∣&#xff0c;使得

标签:题解  

网址如下&#xff1a;P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 水了道题 学了求最小公倍数和最大公因数的新方法 我对辗转相除法这个东西有所耳闻&#xff0c;但是从来没有用过 所以我只会枚举法求这两个东西 而且两个数的最小公倍数和最大公因数的乘积等于这两个数的乘

标签:最小公倍数  

网址如下&#xff1a;P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 水了道题 学了求最小公倍数和最大公因数的新方法 我对辗转相除法这个东西有所耳闻&#xff0c;但是从来没有用过 所以我只会枚举法求这两个东西

标签:最小公倍数  

蓝桥杯备赛 | 洛谷做题打卡day26 文章目录 蓝桥杯备赛 | 洛谷做题打卡day26题目描述输入格式

标签:蓝桥杯冲  

题目背景 NOIP2013 普及组 T1 题目描述 试计算在区间 1 到 n 的所有整数中&#xff0c;数字 x&#xff08;0≤x≤9&#xff09;共出现了多少次&#xff1f;例如&#xff0c;在 1 到 11 中&#xff0c;即在 1,2,3,4,5,6,7,8,9,10,11 中&#xff0c;数字 1 出现了 4 次。 输入格式 2 个整数 n,x&#xff0c;之间用一个空格隔开。 输出格式 11 个整数&#xff0c;表示 x 出现的次数。 输入输出样例 输入 

标签:洛谷  

题目 棋盘上A点有一个过河卒&#xff0c;需要走到目标B点。卒行走的规则&#xff1a;可以向下、或者向右。同时在棋盘上C点有一个对方的马&#xff0c;该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示A点(0,0)(0,0)、B点(n,m)&#xff0c;同样马的位置坐标是需要给出的。

标签:题解  

网址如下&#xff1a;P1026 [NOIP2001 提高组] 统计单词个数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 怠惰了 半个月没写代码 呆在学校的时候想着回家肯定会收到管制&#xff0c;然后没怎么写 15号晚上到的家 16号有事 中间两天不想写 直到今天 乐死了

标签:单词  

题目 一元n次多项式可用如下的表达式表示&#xff1a;

标签:多项式  

目录 1  53. 最大子数组和 2  56. 合并区间

标签:数组  

为什么说最简单&#xff0c;因为本人就是一个算法小白&#xff0c;只学过一点数据结构&#xff0c;打算备战蓝桥杯的&#xff0c;网上说备战蓝桥杯就去刷洛谷&#xff0c;早有听闻洛谷很难&#xff0c;今天一看算是真的被打醒了&#xff0c;对于小白是真的太难了。(;´༎ຶД༎ຶ&#96;) 解题之前&#xff0c;先了解一下Java快速输入输出工具。 Java&#xff08;最&#xff09;快速输入输出工具&#xff1a; 首先&#xff0c;听说Java输入输出有快速的方法&#xff0c;于是乎做这道题&#xff0c;在网上搜了一些快速输入输出的方法&#xff0c;我觉得这个东西就是理解为模板吧&#xff0c;就类似于S

标签:题解  

1. 前言唉,好想玩滋嘣。2. 计算属性直接传参接收不到表格数据某一列需要用的计算属性时,模板中使用计算属性 fullName 就会直接调用 fullName 函数,而在模板中 fullName(item) 相当于fullName()(item),此处为函数柯里化。<el-table-column label=名称 align=center min-width=20%>

标签:第三方  组件  属性  方式  

目录 [NOIP2006 普及组] 明明的随机数题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #

标签:随机数  

题目传送门 题目背景 每样商品的价格越低&#xff0c;其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量&#xff08;产品不会低于成本销售&#xff09;&#xff0c;并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后&#xff0c;销量以某固定数值递减。&#xff08;我们假设价格及销售量都是整数&#xff09; 对于某些特殊商品&#xff0c;不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。&#xff08;所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币&#xff09; 题目描述 你是某家咨询公司的项目经理&#xff0c;现在你

标签:税收  

[NOIP2003 普及组] 栈 - 洛谷 我先写了个打表的代码&#xff0c;写了一个小时&#xff0c;o(╥﹏╥)o只能说我真不擅长dfs。 int n;std::unordered_map<std::string, int>map;void dfs(std::vector<int>&a, int step,std::stack<int>p, std::string s) {if (step &#61;&#61; n &#43; 1) {if (map.find(s) &#61;&#61; map.end() && s.size

标签:数论  

目录 [NOIP2009 普及组] 分数线划定题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1

标签:分数线  

本系列文章是学习了网课《哈尔滨工业大学–计算机组成原理》之后&#xff0c;用以梳理思路而整理的听课笔记及相关思维拓展。本文涉及到的观点均为个人观点&#xff0c;如有不同意见&#xff0c;欢迎在评论区讨论。

标签:计算机  

PTA数组及排序查找题解与解题思路函数题目函数题目为平台提供的裁判程序调用所完成的函数进行判题,题目规定语言为C语言6-1 求出二维数组的最大元素及其所在的坐标本题较为简单,考察的是如何遍历一个二维数组,只需要两个循环依次遍历其每个维度和元素即可如何寻找最大值?只需要在遍历每个元素的过程中,使用一个变量记录最大值,当出现更大的值时,更新最大值的变量即可,同时更新最大值所在的坐标(题目已经给出的全局变量中已经定义,即Row与C

标签:题解  数组  思路  PTA  

目录 [NOIP2001 提高组] 数的划分题目描述输入格式输出格式样例 #1

标签:动态  

目录 [NOIP2001 提高组] 数的划分题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1

标签:动态  

打印输出数组里所有的奇数 [5, 2, 8, 10, 3, 7] <script>let arrNums &#61; [5, 2, 8, 10, 3, 7] let newArr&#61;[]for(let i&#61;0;i<arrNums.length;i&#43;&#43;){if(arrNums[i]%2!&#61;&#61;0){newArr.push(arrNums[i])}}console.log(newArr)</script> 效果&#xff1a;

标签:奇数  

目录 [NOIP2001 提高组] 一元三次方程求解题目描述输入格式输出格式样例 #1样例输入 #1样例输出

标签:方程  

蓝桥杯备赛 | 洛谷做题打卡day25 文章目录 蓝桥杯备赛 | 洛谷做题打卡day25[NOIP2003 普及组] 数字游戏

标签:数字  

计算属性file:[Demo.vue - script]import json from ./data.json;const jsonData = ref(JSON.stringify(json, null, 2));const formattedJson = computed(() => { console.log(computed!); formatJson(jsonData.value);});v-html 调用计算属性 formattedJson 函数三次,其中的

标签:有什么区别  函数  属性  vue  

题目:给你一个下标从 0 开始长度为 n 的整数数组 nums 。如果以下描述为真,那么 nums 在下标 i 处有一个 合法的分割 :前 i + 1 个元素的和 大于等于 剩下的 n - i - 1 个元素的和。下标 i 的右边 至少有一个 元素,也就是说下标 i 满足 0 <= i < n - 1 。请你返回 nums 中的 合法分割 方案数。示例 1:输入:nums = [10,4,-8,7]输出:2解释:总共有 3 种不同的方案可以将 nums 分割成两个非空的部分:在下标 0 处分割 nums 。那么第一部分为

标签:数组  算法  方案  

蓝桥杯备赛 | 洛谷做题打卡day27 文章目录 蓝桥杯备赛 | 洛谷做题打卡day27题目背景题目描述

标签:蓝桥杯冲  

猜你喜欢

《力扣算法训练提升》图解数组篇-打卡数组统计-【189】旋转数组今日份打卡题[189. 旋转数组]给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。具体描述

标签:数组  算法  

大家好,我是 Java陈序员。俗话说得好,面试造火箭,入职拧螺丝。我们在工作中,其实很少用到一些计算机底层知识,往往只要编码完事。但是,知其然还要知其所以然,我们不仅要做一个合格的“CV 工程师”,更是要掌握一些底层原理!计算机基础知识,作为计算机的底层原理,往往是晦涩难懂,如果没用心的去学习,是很难掌握的。今天,给大家介绍一个图解计算机基础的文章汇总项目。以图解的方式,详述计算机基础知识,不仅通俗易懂,而且鞭辟入里!项目介绍CS-Base

标签:计算机网络  操作系统  数据库  计算机  Star  

从事金融行业的PHPer,资金运算频繁,稍不留神,用户资金可能损失几十万,甚至更可怕......直接上实例吧:javascript0.1 + 0.2 为啥不等于 0.3 ? (正确结果:0.30000000000000004)0.8 * 7 为啥不等于 5.6 ? (正确结果:5.6000000000000005)PHPvar_dump(intval(0.58 * 100));正确结果是 57,而不是 58浮点运算惹的祸

标签:详解  php  

文章目录 一、实验目的、内容二、实验程序设计及结构1.需求分析类变量函数 2.设计结构或

标签:大数  

题目链接&#xff1a;等差数列末项计算 - 洛谷 题目难度&#xff1a;入门 涉及知识点&#xff1a;等差数列 题意&#xff1a; 输入样例&#xff1a;1 4 100 输出样例&#xff1a;298 分析&#xff1a;直接代入公式输出即可 AC代码&#xff1a;

标签:等差数列  

文章目录数据的表示与运算数据表示定点数的表示与运算定点数的表示无符号数有符号数定点整数定点小数四码反码补码移码

标签:原理  计算机  数据  

给定一个整数数组 nums&#xff0c;请编写一个能够返回数组“中心下标”的方法。 中心下标是数组的一个下标&#xff0c;其左侧所有元素相加的和等于右侧所有元素相加的和&#xff1b;如果数组不存在中心下标&#xff0c;返回 -1。

标签:下标  

插: 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。坚持不懈,越努力越幸运,大家一起学习鸭~~~题目:给你一个下标从 0 开始的整数数组 nums ,如果满足下述条件,则认为数组 nums 是一个 美丽数组 :nums.length 为偶数对所有满足 i % 2 == 0 的下标 i ,nums[i] != nums[i + 1] 均成立注意,空数组同样认为是美丽数组。你可以从 nums 中删除任意数量的元素。当你删除

标签:数组  算法  

&nbsp;&nbsp;众所周知,计算机是从0开始计数,而不是我们平时常用的从1开始计数,但你有想过为什么吗?&nbsp;其实不是计算机从0开始计数而是多数编程语言中的数组都使用0作为起始下标,又是为什么呢?&nbsp;经过大量的搜索查证,我终于找到了答案。&nbsp;故事还要从一位真正的大佬艾兹格·迪

标签:计算机科学  

看到一个视频《李永乐老师的抖音 - 骰子概率问题》&#xff0c;计算投出6个骰子恰好出现1、2、3、4、5、6这6个点数的概率 李永乐老师的计算方法是&#xff0c;第1个概率为1即6/6&#xff0c;第2个不与之前相同的概率为5/6&#xff0c;第

标签:组合  

题目:给你一个整数数组 arr ,请你删除一个子数组(可以为空),使得 arr 中剩下的元素是 非递减 的。一个子数组指的是原数组中连续的一个子序列。请你返回满足题目要求的最短子数组的长度。示例 1:输入:arr = [1,2,3,10,4,2,3,5]输出:3解释:我们需要删除的最短子数组是 [10,4,2] ,长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。另一个正确的解为删除子数组 [3,10,4] 。示例 2:输入:arr = [5,4,3,2,1]输出:4解释:由于数组是严格递减的,我们只能保留一个元素

标签:数组  最短  算法  剩余  

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java

标签:数据结构  

学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。各位小伙伴&#xff0c;如果您&#xff1a; 想系统/深入

标签:计算机系统  

《力扣算法训练提升》图解数组篇-打卡数组统计-【283】移动零囧么肥事今日打卡题目力扣【283.移动零】给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

标签:数组  算法  

《力扣算法训练提升》图解数组篇-打卡数组统计-【665】非递减数列数组的基本特性数组是最简单的数据结构。数组是用来存储一系列相同类型数据,数据连续存储,一次性分配内存。数组中间进行插入和删除,每次必须搬移后面的所有数据

标签:数组  数列  算法  

目录 数组在计算机中的执行原理 Java内存分配介绍

标签:数组  

目录 引言  一&#xff1a;一维数组 举例如下

标签:深层次  

一、选择题 1.有关循环结构的说法不正确的是(&nbsp;&nbsp;&nbsp; )。 A.循环结构是算法的基本结构之一 B.有的的程序设计中没有循环结构 C.循环结构在程序设计有可能会有嵌套出

标签:真题  

一、选择题 1.要实现将实数型变量a的值保留三位小数,以下python可以实现的是(&nbsp;&nbsp;&nbsp; ) A.a%0.001&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp

标签:真题  

全国计算机等级考试二级Python真题及解析(8)图文 一、选择题 1.python中表达式4**3=(&nbsp;&nbsp;&nbsp;&nbsp; )。

标签:真题  

一、选择题 1.在编写python程序时缩进的作用是()。 A.让程序更美观&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&

标签:真题  

一、选择题 1.要实现将实数型变量a的值保留三位小数,以下python可以实现的是(&nbsp;&nbsp;&nbsp; ) A.a%0.001&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp

标签:真题  

前言本篇笔记是分析transformer模型的参数量、计算量、中间激活、KV cache - 知乎 (zhihu.com)的学习记录。大部分内容都是来自那篇文字。符号表本文的示例模型是decoder-only模型,即若干个相同的层,有的人称之为block,每个block包含:self-attention层、MLP层(或者称为FFN层)。如下:

标签:计算方法  模型  内存  参数  

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java

标签:数据结构  

相关问题

相关文章

热门文章

推荐文章

相关标签