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

2005-NOIP-普及组复赛真题及解析摘要本文收录了 2005 年 NOIP 普及组复赛的全部四道真题及详细解析。T1「数的计算」采用递推与规律归纳法求解序列数量T2「最大公约数和最小公倍数问题」基于最大公约数与最小公倍数的数学性质进行枚举验证T3「求先序排列」通过后序遍历与中序遍历恢复二叉树的先序遍历序列T4「装箱问题」则是经典的 01 背包变形利用动态规划求解最小剩余空间。每道题均附有完整的思路分析和可运行的 C 代码实现。说明点击题目名称即可跳转原题链接 题号题目知识点难度T1数的计算递推递归普及-T2最大公约数和最小公倍数问题数学枚举gcd普及-T3求先序排列字符串树递归普及-T4装箱问题动规背包普及-数的计算思路可以把前几项的序列先手动模拟生成尝试找到数字之间的规律。1: 12: 2, 2 13: 3, 3 14: 4, 4 2, 4 1, 4 2 15: 5, 5 2, 5 1, 5 2 16: 6, 6 3, 6 2, 6 1, 6 3 1, 6 2 1会发现奇数项结果同上一个偶数项的结果。可以这样理解项数每加 1多出来能补左边的数只有 0.5对补整数没有用只有项数 2才能有个新的能补的整数所以答案数据变化都发生在偶数项之间。偶数项每两项多出一个新的 (n / 2) 可补在左边在上项结果基础上新增数量 f(n / 2)得到递推公式是 f(n) f(n - 1) f (n / 2)。实际上由于奇数项结果等于上一个偶数项所以递推公式也可以写成 f(n) f(n - 2) f (n / 2)。代码具体实现可以用递推也可以用递归 记忆化搜索。代码#includebits/stdc.husingnamespacestd;intn,a[1005]{};intmain(){cinn;a[1]1;for(inti2;in;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];}couta[n];return0;}最大公约数和最小公倍数问题思路数学知识 gcd(a, b) * lcm(a, b) a * b即 a 和 b 的最大公约数(gcd) 与 最小公倍数(lcm) 的乘积等于 a 与 b 的乘积。可以用辗转相除法递归求两个数的最大公约数如下intgcd(inta,intb){// 返回 a 和 b 的最大公约数if(!b)returna;returngcd(b,a%b);}已知 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这里是整除向下取整。对于枚举的 p 和 q 的值还要检验是否满足题意即 p * q x * y 且 gcd(p, q) x满足条件的答案计数加 1。代码#includebits/stdc.husingnamespacestd;intx,y,p,q,ans;intgcd(inta,intb){// 返回 a 和 b 的最大公约数if(!b)returna;returngcd(b,a%b);}intmain(){cinxy;for(intpx;py;px){// p尝试枚举 y 以内 x 的倍数qx*y/p;// p * q x * yif(p*qx*ygcd(p,q)x){ans;}}coutans;return0;}求先序排列思路后序遍历的最后一个结点为根结点因此可在中序遍历序列中查找后序遍历的最后一个结点以此为界左半边就是左子树右半边就是右子树注意在两个序列中划分左右子树的端点计算详见代码注释。先序遍历顺序为根-左-右因此找到左右子树后按照先输出根结点再遍历左子树最后遍历右子树的顺序访问每个结点即可。代码#includebits/stdc.husingnamespacestd;string po,in;voidf(intpl,intpr,intil,intir){// pl/r: 后序左/右端点il/r: 中序左/右端点if(plpr||ilir){// 结束条件左右边界越界即序列无元素return;}intkin.find(po[pr]);// 在中序序列中找出后序终点根结点所在下标 k// 中序左半子树[il...(k-1)] 根[k] 右半子树[(k1)...ir]// 左半子树元素个数k-1-il1 k-il个 右半子树元素个数ir-k-11ir-k 个// 后序左半子树[pl...(plk-il-1)] 右半子树[(plk-il)...(pr-1)] 根[pr]coutin[k];// 输出根结点也可以是 po[pr]f(pl,plk-il-1,il,k-1);// 递归遍历左半子树f(plk-il,pr-1,k1,ir);// 递归遍历右半子树}intmain(){cininpo;// in:中序 po:后序intlenin.size();f(0,len-1,0,len-1);// 传参两个序列的左右端点return0;}装箱问题思路这个题是一道 01 背包的变形。n 个物品每个物品有一个体积背包总容量为 V要选择若干物品使背包剩余空间尽可能小由此可分析出对每个物品来说选择的成本是它的体积带来的收益也是它的体积。状态定义dp[i][j] 表示前 i 个物品背包容量为 j 的最大收益。状态转移方程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])最后输出 v - dp[v] 为背包最小余量。代码#includebits/stdc.husingnamespacestd;intv,n,ans,cost[35],dp[20005];intmain(){cinvn;for(inti1;in;i){cincost[i];}for(inti1;in;i){// 遍历每一个物品for(intjv;jcost[i];j--){// 逆序枚举背包容量dp[j]max(dp[j],dp[j-cost[i]]cost[i]);// 取选第 i 个物品和不选第 i 个物品方案中的最大值}}coutv-dp[v];// 剩余最小容量return0;}