我的代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 测试点结果：

题目 【递归】斐波那契数列 最大公约数 最小公倍数 进制转换1 进制转换2 进制转换3 前 n 项和 汉诺塔2 【递归】斐波那契数列 题目大意 给定一个正整数 nnn（1≤n≤301 \leq n \leq 301≤n≤30），请用递归方法求出斐波那契数列的第 nnn 项。 斐波那契数列定义如下： F(1)=1,F(2)=1,F(n)=F(n−1)+F(n−2)(n≥3)F(1) = 1,\quad F(2) = 1,\quad F(n) = F(n-1) + F(n-2)\quad (n \geq 3)F(1)=1,F(2)=1,F(n)=F(n−1)+F(n−2)(n≥3) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 根据定义，我们可以用最朴素的递归方法实现。 对于输入的 nnn： * 如果 n=1n = 1n=1 或 n=2n = 2n=2，直接返回 111； * 否则返回 f(n−1)+f(n−2)f(n - 1) + f(n - 2)f(n−1)+f(n−2)。 虽然这个方法在效率上不是最优（时间复杂度是指数级的 O(2n)O(2^n)O(2n)），但题目明确要求使用递归，并且 n≤30n \leq 30n≤30，可以接受。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 时间复杂度：O(2n)O(2^n)O(2n)，因为会有大量重复递归调用； * 空间复杂度：O(n)O(n)O(n)，递归深度最多为 nnn。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现（C++） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最大公约数 题目大意 给定两个正整数 aaa 和 bbb，要求输出它们的最大公约数（Greatest Common Divisor, GCD），即同时整除 aaa 和 bbb 的最大正整数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 最大公约数是整数运算中非常基础的概念。可以使用辗转相除法（欧几里得算法）来高效计算： * gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a, b) = \gcd(b, a \bmod b)gcd(a,b)=gcd(b,amodb) * 当 b=0b = 0b=0 时，结果为 aaa 例如： * gcd⁡(16,6)→gcd⁡(6,4)→gcd⁡(4,2)→gcd⁡(2,0)=2\gcd(16, 6) \to \gcd(6, 4) \to \gcd(4, 2) \to \gcd(2, 0) = 2gcd(16,6)→gcd(6,4)→gcd(4,2)→gcd(2,0)=2 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用递归实现欧几里得算法，时间复杂度为 O(log⁡min⁡(a,b))O(\log \min(a, b))O(logmin(a,b))，即使 a,ba, ba,b 最大为 10510^5105，效率也非常高。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 时间复杂度：O(log⁡min⁡(a,b))O(\log \min(a, b))O(logmin(a,b)) * 空间复杂度： * 递归实现：O(log⁡min⁡(a,b))O(\log \min(a, b))O(logmin(a,b))（递归栈） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最小公倍数 题目大意 给定两个正整数 aaa 和 bbb，求它们的最小公倍数 LCM(a,b)LCM(a, b)LCM(a,b)，即能同时被 aaa 和 bbb 整除的最小正整数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 最小公倍数与最大公约数的关系如下： LCM(a,b)=a×bgcd⁡(a,b)\mathrm{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}LCM(a,b)=gcd(a,b)a×b 其中 gcd⁡(a,b)\gcd(a, b)gcd(a,b) 表示 aaa 和 bbb 的最大公约数。 举个例子： * gcd⁡(3,4)=1\gcd(3, 4) = 1gcd(3,4)=1，LCM(3,4)=3×41=12\mathrm{LCM}(3, 4) = \frac{3 \times 4}{1} = 12LCM(3,4)=13×4 =12 * gcd⁡(2,6)=2\gcd(2, 6) = 2gcd(2,6)=2，LCM(2,6)=2×62=6\mathrm{LCM}(2, 6) = \frac{2 \times 6}{2} = 6LCM(2,6)=22×6 =6 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 使用欧几里得算法计算 gcd⁡(a,b)\gcd(a, b)gcd(a,b)； 2. 使用公式 LCM(a,b)=a⋅bgcd⁡(a,b)\mathrm{LCM}(a, b) = \dfrac{a \cdot b}{\gcd(a, b)}LCM(a,b)=gcd(a,b)a⋅b 计算最小公倍数； 3. 注意防止乘法时超出整数范围（不过本题数据保证结果在 int 范围内）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 计算 gcd⁡\gcdgcd：O(log⁡min⁡(a,b))O(\log \min(a, b))O(logmin(a,b)) * 总体复杂度：O(log⁡min⁡(a,b))O(\log \min(a, b))O(logmin(a,b)) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最小公倍数 题目大意 输入两个正整数 aaa 和 bbb，求它们的最小公倍数（LCM）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 最小公倍数和最大公约数之间有如下关系： LCM(a,b)=a×bgcd⁡(a,b)\mathrm{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}LCM(a,b)=gcd(a,b)a×b ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 使用欧几里得算法计算 gcd⁡(a,b)\gcd(a, b)gcd(a,b)； 2. 再使用公式 LCM=a⋅bgcd⁡(a,b)\mathrm{LCM} = \dfrac{a \cdot b}{\gcd(a, b)}LCM=gcd(a,b)a⋅b ； 3. 为防止整数溢出，使用 long long 存储结果。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 计算最大公约数：O(log⁡min⁡(a,b))O(\log \min(a, b))O(logmin(a,b)) * 计算最小公倍数：O(1)O(1)O(1) 总时间复杂度：O(log⁡min⁡(a,b))O(\log \min(a, b))O(logmin(a,b)) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++ 代码实现 进制转换1 题目大意 将输入的一个十进制正整数 nnn 转换为对应的二进制数，并输出结果。要求必须使用递归完成。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 例如十进制数 666，它的二进制形式为 110110110。 * 本质上是将 nnn 不断除以 222，从而构造出它的二进制表达。 * 输出顺序是从高位到低位，因此递归非常适合这个问题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 我们考虑将十进制数 nnn 转换为二进制数的过程： 1. 对 nnn 进行整数除以 222 得到下一层递归； 2. 每次输出当前位的余数：nn % 2n； 3. 递归的结束条件是：n==0n == 0n==0 时终止（但实际要从 n>0n > 0n>0 才开始输出）。 为了防止前导 0 输出，我们在主程序中单独处理 n=0n=0n=0 的情况。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 每次递归都会将 nnn 除以 222，最多递归 log⁡2n\log_2 nlog2 n 层； * 时间复杂度为 O(log⁡n)O(\log n)O(logn)，空间复杂度也是 O(log⁡n)O(\log n)O(logn)，非常高效。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 进制转换2 题目大意 输入两个整数 XXX 和 MMM，将十进制整数 XXX 转换为 MMM 进制的数，并输出对应结果。要求必须使用递归实现。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 需要将 XXX 从十进制转换成 MMM 进制（其中 2≤M≤162 \leq M \leq 162≤M≤16）； * 若 MMM 为 161616，则要处理 10∼1510\sim1510∼15 对应的字符 A~F； * 输出顺序是从高位到低位，天然适合递归。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 递归函数思路如下： 1. 若 X==0X == 0X==0，终止递归； 2. 否则先递归处理 X/MX / MX/M； 3. 然后输出当前位：XX % MX，若大于等于 101010，输出 A~F。 另外在 main() 中要特殊处理 X=0X = 0X=0 的情况（输出 0）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度解析 * 每次递归将 XXX 除以 MMM，最多递归 log⁡MX\log_M XlogM X 次； * 因此时间和空间复杂度均为 O(log⁡X)O(\log X)O(logX)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 进制转换3 题目大意 给定一个 N进制的数 XXX（字符串形式） 和一个整数 NNN，将其转换为十进制数并输出。要求使用递归算法。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 输入中 XXX 是一个 字符串，可能包含数字 0~9 和字母 A~F 或 a~f（表示 10~15）； * 进制 NNN 范围在 2∼162 \sim 162∼16； * 要将字符串 XXX 解释为 NNN 进制，转化成十进制整数； * 用递归实现：自然可以从左到右依次处理每一位。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 我们可以定义一个递归函数如下： * 定义：convert(s, len, base) 表示将前 len 位的字符串 s 视为 base 进制数，转换为十进制。 * 递归表达式： * 若长度为 1：直接返回该位的十进制值； * 否则，答案为：convert(s, len-1, base) * base + 当前位的十进制值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度 * 每一位递归一次，共有 len(X)\text{len}(X)len(X) 位； * 时间复杂度为 O(len(X))O(\text{len}(X))O(len(X))，最多约为 O(7)O(7)O(7)，很快。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前 N 项和 题目大意 输入一个正整数 nnn，使用递归的方式求出 1+2+3+⋯+n1 + 2 + 3 + \cdots + n1+2+3+⋯+n 的结果。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 题目要求使用递归方法求和； * 不能使用循环或数学公式 n(n+1)/2n(n+1)/2n(n+1)/2。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 使用递归公式定义： * 定义 f(n) 为前 nnn 项和； * 递推关系： * f(n)=f(n−1)+nf(n) = f(n - 1) + nf(n)=f(n−1)+n * 边界：f(1)=1f(1) = 1f(1)=1 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 * 每次递归调用 n−1n-1n−1 次，时间复杂度为 O(n)O(n)O(n)； * 空间复杂度（递归栈）也是 O(n)O(n)O(n)，对于 n≤100n \leq 100n≤100 完全可以接受。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 汉诺塔2 题目大意 有 nnn 种大小不同的圆盘，每种大小各有两个相同的圆盘（共 2n2n2n 个），初始都在柱子 A 上。按照 汉诺塔规则（一次只能移动一个圆盘、且大盘不能放在小盘上），将所有盘子移动到柱子 C 上，输出最少移动次数。 注意：同一尺寸的两个圆盘是不可区分的。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意分析 * 和普通汉诺塔不同的是：每种尺寸有 两个不可区分的圆盘。 * 目标是移动这 2n2n2n 个圆盘到柱 C，最少需要多少步？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 观察样例和递归特性，我们可以发现： 普通汉诺塔的递归步骤（n 个不同盘）：移动 nnn 个盘子的最少步数为 2n−12^n - 12n−1。 本题特殊之处：每个盘有两个一模一样的拷贝，但规则仍然要求不能把大盘放在小盘上。 构造递推公式： 设 f(n)f(n)f(n) 表示将 nnn 种盘移动到目标柱的最小步数，则： * 首先把 n−1n-1n−1 对盘移到辅助柱子，需要 f(n−1)f(n-1)f(n−1) 步； * 然后将当前第 nnn 对盘子从起始柱移到目标柱，共 2 步； * 然后再将辅助柱上的 n−1n-1n−1 对盘子移到目标柱，再需要 f(n−1)f(n-1)f(n−1) 步。 于是可以得出递推式： f(n)=2×f(n−1)+2f(n) = 2 \times f(n-1) + 2f(n)=2×f(n−1)+2 * 边界条件：f(1)=2f(1) = 2f(1)=2 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 时间复杂度分析 这是一个递归式，时间复杂度为 O(n)O(n)O(n)，不会爆栈或超时，n≤15n \leq 15n≤15 时可以安全运行。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码演示

😊互动游戏😊 🎉在评论区发表你将二进制转化到十进制后的结果。🎉 往期挑战日志 （暂时是空的） 本期挑战！ 复制一下这个数字然后在评论区发表你的解析吧😊！

第二个测试点有问题啊 题目说明n<999 他硬是来个1008？ 但我们可以加个：if(n>=1000) cout<<1000<<endl<<1001;

前五个点是错的，但后五个是对的，有人解释下吗？

思路： 创建一个 n x n 的二维矩阵，并将所有元素初始化为 0。 初始化四个变量：top、bottom、left 和 right，以表示矩阵的边界。 从矩阵的左上角开始，向右移动，依次填充元素（1, 2, 3,...）。 当达到右边界时，向下移动，依次填充元素。 当达到下边界时，向左移动，依次填充元素。 当达到左边界时，向上移动，依次填充元素。 重复步骤 3-6，直到矩阵中的所有元素都被填充。 公式： 让 matrix[i][j] 表示矩阵中第 i 行第 j 列的元素。让 num 是当前要填充到矩阵中的数字。 填充矩阵元素的公式是： matrix[top][left] = num; num++;（向右移动） matrix[top][left + 1] = num; num++;（向右移动） 3.... matrix[top][right] = num; num++;（向下移动） matrix[top + 1][right] = num; num++;（向下移动） 6.... matrix[bottom][right] = num; num++;（向左移动） matrix[bottom][right - 1] = num; num++;（向左移动） 9.... matrix[bottom][left] = num; num++;（向上移动） matrix[bottom - 1][left] = num; num++;（向上移动） 12.... 循环继续，直到矩阵中的所有元素都被填充。 伪代码：

官方题解 | 欢乐赛#50 题解 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 50！ 入门 T2 农场修缮 入门 T3 赛马大会 入门 T4 小明和藏宝库 入门 T5 指针夹角 入门 T6 小明的acm罚时 普及- T1 50！ 题目大意 输出一个表示 50 的图形。 题解思路 直接参考样例输出内容， 逐行输出即可。 参考代码 T2 农场修缮 题目大意 给定一片 n×mn \times mn×m 的农田， 现在需要在里面修建一条水平的宽度为 aaa 的道路， 并且在 qqq 条竖直通路中选择一条。求最终农田能够剩余的面积最大值。 题解思路 为了使得剩余的面积尽量大， 应该选择一条宽度最小的通路，设其宽度为 bbb 。 那么水平的道路占用了 a⋅ma \cdot ma⋅m 的面积， 竖直的道路占用了 b⋅nb \cdot nb⋅n ， 水平和竖直道路的重叠区域的面积为 a⋅ba \cdot ba⋅b 因此答案应该为 n⋅m−a⋅m−b⋅n+a⋅bn \cdot m - a \cdot m - b \cdot n + a \cdot bn⋅m−a⋅m−b⋅n+a⋅b 参考代码 T3 赛马大会 题目大意 小明和对手都按顺序派出 nnn 匹马参加赛马大会， 对于每一场比赛获胜则加 333 分， 平局减 333 分，平局分数不变。 求最终小明的得分。 题解思路 分别将小明的所有马的速度值存在数组 aaa 中， 对手的所有的马的速度值存在 bbb 中。 然后从 1∼n1 \sim n1∼n 遍历每一场比赛，比较双方马匹的速度值然后修改小明的得分值。 参考代码 T4 小明和藏宝库 题目大意 存在 nnn 个宝箱， 每个宝箱都有 mmm 个密码， 只要输入其中一个就可以打开宝箱。 问有多少个密码可以同时解锁 nnn 个宝箱？ 题解思路 使用桶数组来存储一下每个密码能够打开的宝箱的数量。 对于每个宝箱， 使得该宝箱的 mmm 个密码能够解开的宝箱数量+1. 如果说某个数字能够打开的宝箱数量为 nnn， 则说明可以打开所有的宝箱，记录答案 + 1。 参考代码 T5 指针夹角 题目大意 求 aaa 时 bbb 分的时针和分针夹角度数。 题解思路 一圈为 360°360 \degree360° , 一小时 606060 分钟， 因此一分钟为 6°6 \degree6° ，分针的角度 rbrbrb 为 6×b6 \times b6×b 。 一天121212 小时， 因此一小时为 30°30 \degree30° ，当前这一个小时已经过去了 b/60b / 60b/60 ， 因此时针的角度 rarara 为 30×a+b/60×3030 \times a + b / 60 \times 3030×a+b/60×30 。 最终记得取相对小的夹角度数输出。 参考代码 T6 小明的ACM罚时 题目大意 在一场acm比赛中， 给定每一个队伍的提交记录。 按照acm的规则将所有的队伍进行排名并且按照排名从高到低输出每一只队伍的编号。 题解思路 需要先比较题数，再比较罚时， 都一直的情况下再比较编号大小，因此显然选择使用结构体排序。 定义结构体存储每个队伍的通过题数， 罚时， 编号。 在排序之后按队伍排名从高到低输出队伍编号。 参考代码

开始之前没加入团队的点击图片加入： ———————————————————————————————————————————— 下面正式开始： T1：猜生日： 原题链接：U18794.猜生日 这道题是一道很简单的猜生日题，它会给你几个线索，让你猜生日 我们根据题目就可以知道我宝的生日天数是偶数 到这里为止就排除了16个，我们搜索一下5月份的重要日子便可知对于一些人来说就是520了，也就是”我爱你“对应的就是2013.5.20，这就是正确答案 Answer： T2：冲向饭堂： 原题链接 这道题题目说输出小明到达饭堂的最短时间，其实第一个条件是多余的，只用将后面两个条件相乘就行了！ Answer： T3：查找最近元素： 原作者链接 题目链接 这道题考的是在一个非降序列中，查找与给定值最接近的元素，在这里就不作过多的解释了 Answer： T4：谁考了第k名： 原作者链接 题目链接 这道题很简单，不懂的自行查百度： Answer： T5：成绩排序： 原作者链接 题目链接 这道题是考结构体的应用，那我就简单介绍一下结构体（毕竟题解不能太短） ”结构体就是一个可以包含不同数据类型的一个结构，它是一种可以自己定义的数据类型，它的特点和数组主要有两点不同，首先结构体可以在一个结构中声明不同的数据类型。第二，相同结构的结构体变量是可以相互赋值的，而数组是做不到的，因为数组是单一数据类型的数据集合，它本身不是数据类型（而结构体是），数组名称是常量指针，所以不可以作为左值进行运算，所以数组之间就不能通过数组名称相互复制了，即使数据类型和数组大小完全相同。“ ——内容又百度提供 Answer：

这道题有谁能做出来

RT，现在为2.56MB

谁能发一下A30676的解啊？

主播主播这题怎么做

给你们先看看我的代码

这么难居然不是黑题

蜀道难三段

传送 传送 传送 有趣的东西

我没BING 但万万没想到：