目录
1. A · B Problem
题目链接
解题思路
Python 代码实现
2.园艺
题目链接
解题思路
Python 代码实现
1.暴力实现（8个用例会超时）
2.动态规划
3.书架还原
题目链接
解题思路
Python 代码实现
1. A · B Problem
输入格式
输入的第一行包含一个正整数 L，表示题目描述中的限制条件。
输出格式
输出一行包含一个整数表示答案。
样例输入 1
2
样例输出 1
1
样例输入 2
3
样例输出 2
5
题目链接
0A · B Problem – 蓝桥云课
解题思路
1. 问题转化：把向量内积拆成两个独立的乘积和
原式 = u+v≤L
2. 预处理：计算每个数的有序因数对数量
定义了数组 yinshu[]，其中 yinshu[k] 表示满足 x*y=k 的正整数有序对 (x,y) 的数量
eg: k=12 时，有序对有 (1,12),(2,6),(3,4),(4,3),(6,2),(12,1)，共 6 对，所以 yinshu[12] = 6
3. 累加所有合法组合
遍历所有可能的 u（从 1 到 L−1）
对每个 u，v 的取值范围是 1 到 L−u
每一组 (u,v) 对应的合法向量对数量是 yinshu[u] * yinshu[v]
把所有这些值累加起来，就是最终的答案
Python 代码实现
import os
import sys
# 请在此输入您的代码
l = int(input())
# l = (ac)+(bd)
# l = u + v
yinshu = [0] * (l+1)
for i in range(1,l+1): # 因数
for j in range(i,l+1,i): # 被除数,i 是 j 的因数
yinshu[j]+=1 # j的因数个数加1，因子个数 = (a,c) 有序对个数
# 12=1×12=2×6=3×4=4×3=6×2=12×1
# (1,12)
# (2,6)
# (3,4)
# (4,3)
# (6,2)
# (12,1)
ans = 0
for u in range(1,l):
maxv = l-u
for v in range(1,maxv+1):
ans += yinshu[u] * yinshu[v]
print(ans)
2.园艺
问题描述
小蓝从左到右种了 n 棵小树，第 i 棵树的高度为 hi，相邻树的间隔相同。
小蓝想挪走一些树，使得剩下的树等间隔分布，且从左到右高度逐渐上升（相邻两棵树高度满足右边的比左边的高），小蓝想知道最多能留下多少棵树。
输入格式
输入的第一行包含一个正整数 nn。
第二行包含 nn 个正整数 h1,h2,…,hn，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数，表示最多能留下的树的数量。
样例输入
6
3 5 4 7 6 7
样例输出
3
样例说明
留下第 11、33、55 棵树，它们等间隔且从左到右高度逐渐上升。
题目链接
0园艺 – 蓝桥云课
解题思路
题目核心：寻找原序列中下标成等差数列、高度成严格递增的最长子序列
这道题的难点在于“等间隔”。一旦公差 $d$ 固定，原序列就被拆分成了 $d$ 条独立的“轨道”。我们只需要在每条轨道上统计连续上升的段长度即可。
-
暴力突破：枚举所有可能的公差 d[1, n]。
-
线性优化：对于固定的 d，利用“贪心+模拟”的思想，遍历所有轨道。
Python 代码实现
1.暴力实现（8个用例会超时）
import os
import sys
# 请在此输入您的代码
n = int(input())
h = list(map(int,input().split()))
max_count = 1
# 遍历间隔
for d in range(1,n):
# 遍历起始位置
for start in range(d):
cur = 1
# 在当前轨道遍历
for i in range(start,n,d):
if h[i] > h[i-d]:
cur += 1
else:
max_count = max(max_count,cur)
cur = 1 # 到当前截断，后面的数字依然还要计算最大
# 每一条轨道跑完，都要更新一次最大值
max_count = max(max_count,cur)
if n//d+1 <= max_count: # 数量不足剪枝
pass
print(max_count)
2.动态规划
暴力框架里，我们写了 for start in range(d)。但在你这段代码里，我们直接 for i in range(d, n)。这是为什么？
因为每一个 i 都在查找它的“前任” i-d：
如果 h[i] > h[i-d]：
说明当前这棵树可以完美地接在 i-d 后面，形成更长的上升序列。那么长度就是：
counts[i] = counts[i-d] + 1
这就好比你在接力赛，你接过了 i-d 手里的棒，并在他的基础上又跑了一程。
如果 h[i] <= h[i-d]：
虽然间隔是对的，但高度不符合“严格递增”。这时候 i 不能接在 i-d 后面，它只能“自立门户”，长度重置为 1。由于初始化已经是 1 了，所以这里不需要写
import os
import sys
# 请在此输入您的代码
n = int(input())
h = list(map(int, input().split()))
max_count = 1
# 枚举公差 d
for d in range(1, n):
# 优化：如果剩余长度不足，提前退出
if n // d + 1 <= max_count: break
# 使用 dp 在轨道上扫描
counts = [1] * n
for i in range(d, n):
if h[i] > h[i-d]:
# 以第i棵树结尾，且公差为d的等间隔上升序列，目前最长是多少
counts[i] = counts[i-d] + 1
max_count = max(max_count, counts[i])
print(max_count)
3.书架还原
问题描述
在一个偏远的图书馆里，有个书架上放着 NN 本书，每本书上都标有一个唯一的编号，从 11 到 NN。
按照规矩，这些书应该按编号从小到大依次排列：11 号书位于最左端，22 号书紧随其后，以此类推，直到 NN 号书在最右端。这样的顺序不仅看起来整齐，也方便读者快速找到想借的书。
可昨天店里人来人往，借书还书忙得不可开交，书架上的顺序出现了错乱。现在，书架上的书变成了 A=(A1,A2,…,ANA=(A1,A2,…,AN)，其中 AiAi 表示第 ii 个位置上的书编号。
管理员决定动手整理书架，但时间有限，他希望用最少的操作把书的顺序恢复到正确的排列。每次操作，他可以挑选书架上任意两本书，交换它们的位置。例如，如果当前排列是 (3,1,2)(3,1,2)，他可以交换第 11 本和第 22 本，得到 (1,3,2)(1,3,2)，再交换第 22 本和第 33 本，得到 (1,2,3)(1,2,3)。
你的任务是帮助管理员计算，最少需要进行多少次操作，才能让书架上的书的编号排列变为 (1,2,…,N)(1,2,…,N)。
输入格式
第一行包含一个整数 NN，表示书架上书的总数。
第二行包含 NN 个空格分隔的整数 A1,A2,…,ANA1,A2,…,AN，表示当前书架上每本书的编号。A1,A2,…,ANA1,A2,…,AN 是一个 11 到 NN 的随机排列。
输出格式
输出一个整数，表示将书架上的书恢复到正确排列所需的最少操作次数。
样例输入
3
3 1 2
样例输出
2
题目链接
0书架还原 – 蓝桥云课
解题思路
题目核心：将一个乱序排列通过最少次数的“两两交换”恢复成递增序列。
这是一个典型的图论模型——置换环。
-
找环：每个元素 Ai 都有一个它应该去的“正确位置”。我们将当前位置指向它目标位置，最终会形成若干个封闭的环。
-
结论：对于一个长度为 k 的环，将其内部元素全部归位需要 k-1 次交换。
-
公式：总操作次数 = sum (ki – 1) = N – (环的个数)。
Python 代码实现
import os
import sys
# 请在此输入您的代码
inputt = sys.stdin.read().split()
n = int(inputt[0])
a = [0] + list(map(int,inputt[1:]))
visted = [False] * (n+1)
cnt = 0
for i in range(1,n+1):
if not visted[i]:
# 发现一个新的环
cnt += 1
curr = i
# 样例：3 1 2
# 环：位置1 -> 书号3 -> 去位置3 -> 书号2 -> 去位置2 -> 书号1 -> 回到位置1
while not visted[curr]:
visted[curr] = True
curr = a[curr]
# 总的最少交换次数 = (环1长度-1) + (环2长度-1) + …
# 简化公式：最少交换次数 = 总书数n – 环的数量
print(n-cnt)
