距离蓝桥杯还有29天 下面对执梗大哥给出的每日训练作出分析——所有题目均可在蓝桥官网找到
1.奇数倍数
def judge(x): p=str(x) for i in p: if int(i)%2==0: return False return True i=2019 while True: if judge(i): print(i) break else: i+=2019
比较简单 遍历每一位 判断能否整除2 不能就是奇数
2.第几个幸运数字
s=[] for i in range(100): for j in range(100): for k in range(100): s.append(3**i*5**j*7**k) s.sort() print(s.index(59084709587505))
因为只有三种因子，不妨假设n=3^i*5^j*7^k 三重循环枚举所有可能即可 非常简单
3.四数平方和
n=int(input()) l=[0]*5000000 for i in range(0,int(n**0.5)+1): for j in range(i,int(n**0.5)+1): if i**2+j**2<=n: l[i**2+j**2]=1 def f(n): for i in range(0,int(n**0.5)+1): for j in range(i,int(n**0.5)+1): if l[n-i**2-j**2]==1:#tmp=n-(i**2+j**2)存在(i**2+j**2递增) tmp=n-i**2-j**2#待寻找的两数平方和 for k in range(j,int(n**0.5)+1):#i<=j<=k<=p p=int((tmp-k**2)**0.5)**2#待判断数 if p==tmp-k**2:#判断是否是完全平方数，右侧是目标数字的平方，左边是待判断数 print(i,j,k,int(p**0.5)) return 0 f(n)
没有AC，75分，思路和cpp一样，但没过去，如果有更好的办法，恳请指导。下面对这种思路进行讲解，在cpp应该是能过的哈。假设n=x^2+y^2+z^2+p^2
先考虑两数的平方之和 把x^2+y^2<=n所有满足的整数解 记录下来 表示为1
其余表示为0的无非是其平方和>n或者无法用平方和表示出来（比如3就没法用两数平方和表示），不在考虑范围内
等于说现在我们已经有了一个数字 这个数字<=n,并可以用两数平方和表示
题目要求四数平方和，我们只需要在刚刚我们划分为1的数据内继续找两个
4.迷宫
s="""01010101001011001001010110010110100100001000101010 00001000100000101010010000100000001001100110100101 01111011010010001000001101001011100011000000010000 01000000001010100011010000101000001010101011001011 00011111000000101000010010100010100000101100000000 11001000110101000010101100011010011010101011110111 00011011010101001001001010000001000101001110000000 10100000101000100110101010111110011000010000111010 00111000001010100001100010000001000101001100001001 11000110100001110010001001010101010101010001101000 00010000100100000101001010101110100010101010000101 11100100101001001000010000010101010100100100010100 00000010000000101011001111010001100000101010100011 10101010011100001000011000010110011110110100001000 10101010100001101010100101000010100000111011101001 10000000101100010000101100101101001011100000000100 10101001000000010100100001000100000100011110101001 00101001010101101001010100011010101101110000110101 11001010000100001100000010100101000001000111000010 00001000110000110101101000000100101001001000011101 10100101000101000000001110110010110101101010100001 00101000010000110101010000100010001001000100010101 10100001000110010001000010101001010101011111010010 00000100101000000110010100101001000001000000000010 11010000001001110111001001000011101001011011101000 00000110100010001000100000001000011101000000110011 10101000101000100010001111100010101001010000001000 10000010100101001010110000000100101010001011101000 00111100001000010000000110111000000001000000001011 10000001100111010111010001000110111010101101111000""" maze=s.split('\n')#30行50列 maze[n][m] 0<=n<=29,0<=m<=49 dy=[0,-1,1,0] dx=[1,0,0,-1] def judge(x,y): global parent,maze if 0<=x<=29 and 0<=y<=49 and maze[x][y]=='0' and (x,y) not in parent.keys(): return True return False parent={(0,0):(0,0)} endx,endy=29,49 searched=[(0,0)] def g(x1,y1,x2,y2): if x2-x1>0: return 'D' if x2-x1<0: return 'U' if y2-y1>0: return 'R' if y2-y1<0: return 'L' while searched: now=searched.pop(0) x,y=now[0],now[1] if x==endx and y==endy: end=(x,y) start=(0,0) t='' while parent[end]!=start: print(end) t=g(parent[end][0],parent[end][1],end[0],end[1])+t end=parent[end] t=g(parent[end][0],parent[end][1],end[0],end[1])+t print(t) break else: for i in range(4): nx,ny=x+dx[i],y+dy[i] if judge(nx,ny): parent[(nx,ny)]=(x,y) searched.append((nx,ny))
利用广度优先搜索 同时要记录路径 需要一个字典来记录前驱结点 每次出队的元素
对其合法邻居入队 何为合法邻居：在地图内，不是障碍物，没有创建过前驱关系（一个结点只能有一个parent）
有任何疑惑和建议欢迎提出 希望大家都能在这次蓝桥杯省赛中拿到省一！！！
