备战蓝桥杯国赛【day2】
一、数的计算：递归背后的"分形"思维
题目回顾
给定自然数nnn，可以在其左侧不断添加不超过前一个数一半的数字，问能生成多少个数。
初看：简单的递归
deff(n):ifn==1:return1ans=1# 不作任何处理，算一个foriinrange(1,n//2+1):ans+=f(i)returnans深度思考：这其实是"记忆化搜索"的裸题
这道题的本质是什么？每一个数nnn的生成方案，完全依赖于所有小于等于n/2n/2n/2的数的方案之和。这形成了一棵天然的递归树：
f(6) = 1 + f(1) + f(2) + f(3) = 1 + 1 + (1+f(1)) + (1+f(1)) = 6但等等——如果n≤1000n \leq 1000n≤1000，纯递归会不会超时？
答案是：不会。因为递归深度最多log2n\log_2 nlog2n，且每个f(i)f(i)f(i)被重复计算的次数有限。但如果nnn扩大到10510^5105呢？这就引出了动态规划的思想：
dp=[0]*(n+1)dp[1]=1foriinrange(2,n+1):dp[i]=1+sum(dp[1:i//2+1])更进一步，利用前缀和优化，可以将O(n2)O(n^2)O(n2)降到O(n)O(n)O(n)：
dp[1]=prefix[1]=1foriinrange(2,n+1):dp[i]=1+prefix[i//2]prefix[i]=prefix[i-1]+dp[i]💡感悟：递归是"自顶向下"的诗意，DP是"自底向上"的务实。好的算法工程师，能在两者之间自由穿梭。
二、时间加法：不要过度工程化
题目
给定aaa点bbb分，求ttt分钟后的时间。
我的解法：利用 Python 的datetime
fromdatetimeimportdatetime,timedelta a=int(input())b=int(input())t=int(input())time1=datetime(2000,1,1,a,b)delta=timedelta(minutes=t)time1+=deltaprint(time1.hour)print(time1.minute)反思：这是"优雅"还是"过度设计"？
用datetime确实简洁，但它背后创建了整个日期对象，调用了 C 扩展，对于这么简单的问题是否杀鸡用牛刀？
更底层的思考：
# 纯数学解法total=a*60+b+tprint(total//60%24)print(total%60)| 方案 | 时间复杂度 | 空间复杂度 | 可读性 | 适用场景 |
|---|---|---|---|---|
| datetime | O(1)O(1)O(1) | 较高 | 极高 | 复杂日期计算 |
| 纯数学 | O(1)O(1)O(1) | O(1)O(1)O(1) | 高 | 简单时间运算 |
💡感悟：工程中没有绝对的"最好"，只有"最合适"。
datetime胜在语义清晰，数学法胜在零依赖。面试时，先写数学法展示基本功，再提datetime展示工程意识——双保险。
三、人物相关性分析：双指针的华尔兹
题目
统计文本中Alice和Bob作为独立单词出现，且相距不超过KKK个字符的次数。
核心难点
- 单词边界：
Bobbi不算Bob，需要\b词边界 - 字符距离：不是单词距离，是字符位置距离
- 效率：字符串长度可达10610^6106，暴力O(n2)O(n^2)O(n2)会 TLE
我的解法：预处理 + 滑动窗口
importre k=int(input())s=input()# 预处理：找出所有 Alice 和 Bob 的起始位置A=[m.start()forminre.finditer(r'\bAlice\b',s)]# Alice 起始位置B=[m.start()forminre.finditer(r'\bBob\b',s)]# Bob 起始位置count=0left=0right=0lenB=len(B)forainA:# Alice 占据 [a, a+5)，Bob 占据 [b, b+3)# 两者距离 = max(起点差) - min(终点差) 的某种形式...# 实际上，题目定义的"之间字符数"需要仔细处理L=a-k-3# Bob 最早可以出现的位置R=a+k+5# Bob 最晚可以出现的位置# 移动左指针：找到第一个 >= L 的 Bobwhileleft<lenBandB[left]<L:left+=1# 移动右指针：找到第一个 > R 的 Bobwhileright<lenBandB[right]<=R:right+=1# [left, right) 内的 Bob 都满足条件count+=right-leftprint(count)算法剖析：为什么这是O(n)O(n)O(n)？
关键在于两个指针都只向右移动：
left指针：一旦越过某个 Bob，再也不会回头right指针：随着 Alice 位置右移，R增大，right也只会右移
这形成了经典的滑动窗口模式，总时间复杂度O(∣A∣+∣B∣)O(|A| + |B|)O(∣A∣+∣B∣)，即线性。
边界条件的艺术
这里的L和R计算需要极其小心：
Alice长度为 5，Bob长度为 3- 如果 Alice 在 Bob 前面，距离 =
B - (A + 5) - 如果 Bob 在 Alice 前面，距离 =
A - (B + 3)
统一处理：
有效区间 = [A - K - 3, A + K + 5]💡感悟：双指针算法的精髓在于单调性。当一个问题具有"如果iii满足条件，则i+1i+1i+1也可能满足"的单调特征时，双指针就是你的华尔兹舞伴。
四、最大距离：暴力中的数学直觉
题目
数列中两元素距离定义为∣i−j∣+∣ai−aj∣|i-j| + |a_i - a_j|∣i−j∣+∣ai−aj∣，求最大值。
数据范围
n≤1000n \leq 1000n≤1000，允许O(n2)O(n^2)O(n2)暴力。
n=int(input())ls=list(map(int,input().split()))num=-1foriinrange(n):forjinrange(i+1,n):cur=j-i+abs(ls[j]-ls[i])num=max(num,cur)print(num)但如果n≤105n \leq 10^5n≤105呢？
绝对值展开后：
∣i−j∣+∣ai−aj∣=max{(i+ai)−(j+aj)(i−ai)−(j−aj)(j+aj)−(i+ai)(j−aj)−(i−ai)|i-j| + |a_i - a_j| = \max\begin{cases} (i + a_i) - (j + a_j) \\ (i - a_i) - (j - a_j) \\ (j + a_j) - (i + a_i) \\ (j - a_j) - (i - a_i) \end{cases}∣i−j∣+∣ai−aj∣=max⎩⎨⎧(i+ai)−(j+aj)(i−ai)−(j−aj)(j+aj)−(i+ai)(j−aj)−(i−ai)
即：
max(∣(i+ai)−(j+aj)∣,∣(i−ai)−(j−aj)∣)\max(|(i+a_i) - (j+a_j)|, |(i-a_i) - (j-a_j)|)max(∣(i+ai)−(j+aj)∣,∣(i−ai)−(j−aj)∣)
所以只需维护(i+ai)(i+a_i)(i+ai)和(i−ai)(i-a_i)(i−ai)的最大最小值，O(n)O(n)O(n)搞定！
# 进阶版 O(n) 解法max1=max2=-float('inf')min1=min2=float('inf')fori,xinenumerate(ls):max1=max(max1,i+x)min1=min(min1,i+x)max2=max(max2,i-x)min2=min(min2,i-x)print(max(max1-min1,max2-min2))💡感悟：绝对值问题，第一反应永远是去绝对值分类讨论。这不仅是技巧，更是一种代数直觉——把几何问题转化为线性问题。
五、进制转换：计算机世界的"翻译官"
题目
实现任意进制（2-16）之间的转换。
核心代码
int_to_char="0123456789ABCDEF"char_to_int={ch:ifori,chinenumerate(int_to_char)}deftrans(s,n,m):# Step 1: N进制 -> 十进制num=0forchins:num=num*n+char_to_int[ch]# Step 2: 十进制 -> M进制ifnum==0:return"0"ans=""whilenum!=0:ans+=int_to_char[num%m]num//=mreturnans[::-1]进制转换的数学本质
任意进制转十进制：
(2022)9=2×93+0×92+2×91+2×90=1472(2022)_9 = 2 \times 9^3 + 0 \times 9^2 + 2 \times 9^1 + 2 \times 9^0 = 1472(2022)9=2×93+0×92+2×91+2×90=1472
代码中的num = num * n + char_to_int[ch]正是霍纳法则（Horner’s Method），将O(n)O(n)O(n)次乘法优化到最优。
十进制转任意进制：
本质是不断取模，相当于：
x=dk⋅mk+dk−1⋅mk−1+⋯+d0x = d_k \cdot m^k + d_{k-1} \cdot m^{k-1} + \cdots + d_0x=dk⋅mk+dk−1⋅mk−1+⋯+d0
每次num % m得到最低位d0d_0d0，然后num //= m去掉最低位。
💡感悟：进制转换教会我们——所有进制都是十进制的"投影"。十进制是人类的直觉，二进制是计算机的母语，而算法是它们之间的翻译官。
六、今日心法总结
┌─────────────────────────────────────────┐ │ 1. 递归 → 找重叠子问题 → 考虑记忆化/DP │ │ 2. 字符串匹配 → 预处理 + 双指针/滑动窗口 │ │ 3. 绝对值最值 → 拆四种情况 → 维护极值 │ │ 4. 进制转换 → 霍纳法则 + 取模迭代 │ │ 5. 工程思维 → 没有最好，只有最合适 │ └─────────────────────────────────────────┘写在最后
刷题不是为了背诵模板，而是为了训练思维的模式识别。
当你看到"左边添加不超过一半"时，能否想到递归树？当你看到"两个元素距离限制"时，能否想到滑动窗口？当你看到"绝对值求最值"时，能否想到分类讨论？
这些直觉，才是算法竞赛给予我们最宝贵的财富。
“代码会过时，思维永流传。”
如果你也在刷题路上，欢迎留言交流。算法的世界，一个人走很快，一群人走很远。🚀