蓝桥杯第24天（Python）（疯狂刷题第7天）
题型：
1.思维题/杂题：数学公式，分析题意，找规律
2.BFS/DFS：广搜（递归实现），深搜（deque实现）
3.简单数论：模，素数（只需要判断到 int（sqrt（n））+1），gcd，lcm，快速幂（位运算移位操作），大数分解（分解为质数的乘积）
4.简单图论：最短路（一对多（Dijstra，临接表，矩阵实现），多对多（Floyd，矩阵实现）），最小生成树（并查集实现）
5.简单字符串处理：最好转为列表操作
6.DP：线性DP，最长公共子序列，0/1背包问题，最长连续字符串，最大递增子串
7.基本算法：二分，贪心，组合，排列，前缀和，差分
8.基本数据结构：队列，集合，字典，字符串，列表，栈，树
9.常用模块：math，datetime，sys中的设置最大递归深度（sys.setrecursionlimit(3000000)），collections.deque（队列），itertools.combinations（list,n）（组合），itertools.permutations（list,n）（排列） heapq（小顶堆）
目录
题型：
刷题：1.《GCD》真题练习（思维 ，数学性质，gcd）
2.《青蛙过河》真题练习（二分，数学思维）
3.《因数平方和》真题练习（数论）
4. 《卡片》真题演习（思维）
5.《直线》真题演习（空间直线，集合）
6.《货物摆放》真题演习（去重，大数分解，因数分解）
7.路径（Floyd算法）
8.《回路计数》真题演习（dp）
9.《时间显示》真题演习（格式化输出）
10.《杨辉三角形》真题演习（二分，难题骗分就行）
11.《左孩子右兄弟》真题演习（dfs，树）
12.《异或数列》真题演习（难，不要这分）
13.《括号序列》真题演习（只要暴力分即可）
14.门牌制作（字符串操作）
15.《 寻找 2020》真题演习（暴力循环字符串操作）
16.《跑步锻炼》真题演习（datetime库的使用）
17.《蛇形填数》真题演习（思维规律）
18.《排序》真题演习（全排列，找规律）
19.《装饰珠》真题演习编辑
20.《 成绩统计》真题演习（选择）
21.《单词分析》真题演习（内置函数，max，min）
22.《 数字三角形》真题演习（暴力循环）
23.《平面切分》真题演习（找规律）
刷题：
1.《GCD》真题练习（思维 ，数学性质，gcd）
初步思路：暴力枚举k，这样我感觉不能通过全部数据，题目要求找到最小k值。
找规律看看有不有规律？（错误了，只过了2个测试点）
import sys #设置递归深度
import collections #队列
import itertools # 排列组合
import heapq #小顶堆
import math
sys.setrecursionlimit(300000)
import functools # 自定义比较函数 -1不变，1交换'''
12 23 34 45 56 67 0
13 35 57 79 (2 1)
14 47 25 36 (3 2)
15 59 (4 1)
16 5 10 （5 4）
# 规律，相差为质数，就是质数-1 即d-1'''
def is_prime(x):for i in range(2,int(math.sqrt(x))+1):if x%2==0:return Falseelse:return Truea,b=map(int,input().split())
if is_prime(abs(b-a)):print(abs(a-b)-1)
else:print(0)
正解：性质：gcd（a，b）=gcd（a-b，b）
gcd(a+k,b+k)=gcd(a+k,b-a)≤min(a+k,b-a)，直接让gcd=b-a，保证gcd最大
标程：
a, b = map(int, input().split())
r = a % (b - a)
if r == 0:print(0)
else:print(b - a - r)2.《青蛙过河》真题练习（二分，数学思维）
初步思路：通过深搜DFS做，一个标记数组，维护石头数，（次数，位置）
正解：答案存在单调性，最小跳跃距离为1，最大为n，通过二分答案进行求解。
标程：
n, x = list(map(int, input().split()))
H = [0, *list(map(int, input().split()))] #下标从1开始
Pre_Sum = [0] * (n)
for idx in range(1, n): #预处理前缀和Pre_Sum[idx] = Pre_Sum[idx - 1] + H[idx]#判定能力为y时，是否合法
def check(y):#枚举所有长度为y的区间for l in range(1, n - y + 1):r = l + y - 1if Pre_Sum[r] - Pre_Sum[l - 1] < 2 * x:return Falsereturn True#二分答案
l, r = 1, n
ans = -1
while l <= r:mid = (l + r) // 2if check(mid):ans = midr = mid - 1else:l = mid + 1
print(ans)3.《因数平方和》真题练习（数论）
初步思路：暴力循环
正解：考虑优化，记录每个因子出现次数
标程：
MOD = 1000000007#求数字1-n的平方和
def S(x):return x * (x + 1) * (2 * x + 1) // 6n = int(input())
ans = 0
l = 1
#枚举左端点
while l <= n:r = min(n // (n // l), n)ans += (n // l) * (S(r) - S(l - 1))l = r + 1
print(ans % MOD)4. 《卡片》真题演习（思维）
初步思路：看谁用的最少，然后循环，用完跳出就行
正解：一样
标程：
a = [2021 for i in range(10)]
def check(x):while(x > 0):now = int(x % 10)if(a[now] > 0):a[now] -= 1else:return 0x = x // 10return 1cnt = 1
while(check(cnt)):cnt += 1
print(cnt - 1)5.《直线》真题演习（空间直线，集合）
初步思路：通过集合去重放不同斜率，垂直于x轴的单独计算数量
正解：一样，但是要注意小数精度问题，利用集合去重
标程：
import sys #设置递归深度
import collections #队列
import itertools # 排列组合
import heapq #小顶堆
import math
sys.setrecursionlimit(300000)
import functools # 自定义比较函数 -1不变，1交换import os
import sys# 请在此输入您的代码
m=set()
for i in range(0,20): # 0-1for j in range(0,21): # 0-2for x in range(0,20):for y in range(0,21):if x-i!=0:# y=kx+bk=(y-j)/(x-i)b=y-k*xm.add((round(k,5),round(b,5))) # 精度问题，不保留小数会出现问题#m.add((k,b)) # 除法保留16位小数print(len(m)+20)
6.《货物摆放》真题演习（去重，大数分解，因数分解）
初步思路：无
正解：记录n的因子，3重循环遍历因子组合，有一个优化，就是前两重因子如果相乘大于n了，就跳过进行下一层循环，剪枝操作。
通过大数分解将n质因数分解，然后通过BFS遍历有多少种组合，即
（len（质因数个数），x，y，z），用集合去重。
标程：
n = 2021041820210418
i = 1
a = []
cnt = 0
while i * i <= n:if n % i == 0:a.append(i)if i != n / i:a.append(int(n / i))i += 1
for i in range(len(a)):for j in range(len(a)):if a[i] * a[j] > n:continuefor k in range(len(a)):if a[i] * a[j] * a[k] == n:cnt += 1
print(cnt)7.路径（Floyd算法）
初步思路：Floyd算法（3重循环），或者警察问路那个算法（2重循环）。
正解：Dijstra算法，最简便为Floyd
标程：
import mathdef lcm(a, b):return int(a * b / math.gcd(a, b))n = 2021
g = [[0 for i in range(1, n + 2)] for j in range(1, n + 2)]
for i in range(1, n + 1):for j in range(1, n + 1):if i == j:g[i][j] = g[j][i] = 0elif abs(i - j) <= 21:g[i][j] = g[j][i] = lcm(i, j)else:g[i][j] = 1000000000
for k in range(1, n + 1):for i in range(1, n + 1):for j in range(1, n + 1):if g[i][j] > g[i][k] + g[k][j]:g[i][j] = g[i][k] + g[k][j]
print(g[1][n])8.《回路计数》真题演习（dp）
初步思路：首先建图，通过邻接表建图，然后通过dfs搜索，最终回到原点就计数加1.
正解：通过矩阵构建临接矩阵，状态DP
标程：
# python 跑的相当慢，不过这是道填空题就无所谓了
import mathdp = [[0] * (22) for i in range(2100000)]
g = [[0 for i in range(22)] for i in range(22)]
n = 1 << 21
for i in range(1, 22):for j in range(1, 22):if math.gcd(i, j) == 1:g[i - 1][j - 1] = g[j - 1][i - 1] = 1
dp[1][0] = 1
i = 1
while i < n:for j in range(0, 21):if (i >> j & 1) == 0:continuefor k in range(0, 21):if g[j][k] == 0 or (i >> k & 1) != 0:continuedp[(i + (1 << k))][k] += dp[i][j]i += 1
res = 0
for i in range(0, 21):res += dp[n - 1][i]
print(res)9.《时间显示》真题演习（格式化输出）
初步思路：直接取余计算当天的时分秒，然后进行整除得到时分秒
import os
import sys# 请在此输入您的代码
n=int(input())
time=n%(1000*60*60*24)
h=time//(1000*60*60)
m=(time-h*1000*3600)//(1000*60)
s=(time-h*1000*3600-m*60*1000)//1000
print('{:0>2d}:{:0>2d}:{:0>2d}'.format(h,m,s))正解：只考虑最后一天，1s=1000ms
标程：
import os
import sys
n = int(input())
n /= 1000
n %= 24 * 60 * 60
h = int(n / 3600)
m = int(n / 60) % 60
s = int(n % 60)
if h <= 9:h = str(0) + str(h)
else :h = str(h)
if m <= 9:m = str(0) + str(m)
else:m = str(m)
if s <= 9:s = str(0) + str(s)
else:s = str(s)
print(h + ':'+ m + ':' + s)10.《杨辉三角形》真题演习（二分，难题骗分就行）
初步思路：先把前面几十行的数值计算出来，拼接成一行，通过列表的索引来求值
正解：二分行号
import os
import sys# 请在此输入您的代码
n=[0,1,1,1,1,2,1]
#n=[[0],[1,1],[1,2,1]]
last=[1,2,1]
for i in range(50):new=[]for a,b in zip(last+[0],[0]+last):new.append(a+b)n.append(new)last=newm=int(input())
print(n.index(m))
正解：
标程：
import os
import sysn = int(input())def C(a, b):res = 1i = aj = 1while j <= b:res = int(res * i / j)if res > n:return int(res)i -= 1j += 1return int(res)for k in range(16, -1, -1):l = 2 * kr = max(n, l)res = int(-1)while l <= r:mid = l + r >> 1if C(mid, k) >= n:res = midr = mid - 1else:l = mid + 1if C(res, k) == n:print((res + 1) * res // 2 + k + 1)break11.《左孩子右兄弟》真题演习（dfs，树）
初步思路： 无
正解：通过列表存储多叉树，dfs搜索，即dfs（i） i根二叉树最高高度
dfs（i）=孩子的数目 + max（）dfs（各孩子））
5
1 1 [ 2 3 4 ]
1 2 [ 5 ]
1 3 [ ]
2 4 [ ]
5 [ ]
标程：
import sys #设置递归深度
import collections #队列
import itertools # 排列组合
import heapq #小顶堆
import math
sys.setrecursionlimit(300000)
import functools # 自定义比较函数 -1不变，1交换n = int(input())
A = [[]for i in range(n+1)]
for i in range(2,n+1):v=int(input())A[v].append(i) # 添加子节点def dfs(i):if A[i] is None:return 0maxn = 0for j in A[i]:maxn = max(maxn ,dfs(j))return len(A[i])+maxn
print(dfs(1))
12.《异或数列》真题演习（难，不要这分）
初步思路：无
正解：博弈论知识
13.《括号序列》真题演习（只要暴力分即可）
初步思路： 将括号转为0,1数字，看有多少种插入方法，dfs从左到右搜索？
"""
0001
010101
010011
001101
001011
000111"""
标程（暴力）：
for(int i = 1 ; i <= cnt ; i ++) dp[1][i] = 1;if(sum[1] > 0) dp[1][0] = 1;for(int i = 2 ; i <= n ; i ++){for(int j = i - sum[i] ; j <= cnt ; j ++){for(int k = 0 ; k <= j ; k ++){dp[i][j] += dp[i - 1][k];dp[i][j] %= mod;}}}14.门牌制作（字符串操作）
字符串操作
15.《 寻找 2020》真题演习（暴力循环字符串操作）
暴力循环就行，统计。
import sys #设置递归深度
import collections #队列
import itertools # 排列组合
import heapq #小顶堆
import math
sys.setrecursionlimit(300000)
import functools # 自定义比较函数 -1不变，1交换import os
import sys# 请在此输入您的代码
a="""022220000002200200202022000202222022202222222202022002222200022200222220020200222020002022222220022202000002220020220002022222022022002022202222222000022002020002202002022000022000202200000220200022200020220222000022202222000222222022202022222022200002202220222000202000200002220200000200202002202202
"""
b=[]
a=a.split() # 300*300
for i in a:b.append(list(i))
ans=0
#s="002000000220202000222000202200222220202202020002220002020022202200220220202002002220020200000000220022200202222022220222000022220220020020222020022220022220220000022022002020220002200220020020022200020222020200200000020220020022002202000202222020220020020022020000202022220222200022220000000020020020"
#print(len(s))
def check1(i,j):if i+3<=299 and b[i][j]=='2' and b[i+1][j]=='0' and b[i+2][j]=='2' and b[i+3][j] =='0':return Trueelse :return False
def check2(i,j):if j+3<=299 and b[i][j]=='2' and b[i][j+1]=='0' and b[i][j+2]=='2' and b[i][j+3] =='0':return Trueelse :return False
def check3(i,j):if i+3<=299 and j+3<=299 and b[i][j]=='2' and b[i+1][j+1]=='0' and b[i+2][j+2]=='2' and b[i+3][j+3] =='0':return Trueelse :return Falsefor i in range(300):for j in range(300):if check1(i,j):ans+=1if check2(i,j):ans+=1if check3(i,j):ans+=1print(ans)标程：
n = 300
ans = 0
s = []
for i in range(n):t = input()s.append(t)
for i in range(len(s)):for j in range(len(s[i])):if j + 3 < len(s[i]) and s[i][j] + s[i][j + 1] + s[i][j + 2] + s[i][j + 3] == '2020':ans += 1
for i in range(len(s)):for j in range(len(s[i])):if i + 3 < len(s) and s[i][j] + s[i + 1][j] + s[i + 2][j] + s[i + 3][j] == '2020':ans += 1
for i in range(len(s)):for j in range(len(s[i])):if i + 3 < len(s) and j + 3 < len(s[i]) and s[i][j] + s[i + 1][j + 1] + s[i + 2][j + 2] + s[i + 3][j + 3] == '2020':ans += 1
print(ans)16.《跑步锻炼》真题演习（datetime库的使用）
送分题？使用datetime库循环遍历即可
import sys #设置递归深度
import collections #队列
import itertools # 排列组合
import heapq #小顶堆
import math
sys.setrecursionlimit(300000)
import functools # 自定义比较函数 -1不变，1交换
import datetime # date,timedelta,isoweekday()begin=datetime.date(2000,1,1)
end=datetime.date(2020,10,1)
delta=datetime.timedelta(1)
ans=0
while begin !=end:if begin.day==1 or begin.isoweekday()==1: #月初或者星期一ans+=2else: ans+=1begin+=delta
print(ans+2)
标程：
import os
import sys
import datetimestart = datetime.date(2000, 1, 1)
end = datetime.date(2020, 10, 1)
days = datetime.timedelta(days=1)
ans = 0while end >= start:if start.day == 1 or start.weekday() == 0:ans += 2else:ans += 1start += days
print(ans)
17.《蛇形填数》真题演习（思维规律）
找规律的题
18.《排序》真题演习（全排列，找规律）
19.《装饰珠》真题演习
初步思路：题意都读不懂，跳了
20.《 成绩统计》真题演习（选择）
选择判断，送分题
import os
import sys
n = int(input())
cnt1 = 0
cnt2 = 0
for i in range(1 , n + 1):x = int(input())if x >= 60:cnt1 +=1if x >= 85:cnt2 += 1
print("{:.0f}%".format(round(100.0 * cnt1 / n , 2)))
print("{:.0f}%".format(round(100.0 * cnt2 / n , 2)))21.《单词分析》真题演习（内置函数，max，min）
送分，使用内置函数寻找最大最小
import os
import sys
s = input()
ma = 0
ch = 'z'
for j in s:cnt = s.count(j)if cnt >= ma:ma = cnt
for j in s:if s.count(j) == ma:ch = min(ch , j)
print(ch)
print(ma)22.《 数字三角形》真题演习（暴力循环）
初步思路：从上到下遍历，因为向左下走的次数与向右下走的次数相差不能超过 1，最后的终点肯定是中间位置。
import os
import sysdp = []n = int(input())for i in range(n):dp.append(list(map(int, input().split())))for i in range(n):for j in range(i + 1):if i == 0:dp[i][j] = dp[i][j]elif j == 0:dp[i][j] = dp[i - 1][j] + dp[i][j]elif j == i:dp[i][j] = dp[i - 1][j - 1] + dp[i][j]else:dp[i][j] = max(dp[i - 1][j - 1],dp[i - 1][j]) + dp[i][j]if n % 2 == 0:print(max(dp[n - 1][n // 2 - 1],dp[n - 1][n // 2]))
else:print(dp[n - 1][n // 2])23.《平面切分》真题演习（找规律）
初步思路：画图找规律
正解：增加n个交点，就增加n+1个平面，注意去重，交点和线去重。
标程：
import os
import sys
n = int(input())
line = set()
node = set()
ans = 1
def calc(a , b):node.clear()for j in line:A = j[0]B = j[1]if A == a:continue x = 1.0 * (B - b) / (a - A)y = x * a + bnode.add((x , y));return len(node) + 1for i in range(n):a, b = list(map(int, input().split()))if (a, b) in line:continue ans += calc(a , b)line.add((a, b))
print(ans)
