【小赛1】蓝桥杯双周赛第5场（小白）思路回顾

我的成绩：小白(5/6)

完稿时间：2024-2-13

比赛地址：https://www.lanqiao.cn/oj-contest/newbie-5/

相关资料：

1、出题人题解：“蓝桥杯双周赛·第5次强者挑战赛/小白入门赛”出题人题解 - 知乎 (zhihu.com)

2、矩阵快速幂：算法学习笔记(4)：快速幂 - 知乎 (zhihu.com)

• 讲得挺好的，从快速幂到矩阵快速幂，以及在求解递推式中的应用。

3、矩阵乘法结合律证明：如何把矩阵乘法结合律的证明写得简单易懂（针对初学者） - 知乎 (zhihu.com)

• 我突然疑惑矩阵乘法为什么会满足结合律，找了篇文章，还没来得及看

一、我思路回顾

1、十二生肖

思路：

此题令我有点意外，显然2024是龙年，在12生肖中排第5个，print即可。

代码：

print(5)

2、欢迎参加福建省大学生程序设计竞赛

思路：

题中说将相同题数，相同罚时的队伍归为一类，那么如果每行输入作为一个元素，问题就变成了：有多少个不同的元素。而刚好集合数据结构就具有元素不重复的特点，将所有输入数据加入集合，输出集合中元素数量即可。

在python中，输入是字符串，将它作为字典的键就可实现去重。

代码：

if __name__ == '__main__':n = int(input())d = {}for i in range(n):x = input()if x not in d:d[x] = 1print(len(d))

3、匹配二元组的数量

思路：

这题想了一会儿，看到比值就想一项，但移完之后呢？

$\frac{a_i}{j}=\frac{a_j}{i}$，变形一下，$i{a}_i=j{a}_j$，于是可以将数组A的每一元素乘以它的下标，得新数组B，后统计B中重复元素数量。（注这里下标从1开始）

出现2次的算1一个匹配二元组，出现3次的算3个······出现x次的算组合数$C_x^2$，即$\frac{x!}{2}$。

代码：

def f(x):'''x的阶乘'''r = 1for i in range(x):t = i + 1r *= t return rif __name__ == '__main__':n = int(input())nums = [int(x) for x in input().split(' ')]d = {}for i, num in enumerate(nums):nums[i] = (i + 1) * num for num in nums:if num not in d:d[num] = 0d[num] += 1result = 0for key in d:result += f(d[key]) // 2print(result)

4、元素交换

思路：

这题像脑筋急转弯，初看非常的手足无措。

数组中有N个0和N个1，“不存在连续的0或1”，那合规数组仅两种：1）010101...，2）101010...，于是逐项对比输入与合规数组，得不同的项的数量c，而每次交换可以把两个不同项变为相同，所以交换次数为n/2 。

那为什么，每次交换可以减少两个不同？

因为1对上0的数量，必然和0对上1的数量一样。不妨令N为5，假设合规数组中，有3个1没匹配上。那么必然有2个1匹配上了，那么输入中还剩3个1，让合规数组中的0也有3个匹配不上。

合规：0 1 0 1 0 1 0 1 0 1
输入：  0   0   0   1   1

在比赛中，我经常就只能先将输入胡乱摆弄一阵，然后去猜规律，有时猜得对，有时猜得半对，有时猜得不对。在下一题，下棋的贝贝中，就是先草率地猜错了，然后又重新猜。

代码：

def jdz(x):'''绝对值'''return x if x >= 0 else -xif __name__ == '__main__':n = int(input())nums = [int(x) for x in input().split(' ')]# 合规数组h1 = [0, 1] * n h2 = [1, 0] * n# 对比差距c1 = sum([jdz(h1[i] - nums[i]) for i in range(len(nums))])c2 = sum([jdz(h2[i] - nums[i]) for i in range(len(nums))])c = min(c1, c2)r = c // 2  # 每次交换可以减少两个不同print(r)

5、下棋的贝贝

思路：

题意还比较清晰，在整数格子上放棋子，横竖挨着的棋子算相邻，相邻的棋子有一条边，如果边的总数为e，输出$2\ast e$ 。

于是我开始在草稿纸上施法，期待老天爷降下神谕。很快我就觉得，这是一个类似等差的数列，之后隔两项的差都是3。然而提交之后的error告诉我，还是高兴得太早了。

于是我又猜了第二版。有的棋子放下时不增加边（1号）或只会增加一条边，如下图中带圈圈的；有的棋子放下时增加两条边，如下图中不带圈圈的。然后统计带圈圈类型的棋子数量。

设总棋子数为m，平方根向下取整为n，于是带圈圈的棋子数single_edge分两类统计：

1. 一个是内侧正方形中的（如图中蓝框），数量为2n-1
2. 外正方形的，会有两个临界值，当m的值超过它们时，带圈圈的棋子数加1。

如果每个棋子会产生两条边，那么总边数为$2m$。然后减去只产生一条边的棋子数量（因为一号棋子不产生边，可以抵两个只产生一条边的棋子），就可以得到边的总数。

为什么以上方法就是放置棋子的最佳策略（产生最多的边）？

大家可以思考一下。

代码：

import mathdef method2(m):'''边的数量'''n = math.sqrt(m)n = math.floor(n)single_edge = n * 2if m >= n**2 + 1:single_edge += 1if m >= n**2 + 1 + n:single_edge += 1 r = 2 * m - single_edgereturn rif __name__ == '__main__':m = int(input())r = method2(m)print(r * 2)

---

二、补题

6、方程

这题当时完全没有思路，希望我下次会有进步。如果还没有，就多下几次！

思路：

有两个步骤。第一步是得到递推式，但n数据范围是$[1,10^9]$，逐步递推时间复杂度$O(n)$太高。于是第二步用到矩阵快速幂，将复杂度降到$O(logn)$。

1、得到递推式

题为$x+\frac{1}{x}=k$，求$x^n+\frac{1}{x^n}$的值。令$f(n)=x^n+\frac{1}{x^n}$，则：$kf(n)=(x+\frac{1}{x})(x^n+\frac{1}{x^n})=f(n+1)+f(n-1)$。

即：$f(n+1)=kf(n)-f(n-1)$

又易得：$f(0)=2$，$f(1)=k$ 。

2、矩阵快速幂

这部分参考了文首的资料1和资料2，大家也可以看一下。

a、为什么要有快速幂算法？

在求一个数的n次幂的过程中，比如$10^8=10\ast 10\ast 10\ast 10\ast 10\ast 10\ast 10\ast 10$，需要8次乘法运算。但如果这样算：$10^2=10\ast 10，10^4=10^2\ast 10^2，10^8=10^4\ast 10^4$，只需要3次乘法，这其实是二分的思路。

也就是说，可以以$O(logn)$的时间复杂度计算数x的n次幂$x^n$。

b、矩阵乘法如何计算递推式？

就以本题为例，我们发现$\left[\begin{array}{cc}k& -1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{f}_{n-1}\\ f_{n-2}\end{array}\right]=\left[\begin{array}{c}{f}_n\\ f_{n-1}\end{array}\right]$ ，于是我们每一次矩阵乘法，就是一步递推。

但这有什么用呢，好像莫名奇妙凑出一个矩阵的形式，把简单的问题复杂化。

c、快速幂加上矩阵乘法：快速计算递推式。

令$A=\left[\begin{array}{cc}k& -1\\ 1& 0\end{array}\right]$ ，则：$\left[\begin{array}{c}{f}_n\\ f_{n-1}\end{array}\right]=A\left[\begin{array}{c}{f}_{n-1}\\ f_{n-2}\end{array}\right]=A^2\left[\begin{array}{c}{f}_{n-2}\\ f_{n-3}\end{array}\right]=...=A^{n-1}\left[\begin{array}{c}{f}_1\\ f_0\end{array}\right]$，

看见$A$头上的幂次了吗？将递推的时间复杂度从$O(n)$降到$O(logn)$，我想你已经知道该怎么做了。

代码：

class Matrix:'''封装矩阵乘法'''MOD_NUM = 10**9 + 7def __init__(self, value) -> None:self.v: list = value def mul(self, obj):# 两个矩阵维度分别是(a,b), (b,c)obj: Matrix = obja, b, c = len(self.v), len(self.v[0]), len(obj.v[0])matrix = [[0] * c for i in range(a)]  # 乘积维度：(a,c)r = Matrix(matrix)for i in range(a):for j in range(c):for k in range(b):r.v[i][j] = (r.v[i][j] + self.v[i][k] * obj.v[k][j]) % self.MOD_NUMreturn rdef mi(A: Matrix, n: int) -> Matrix:'''求矩阵A的n次幂'''if n == 1:return Aif n % 2 == 1:return mi(A, n-1).mul(A)else:t = mi(A, n // 2)return t.mul(t)def method(n, k):'''求解一个测试用例'''if n == 1:return k elif n > 1:A = Matrix([[k, -1], [1, 0]])F = Matrix([[k], [2]])  # f(0)=2, f(1)=kR = mi(A, n-1).mul(F)return R.v[0][0]if __name__ == '__main__':m = int(input())for _ in range(m):n, k = map(int, input().split(' '))  # 以前我总用列表推导式print(method(n, k))

---

这次比赛强者级还有3个题，但比赛就没看，相关内容也没咋学，又考虑到时间问题，就不打算补了。

三、小结

本次比赛有小白和强者两个级别，感觉自己还比较菜，于是报了小白。后来发现小白的后3题正是强者级的头三题，这么看来，我在强者级只能写两个题？但问题不大，我对未来仍然抱有一种迷之信心。

*脱节：从实践出发，又要从基础出发

脱节问题在我们的生活中尤其严重。常有人说大学教育与社会需求脱节。然而细看我自己，又何尝不是处处脱节？就如学英语数十年，却不能说英语，学习和运用是脱节的。读英文时脑海里止步于模糊的“英式汉语”，想将心中的地道汉语用英语说出来，自然是困难的，因为缺少了一个从输入英语到地道汉语的过程。盲目期待所谓“英语思维”，于是学习方法本身便是脱节的。汉语是我们的母语，想将它一下子甩掉不太现实。

早在学校的数据结构与算法课程，弊端就已经显现。算法本身被孤立地灌输给我，要我如何能够面对问题分析问题用算法解决问题？大多的算法都只是跟着实现一遍，也大概就算是学过了。诚然，师傅领进门，修行靠个人，学习本就要靠自己的努力。可我就是缺少指导呀。（吐槽）

回看算法的学习，也应该多参加小比赛，多自己写，才能学会自己写。实践中有其独特而珍贵的经验，而且能为学习方向的调整提供指导。

然而，也常听见一个建议：在做的过程中学。但我曾理解得有些片面，于是钟爱教程而疏于理论，止于模仿而失了变通；于是遇到难题抓脑袋，有一段时间，沉陷在反复的焦虑之中。后来有一次zxl对我说，解决不了，就要想想是不是缺了基础知识，又让我一下子觉得：早该这样。

再看算法学习，总专注于比赛、刷题，而不重视系统性的理论学习，同样不合适。望自警醒。

拼命追着跑还是被匆匆拖着跑，都不太好，得一起跑。

回顾此回顾

要常回顾，以免在歧途上发足狂奔。但我目前有一个大问题，就是我太慢了，相当于在路上花费了太多的时间东张西望。此次比赛回顾，写到这句话，我已经花了8小时。比赛本身也才2小时！

这种习惯对于“常回顾”的目标，必然是极大的负担。

---