安卓手机做网站服务器,上海热点新闻,东莞营销型网站建设流程,北京网站建设网站我的成绩#xff1a;小白(5/6) 完稿时间#xff1a;2024-2-13 比赛地址#xff1a;https://www.lanqiao.cn/oj-contest/newbie-5/ 相关资料#xff1a; 1、出题人题解#xff1a;“蓝桥杯双周赛第5次强者挑战赛/小白入门赛”出题人题解 - 知乎 (zhihu.com) 2、矩阵快速幂小白(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、十二生肖2、欢迎参加福建省大学生程序设计竞赛3、匹配二元组的数量4、元素交换5、下棋的贝贝 二、补题6、方程 三、小结*脱节从实践出发又要从基础出发回顾此回顾 一、我思路回顾
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、匹配二元组的数量
思路
这题想了一会儿看到比值就想一项但移完之后呢 a i j a j i \frac{a_i}{j}\frac{a_j}{i} jaiiaj变形一下 i a i j a j ia_ija_j iaijaj于是可以将数组A的每一元素乘以它的下标得新数组B后统计B中重复元素数量。注这里下标从1开始
出现2次的算1一个匹配二元组出现3次的算3个······出现x次的算组合数 C x 2 C^2_x Cx2即 x ! 2 \frac{x!}{2} 2x!。
代码
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”那合规数组仅两种1010101...2101010...于是逐项对比输入与合规数组得不同的项的数量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 ∗ e 2*e 2∗e 。
于是我开始在草稿纸上施法期待老天爷降下神谕。很快我就觉得这是一个类似等差的数列之后隔两项的差都是3。然而提交之后的error告诉我还是高兴得太早了。 于是我又猜了第二版。有的棋子放下时不增加边1号或只会增加一条边如下图中带圈圈的有的棋子放下时增加两条边如下图中不带圈圈的。然后统计带圈圈类型的棋子数量。
设总棋子数为m平方根向下取整为n于是带圈圈的棋子数single_edge分两类统计
一个是内侧正方形中的如图中蓝框数量为2n-1外正方形的会有两个临界值当m的值超过它们时带圈圈的棋子数加1。
如果每个棋子会产生两条边那么总边数为 2 m 2m 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 , 1 0 9 ] [1,10^9] [1,109]逐步递推时间复杂度 O ( n ) O(n) O(n)太高。于是第二步用到矩阵快速幂将复杂度降到 O ( l o g n ) O(logn) O(logn)。
1、得到递推式
题为 x 1 x k x\frac{1}{x}k xx1k求 x n 1 x n x^n\frac{1}{x^n} xnxn1的值。令 f ( n ) x n 1 x n f(n)x^n\frac{1}{x^n} f(n)xnxn1则 k f ( n ) ( x 1 x ) ( x n 1 x n ) f ( n 1 ) f ( n − 1 ) kf(n)(x\frac{1}{x})(x^n\frac{1}{x^n})f(n1)f(n-1) kf(n)(xx1)(xnxn1)f(n1)f(n−1)。
即 f ( n 1 ) k f ( n ) − f ( n − 1 ) f(n1)kf(n)-f(n-1) f(n1)kf(n)−f(n−1)
又易得 f ( 0 ) 2 f(0)2 f(0)2 f ( 1 ) k f(1)k f(1)k 。
2、矩阵快速幂
这部分参考了文首的资料1和资料2大家也可以看一下。 a、为什么要有快速幂算法 在求一个数的n次幂的过程中比如 1 0 8 10 ∗ 10 ∗ 10 ∗ 10 ∗ 10 ∗ 10 ∗ 10 ∗ 10 10^810*10*10*10*10*10*10*10 10810∗10∗10∗10∗10∗10∗10∗10需要8次乘法运算。但如果这样算 1 0 2 10 ∗ 10 1 0 4 1 0 2 ∗ 1 0 2 1 0 8 1 0 4 ∗ 1 0 4 10^210*1010^410^2*10^210^810^4*10^4 10210∗10104102∗102108104∗104只需要3次乘法这其实是二分的思路。
也就是说可以以 O ( l o g n ) O(logn) O(logn)的时间复杂度计算数x的n次幂 x n x^n xn。 b、矩阵乘法如何计算递推式 就以本题为例我们发现 [ k − 1 1 0 ] [ f n − 1 f n − 2 ] [ f n f n − 1 ] \begin{bmatrix}k -1 \\ 1 0 \end{bmatrix} \begin{bmatrix}f_{n-1}\\f_{n-2} \end{bmatrix} \begin{bmatrix}f_{n}\\f_{n-1} \end{bmatrix} [k1−10][fn−1fn−2][fnfn−1] 于是我们每一次矩阵乘法就是一步递推。
但这有什么用呢好像莫名奇妙凑出一个矩阵的形式把简单的问题复杂化。 c、快速幂加上矩阵乘法快速计算递推式。 令 A [ k − 1 1 0 ] A\begin{bmatrix}k -1 \\ 1 0 \end{bmatrix} A[k1−10] 则 [ f n f n − 1 ] A [ f n − 1 f n − 2 ] A 2 [ f n − 2 f n − 3 ] . . . A n − 1 [ f 1 f 0 ] \begin{bmatrix}f_{n}\\f_{n-1} \end{bmatrix} A \begin{bmatrix}f_{n-1}\\f_{n-2} \end{bmatrix} A^2 \begin{bmatrix}f_{n-2}\\f_{n-3} \end{bmatrix} ... A^{n-1} \begin{bmatrix}f_{1}\\f_{0} \end{bmatrix} [fnfn−1]A[fn−1fn−2]A2[fn−2fn−3]...An−1[f1f0]
看见 A A A头上的幂次了吗将递推的时间复杂度从 O ( n ) O(n) O(n)降到 O ( l o g n ) O(logn) 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小时
这种习惯对于“常回顾”的目标必然是极大的负担。
