金币
题目大意
按照特定规则，国王每天给骑士发金币：
* 第 1 天发 1 枚金币；
* 第 2～3 天每天发 2 枚金币；
* 第 4～6 天每天发 3 枚金币；
* 第 7～10 天每天发 4 枚金币；
* 以此类推。
规律是：金币数为 nnn 的这一轮，会持续 nnn 天。然后进入金币数为 n+1n+1n+1 的下一轮，持续 n+1n+1n+1 天。
给定前 kkk 天，求骑士一共获得了多少金币。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
本质是将天数分组，第 nnn 组有 nnn 天，每天发 nnn 枚金币。
例如：
* 第 1 组：1 天，每天 1 枚 → 总计 1 枚
* 第 2 组：2 天，每天 2 枚 → 总计 4 枚
* 第 3 组：3 天，每天 3 枚 → 总计 9 枚
* 第 4 组：4 天，每天 4 枚 → 总计 16 枚
* ...
题目要求我们从第 1 天起，一直到第 kkk 天，计算每天金币数的总和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
模拟发放金币的过程：
1. 用两个变量：
* day：记录已经走过的天数；
* value：当前阶段每天发的金币数量，也是阶段的天数；
2. 每次判断：
* 如果 day + value <= k，说明当前阶段所有天数都能算入，总金币加 value * value；
* 否则说明只剩下不足一个阶段的天数了，加上 (k - day) * value，结束；
3. 最后输出金币总数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度解析
每轮最多走 1+2+3+⋯+n1 + 2 + 3 + \cdots + n1+2+3+⋯+n 天，直到超过 kkk，最多循环 2k\sqrt{2k}2k 次，远小于 10410^4104，因此 时间复杂度为 O(k)O(\sqrt{k})O(k )，可以快速处理。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
买奶茶
题目大意
有 nnn 个人排队买奶茶，每人奶茶的制作时间为 TiT_iTi 。奶茶店每次只能为一个人制作奶茶。一个人的等待时间是他开始制作之前所有人制作时间的总和。
例如制作时间顺序为 [1, 2, 3]：
* 第一个人等待时间为 000
* 第二个人等待时间为 111
* 第三个人等待时间为 1+2=31 + 2 = 31+2=3
总等待时间为 0+1+3=40 + 1 + 3 = 40+1+3=4，平均等待时间为 4/3=1.334 / 3 = 1.334/3=1.33。
本题要求：找一种排队顺序，使得 所有人平均等待时间最小。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
问题本质：最小化总等待时间。
关键观察：
* 第 iii 个人的等待时间是 他前面所有人制作时间之和。
* 所以：先做制作时间小的，可以减少后面所有人的等待时间。
这是经典的贪心策略问题，结论如下：
> 将所有制作时间 TiT_iTi 从小到大排序，按此顺序排队，可以得到最小的平均等待时间。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 输入 nnn 和 nnn 个制作时间 TiT_iTi 。
2. 将 TiT_iTi 排序。
3. 遍历排序后的数组：
* 累加当前人的等待时间；
* 每轮累加前面的总时间，注意第一个人等待时间是 000。
4. 求平均等待时间：总等待时间n\frac{\text{总等待时间}}{n}n总等待时间 ，保留两位小数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 排序：O(nlogn)O(n \log n)O(nlogn)
* 遍历计算等待时间：O(n)O(n)O(n)
总时间复杂度为：O(nlogn)O(n \log n)O(nlogn)，对于 n≤105n \leq 10^5n≤105 是可以接受的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
种树
题目大意
一条街分为 nnn 个区域，每个区域最多可以种一棵树。现在有 hhh 个居民，每个居民想在区间 [bi,ei][b_i, e_i][bi ,ei ] 中至少看到 tit_iti 棵树。
这些居民的要求区间可能会重叠。我们需要决定在哪些位置种树，使得总共种树数最少，并且满足所有居民的要求。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
本题要求我们满足所有区间最小树数的限制，且总种树数量最少。这是一个贪心 + 差分 + 贪心调度的组合问题，具有如下特征：
* 每个区域最多一棵树（0或1）；
* 每个区间的需求是至少 tit_iti 棵树；
* 要求在满足所有区间的前提下，总种树数量最小。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
我们使用如下策略：
1. 维护每个位置是否已经种树（用数组 vis[] 表示）；
2. 按照区间结束位置升序排序（先处理结束早的区间）；
3. 处理每个居民的区间要求时，计算当前区间内已种了多少棵树；
4. 如果不满足，就从区间右端往左贪心地种树，每种一棵就 t--，直到满足或区间种满。
这个策略的关键是：从右往左种树，因为右边的区域对后面的区间干扰更小，有利于节省树。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度
* 排序：O(hlogh)O(h \log h)O(hlogh)；
* 每个区间最多访问 ei−bi+1e_i - b_i + 1ei −bi +1 个位置，总最多为 O(nh)O(nh)O(nh)，但由于提前剪枝（最多每个点种一次），实际复杂度接近 O(n+hlogh)O(n + h \log h)O(n+hlogh)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
水壶
题目大意
有 nnn 个编号为 111 到 nnn 的水壶，每个水壶初始时有 AiA_iAi 单位水。你最多可以进行 kkk 次操作，每次操作可以将某个水壶 iii（1≤i≤n−11 \le i \le n-11≤i≤n−1）的水全部倒入它右边的水壶 i+1i+1i+1 中（然后 AiA_iAi 变成 0）。
最终你可以任选一个水壶，将其中的水全部喝掉。请问最多可以喝到多少水。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这个问题本质上是在问：最多经过 kkk 次“左往右倒水”操作后，某个水壶中水量最多是多少？
由于每次只能往右倒水，因此水是“右移”趋势。我们目标是集中水量，形成一个“巨无霸”水壶。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
* 想喝最多的水，就要把尽量多的水“搬运”到某个水壶中；
* 由于操作有限 (kkk 次)，只能将连续的 k+1k+1k+1 个水壶合并成一个，这样能把最多的水集中在一个水壶中；
* 最优策略：选一个长度为 k+1k+1k+1 的连续子数组，求其和，最大值即为答案。
所以问题转化为：在数组 AAA 中，找到长度为 k+1k+1k+1 的连续子段最大和。
可以使用前缀和快速解决。
利用 前缀和 数组 sss，定义：
* s[i]=A[1]+A[2]+⋯+A[i]s[i] = A[1] + A[2] + \cdots + A[i]s[i]=A[1]+A[2]+⋯+A[i]
那么，区间 [l,r][l, r][l,r] 的和为：
* s[r]−s[l−1]s[r] - s[l-1]s[r]−s[l−1]
遍历所有长度为 k+1k+1k+1 的区间 [i,i+k][i, i + k][i,i+k]，找到其中区间和最大值即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度
* 构造前缀和数组：O(n)O(n)O(n)
* 枚举所有长度为 k+1k+1k+1 的区间：O(n)O(n)O(n)
* 总体复杂度：O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
钞票问题
题目大意
你有三种钞票面值：1元、5元、11元。现在你需要刚好凑出 n 元，问最少需要多少张钞票。
题意分析
这是一个典型的 完全背包问题，每种钞票可以使用任意多次，目标是最小化使用的张数，凑出固定的金额。
解题思路
我们设 dp[i] 表示凑出 i 元 需要的最少钞票数。
状态表示：
* dp[i]：表示凑出金额 i 所需的最少钞票数。
初始条件：
* dp[0] = 0：凑出 0 元不需要任何钞票。
* 其他 dp[i] 初始设为一个很大的值（比如 2e6 或 INT_MAX/2），表示尚未计算过。
状态转移方程推导：
我们有三种钞票：1、5、11 元。
我们考虑金额 i 时，它可能是由以下几种方式得到的：
* 从 i-1 元加上一张 1元 的钞票。
* 从 i-5 元加上一张 5元 的钞票（前提是 i ≥ 5）。
* 从 i-11 元加上一张 11元 的钞票（前提是 i ≥ 11）。
所以我们有状态转移方程：
dp[i]=min(dp[i−1]+1, dp[i−5]+1, dp[i−11]+1)dp[i] = \min(dp[i-1] + 1,\ dp[i-5] + 1,\ dp[i-11] + 1)dp[i]=min(dp[i−1]+1, dp[i−5]+1, dp[i−11]+1)
当然，i-5 和 i-11 必须 ≥ 0。
这就是完全背包的标准套路：用物品来更新状态，每个状态都由更小的状态转移而来。
最终答案：
dp[n]dp[n]dp[n]
时间复杂度解析
* 时间复杂度：O(n)O(n)O(n)，每个金额只被遍历一次，常数为 3。
* 空间复杂度：O(n)O(n)O(n)，用了一个一维数组 dp 存状态。
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
数字金字塔问题
题目大意
给定一个数字金字塔，共有 n 行，每行包含对应数量的正整数。
从金字塔顶端出发，每一步可以向左下方或右下方移动，求路径上数字和的最大值。
题意分析
这是一个经典的二维动态规划问题。
* 从顶部到底部的路径有很多条，但每一步只能往左下或右下走。
* 需要找到一条路径，使得路径上的数字和最大。
解题思路
状态定义
设 dp[i][j] 表示从顶端到第 i 行第 j 个数字位置的最大路径和。
状态转移
对于第 i 行第 j 个数字，它可以从上一行的两个位置转移而来：
* dp[i-1][j-1] （左上方）
* dp[i-1][j] （右上方）
因此，
dp[i][j]=value[i][j]+max(dp[i−1][j−1],dp[i−1][j])dp[i][j] = \text{value}[i][j] + \max(dp[i-1][j-1], dp[i-1][j])dp[i][j]=value[i][j]+max(dp[i−1][j−1],dp[i−1][j])
其中，dp[i-1][j-1] 和 dp[i-1][j] 需合法存在。
边界条件
* 顶点：dp[1][1] = value[1][1]
* 对于每一行的第一个和最后一个元素，只能从一个位置转移。
最终答案
最后一行 dp[n][j] 的最大值就是所求路径最大和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度和空间复杂度
* 时间复杂度：O(n2)O(n^2)O(n2)
* 空间复杂度：O(n2)O(n^2)O(n2)，可以优化成 O(n)O(n)O(n)（只保留上一行数据）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
传球游戏
题目大意
有 nnn 个同学围成一个圆圈，编号从 111 到 nnn。球从编号为 111 的同学开始传，传球规则是每次只能传给左右相邻的同学（即球可以传给当前同学的左边或右边）。问传了 mmm 次球后，球又回到编号为 111 的同学，有多少种不同的传球方法。
两种传球方法被认为不同当且仅当球的传递顺序（即每次接球的同学编号组成的序列）不同。
题意分析
* 圆圈中每个同学都有两个邻居：左邻居和右邻居。
* 起点固定是同学 111。
* 传球 mmm 次后回到同学 111，计算所有可能的传球路径数。
* 因为路径顺序不同即为不同方法，所以统计所有符合条件的路径数量。
解题思路
使用动态规划（DP）模拟传球过程：
定义状态：
* dp[i][j]dp[i][j]dp[i][j]：表示传球进行了 iii 次，球现在在编号为 jjj 的同学手中的方法数。
状态转移：
* 因为每次只能传给左右邻居，所以
dp[i][j]=dp[i−1][left(j)]+dp[i−1][right(j)]dp[i][j] = dp[i-1][left(j)] + dp[i-1][right(j)]dp[i][j]=dp[i−1][left(j)]+dp[i−1][right(j)]
其中，左邻居 left(j)=j−1left(j) = j-1left(j)=j−1（若 j=1j=1j=1，则左邻居是 nnn），右邻居 right(j)=j+1right(j) = j+1right(j)=j+1（若j=nj=nj=n，则右邻居是 111）。
初始条件：
* dp[0][1]=1dp[0][1] = 1dp[0][1]=1，因为传球开始时球在同学 111 手中，且传球次数为 0。
目标：
* 计算 dp[m][1]dp[m][1]dp[m][1]，即传球了 mmm 次后球回到同学 111 的方法数。
时间复杂度分析
* 状态数量为 m×nm \times nm×n，
* 每次转移花费 O(1)O(1)O(1) 时间，
* 总时间复杂度为 O(mn)O(mn)O(mn)，满足题目要求。
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
奶牛分群
题目大意
有 NNN 头奶牛组成一个群，群体可能在三岔路口分裂。分裂条件是：如果群体能恰好分成两部分，且这两部分奶牛数目相差为 KKK，则分裂成两个群，否则不分裂。问最终会有多少群奶牛静静吃草。
题意分析
* 传入当前奶牛数 xxx。
* 判断是否满足分裂条件：
* x>Kx > Kx>K，且 (x−K)(x - K)(x−K) 是偶数；
* 否则不分裂，返回1表示当前群数。
* 满足条件则分裂为两个群，大小分别为 x−K2\frac{x - K}{2}2x−K 和 x+K2\frac{x + K}{2}2x+K 。
* 递归求两个子群的最终群数之和。
解题思路
用递归实现，核心逻辑是：
1. 判断当前奶牛数是否满足分裂条件。
2. 不满足直接返回1。
3. 满足则递归求左右两部分的群数。
4. 返回左右部分群数之和。
代码演示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
国王的魔镜
题目大意
国王有一个魔镜，每次将项链的一端接触镜面，会使整条项链复制一份翻转后的副本并接在原项链尾部。
例如，初始为 ABABAB：
* 第一次镜像后：AB→ABBAAB \rightarrow ABBAAB→ABBA
* 第二次镜像后：ABBA→ABBAABBAABBA \rightarrow ABBAABBAABBA→ABBAABBA
* 第三次镜像后：ABBAABBA→ABBAABBAABBAABBAABBAABBA \rightarrow ABBAABBAABBAABBAABBAABBA→ABBAABBAABBAABBA
给定最终的字符串，求最初可能的最短项链长度。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
观察发现，每次操作是将字符串翻转后接在原串末尾：
* 设初始字符串为 S0S_0S0 ，长度为 lll；
* 镜像一次：S1=S0+rev(S0)S_1 = S_0 + \text{rev}(S_0)S1 =S0 +rev(S0 )，长度 2l2l2l；
* 镜像两次：S2=S1+rev(S1)S_2 = S_1 + \text{rev}(S_1)S2 =S1 +rev(S1 )，长度 4l4l4l；
* 依此类推，最终长度为 L=l⋅2kL = l \cdot 2^kL=l⋅2k；
题目给定的是一个最终结果 SSS，我们需要从 SSS 中还原出最初的项链，即找出最短的字符串 sss，使得不断镜像可以构造出原串。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
从题目定义反向思考：
每次镜像形成的是：S→S+rev(S)S \rightarrow S + \text{rev}(S)S→S+rev(S)。
因此原串可以每次都从中间折半检查是否回文对称，如果是，则可能是某一次镜像的结果，可以继续还原。
我们采用如下策略：
1. 当前字符串长度为 LLL；
2. 判断前一半 S[0,L/2−1]S[0, L/2 - 1]S[0,L/2−1] 是否等于后一半的翻转；
* 即：S[0,L/2−1]==rev(S[L/2,L−1])S[0, L/2 - 1] == \text{rev}(S[L/2, L - 1])S[0,L/2−1]==rev(S[L/2,L−1])；
3. 若成立，说明这个串是由 L/2L/2L/2 长度的字符串镜像而来，继续向下处理；
4. 否则，无法继续折叠，当前字符串即为最短原始项链。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每次字符串长度减半，共最多 log2n\log_2 nlog2 n 次；
* 每次比较一半的字符串是否为翻转，代价 O(n)O(n)O(n)；
* 总体时间复杂度为 O(n)\boxed{O(n)}O(n) ，因为每个字符最多比较一次。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
ZZC 种田
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目大意
给定一个长为 xxx、宽为 yyy 的矩形田地，每次可以种一个正方形区域，体力消耗等于这个正方形的周长，不能重叠种地。
求：种满这块矩形田地的最小体力值总和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
体力消耗 = 所种正方形周长总和，而每次种的正方形不能重复、不能重叠，我们的目标是用若干个不重叠的正方形，完全铺满 x×yx \times yx×y 的矩形，使得总周长最小。
关键思路：递归 + 贪心
从 x×yx \times yx×y 这块田开始，每次都贪心种一个最大的正方形（边长为 min(x,y)\min(x, y)min(x,y)）：
* 体力消耗：4×min(x,y)4 \times \min(x, y)4×min(x,y)（周长）
* 然后剩下一个矩形：(x−min(x,y))×y(x - \min(x, y)) \times y(x−min(x,y))×y 或 x×(y−min(x,y))x \times (y - \min(x, y))x×(y−min(x,y))
* 不断递归处理剩余的区域
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
这是一个经典的「矩形划分为若干个不重叠正方形的最优分割问题」，我们用如下策略：
1. 每次从矩形中剪去最大的正方形（边长 =min(x,y)= \min(x, y)=min(x,y)）
2. 记录它的周长：4×min(x,y)4 \times \min(x, y)4×min(x,y)
3. 然后继续对剩余的矩形递归
4. 终止条件：x=0x = 0x=0 或 y=0y = 0y=0
注意：数据范围极大，x,y≤1016x, y \leq 10^{16}x,y≤1016，所以不能暴力模拟，必须使用 long long 类型，且每步必须贪心取最大正方形。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
每一步减少 min(x,y)\min(x, y)min(x,y) 的倍数次，相当于模拟欧几里得算法，复杂度为 O(logmin(x,y))\mathcal{O}(\log \min(x, y))O(logmin(x,y))。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
蛋糕
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目大意
有 nnn 个长方形蛋糕，第 iii 个蛋糕的尺寸为 Hi×WiH_i \times W_iHi ×Wi （长和宽为整数）。
现在有 kkk 个人，每人要分到一块 面积相同的正方形蛋糕，且正方形的边长必须是整数。
要求求出能分到的正方形蛋糕的最大可能边长。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
约束条件：
1. 切出来的所有正方形边长相同；
2. 每个人得到一块（总共至少切出 kkk 块）；
3. 边长必须是整数。
关键问题：
* 给定一个正方形边长 lenlenlen，如何判断能否切出至少 kkk 块？
* 如果能切出来，则尝试更大的边长；如果不能，则尝试更小的边长。
这就是典型的二分答案思路。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 判断函数 check(len)
对于每个蛋糕 Hi×WiH_i \times W_iHi ×Wi ：
* 能切出的正方形个数是：
⌊Hilen⌋×⌊Wilen⌋\left\lfloor \frac{H_i}{len} \right\rfloor \times \left\lfloor \frac{W_i}{len} \right\rfloor⌊lenHi ⌋×⌊lenWi ⌋
* 累加所有蛋糕的个数，如果总和 ≥k\ge k≥k，则表示边长 lenlenlen 可行。
2. 二分搜索边长
* 左边界 l=1l = 1l=1（最小可能的边长）；
* 右边界 r=max(Hi,Wi)r = \max(H_i, W_i)r=max(Hi ,Wi )（最大可能的边长）；
* 二分过程中：
* 如果 check(mid) 为真，说明可以切得更大，l=mid+1l = mid + 1l=mid+1；
* 否则缩小，r=mid−1r = mid - 1r=mid−1；
* 最终答案是最大的可行边长。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每次 check 需要遍历 nnn 个蛋糕，复杂度 O(n)O(n)O(n)；
* 二分次数是 O(logmax(Hi,Wi))≈O(log105)≈17O(\log \max(H_i, W_i)) \approx O(\log 10^5) \approx 17O(logmax(Hi ,Wi ))≈O(log105)≈17；
* 总复杂度 O(nlogM)O(n \log M)O(nlogM)，其中 M=max(Hi,Wi)M = \max(H_i, W_i)M=max(Hi ,Wi )；
* 在 n≤105n \le 10^5n≤105 范围内可轻松运行。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现
小苹果
题目大意
桌上有 nnn 个编号为 111 到 nnn 的苹果排成一列。每天，小苞从当前序列的第一个苹果开始，按“拿一个苹果，跳过两个苹果，拿一个苹果，跳过两个苹果……”的规则拿走苹果，被拿走的苹果移除，剩余的苹果重新排列。问：
* 多少天后所有苹果被拿完？
* 编号为 nnn 的苹果是哪一天被拿走的？
题意分析
* 每天的规则是从序列左侧第一个苹果开始，间隔两苹果拿一个，即序列中位置为 pospospos 满足 pos≡1(mod3)pos \equiv 1 \pmod{3}pos≡1(mod3) 的苹果当天被拿走。
* 被拿走的苹果被移除，剩余的苹果重新排列，继续下一天。
* 需要求编号 nnn 的苹果被拿走的天数，以及所有苹果被拿完所需天数。
解题思路
* 观察到每天被拿走的苹果在当前序列中的位置是 1,4,7,10,…1, 4, 7, 10, \ldots1,4,7,10,…，即位置为 pos≡1(mod3)pos \equiv 1 \pmod{3}pos≡1(mod3)。
* 剩余苹果的序号需要转换到下一天的位置。
* 编号为 nnn 的苹果被拿走的天数即为它经过若干次“剩余序号变换”后，首次出现在位置 pos≡1(mod3)pos \equiv 1 \pmod{3}pos≡1(mod3) 的天数。
* 总天数是所有苹果被拿完的天数，即编号 nnn 苹果被拿走的天数。
基于以上，我们用循环模拟这个“位置更新”过程：
* 初始化天数 sum=0sum=0sum=0。
* 每次循环：
* 天数加一。
* 判断当前苹果编号是否满足当天被拿的条件 nn % 3 == 1n。
* 计算下一天编号更新：
n=n−n−13−1n = n - \frac{n-1}{3} - 1n=n−3n−1 −1
* 直到 nnn 减至 0（即苹果被拿完）。
复杂度分析
* 每天苹果数量减少大约三分之一，循环次数最多约为 log1.5(n)\log_{1.5}(n)log1.5 (n)，效率非常高，适合 nnn 高达 10910^9109。
代码实现
二叉树最近公共祖先（暴力版）
题目大意
给定一个用数组表示的二叉树，根节点下标为 1。
节点下标 xxx 的左孩子是 2x2x2x，右孩子是 2x+12x+12x+1（若存在）。
需要对 qqq 次查询，给定两个节点编号 id1,id2id_1, id_2id1 ,id2 ，求它们的最近公共祖先（LCA）节点编号。
题意分析
* 节点编号即数组下标，表示树结构。
* 最近公共祖先定义为两个节点的公共祖先中离根最近的那个节点。
* 这里是完全二叉树（虽然节点可能不满），节点父节点编号为 ⌊x/2⌋\lfloor x/2 \rfloor⌊x/2⌋。
* 目标是快速求多个节点对的 LCA。
解题思路
* 对于任意两个节点 u,vu, vu,v，不断将编号较大的节点上移其父节点（x→⌊x/2⌋x \to \lfloor x/2 \rfloorx→⌊x/2⌋），直到两者相等为止。
* 该公共节点即为 LCA。
* 这是利用二叉树性质，父节点编号为 ⌊x/2⌋\lfloor x/2 \rfloor⌊x/2⌋，向上跳到同一深度再相等即可。
* 时间复杂度均摊较高，但对于 q≤105q \leq 10^5q≤105，且编号最大 n≤105n \leq 10^5n≤105，暴力方法可行。
复杂度分析
* 每次查询最坏情况跳转 logn\log nlogn 次，qqq 次查询共 O(qlogn)O(q \log n)O(qlogn)，符合题目要求。
代码实现
逃离迷宫
题目大意
给定一个 M×NM \times NM×N 的迷宫地图，其中：
* @ 表示起点位置；
* . 表示可以通行的安全格子；
* # 表示有陷阱，不能通行；
* * 表示宝物位置。
要求从起点出发，经过最少的格子数（包含起点），找到宝物。如果无法到达宝物，输出 -1。
输入包含多组数据，以 0 0 结束。
题意分析
* 迷宫由多个格子组成，起点和宝物各唯一。
* 需要在迷宫中找到从起点到宝物的最短路径长度。
* 路径只能经过安全格子（. 和 @ 起点），不能经过陷阱格子（#）。
* 典型的迷宫最短路径问题，适合用 广度优先搜索（BFS）。
解题思路
* 使用 BFS 从起点开始搜索。
* 队列中保存当前坐标和走过的步数。
* 遍历四个方向（上下左右），只访问没有访问过且安全的格子。
* 如果找到宝物，输出当前步数。
* BFS 结束仍未找到宝物，输出 -1。
时间复杂度
* BFS 最多遍历 M×NM \times NM×N 个格子，每个格子最多访问一次。
* 时间复杂度为 O(M×N)O(M \times N)O(M×N)。
* M,N≤20M, N \leq 20M,N≤20，效率足够。
代码实现
逃离迷宫2
题目大意
给定一个 n×mn \times mn×m 的迷宫，由空地 . 和障碍物 # 组成。
要求从左上角格子 (1,1)(1,1)(1,1) 走到右下角格子 (n,m)(n,m)(n,m)，输出最短路径步数（每步移动到上下左右相邻格子），如果无法到达输出 -1。
题意分析
* 迷宫格子小（n,m≤10n,m \leq 10n,m≤10），可用 DFS 搜索所有路径，找出最短路径。
* 每次 DFS 递归尝试四个方向，剪枝避免重复访问。
* 记录最短步数。
* 起点终点必为通路，保证有效起点和终点。
解题思路
* 使用 DFS 深度优先搜索遍历所有可能路径。
* 维护访问标记数组 vis，防止走回头路导致死循环。
* 当走到终点时，更新当前路径长度最小值。
* 最终输出最短路径长度或 -1。
时间复杂度
* DFS 最坏情况下搜索全部空地格，格子数最多为 n×m≤100n \times m \leq 100n×m≤100，复杂度约为 O(4n×m)O(4^{n \times m})O(4n×m)，但实际由于剪枝访问且网格较小，运行可接受。
* 适合小规模迷宫。
代码实现
【DFS】八皇后问题
题目大意
给定一个 n×nn \times nn×n 的棋盘，要求放置 nnn 个棋子，使得：
* 每行恰好一个棋子；
* 每列恰好一个棋子；
* 每条对角线上最多一个棋子（包括主对角线及所有平行对角线）；
输出所有满足条件的放置方案，方案以行号从1到nnn表示，序列中第iii个数字表示第iii行棋子所在的列号。
要求按字典序输出前三个解，并输出所有解的总数。
题意分析
* 本题即经典的 nnn 皇后问题变种。
* 约束条件保证每行列和两条对角线不能有重复棋子。
* 利用 DFS 回溯，逐行放置棋子，遇冲突则回溯。
解题思路
* 使用三个布尔数组分别标记列、主对角线、副对角线是否已被占用：
* dy[i]：第 iii 列是否有棋子。
* add[i+x]：主对角线标记。这里 i+xi+xi+x 保证从左上到右下的对角线索引唯一。
* minu[i - x + n]：副对角线标记。这里偏移 +n+n+n 避免负数索引。
* 每行从列1到nnn尝试放置，若未冲突则递归放下一行。
* 每找到一个合法解，计数器加一，并在前三个解时输出。
* 最终输出总解数。
复杂度分析
* 该算法最坏情况下时间复杂度约为 O(n!)O(n!)O(n!)，因需要枚举排列。
* 对于 n≤13n \leq 13n≤13，回溯剪枝可接受。
代码实现
神庙迷宫1
题目大意
给定一个 n×mn \times mn×m 的迷宫，起点在左上角 (1,1)(1,1)(1,1)，终点在右下角 (n,m)(n,m)(n,m)。
迷宫中 . 表示可通行格子，# 表示障碍物。
判断是否存在路径可以从起点走到终点，只能上下左右移动。
题意分析
* 典型的网格路径搜索问题。
* 需要判断起点是否能通过合法路径达到终点。
* 适合使用广度优先搜索（BFS）遍历迷宫。
* 维护访问数组避免重复访问。
解题思路
* 使用队列实现 BFS，从起点开始搜索可达的相邻通路格子。
* 搜索过程中标记访问。
* 搜索结束后检查终点是否被访问。
* 若访问过输出 YES，否则输出 NO。
复杂度分析
* BFS 最坏遍历全部格子，时间复杂度 O(n×m)O(n \times m)O(n×m)，符合题目限制。
代码实现
神庙迷宫2
题目大意
给定一个 n×mn \times mn×m 的迷宫地图，地图中 . 表示空地可以通行，# 表示障碍物不能通行。
起点为左上角格子 (1,1)(1,1)(1,1)，终点为右下角格子 (n,m)(n,m)(n,m)。
要求找出从起点到终点的最短路径长度（包含起点和终点所在格子），如果无法到达输出 -1。
题意分析
* 需要计算网格中两点间最短路径长度。
* 经典的网格 BFS 问题，利用队列层层扩展，记录距离。
* 访问数组 vis 除了标记访问外，也存储当前节点到起点的距离。
* 距离即为从起点到当前格子的步数。
解题思路
* 使用 BFS，从起点开始搜索可达的相邻格子。
* 记录访问并标记距离，距离初始为1（表示起点）。
* 当到达终点，直接输出距离-1（因为起点计为1，但题目要求路径长度一般是步数，即格子数减1）。
* 搜索结束后如果终点未访问，输出 -1。
时间复杂度分析
* BFS 最多访问所有格子一次，时间复杂度为 O(n×m)O(n \times m)O(n×m)。
* 适合 n,m≤40n,m \leq 40n,m≤40 的限制。
代码实现
神庙迷宫3
题目大意
给定一个 n×mn \times mn×m 的迷宫地图，. 表示空地，# 表示障碍。
起点为左上角 (1,1)(1,1)(1,1)，求每个格子到起点的最短距离（步数）。
若该格子不可达或为障碍，则输出 -1。
输出整个迷宫对应的距离矩阵。
题意分析
* 需要求从起点到每个格子的最短距离，属于多源最短路中的单源多点问题。
* 适用广度优先搜索（BFS）完成。
* BFS从起点扩展，vis[i][j]记录距离（步数+1，方便处理）。
* 访问障碍物不计距离且不可通行。
* BFS结束后，对于未访问的格子（vis[i][j]==0），输出 -1。
解题思路
* 初始化 vis 数组为0，表示未访问。
* 起点 vis[1][1]=1，距离起点为0。
* 使用队列实现 BFS，依次扩展相邻四个方向。
* 如果新位置合法且非障碍且未访问，更新距离并入队。
* BFS结束后，遍历输出距离矩阵，未访问格子输出 -1。
复杂度分析
* BFS遍历所有格子一次，时间复杂度 O(n×m)O(n \times m)O(n×m)。
* 适用于 n,m≤1000n, m \leq 1000n,m≤1000 的规模。
代码实现
