蓝桥杯python组算法模板与习题_蓝桥杯python组和c++组题目一样吗

目录

一、一些简单的处理技巧和语法

1、小技巧

1.1   python中的快读（sys库）

1.2  python程序测试时间（仅供参考实际比赛可能也没啥用）

1.3  python中日期处理等问题小技巧

2、基础语法

2.1  首先就是标准格式化输入输出

2.2  四舍五入和取整函数以及math库其他常用api

2.3、循环的使用

2.4、进制转换

2.5、列表(list)的一些api

2.6、集合(set)的一些api

2.7、字符串(str)的一些api

二、基础算法篇

1、排序算法（快排、归并排、内置sort）

1.1  快速排序板子     快速排序模板题（洛谷）

1.2  归并排序板子     归并排序模板题（洛谷）

1.3  归并排序的运用--求逆序对     求逆序对数量（AcWing） 逆序对（洛谷）

1.4  内置sort排序     分数划定（洛谷）

2.1 二分算法     

3.1前缀和差分  

---

一、一些简单的处理技巧和语法

1、小技巧

1.1   python中的快读（sys库）

def read():
    return sys.stdin.readline().strip()

       通过一些简单的测试发现在较多行数据读入的时候是可以读入更快的本人实测了跑了一个当时是用快读比普通读入快一倍左右，对于蓝桥杯oi赛制来说还是挺有用的，当然个别题好像不快读用python还过不了。

1.2  python程序测试时间（仅供参考实际比赛可能也没啥用）

import time
def my_function():
    main()
    '''
    res = 0
    for i in range(28900000):
        res+=i
    '''
start_time = time.time()
my_function()
end_time = time.time()
print("Time taken: {:.5f} seconds".format(end_time - start_time))

        通过以上代码你可以测试一下你写的代码需要运行的时间，个人实测了一下我的电脑跑python的程序大概每秒可以进行约3e7次加法，当然实际上蓝桥的测评机应该会小于这个数值。在实际比赛中可以利用这个小技巧不断的提高程序效率骗分。·

1.3  python中日期处理等问题小技巧

#python中时间日期包的使用技巧
from datetime import datetime, timedelta
 
start_date = datetime(2023, 4, 1)  # 起始日期
end_date = datetime(2023, 4, 10)  # 结束日期
 
current_date = start_date
# 循环遍历日期范围内每一天并输出
while current_date <= end_date:
    print(current_date.strftime('%Y-%m-%d'))
    current_date += timedelta(days=1)

       日期时间问题也是蓝桥杯中基本上每年都是必考点了，处理日期问题利用python还是很方便的，但是难点可能就是记不住那些日期时间的api，深刻的领悟，然而python的帮助文档还是全英文的，看起来很废时间。 当然可能会想到使用excel来处理时间。不过有些考点好像是不会装excel的。时间日期问题在蓝桥官网题库里还是有一些的，建议可以统统刷一遍总结一下出题思路，万变不离其中。

2、基础语法

2.1  首先就是标准格式化输入输出

#首先就是python不换行输出可以利用,end参数
for i in range(10):
    print("You will Win",end=' ')
#通过上述方法就可以不换行输出以单空格输出了
 
print("You will get {:.6f}".format(149.999999))
print("You will get %.6lf"%(149.999999))
#格式化输出常采用上述两种方法

2.2  四舍五入和取整函数以及math库其他常用api

#四舍五入和取整
import math
x = 3.1415926
print(round(x,2))  #保留两位小数
print(math.ceil(x))  #上取整
print(math.floor(x))  #下取整
print(int(x))  #向0取整
 
#math库其他常用api
print(math.sqrt(4))  #开根号函数
print(math.pow(2,4))  #指数函数其实也可以用2**4
print(math.fabs(-1))  #浮点绝对值函数

2.3、循环的使用

#python的循环的使用
a = [0,1,2,3,4,5,6,7,8,9,10]
for i in range(2,5):  #部分正序输出
    print(a[i],end = ' ')
print()
for i in range(4,1,-1):  #部分逆序输出
    print(a[i],end = ' ')
print()
#.join函数的使用其实就是split()函数的逆过程对象必须为字符串列表
print('-'.join(['1','2','3']))

2.4、进制转换

#python中常用的进制转换   转换后的东西一般为字符串需要处理掉前两位
print(bin(7)[2:])  #二进制
print(oct(8*8*8-1)[2:])  #八进制
print(hex(16*16-1)[:])  #十六进制
 
print(int('111',2))   #二转10
print(int('777',8))   #八转10
print(int('ff',16))   #16转10
 
#字符串可以直接转化为整形和浮点形
a,b = input().split()
print(int(a),float(b))
#ASCLL转整数和整数转ASCLL
print(ord('A')) #ascll转整数
print(chr(65))  #整数转字符
print(str(65))

       有关各种进制问题的处理也是蓝桥杯常考的点，这部分建议大家还是得掌握一下并且多刷题，一般好像也不会很难。

2.5、列表(list)的一些api

#python列表的一些api
a = [0,1,2,3]
a.insert(0,-1) #i的位置插入b insert(i,b)
print(a)
a.remove(-1)  #删除列表中第一个值为num的数 ,如果找不到会报错
print(a)
print(-1 in a)
tep = a.pop(0)  #移除并返回索引为i的数
print(tep,a)
tep = a.count(1)  #返回列表中num的数量
print(tep)
b = [[1,2],[3,2],[3,1],[2,0],[2,3],[2,-19]]
def cmp(a):      #自定义排序
    return (a[0],a[1])
b.sort(key=cmp)
print(b)
b.reverse()    #逆序反转
print(b)

        python的列表相比于c++的vector等容器还是强大很多，类型不受限制。不过python的列表占用的空间相比较与c++的数组啥的还是大很多，开大了容易寄。

2.6、集合(set)的一些api

#python集合的一些api
a = set()
for i in range(11):
    a.add(i)   #添加元素
print(a)
a.remove(0)
print(a)
#遍历集合只能用for i in a:
#判断某个元素是否在集合中可以用in关键字
print(0 in a)
a.clear() #清空

2.7、字符串(str)的一些api

#python字符串的一些api
s = 'hello world'
i = s.find('world')  # 查找子字符串在原字符串中的位置
print(i)
s = 'Hello World'
lower_s = s.lower()  # 转换为小写
upper_s = s.upper()  # 转换为大写
print(lower_s,upper_s)   #大小写转换函数（非字母不变）

二、基础算法篇

1、排序算法（快排、归并排、内置sort）

1.1  快速排序板子     快速排序模板题（洛谷）

#python快速排序板子
def quicksort(nums, start, end):
    if start >= end :
        return 
    left, right = start, end
    pivot = nums[(start + end) // 2]
    while left <= right:
        while left <= right and nums[left] < pivot:
            left += 1
        while left <= right and nums[right] > pivot:
            right -= 1
        if left <= right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -=1
    quicksort(nums, start, right)
    quicksort(nums, left, end)

1.2  归并排序板子     归并排序模板题（洛谷）

n = int(input())
list1 = list(map(int, input().split()))
 
def merge_sort(list1):
    if len(list1) <= 1:
        return
    mid = len(list1) // 2
    L = list1[:mid]
    R = list1[mid:]
    merge_sort(L)
    merge_sort(R)
    i = j = k = 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            list1[k] = L[i]
            i += 1
        else:
            list1[k] = R[j]
            j += 1
        k += 1
    while i < len(L):
        list1[k] = L[i]
        k += 1
        i += 1
    while j < len(R):
        list1[k] = R[j]
        k += 1
        j += 1

1.3  归并排序的运用--求逆序对     求逆序对数量（AcWing） 逆序对（洛谷）

def merge_sort(nums):
    if len(nums) <= 1:
        return 0
    mid = len(nums) // 2
    L = nums[:mid]
    R = nums[mid:]
    ans = merge_sort(L) + merge_sort(R)
    # 归并的过程
    i = j = k = 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            nums[k] = L[i]
            k += 1
            i += 1
        else:
            nums[k] = R[j]
            ans += len(L) - i
            k += 1
            j += 1
    while i < len(L):
        nums[k] = L[i]
        k += 1
        i += 1
    while j < len(R):
        nums[k] = R[j]
        k += 1
        j += 1
    return ans

1.4  内置sort排序     分数划定（洛谷）

#用列表来模拟结构体，以首先以第一个数大小排序，然后以第二个数大小排序
def cmp(x):
    return (x[0],x[1])
a.sort(key=cmp,reverse=False)

       排序算法特别基础，相较于快排和归并其实python内置的sort函数是更快的，所以学会自定义排序,利用sort函数和key排序规则十分重要。当然貌似一般的比赛中会sort就足够了，快排和归并的思想还是要会的，特别是利用归并排序求逆序对数量是一个比较有用的方法。如果感兴趣可以刷一下下面的题单：排序算法题单

2.1 二分算法     

#二分：整数二分
def check(mid):
    '''条件'''
def erfen1(l,r):
    while l<r:
        mid = (l+r)>>1;
        if check(mid):
            r = mid
        else:
            l = mid+1
    return l
def erfen2(l,r):
    while l<r:
        mid = (l+r+1)>>1;
        if check(mid):
            l = mid
        else:
            r = mid-1
    return l
 
#浮点数二分
def erfen3(l,r):
    eps = 0.0000001
    while l<r:
        mid = (l+r)/2
        if check(mid):
            r = mid
        else:
            l = mid
    return l
#通用
def binary_search(arr, target):
    """
    在有序数组arr中查找目标值target
    :param arr: 有序数组
    :param target: 目标值
    :return: 如果找到，返回目标值在数组中的索引；否则，返回-1
    """
    left, right = 0, len(arr) - 1  # 定义左右指针
    while left <= right:
        mid = (left + right) // 2  # 计算中间位置
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

        二分算法一般是用来做优化的，一般情况下不用二分的话直接暴力也可以拿到一些分。二分算法的模板比较简单一定要会。同时对于python来说就没有什么所谓的高精度了，python自带高精度，可以直接进行大数运算。习题：洛谷二分题集   

3.1前缀和差分  

#一维的前缀和
s[i] = s[i-1] + a[i]
#二维的前缀和
s[i][j] = s[i-1][j] + s[i][j-1] -s[i-1][j-1] + a[i][j]
#一维的差分 区间[l,r]中的每个数加上c:  
a[l] += c,a[r+1] -= c
#二维差分  给左上角(x1,y1),(x2,y2)为右下角的子矩阵中所有元素加上c
s[x1][y1] += c, s[x1][y2+1] -=c; s[x2+1][y1] -= c, s[x2+1][y2+1] +=c
#位运算   求n的第k位数字: n>>k&1
#返回n的最后一位1: lowbit(n) = n&(-n)
 

---