【洛谷 P1028】[NOIP2001 普及组] 数的计算 题解(递归)

简介: **NOIP2001普及组数的计算**:给定自然数n,构造数列,新数不超过序列最后一项一半。求合法数列个数。输入n1n103)。样例:输入6,输出6。递归解决,代码中定义函数`f`实现递归计算,总和存储在`cnt`中,最后输出。

[NOIP2001 普及组] 数的计算

题目描述

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

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

请你求出,一共有多少个合法的数列。两个合法数列 a,b 不同当且仅当两数列长度不同或存在一个正整数 i|a|,使得 aibi

输入格式

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

输出格式

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

样例 #1

样例输入 #1

6
AI 代码解读

样例输出 #1

6
AI 代码解读

提示

样例 1 解释

满足条件的数列为:

  • 6
  • 6,1
  • 6,2
  • 6,3
  • 6,2,1
  • 6,3,1

数据规模与约定

对于全部的测试点,保证 1n103

说明

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

我们要求找出具有下列性质数的个数(包含输入的正整数 n)。

先输入一个正整数 nn1000),然后对此正整数按照如下方法进行处理:

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

思路

暴力递归。数据过大,需要打开O2优化。

AC代码

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 100005;

int n;
long long cnt = 0;

void f(int x){
   
    for(int i = 1; i <= x / 2; i++){
   
        f(i);
    }
    cnt++;
}

int main(){
   
    cin >> n;
    f(n);
    cout << cnt << endl;
}
AI 代码解读
HEX9CF
+关注
目录
打赏
0
0
0
0
1
分享
相关文章
【2001NOIP普及组】T3. 求先序排列 试题解析
【2001NOIP普及组】T3. 求先序排列 试题解析
|
9月前
【洛谷 P1980】[NOIP2013 普及组] 计数问题 题解(取余)
NOIP2013普及组计数问题,求区间[1, n]内数字x出现的次数。输入为n和x,输出x的出现次数。样例输入11 1,输出4。代码通过逐位检查每个数是否等于x来计数,适用于n1060x9的情况。
114 0
|
9月前
【洛谷 P1307】[NOIP2011 普及组] 数字反转 题解(取余)
NOIP2011普及组试题,要求反转整数N的位得到新数,保持正负号和非零最高位。输入一个整数N,输出反转后的新数。样例输入1:123,输出:321;样例输入2:-380,输出:-83。代码使用取余法实现,处理负数时保留符号。
86 0
|
9月前
|
C++
【洛谷 P1307】[NOIP2011 普及组] 数字反转 题解(字符串)
**NOIP2011普及组题目:给定整数N,反转其位得到新数。新数首位非0(除非N=0)。输入0时直接输出0,其他情况输出反转后的数,考虑负数及前导0。提供的C++代码实现通过读入字符串,反转数字顺序并处理符号和前导0。**
53 0
|
8月前
【洛谷】P1308 [NOIP2011 普及组] 统计单词数
然后要被查找的b字符串,可能会出现第二个样例中的情况,也就是字符串a是to,而字符串b的Ottoman,这样是不符合题意的。为了 解决这个问题,我们将字符串a首尾都加一个空格,同时将字符串b首尾都加一个空格(这里是为了让字符串b的首单词和尾单词前后均有空格)为了能持续找字符串b中的所有字符串a,我们用一个while循环,如果能找到,就每次从能找到的位置的下一个位置(也就是能找到的位置下标+1)开始找,并及时更新位置,同时计数。因为不区分大小写,所以可以将两个字符串a,b都转为小写(也可以都转为大写)。
205 10
【洛谷】P1308 [NOIP2011 普及组] 统计单词数
|
9月前
|
C++
【洛谷 P1044】[NOIP2003 普及组] 栈 题解(递归+记忆化搜索)
**NOIP2003普及组栈问题**:给定操作数序列1到n,仅允许push(进栈)和pop(出栈)操作。目标是计算所有可能的输出序列总数。输入包含一个整数n(1≤n≤18)。示例输入3,输出5。当队列空时返回1,栈空则只能入栈,栈非空时可入栈或出栈。AC C++代码利用记忆化搜索求解。
111 1
【洛谷 P1028】[NOIP2001 普及组] 数的计算 题解(递推)
在NOIP2001普及组的数的计算题目中,给定自然数`n`,需构造遵循特定规则的合法数列。合法序列始于`n`,新元素不超过前一项的一半。任务是找出所有这样的数列数量。例如,当`n=6`时,合法序列包括`6`, `6,1`, `6,2`, `6,3`, `6,2,1`, `6,3,1`。程序通过动态规划求解,当`i`为奇数时,`a[i] = a[i - 1]`;为偶数时,`a[i] = a[i - 1] + a[i / 2]`。代码中预处理数组`a`并输出`a[n]`作为答案。输入`n`后,程序直接计算并打印合法数列个数。
105 0
|
9月前
【洛谷 P1035】[NOIP2002 普及组] 级数求和 题解(循环)
**NOIP2002普及组题目:求级数Sn=1+12+13+...+1n超过k的最小n。给定1k15,输出满足S_n&gt;kn。输入1个整数k,输出相应n。例如,输入1,输出2。代码中使用double确保精度,通过累加求和判断条件找到n。**
77 0
|
9月前
|
C++
【洛谷 P1075】[NOIP2012 普及组] 质因数分解 题解(判断质数)
NOIP2012普及组题目,给定合数n由两个不同质数乘积组成,求较大质数。输入一个正整数n,输出较大质因子。例如输入21,输出7。代码使用C++,通过循环和质数判断找到能整除n的质数,再求另一个质数,并输出较大者。
110 0
|
9月前
|
C++
【洛谷 P1059】[NOIP2006 普及组] 明明的随机数 题解(集合)
**NOIP2006普及组题目**,明明需生成不重复的1-1000间随机整数,输入含两行:第一行是整数N(≤100),第二行是N个随机数。输出两行,第一行是唯一数的个数M,第二行是排序后的唯一数。示例:输入10个数含重复,输出8个不同数排序后结果。解题方法:利用C++的`set`进行去重和排序。
101 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等