蓝桥杯--算法

77 阅读 0 评论 51 点赞

我是靠谱客的博主含糊高跟鞋，最近开发中收集的这篇文章主要介绍蓝桥杯--算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在准备蓝桥杯时做的一些笔记在这里记录一下。
#选择排序算法

for x in range(n-1):
	for y in range(x+1,n):
		if s[x]<s[y]:
			s[x],s[y]=s[y],s[x]

#冒泡排序算法

for x in range(n-1):
	for y in range(n-1-x):
		if s[y]<s[y+1]:
			s[y],s[y+1]=s[y+1],s[y]

index()可以获取指定元素首次出现的下标

count()指定元素在列表中出现的次数

list.sort(reverse=True)降序排序

zip将多个列表或元组对应位置的元素组合为元组，返回列表

enumerate()返回枚举对象中每个元素包含下标和元素值的元组

list(zip(*matrix))矩阵转置bvfrom operator import itemgetter

hec()十进制转化为十六进制

oct()十进制转化为八进制

bin()十进制转化为二进制

把x保留到小数点后要求的位数

round(x,3)
print('%.3f'%x)
print('{:.3f}'.format(x))

map(function,iter)根据提供的函数对指定序列做映射。

sort()无返回值。sorted（）返回一个新的list

1.列表转化为字符串

ls = [“1”,“2”,“3”]

“”.join(ls)

2.sep实现分隔符

3.字符串可以看作为可迭代对象

s = “abc”
for i in s:
print(i)

字符串是不可变对象

s = “abc”
temp = list(s)
temp[2] = “d”
s = “”.join(temp)
print(s)

或者

s = “abc”
s = s.replace(“c”,“d”)
print(s)

接收由空格分开的多个数据

ls = input().split()

同时改变列表中所有元素的类型

ls = input().split()
ls2 = list(map(int,ls))

基本操作

1、输入输出

#循环读取到文件末尾
try:
	while True:
        s=input()
except:
    pass

#读取n,m,再读取n个数，m行
n,m=(int(_) for _ in input().strip().split(" "))
a=[int(_) for _ in input().strip().split(" ")]
for i in range(m):
    s = input()

# 读取的第二种方法，map映射
a1 = list(map(int, input().split()))

# 输出n个数在一行（无行尾空格）
ans = [1, 2, 3, 4]
for j in ans[:-1]:
    print(j, end=" ")
print(ans[-1])

2、算法模板

（1）线性筛

N = int(1e6 + 5)
isPrime = [1 for _ in range(N)]
Prime = []


def getprime(n):
    isPrime[1] = 0
    for i in range(2, n + 1):
        if isPrime[i]:
            Prime.append(i)
        for j in Prime:
            if i * j > N:
                break
            isPrime[i * j] = 0
            if i % j == 0:
                break

（2）扩展欧几里得

def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    x, y, g = exgcd(b, a % b)
    x, y = y, x - a // b * y
    return x, y, g


T = int(input())
for i in range(T):
    n, d, x, y = (int(x) for x in input().strip().split(' '))
    t1, t2, g = exgcd(n, d)
    if (y - x) % g:
        print("Impossible")
    else:
        t2 *= (y - x) // g
        n //= g
        print(t2 % n)

基础

**1.fibonacci数列

n=int(input())
f=[1 for i in range(n+1)]
k=3
while k<=n:
    f[k]=(f[k-1]+f[k-2])%10007
    k+=1
print(f[n])

2.圆的面积

import math
r=int(input())
area=math.pi*r*r
print('%.7f'%area)

3.序列求和

用等差数列公式，不要用循环，否则当数据规模变大会超时

n=int(input())
sum=n*(n+1)/2
print('%d'%sum)

4.A+B问题

a,b=map(int,input().split())

print(a+b)

5.数列排序

n=int(input())
arr=list(map(int,input().split()))
arr.sort()
for i in arr:
print(i,end=’ ')

6.进制之间的转换

将整数转换为二进制、八进制和十六进制

bin() oct() hex()

如果不带Ob,Oo或Ox前缀的话，用format()函数

format(x,‘b’) format(x,‘o’) format(x,‘x’)

int()函数用于将一个字符串或数字转换为整型

字符和ASCII码的转换

ord(‘A’) chr(65)

十六进制转八进制

n=int(input())
for i in range(n):
    a=input()
    a=format(int(a,16),'o')
    print(a)

十六进制转十进制

n=input()
print(int(n,16))

十进制转十六进制

n=input()
print(format(n,'x'))

7.特殊回文数

import time
def ispal(i):
    i=str(i)
    if i==i[::-1]:
        return True
    else:
        return False
def sums(i):
    i=str(i)
    s=0
    for j in range(len(i)):
        s+=int(i[j])
    return s
n=int(input())
i=10000
while i<1000000:
    if ispal(i):
        if sums(i)==n:
            print(i)
    i+=1

8.回文数

import time
def ispal(i):
    i=str(i)
    if i==i[::-1]:
        return True
    else:
        return False
i=1000
while i<10000:
    if ispal(i):
            print(i)
    i+=1

9.水仙花数

def iswater(i):
    a = i % 10 # 十位
    b = (i//10) % 10 # 百位 注意Python中除法一定会得到浮点数 要取整 而C中则不需要
    c = i//100
    if a**3+b**3+c**3==i:
        return True
    else:
        return False
i=100
while i<1000:
    if iswater(i):
        print(i)
    i+=1

10.杨辉三角

n=int(input())
yang=[]
for i in range(n):
    yang.append([0 for j in range(i+1)])
for i in range(n):
    yang[i][0]=yang[i][-1]=1

for i in range(n):
    for j in range(1,i):
        yang[i][j]=yang[i-1][j-1]+yang[i-1][j]
for i in range(n):
    for j in range(i+1):
        print(yang[i][j],end=' ')
    print()

11.查找整数

n=int(input())
lists=list(map(int,input().split()))
a=int(input())
flag=1
for i in lists:
    if i==a:
        print(lists.index(i)+1)
        flag==0
        break
    
if flag:
    print('-1')

12.数列特征

n=int(input())
lists=list(map(int,input().split()))
print(max(lists))
print(min(lists))
print(sum(lists))

python列表中的sort()函数对有负数的列表无法进行排序的

13.字母图形

n,m=map(int,input().split())
lists=[[0 for j in range(m)] for i in range(n)]
for i in range(n):
    for j in range(m):
        if j>i:
            lists[i][j]=chr(ord('A')+j-i)
        else:
            lists[i][j]=chr(ord('A')+i-j)

for i in range(n):
    for j in range(m):
        print(lists[i][j],end='')
    print()

14.字串01（在前面添加0)

for i in range(32):
    print("{0:0>5}".format(format(i,'b')))

15.闰年判断

year=int(input())
if (year%4==0 and year%100!=0)|(year%400==0):
    print('yes')
else:
    print('no')

16.阶乘计算

n=int(input())
a=s=1
while a<=n:
    s=s*a
    a+=1
print(s)

17.长整数加法

18.哈夫曼树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NqcCdqwb-1650248123225)(C:UsersTianAppDataRoamingTyporatypora-user-imagesimage-20220402205218992.png)]

n=int(input())
lists=list(map(int,input().split()))
sum=0
while len(lists)!=1:
    min1=min(lists)
    lists.remove(min1)
    min2=min(lists)
    lists.remove(min2)
    min_sum=min1+min2
    sum+=min_sum
    lists.append(min_sum)
print(sum)

n=int(input())
lists=list(map(int,input().split()))
price=[0 for i in range(n-1)]
for i in range(n-1):
    lists.sort()
    value1=lists.pop(0)
    value2=lists.pop(0)
    price[i]=value1+value2
    lists.append(price[i])
print(sum(price))

19.2N 皇后问题

def queen(A, cur=0):  # cur表示当前行数下标，A储存每行有皇后的列的下标
   global count
   if cur == len(A):  # 溢出棋盘边界，跳出递归判断
       print(A)  # 打印位置
       count += 1  # 可能+1
       return 0  # 跳出本次递归
   for col in range(len(A)):  # col表示当前列下标，从第一行到最后一行遍历
       A[cur], flag = col, True  # 存储当前列下标，暂时判定可以放置皇后
       for row in range(cur):  # 遍历前cur行
           if A[row] == col or abs(col - A[row]) == cur - row:
               flag = False  # 不可以放置皇后
               break  # 跳出for循环
           if flag:  # 判断是否可以放置皇后
               queen(A, cur+1)  # 可以放置皇后进行下一行皇后的判断
count = 0  # 初始化可能数
queen([None]*8)  # 调用递归函数并赋值棋盘最大行
print(count)  # 打印总的可能个数
def black_queen(k):  # 定义黑皇后递归函数，k为行下标
   global count  # 定义全局变量
   for q in range(k - 1):  # 循环遍历前k-1列，判断是否可以放置黑皇后
       judge = b_queen[q] - b_queen[k - 1]  # 第q+1行与第k行列下标差值
       if judge == 0 or k - 1 - q == abs(judge):  # judge == 0重复放置同一列，k - 1 - q == abs(judge)黑皇后位置在同一斜线上
           return  # 此可能性不成立跳出递归
   if k == n:  # 溢出棋盘边界
       count += 1  # 放置皇后可能性+1
       return  # 跳出递归
   for q in range(n):  # 从第一列遍历到最后一列
       if q != w_queen[k] and chessboard[k][q] == 1:  # q != w_queen[k]与白皇后第k+1行列下标相同不可再放置黑皇后，
                                                       # chessboard[k][q] == 1棋盘位置条件位置为1可以放置皇后
           b_queen[k] = q  # 存储当前黑皇后列下标
           black_queen(k + 1)  # 进行下一行皇后的判断递归


def white_queen(k):  # 定义白皇后递归函数，k为行下标
   for p in range(k - 1):  # 循环遍历前k-1列，判断是否可以放置白皇后
       judge = w_queen[p] - w_queen[k - 1]  # 第q+1行与第k行列下标差值
       if judge == 0 or k - 1 - p == abs(judge):  # judge == 0重复放置同一列，k - 1 - q == abs(judge)白皇后位置在同一斜线上
           return  # 此可能性不成立跳出递归
   if k == n:  # 溢出棋盘
       black_queen(0)  # 白皇后放置完成，进行黑皇后放置递归
       return  # 跳出递归
   for p in range(n):  # 从第一列遍历到最后一列
       if chessboard[k][p] == 1:  # chessboard[k][q] == 1棋盘位置条件位置为1可以放置皇后
           w_queen[k] = p  # 存储当前白皇后列下标
           white_queen(k + 1)  # 进行下一行皇后的判断递归


n = int(input())  # 输入n表示棋盘大小
count = 0  # 放置皇后可能性
chessboard = [[] for _ in range(n)]  # 棋盘
for i in range(n):  # 循环得到棋盘位置是否可以放置皇后的条件
   arr = input().split()  # 能否放置皇后
   for j in range(n):  # 循环设置棋盘
       chessboard[i].append(int(arr[j]))  # 对棋盘设置1/0
w_queen = [0 for _ in range(n)]  # 初始化白皇后位置列下标
b_queen = [0 for _ in range(n)]  # 初始化黑皇后位置列下标
white_queen(0)  # 以白皇后为起始进行递归，0为行下标
print(count)  # 打印所有放置皇后的可能数值

def black_queen(k):
    #k为行下标
    global count
    for q in range(k-1):#循环遍历前k-1行，判断是否可以放置黑皇后
        judge=b_queen[q]-b_queen[k-1]#第q+1行与第k行列下标差值
        if judge==0 or k-1-q==abs(judge):#放在同一列，或者同一斜线上
            return
    if k==n:#溢出棋盘边界
        count+=1
        return
    for q in range(n):#从第一行遍历到最后一行
        if q!=w_queen[k] and chessboard[k][q]==1:#q不与白皇后第k+1行列下标相同不可再放置黑皇后；chessboard[k][q]==1棋盘位置为一可以放置皇后
            b_queen[k]=q# 存储当前黑皇后列下标
            black_queen(k+1)#进行下一行黑皇后
def white_queen(k):
    for p in range(k-1):
        judge=w_queen[p]-w_queen[k-1]
        if judge==0 or k-1-p==abs(judge):
            return
    if k==n:
        black_queen(0)#白皇后放置完成，进行黑皇后放置递归
        return
    for p in range(n):
         if chessboard[k][p]==1:
             w_queen[k]=p
             white_queen(k+1)
             
n=int(input())#n棋盘大小
count=0
chessboard=[[] for i in range(n)]
for i in range(n):
       chessboard[i]=list(map(int,input().split()))
w_queen=[0 for i in range(n)]
b_queen=[0 for i in range(n)]
white_queen(0)
print(count)

20.报时助手

h, m = map(int, input().split())

time = {0: 'zero', 1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine',
        10: 'ten', 11: 'eleven', 12: 'twelve', 13: 'thirteen', 14: 'fourteen', 15: 'fifteen', 16: 'sixteen',
        17: 'seventeen', 18: 'eighteen', 19: 'nineteen', 20: 'twenty', 21: 'twenty one', 22: 'twenty two',
        23: 'twenty three', 30: 'thirty', 40: 'forty', 50: 'fifty'}
        # 其实21，22，23可以不加入字典中，但为了后边小时略去判断简化代码，直接加在字典中，方便后边直接输出小时

if m == 0:
    print(time[h] + ' o'clock')
else:
    print(time[h], end=' ')
    if 0 < m <= 20 or m == 30 or m == 40 or m == 50:
        print(time[m])
    elif 20 < m < 30:
        print(time[20] + ' ' + time[m - 20])
    elif 30 < m < 40:
        print(time[30] + ' ' + time[m - 30])
    elif 40 < m < 50:
        print(time[40] + ' ' + time[m - 40])
    else:
        print(time[50] + ' ' + time[m - 50])

21.回形取数

m,n=map(int,input().split())
row=col=count=0
qi=[[] for i in range(m)]
for i in range(m):
    qi[i]=list(map(int,input().split()))
while count<n*m:
    while row<m and qi[row][col]!=-1:#向下取数
        print(qi[row][col],end=' ')
        qi[row][col]=-1#将去过的位置设为-1
        row+=1
        count+=1
    row-=1
    col+=1
    while col<n and qi[row][col]!=-1:#向右取数
        print(qi[row][col],end=' ')
        qi[row][col]=-1
        col+=1
        count+=1
    col-=1
    row-=1
    while row>=0 and qi[row][col]!=-1:#向上取数
        print(qi[row][col],end=' ')
        qi[row][col]=-1
        row-=1
        count+=1
    row+=1
    col-=1
    while col>=0 and qi[row][col]!=-1:#向上取数
        print(qi[row][col],end=' ')
        qi[row][col]=-1
        col-=1
        count+=1
    row+=1
    col+=1

22.龟兔赛跑

v1,v2,t,s,lenth=map(int,input().split())
t2=lenth//v2
time=1
l1=l2=0
flag=False
while time<=t2:
    l1+=v1
    l2+=v2
    if l1==lenth or l2==lenth:
        break
    elif l1-l2>=t:
        for i in range(s):
            #可能在兔子休息中，乌龟就到达了终点
            l2+=v2
            time+=1
            if l2==lenth:
               flag=True
               break
        if flag:
            break
    time+=1
if l1>l2:
    print('R')
    print(time)
elif l1<l2:
    print('T')
    print(time)
else:
    print('D')
    print(time)

23.芯片测试

n=int(input())
text=[[] for i in range(n)]
for i in range(n):
    text[i]=list(map(int,input().split()))
out=[1]*n
for j in range(n):
    num=0
    for i in range(n):
        if text[i][j]==0:
            num+=1
    if num>n/2:
        out[j]=0
for i in range(n):
    if out[i]==1:
        print(i+1,end=' ')

24.FJ字符串

n=int(input())
an=''
for i in range(n):
    an=an+chr(ord('A')+i)+an
print(an)

25.sin之舞

n=int(input())
def An(n,i=1):
    if i==n:
        return 'sin('+str(n)+')'
    else:
        if i%2==0:
            s='+'
        else:
            s='-'
        return 'sin('+str(i)+s+An(n,i+1)+')'
def Sn(m,i=1):
    if m==1: 
        return An(m)+'+'+str(i)
    else:
        return '('+Sn(m-1,i+1)+')'+An(m)+'+'+str(i)
print(Sn(n))

26.数的读法

整个字符串倒着每四位截取一次存入一个列表，封装一个四位读法的函数

str.strip()把字符串头和尾的空格，以及位于头尾的nt给删掉

d = {'1':'yi', '2':'er','3':'san','4':'si','5':'wu','6':'liu','7':'qi','8':'ba','9':'jiu','0':'ling'}
n = input().strip()#str.strip()就是把这个字符串头和尾的空格，以及位于头尾的n t之类给删掉
a = []
b = [] #b存的是逆序的读法，最后再逆序输出即为结果
def numexchange(i): 
    i = i[::-1]
    for j in range(len(i)):
        if j == 0:
            if i[j]!='0':
                b.append(d[i[j]])
        elif j == 1:
            if i[j]=='0'  and  i[0]!='0':
                b.append(d['0'])
            elif i[j] == '1' and len(i)==2:
                b.append('shi')
            elif i[j]!='0':
                b.append('shi')
                b.append(d[i[j]])
        elif j == 2:
            if i[j]=='0'  and i[1]!='0':
                b.append(d['0'])
            elif i[j]!='0':
                b.append('bai')
                b.append(d[i[j]])
        elif j == 3:
            if  i[j]!='0':
                b.append('qian')
                b.append(d[i[j]])
            elif i[j]=='0'  and i[2]!='0':
                b.append(d['0'])

while n!='':  #倒着读，每四位为一组字符串
    if len(n)>=4:
        s = n[-4:] #取后四位
        n = n[:-4] #删除后四位
        a.append(s) 
    else:
        a.append(n)
        n = ''
for i in range(len(a)):
    if i == 0:
        numexchange(a[i])
    elif i == 1:
        b.append('wan')
        numexchange(a[i])
    elif i == 2:
        b.append('yi')
        numexchange(a[i])
for i in range(len(b)-1,-1,-1):
    if i == len(b)-1:
        print(b[i],end='')
    else:
        print(' %s'%(b[i]),end='')

27.完美的代价

n=int(input())
pal=list(input())

count=0#count用来计交换的次数
flag=0 #flag判断是否已经有一个单独的奇数个字符了
i=0 #用于计数外层丢弃的字符
while len(pal)>1:
    for k in range(len(pal)-1,0,-1):
        #从后面往前一直到1,寻找和pal[0]相同的pal[k]
        if pal[k]==pal[0]:
            count+=len(pal)-k-1
            #最外层的已构成回文，不考虑
            pal.pop(0)#pal(i)被pop掉后，索引整体前移1，所以k的位置需要-1
            i+=1
            pal.pop(k-1)#把找到的字符直接移到最外层，即直接pop掉
            break
        elif k==1:#如果找不到相同的，该字符放到中间
            pal.pop(0)#找不到的这个数丢弃，不能影响后续判断
            if n%2==0 or flag==1:
                print('Impossible')
                exit()
            flag=1
            count+=int(n/2)-i#把出现奇数次的字符直接移到中间需要的部署
print(count)

28.矩形面积交

while True:
    try:
        n1=list(map(float,input().split()))
        n2=list(map(float,input().split()))

    
        if n1[0]>n1[2]:
            n1[0],n1[2]=n1[2],n1[0]
        if n1[1]>n1[3]:
            n1[1],n1[3]=n1[3],n1[1]
        if n2[0]>n2[2]:
            n2[0],n2[2]=n2[2],n2[0]
        if n2[1]>n2[3]:
            n2[1],n2[3]=n2[3],n2[1]
        x=min(n1[2],n2[2])-max(n1[0],n2[0])
        y=min(n1[3],n2[3])-max(n1[1],n2[1])
        s=0
        if x<0 or y<0:
             s=0
        else:
             s=x*y
        print("{:.2f}".format(s))
    except:
        break

29.矩阵乘法

def multi_rect(rect_1, shape_1, rect_2, shape_2):
    if shape_1[1]!=shape_2[0]:
        return
    rect_=[[0 for _ in range(shape_2[1])] for _ in range(shape_1[0])]
    shape_=(shape_1[0],shape_2[0])
    for i in range(shape_1[0]):
        for k in range(shape_2[1]):
            for j in range(shape_1[1]):
                rect_[i][k]+=rect_1[i][j]*rect_2[j][k]
    return rect_,shape_
n,m=map(int,input().split())
rect=[[] for i in range(n)]
for i in range(n):
    rect[i]=list(map(int,input().split()))
result,shape=rect,(n,n)
#当方阵的0次幂为单位阵
if m==0:
    result=[[0 for _ in range(shape_2[1])] for _ in range(shape_1[0])]
    for i in range(n):
        result[i][i]=1
else:        
    for _ in range(m-1):
        result,shape=multi_rect(rect,(n,n),result,shape)
for i in range(shape[0]):
    for j in range(shape[1]):
        print(result[i][j],end=' ')
    print()

30.分解质因数

import math
#判断是否为质数
def zhi(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            return False
    return True
a,b=map(int,input().split())
for i in range(a,b+1):
    if zhi(i):
        print(i,'=',i,end='',sep='')
    else:
        print(i,'=',end='',sep='')
        temp=i
        while temp>1:
            for j in range(2,i):
                if temp%j==0:
                   temp=temp//j
                   if temp!=1:
                       print(j,'*',end='',sep='')
                   else:
                        print(j,end='',sep='')
                   break
    print()

31.字符串对比

str1=input()
str2=input()
if len(str1)!=len(str2):
    print('1')
else:
    if str1==str2:
        print('2')
    elif str1.upper()==str2.upper():
        print('3')
    else:
        print('4')

32.时间转换

n = int(input())
h = int(n / 3600)
m = int((n - h * 3600) / 60)
s = int(n - h * 3600 - m * 60)
print(h, ':', m, ':', s, sep='')

提高

1.预测身高

gender, father_height, mother_height = map(float, input().split())

if gender == 1:
    height = (father_height + mother_height) / 2 * 1.08
else:
    height = (father_height * 0.923 + mother_height) / 2

print('%.3f' % height)

2.最长滑雪道（深度递归搜索）

def dfs(x,y):
    max_height=1
    if dp[x][y]>0:#如果已经有了当前位置出发的最大距离，则直接返回
        return dp[x][y]
    for k in range(4):
        tx=x+next_[k][0]
        ty=y+next_[k][1]
        if tx<0 or tx>=row or ty<0 or ty>=col:#越界情况
            continue
        if arr[tx][ty]>=arr[x][y]:
            continue
        max_height=max(max_height,dfs(tx,ty)+1)#符合，递归搜索下一个位置且距离加一
    dp[x][y]=max_height#最终距离放在此矩阵中保存
    return dp[x][y]#返回该位置下的最大距离
row,col=map(int,input().split())
dp=[[0 for _ in range(col)] for _ in range(row)]  # 记录从每个位置(x, y)开始，它的最大长度
arr = [list(map(int, input().split())) for _ in range(row)]
next_=[[0, 1], [1, 0], [0, -1], [-1, 0]]  # 用来表示(x, y)的上下左右四个位置
ans=0
for i in range(row):
    for j in range(col):
        ans=max(ans,dfs(i,j))
print(ans)

3.K好数（动态规划DP）

def count(length,kind,ans):
    for i in range(1,kind):
        dp[0][i]=1
    for i in range(1,length):
        for j in range(kind):
            for k in range(kind):
                if abs(j-k)!=1:
                    if j-1==0 and k==0:#排除首位为0的情况
                        continue
                    dp[i][j]=dp[i][j]+dp[i-1][k]
                    dp[i][j]%MOD
    for i in range(kind):
        ans+=dp[length-1][i]
        ans%=MOD
    return ans
K,L=map(int,input().split())
ans=0
MOD=1000000007
dp=[[0 for _ in range(max(L,K))] for _ in range(max(L,K))]
if K==1 and L==1:
    print(0)
elif K>1 and L==1:
    print(K)
elif L>1:
    print(count(L,K,ans))

4.石子游戏（贪心原则）

n=int(input())
result=0
data=[int(input()) for _ in range(n)]
while len(data)!=1:
    data.sort()
    result+=(data[-1]+1)*(data[-2]+1)
    data[-2]+=data[-1]
    data.pop(-1)
print(result)

5.幸运顾客

n=int(input())
arr=[]
rs=[]
ans=0
for i in range(n):
    data=int(input())
    if data!=-1:
        arr.append(data)
    else:
        arr.sort()
        rs.append(arr[ans])
        ans+=1
for i in range(len(rs)):
    print(rs[i])

6.最长公共子序列（动态规划）

def lcs(str_a, str_b):
    len_a = len(a)
    len_b = len(b)
    arr = [[0 for _ in range(len_b + 1)] for _ in range(len_a + 1)]
    for i in range(len_a + 1):
        for j in range(len_b + 1):
            if i == 0 or j == 0:
                arr[i][j] = 0
            elif i > 0 and j > 0 and str_a[i - 1] == str_b[j - 1]:
                arr[i][j] = arr[i - 1][j - 1] + 1
            else:
                arr[i][j] = max(arr[i][j - 1], arr[i - 1][j])
    return arr[len_a][len_b]


a = input()

b = input()

print(lcs(a, b))

7.复数求和

n=int(input())
real=0
imaginary=0
com=[tuple(map(int,input().split())) for _ in range(n)]
for i in range(n):
    real+=com[i][0]
    imaginary+=com[i][1]
print(real,'+',imaginary,'i',sep='')

8.成绩排名（结构体）

n=int(input())
information=[tuple(input().split()) for _ in range(n)]
information.sort(key=lambda x:x[0])#先排姓名，按字母顺序
information.sort(key=lambda x:int(x[1]),reverse=True)#后排成绩，从大到小

for i in range(n):
    print(information[i][0])

9.递归倒置字符数组

字符串是不可变的，要想改变，需要把它强制转为列表

a,b=b,a

n,s=input().split()
n=int(n)
s=list(s)
i=0
while i<n//2:
    s[i],s[n-i-1]=s[n-i-1],s[i]
    print(''.join(s))
    i+=1
print('n'+''.join(s))

10.字符串跳步

s=input()
start,step=map(int,input().split())
print(s[start::step])

11.队列操作

n=int(input())
dui=[]
for i in range(n):
    a=list(map(int,input().split()))

    if a[0]==1:
        dui.append(a[1])
    elif a[0]==2:
        if len(dui)!=0:
            print(dui[0])
            dui.pop(0)
        else:
            print("no")
    else:
        print(len(dui))

12.字符串操作

s=input()
off_on=int(input())
n=int(input())
dui=[]
for _ in range(n):
    ss=input()
    if off_on==1:
        if s in ss:
            dui.append(ss)
    else:
        if s.upper() in ss.upper():
            dui.append(ss)
for i in dui:
    print(i)

13.金陵十三钗（n皇后）

n=int(input())
sum1=0
a=[list(map(int,input().split())) for _ in range(n)]
b=[0 for _ in range(n)]
queen()
print(sum1)
def queen(cur=0):
    global sum1,n
    if cur==n:#所有的皇后都正确放置完毕，输出每个皇后所在的位置
        sum2=0
        for i in range(n):
            sum2+=a[i][b[i]]
        if sum2>sum1:
            sum1=sum2
        return 0

    for i in range(n):
        flag=True
        for j in range(cur):#检测本次所放的位置是否在同行同列
            if b[j]==i:#是的话，该位置不能放，向上回溯
                flag=False
                break
        if flag:#否的话，继续放下一个
            b[cur]=i
            queen(cur+1)

真题

1.不同字串

var = '0100110001010001'
num=1
sep=1
var_n=[]
while sep<len(var):
    var_n.append(var[0:sep])
    print(var_n)
    print('--------------------------------------')
    for i in range(len(var)-sep):#以sep为间隔依次向前推进，sep每轮循环增1
        if var[i+1:i+sep+1] in var_n:
            continue
        else:
            var_n.append(var[i+1:i+sep+1])
    sep+=1
    num+=len(var_n)
    print(var_n)
    var_n=[]
print(num)

2.年号字串

string='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ans=[0 for _ in range(5)]
index=0
n=2019
while n!=0:
    t=n%26
    n=int(n/26)
    ans[index]=string[t-1]
    index+=1
print(ans)
for i in range(index-1,-1,-1):
    print(ans[i],end='')

3.数列求值

给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求第 20190324 项的最后 4 位数字。

ans=[0 for _ in range(20190325)]
ans[0]=ans[1]=ans[2]=1
for i in range(3,20190325):
    ans[i]=(ans[i-1]+ans[i-2]+ans[i-3])%10000
print(ans[20190323])

4.数的分解

#把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包含数字 2 和 4，一共有多少种不同的分解方法？
#注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和 1001+1000+18 被视为同一种。

count=0
def check(x):
    while x!=0:
        t=x%10
        x=int(x/10)
        if t==2 or t==4:
            return False
    return True

for i in range(1,2019):
    if check(i):
        for j in range(i+1,2019):
            if check(j):
                k=2019-i-j
                if k>j and check(k):
                    count+=1
        
print(count)

5.迷宫（广度搜索）

#创建节点类
class Node(object):
    def __init__(self,x,y,w):
        self.x=x
        self.y=y
        self.w=w
    def __str__(self):
        return self.w
def up(node):
   return Node(node.x-1,node.y,node.w+'U')
def down(node):
    return Node(node.x+1,node.y,node.w+'D')
def left(node):
    return Node(node.x,node.y-1,node.w+'L')
def right(node):
    return Node(node.x,node.y+1,node.w+'R')

m,n=map(int,input().split())
visited=set()#存储访问过的节点
queue=[]#存储要访问的节点
arr=[[0]*(n+1)]
for i in range(1,m+1):
    arr.append([0]*(n+1))
    num="0"+input()
    for j in range(n+1):
        arr[i][j]=int(num[j])

node=Node(1,1,"")#从第一个节点开始访问
queue.append(node)
while len(queue)!=0:
    moveNode=queue[0]
    queue.pop(0)
    moveStr=str(moveNode.x)+" "+str(moveNode.y)
    if moveStr not in visited:
        visited.add(moveStr)
        if moveNode.x==m and moveNode.y==n:
            print(len(moveNode.__str__()))
            print(moveNode)
            break
        if moveNode.x < m:
                if arr[moveNode.x + 1][moveNode.y] == 0:  # 向下的情况
                    queue.append(down(moveNode))
        if moveNode.y > 1:
                if arr[moveNode.x][moveNode.y - 1] == 0:  # 向左的情况
                    queue.append(left(moveNode))
        if moveNode.y < n:
                if arr[moveNode.x][moveNode.y + 1] == 0:  # 向右的情况
                    queue.append(right(moveNode))
        if moveNode.x > 1:
                if arr[moveNode.x - 1][moveNode.y] == 0:  # 向上的情况
                    queue.append(up(moveNode))

6.特别数的和

n=int(input())

def check(x):
    while x!=0:
        t=x%10
        x=int(x/10)
        if t==0 or t==1 or t==2 or t==9:
            return True
    return False
sum=0
for i in range(1,n+1):
    if check(i):
        sum+=i
print(sum)

7.完全二叉树的权值

完全二叉树每一行的最后一个数的下标都是等于(2^n)-1

n = int(input())

data = list(map(int, input().split()))

deep = flag_deep = 1

max_sum = 0

while 2 ** deep - 1 <= n:

    data_sum = sum(data[2 ** (deep - 1) - 1:(2 ** deep)-1])

    if max_sum < data_sum:

        max_sum = data_sum

        flag_deep = deep

    deep += 1

print(flag_deep)

8.等差数列

先排序，然后找出等差数列的差值，之后从给数组的最小到最大开始循环，步长为差值

#注意要考虑公差为零的情况
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
d=arr[1]-arr[0]
for i in range(n-1):
    if (arr[i+1]-arr[i])<d:
        d=arr[i+1]-arr[i]
if d==0:
    print(n)
m=(arr[-1]-arr[0])//d+1
print(m)

9.换钞票

min_count=100
for one in range(1,10):
    five=0
    two=one*10
    money=200-two*2-one
    count=0
    if money%5==0:
        five=money/5
    count=one+two+five
    if min_count>count and five!=0:
        min_count=count
print(int(min_count))

10.调手表

每次加1，遇到被整除的地方，原先的计数器置0，整除计数器加1

#最优策略按键，从任意一个分钟调到另外任意一个分钟数最多要按多少次
n,k=map(int,input().split())
ans=[]
count=count_=0

for i in range(1,n):
    if i%k!=0:
        count+=1
    else:
        count=0
        count_+=1
    ans.append(count+count_)
print(ans)
print(max(ans))

11.矩阵求和

import math
n=int(input())
arr=[[0 for i in range(n)] for i in range(n)]
sum=0
mod=10**9+7
for i in range(n):
    for j in range(n):
        arr[i][j]=(math.gcd(i+1,j+1))**2
        sum+=arr[i][j]%mod

print(sum)

12.分数

import math
a=0
for i in range(20):
    a+=2**i
gc=math.gcd(a,2**19)
print(a//gc,'/',2**19//gc,sep='')

13.购物单

def result(s):
    return (float(s[0])*float(s[1]))/100

file=open('data.txt','r')
ans=0
for line in file.readlines():
    s=line.split()
    ans+=result(s)

file.close()
print(ans)

14.等差素数列

def init_num():
    global tot
    for i in range(2, N):
        if dp[i] == 1:
            continue
        prim[tot] = i  # 记录N以内的所有素数
        tot += 1
        j = i
        while i * j < N:
            dp[i * j] = 1  # 不是素数的位置标记1
            j += 1


N = 1000010  # N的大小自己可以估计一下 想想也应该挺大的 多试几次

dp = [1, 1] + [ 0] * N

tot = 0

dif = 1

prim = [0] * N

init_num()

# print(dp[:100])
# print(prim[:100])

print(tot)

while dif * 10 < N:
    for j in range(tot):
        flag, temp = True, prim[j]
        for k in range(1, 10):  # temp后边是否再有9个满足等差条件的素数
            if temp + dif >= N or dp[temp + dif] == 1:
                flag = False
                break
            else:
                temp += dif
        if flag == True:
            print(dif, prim[j])
            exit()
    dif += 1

15.承压计算

arr = [[0] * 30 for _ in range(30)]

k = 0

file = open('data.txt', 'r')

for line in file.readlines():
    new_line = line.split()
    for i in range(len(new_line)):
        arr[k][i] = int(new_line[i])
    k += 1

for i in range(1, 30):
    for j in range(29):
        arr[i][j] += arr[i - 1][j] / 2
        arr[i][j + 1] += arr[i - 1][j] / 2

print(min(arr[29]), max(arr[29]))

print(2086458231 / min(arr[29]) * max(arr[29]))

16.方格分隔

以（3，3）为起点进行深搜，如果搜到了边界，那么它的中心对称点也到了边界沿着已经搜过的点剪开，最后的结果要除于4

def dfs(x, y):
    global ans
    if x == 0 or x == n or y == 0 or y == n:
        ans += 1
        return

    for i in range(4):
        tx = x + directions[i][0]
        ty = y + directions[i][1]
        if arr_map[tx][ty] == 0:
            arr_map[tx][ty] = 1
            arr_map[n - tx][n - ty] = 1
            dfs(tx, ty)
            arr_map[tx][ty] = 0
            arr_map[n - tx][n - ty] = 0

    return ans / 4


n = 6
ans = 0
arr_map = [[0] * (n + 1) for i in range(7)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
arr_map[3][3] = 1
# print(arr_map)

if __name__ == '__main__':
    print(dfs(n // 2, n // 2))  # 509
    # print(ans)

17.迷宫

data=[]
file=open('data.txt','r')
for line in file.readlines():
     line=list(line.strip())
     data.append(line)
data_map = [[0] * 10 for _ in range(10)]

def dfs(x, y):
    global ans
    while True:
        if x > 9 or x < 0 or y > 9 or y < 0:
            ans += 1
            # print(ans)
            break

        if data_map[x][y] == 1:
            break
        # 记录走过的位置
        data_map[x][y] = 1

        if data[x][y] == 'U':
            x -= 1

        elif data[x][y] == 'D':
            x += 1

        elif data[x][y] == 'L':
            # print(x, y)
            y -= 1

        elif data[x][y] == 'R':
            y += 1

def get_num():
    global data_map
    global ans
    for i in range(0,10):
        for j in range(0,10):
            #对每个位置进行遍历，注意每次遍历开始前要先对data_map清0
            data_map=[[0]*10 for _ in range(10)]
            dfs(i,j)
    return ans
ans=0
print(get_num())

18.15.125GB

19.约数个数

n=1200000
num=2
for i in range(2,n):
        if n%i==0:
            num+=1
print(num)

20.叶节点数

21.数字九

def check(n):
    arr=list(str(n))
    for i in range(len(arr)):
        if arr[i]=='9':
            return True
    return False
num=0
for i in range(1,2020):
    if check(i):
        num+=1
print(num)

22.数位递增的数

def check(n):
    arr=list(str(n))
    for i in range(len(arr)-1):
        if arr[i]>arr[i+1]:
            return False
    return True
num=0
n=int(input())
for i in range(1,n):
    if check(i):
        num+=1
print(num)

23.递增三元组

def check(i):
    if a[i]<a[i+1]<a[i+2]:
        return True
    else:
        return False
n=int(input())
a=list(map(int,input().split()))
a.sort()
num=0
for i in range(0,len(a)-2):
    if check(i):
        num+=1
print(num)

24.音节判断

s=list(input())
yuan=['a','e','i','o','u']
num=1
a=1
while num<len(s):
    if s[num] not in yuan:
        num+=1
    else:
        a+=1
        break
    
while num<len(s):
    if s[num]  in yuan:
        num+=1
    else:
        a+=1
        break
while num<len(s):
    if s[num] not in yuan:
        num+=1
    else:
        a+=1
        break
while num<len(s):
    if s[num] in yuan:
        num+=1
    else:
        a+=1
        break
if a==4:
    print('yes')
else:
    print('no')

25.长草

n,m=map(int,input().split())
arr=[[] for i in range(n)]
for i in range(n):
    arr[i]=list(input())

k=int(input())
next_ = [[-1, 0], [1, 0], [0, -1], [0, 1]]  # 用来表示(x, y)的上下左右四个位置

def grow_grass(x,y):
    for q in range(4):
        tx=x+next_[q][0]
        ty=y+next_[q][1]
        if tx>=0 and tx<n and ty>=0 and ty<m:
            if arr[tx][ty]=='.':
                arr[tx][ty]='g'
                flag[tx][ty]=1
for i in range(k):
    flag=[[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if arr[i][j]=='g' and flag[i][j]==0:
                flag[i][j]=1
                grow_grass(i,j)
for i in range(n):
    for j in range(m):
        print(arr[i][j],sep='',end='')
    print()

26.序列计数

n=int(input())
res_list=[]
temp_list=[]
accept_list=[]
MOD=10000

def next_list(res):
    res_=[]
    size=len(res)
    ab=abs(res[size-1]-res[size-2])
    if ab<=1:
        return None
    for i in range(1,ab):
        new_res=[]
        new_res+=res
        new_res.append(i)
        res_.append(new_res)
    return res_

for i in range(1,n+1):
    res=[n,i]
    res_list.append(res)
temp_list+=res_list
while len(temp_list)>0:
    for i in range(len(temp_list)):
        next_=next_list(temp_list[i])
        if next_ is not None:
            accept_list+=next_
    temp_list.clear()
    if len(accept_list)!=0:
        temp_list=temp_list
        res_list+=accept_list
        accept_list.clear()
print(len(res_list)%MOD)

27.晚会节目单

采用了标号的方法，对每一个数按照输入从大到小进行编号，在排列好的前m个最大数在对其标号进行排序，标号小的先输出即可。

n,m=map(int,input().split())
arr=list(map(int,input().split()))
new=[]
for i in range(len(arr)):
    new.append((arr[i],i))
new=sorted(new,reverse=True)
new=new[:m:1]
new=sorted(new,key=lambda x:x[1])
for i in range(len(new)):
    print(new[i][0],end=' ')

28.合根植物

def init(n):
    for i in range(1, n+1):
        pre[i] = i


def find_pre(key):
    """找key的根，也就是找带头大哥"""
    if pre[key] == key:
        return key
    else:
        return find_pre(pre[key])  # 如果当前节点不是根节点，就找当前节点的父节点的根节点。最后的到的根就是key的根


def unite(x, y):
    """如果x和y不相连则连接它们，即x的根和y的根不同，则让一方从属于另一方"""
    rootx = find_pre(x)
    rooty = find_pre(y)
    if rootx != rooty:
        pre[rootx] = rooty


m, n = list(map(int, input().split()))
line = int(input())
ans = 0
lst = [0 for i in range(m*n+1)]
pre = [0 for i in range(m*n+1)]  # 存放以索引值为节点序号的点的根节点
init(m*n)  # 初始化每个节点的根节点都为它自己，即开始时都各不相连
for i in range(line):
    x, y = list(map(int, input().split()))
    unite(x, y)  # 每输入两个有关联的节点，就让他们相连
print(pre)
for i in range(1, m*n+1):
    lst[find_pre(i)] = 1  # 遍历每个节点，把她们对应的根节点的索引位置赋值1，比如节点1的老大是13，5的老大也是13，则他们属于1个节点集，操作和都只能将lst的13索引的地方赋值1
for i in range(1, m*n+1):  # 等于1的个数就是最后的子集个数
    if lst[i] == 1:
        ans += 1
print(ans)

29.第几个幸运数

MAX=59084709587505
a=[3,5,7]
s=set()
tou=1
while True:
    for i in a:
        t=tou*i
        if t<=MAX:
            s.add(t)
    lst=sorted(s)
    for i in lst:
        if i>tou:
            tou=i
            break
    if tou>=MAX:
        break
print(s)
print(len(s))