距离蓝桥杯42天
学习算法的目的是为了提升我们的思维
有梦想有担当 冲击省一 冲进大厂 保持持续性的努力
下面一共3道蓝桥杯真题 问题地址+代码分析+知识点考察（学习建议）
问题描述：1204. 错误票据 - AcWing题库
代码设计分析：(已AC)
先把所有数据存入一个列表s>>利用sort()排序
重号Id必然出现两次 通过循环存储下来
另创建一个连续数值的列表 范围（min(s),max(s)）
通过set中的差集操作 找到漏网之鱼 （最后输出set中的元素需将其转换为列表）
重要知识点考察：列表sort（）函数 Python List sort()方法 | 菜鸟教程 (runoob.com)
集合操作Python set() 函数 | 菜鸟教程 (runoob.com)
n=int(input().strip()) s=[] res="" for i in range(n): tmp=list(map(int,input().strip().split())) s+=tmp s.sort() res="" sl=[i for i in range(min(s),max(s)+1)] res+=str(list(set(sl)-set(s))[0])#取差集 for i in range(len(s)-1): if s[i]==s[i+1]: res+=" "+str(s[i]) break##找重复的 print(res)
问题描述：1205. 买不到的数目 - AcWing题库（已AC）
代码设计分析：掌握数论里面一个定理：裴蜀定理:对于互质正整数a,b
p=ax+by (x,y>=0) p不能表示的最大整数的ab-(a+b)
证明过程：先了解一个数论符号：把下面的视频和文章结合起来 方便理解
n,m=map(int,input().split()) print(n*m-n-m) #ax+by gcd(a,b)=1 则ax+by不能表示的最大整数为ab-(a+b)
暴力枚举法（60分）：利用itertools中的combinations 列举出所有区间可能
n=int(input()) s=list(map(int,input().split())) s.insert(0,0) count=n#[1,1][2,2]...单独一个数也可以作为一个区间 def judge(res): tmp=[i for i in range(min(res),max(res)+1)] res=sorted(res) if tmp==res: return True return False import itertools p=[j for j in range(1,n+1)] for k in itertools.combinations(p,2): #(1，7）或（7，1） start,end=min(k),max(k) if judge(s[start:end+1]): count+=1 print(count)
既然不能满分，转换思路：假设原列表存这样一个连续区间 （顺序不定）
比如[2,4,3,5,6]属于某个列表的子区间，可以发现，它是连续的（按照题意指排序过后）。
题目要求的特定区间 除了需要满足连续性以外 还需要满足下标的某种关系
即子区间的长度=连续区间的长度。详细一点说，我们上面给出的区间，它即是子区间又是连续区间，当把他看作子区间时，他的长度为R-L+1（最左（右）侧对应下标），当把他看作连续区间时，它的长度=6-2+1=5 可以发现=max-min+1
因而题目所要求的就是找到所有满足R-L+1=max-min+1的所有区间的个数
(未AC 80分)
一样的思路C++能过 可能Python跑的就是慢一点吧
n=int(input()) s=list(map(int,input().split())) s.insert(0,0) count=0 for i in range(1,len(s)): for j in range(i,len(s)): if j-i+1==max(s[i:j+1])-min(s[i:j+1])+1: count+=1 print(count)
我是小郑 正在奔赴热爱 奔赴山海 ！欢迎批评指正问题交流
