2005-NOIP-普及组：复赛真题及解析

2005-NOIP-普及组：复赛真题及解析

摘要：本文收录了 2005 年 NOIP 普及组复赛的全部四道真题及详细解析。T1「数的计算」采用递推与规律归纳法求解序列数量；T2「最大公约数和最小公倍数问题」基于最大公约数与最小公倍数的数学性质进行枚举验证；T3「求先序排列」通过后序遍历与中序遍历恢复二叉树的先序遍历序列；T4「装箱问题」则是经典的 01 背包变形，利用动态规划求解最小剩余空间。每道题均附有完整的思路分析和可运行的 C++ 代码实现。

说明：点击题目名称即可跳转原题链接 😃

数的计算

思路

1. 可以把前几项的序列先手动模拟生成，尝试找到数字之间的规律。

   1: 1
   2: 2, 2 1
   3: 3, 3 1
   4: 4, 4 2, 4 1, 4 2 1
   5: 5, 5 2, 5 1, 5 2 1
   6: 6, 6 3, 6 2, 6 1, 6 3 1, 6 2 1

2. 会发现奇数项结果同上一个偶数项的结果。可以这样理解：项数每加 1，多出来能补左边的数只有 0.5，对补整数没有用，只有项数 + 2，才能有个新的能补的整数，所以答案数据变化都发生在偶数项之间。

3. 偶数项每两项多出一个新的 (n / 2) 可补在左边，在上项结果基础上新增数量 f(n / 2)，得到递推公式是 f(n) = f(n - 1) + f (n / 2)。

4. 实际上由于奇数项结果等于上一个偶数项，所以递推公式也可以写成 f(n) = f(n - 2) + f (n / 2)。

5. 代码具体实现可以用递推，也可以用递归 + 记忆化搜索。

代码

#include<bits/stdc++.h>usingnamespacestd;intn,a[1005]={};intmain(){cin>>n;a[1]=1;for(inti=2;i<=n;i++){if(i%2)// 奇数项： a[i] = a[i - 1] (同上一个偶数项)a[i]=a[i-1];else// 偶数项： a[i] = a[i - 1] + a[i / 2] (新增 a[i/2])a[i]=a[i-1]+a[i/2];}cout<<a[n];return0;}

最大公约数和最小公倍数问题

思路

1. 数学知识 ：gcd(a, b) * lcm(a, b) = a * b，即 a 和 b 的最大公约数(gcd) 与 最小公倍数(lcm) 的乘积等于 a 与 b 的乘积。

2. 可以用辗转相除法递归求两个数的最大公约数，如下：

   intgcd(inta,intb){// 返回 a 和 b 的最大公约数if(!b)returna;returngcd(b,a%b);}

3. 已知 gcd(p, q) = x, lcm(p, q) = y，可以尝试枚举所有 x 的倍数作为 p 的值，再由 gcd(p, q) * lcm(p, q) = p * q 反推 q = gcd(p, q) * lcm(p, q) / p，即 q = x * y / p（这里是整除，向下取整）。

4. 对于枚举的 p 和 q 的值还要检验是否满足题意，即 p * q == x * y 且 gcd(p, q) == x，满足条件的，答案计数加 1。

代码

#include<bits/stdc++.h>usingnamespacestd;intx,y,p,q,ans;intgcd(inta,intb){// 返回 a 和 b 的最大公约数if(!b)returna;returngcd(b,a%b);}intmain(){cin>>x>>y;for(intp=x;p<=y;p+=x){// p：尝试枚举 y 以内 x 的倍数q=x*y/p;// p * q = x * yif(p*q==x*y&&gcd(p,q)==x){ans++;}}cout<<ans;return0;}

求先序排列

思路

1. 后序遍历的最后一个结点为根结点，因此可在中序遍历序列中查找后序遍历的最后一个结点，以此为界，左半边就是左子树，右半边就是右子树，注意在两个序列中划分左右子树的端点计算（详见代码注释）。

2. 先序遍历顺序为：根->左->右，因此找到左右子树后，按照先输出根结点，再遍历左子树，最后遍历右子树的顺序访问每个结点即可。

代码

#include<bits/stdc++.h>usingnamespacestd;string po,in;voidf(intpl,intpr,intil,intir){// pl/r: 后序左/右端点，il/r: 中序左/右端点if(pl>pr||il>ir){// 结束条件：左右边界越界（即序列无元素）return;}intk=in.find(po[pr]);// 在中序序列中找出后序终点（根结点）所在下标 k// 中序：左半子树[il...(k-1)] 根[k] 右半子树[(k+1)...ir]// 左半子树元素个数：k-1-il+1 = k-il个， 右半子树元素个数：ir-k-1+1=ir-k 个// 后序：左半子树[pl...(pl+k-il-1)] 右半子树[(pl+k-il)...(pr-1)] 根[pr]cout<<in[k];// 输出根结点，也可以是 po[pr]f(pl,pl+k-il-1,il,k-1);// 递归遍历左半子树f(pl+k-il,pr-1,k+1,ir);// 递归遍历右半子树}intmain(){cin>>in>>po;// in:中序 po:后序intlen=in.size();f(0,len-1,0,len-1);// 传参：两个序列的左右端点return0;}

装箱问题

思路

1. 这个题是一道 01 背包的变形。n 个物品，每个物品有一个体积，背包总容量为 V，要选择若干物品使背包剩余空间尽可能小，由此可分析出对每个物品来说，选择的成本是它的体积，带来的收益也是它的体积。

2. 状态定义：dp[i][j] 表示前 i 个物品背包容量为 j 的最大收益。

3. 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j - cost[i]] + cost[i])

   逆序枚举降维压缩：dp[j] = max(dp[j], dp[j - cost[i]] + cost[i])

4. 最后输出 v - dp[v] 为背包最小余量。

代码

#include<bits/stdc++.h>usingnamespacestd;intv,n,ans,cost[35],dp[20005];intmain(){cin>>v>>n;for(inti=1;i<=n;i++){cin>>cost[i];}for(inti=1;i<=n;i++){// 遍历每一个物品for(intj=v;j>=cost[i];j--){// 逆序枚举背包容量dp[j]=max(dp[j],dp[j-cost[i]]+cost[i]);// 取选第 i 个物品，和不选第 i 个物品方案中的最大值}}cout<<v-dp[v];// 剩余最小容量return0;}