【洛谷 P1028】[NOIP2001 普及组] 数的计算 题解（递推）
创始人
2025-05-29 04:23:37
0次

[NOIP2001 普及组] 数的计算

题目描述

给出自然数 nnn，要求按如下方式构造数列：

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

请你求出，一共有多少个合法的数列。两个合法数列 a,ba, ba,b 不同当且仅当两数列长度不同或存在一个正整数 i≤∣a∣i \leq |a|i≤∣a∣，使得 ai≠bia_i \neq b_iai​=bi​。

输入格式

输入只有一行一个整数，表示 nnn。

输出格式

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

样例 #1

样例输入 #1

6

样例输出 #1

6

提示

样例 1 解释

满足条件的数列为：

  • 666
  • 6,16, 16,1
  • 6,26, 26,2
  • 6,36, 36,3
  • 6,2,16, 2, 16,2,1
  • 6,3,16, 3, 16,3,1

数据规模与约定

对于全部的测试点，保证 1≤n≤1031 \leq n \leq 10^31≤n≤103。

说明

本题数据来源是 NOIP 2001 普及组第一题，但是原题的题面描述和数据不符，故对题面进行了修改，使之符合数据。原题面如下，谨供参考：

我们要求找出具有下列性质数的个数（包含输入的正整数 nnn）。

先输入一个正整数 nnn（n≤1000n \le 1000n≤1000），然后对此正整数按照如下方法进行处理：

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

思路

a[1] = 1;
a[2] = 2; a[3] = 2;
a[4] = 4; a[5] = 4;
a[6] = 6; a[7] = 6;

易知
当i为奇数：a[i] = a[i - 1]
当i为偶数：a[i] = a[i - 1] + a[i / 2]

AC代码

#include 
#define AUTHOR "HEX9CF"
using namespace std;const int maxn = 100005;int n;
int a[maxn];int main(){a[1] = 1;cin >> n;for(int i = 2; i <= n; i++){a[i] = a[i - 1];if(i % 2){continue;}a[i] += a[i / 2];// cout << i << " " << a[i] << endl;}cout << a[n] << endl;
}
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：实验一 Java Web 入门

下一篇：postgresql基本操作与基本对象

相关内容

热门资讯

玩转k8s（六）—— Heal... 用户可以利用Liveness和Readiness探测机制设置更精细的健康检查，进而实现...
财经大V走进广州，感受新质生产... 5月27日，由广州市自媒体协会主办的第四届湾区自媒体创新发展大会在广州鸣泉居酒店圆满举行。在互联网快...
华谊兄弟：从影视巨头到断臂求生... 近日，华谊兄弟董事长王忠军油画作品流拍事件引发市场热议——这幅曾以368万元高价成交的作品，如今30...
嵌入式学深度学习：1、Pyto... 嵌入式学深度学习：1、Pytorch框架搭建1、介绍2、Pytorch开发环境搭建2....
springcloud学习总结 springcloud 构建微服务项目步骤 导入依赖编写配置文件开启这个功能 @Enable...
刚刚，德勤中国官宣新CEO 德... 5月30日，德勤中国宣布，刘明华将接替曾顺福出任德勤中国首席执行官，自2025年6月1日起生效，任期...
React 执行架构流程详细-... React 执行架构流程详细----归阶段 mount 时流程（三） 目...
险资活水入市来 超1700亿元... 既有新的保险系私募证券基金管理人完成备案，也有新的保险系私募基金产品发起设立，还有险企宣布将设立私募...
石药集团：就三项潜在交易进行磋... 新京报贝壳财经讯 5月30日，石药集团在港交所公告，集团目前正与若干独立第三方就三项潜在交易进行磋商...
Spring学习（三） Spring的AOP的XML开发（重要指数五颗星*****） 一、AOP...
缓存穿透，缓存雪崩，缓存击穿 注：该文章基于黑马程序员中《黑马点评》软件的学习 视频链接 涉及视频 p40p42p4...
去年净利增五成，厦门国际银行遭... 来源：密探财经（ID：Spy Finance）刚刚，号称“中国第一家中外合资银行”的厦门国际银行被“...
石药集团：就三项潜在交易进行磋... 新京报贝壳财经讯 5月30日，石药集团在港交所公告，集团目前正与若干独立第三方就三项潜在交易进行磋商...
「开盘」A股三大股指集体低开，... A股三大股指5月30日集体低开。其中，沪指跌0.14%报3358.81点，深成指跌0.36%报100...
淘宝天猫消费者频频上当维权艰难... 文丨顾小白 编辑丨百进来源丨正经社（ID：zhengjingshe）（本文约为3100字）【正经社“...
哪吒汽车“债转股”失败，知情人... 据媒体5月29日报道，哪吒汽车上海总部外墙的“哪吒汽车”LOGO目前被拆除，一并被拆除的还有位于总部...
Struts2—Ognl 表达... 0x00 前言 补充一下Ognl表达式的相关的知识点。尽量调有用的知识点来进行记录。 Ognl&#x...
恒生指数开盘跌0.99%，恒生... 5月30日，恒生指数开盘跌0.99%，网易跌近4%领跌蓝筹，恒生科技指数跌1.26%。手回集团上市首...
昨日获资金净流入，科创板人工智... 5月30日，三大指数集体低开，科技方向震荡走低。截至发稿，上证科创板人工智能指数下跌1.69%。相关...
25. 在QWidget窗口中... 1. 说明： QML开发界面是最近才开始流行，在之前的老项目中一般都是使...