蓝桥杯|蓝桥杯备战每日训练3道真题解析笔记|蓝桥杯|python|算法|Python

真题训练(填空题)：>>考察对datetime模块的使用

文章图片

解析附在代码中答案8879

import datetime start,end=datetime.date(2000,1,1),datetime.date(2020,10,1) #datetime.date(year,month,day) delta=datetime.timedelta(days=1) # datetime.timedelta(days=0, seconds=0, microseconds=0, milliseconds=0, minutes=0, hours=0, weeks=0) #参数可选，默认为0 ans=0 while start<=end: if start.weekday()==0 or start.day==1: ans+=2 #datetime.date(year,month,day).weekday()返回0-6对应周一至周日 #datetime.date().day表示表示几号 else: ans+=1 start+=delta print(ans)

真题训练（填空题）：>>考察简单的数学逻辑答案为761

文章图片

两种解法：1：暴力作图法把蛇形斜着看就是一个标准的金字塔把它打印出来直接找

由于宽度限制两条线将交于761这一点金字塔代码如下：

#枚举前50斜行 n=[] for i in range(1,50): max=int(i*(i+1)/2) if i%2==1: tmp=[i for i in range(max-i+1,max+1)]#奇数行顺序偶数行逆序 else: tmp=[i for i in range(max-i+1,max+1)][::-1] n.append(tmp) for i in n: s='' for j in i: s=s+str(j)+' '#连接每行 print(s.center(150))#居中

解法2：数学递推
以对角线为研究对象，观察对角线上的每个元素
我们会发现每一斜行以对角线上的元素对称（左右元素个数相等）
且斜行是公差为1的等差数列容易想到对角线上的元素等于斜行两端的数字之和/2
如（4+6）/2=5,(11+15)/2=13....所以现在问题就是20行20列的元素处于哪一斜行，斜行两端数字是多少?解决第一个问题：观察容易知道，对角线上元素分布的斜行有以下特征：1，3，5，7....即第n个元素出现在第2n-1个斜行故20行20列元素出现在第39斜行
解决第二个问题：两端元素如何确定。由于每个斜行都是单增的观察易得第n斜行的最大值为(1+n)n/2 故第39斜行最大元素为780 由于第39斜行是公差为1的等差数列，中间元素（对角线）不难求得答案为761

真题训练编程题: >>考察贡献度计算及记录最近出现的操作

文章图片

文章图片

先说记录最近出现的操作的含义：初始化，我们定义abcd..z字母首次都出现在字符串S的索引-1处，last_index=[-1 for i in range(26)] 遍历字符串S (for j in len(S)-1) 当访问到某个字母时记录此时字母对应的索引 j，作为下一次访问到该字母时的‘最近出现的地方’，其次 last_index的索引（这里不是指索引对应的值）对应字母,0——a,1——b，依次类推，所以需要用到ord函数，将其转化为ascci码值
然后是贡献度的问题：每个字符都在一些子串中有所贡献（要求在子串中只出现一次该字符），将每个字符有所贡献的字符串数量相加，等效于将所有子串中的互异字符求和。

这里可能有点不太好理解，给出数学证明方便理解：如果子串x 如果有3个互异字符abc 说明a对x贡献了1 b对x贡献了1 c对x贡献了1 余下23个字母对x 没有贡献；
下面记函数F（α,β）为字母α对字符串β的贡献值所以对于任意一个确定的字符串,(函数f的映射规则如题意所示) f(x)=F（a,x）+F(b,x)...+F(z,x)
最后对所有子串对应的f(x)求和即为answer
记所有子串为x1,x2,x3...xn
所以answer=f(x1)+f(x2)+....+f(xn)
=F（a,x1）+F(b,x1)...+F(z,xn)+f(x)+F（a,x2）+F(b,x2)...+F(z,xn)+...F（a,xn）+F(b,xn)...+F(z,xn)
=[F(a,x1)+F(a,x2)...+F(a,xn)]+[F(b,x1)+F(b,x2)...+F(b,xn)]+...[F(z,x1)+F(z,x2)...+F(z,xn)]
证毕

#贡献值法统计每个字符对答案的增量 S=input() last_index=[-1 for i in range(26)]#last_index[i]用于记录字母最近出现的位置 c=[0 for _ in range(len(S))]for j in range(len(S)): x=ord(S[j])-ord('a') later=len(S) if S[j+1:].find(S[j])==-1 else S[j+1:].find(S[j])+j+1 c[j]=(later-j)*(j-last_index[x]) last_index[x]=j print(sum(c))

我是小郑正在奔赴热爱奔赴山海！