pythonRevive

蓝桥杯 Python 软件赛最基础复习笔记

鼠鼠裸考临时抱佛脚用的

---

1. 输入输出与基础语法

1.1 输入方式总结

# 单个整数
n = int(input())

# 一行多个整数
a, b = map(int, input().split())

# 多行输入
lines = [input() for _ in range(n)]

# 多行整数
nums = [int(input()) for _ in range(n)]

# 多组测试数据（EOF判断）
import sys
for line in sys.stdin:
    # line 为字符串
    pass

---

2. map 的使用技巧

# 读取一行字符串转为整数列表
arr = list(map(int, input().split()))

---

3. 基础排序算法

冒泡排序

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

选择排序

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

---

4. 快速幂与模运算

快速幂模板

def quick_pow(a, b, mod):
    res = 1
    while b:
        if b % 2:
            res = res * a % mod
        a = a * a % mod
        b //= 2
    return res

---

5. 容斥原理

容斥原理公式：

容斥原理常用于求多个集合中交集补集的大小：

|A ∪ B| = |A| + |B| - |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

模板：容斥原理计数（求不被整除的个数）

def count_not_divisible(n, a, b):
    ab = a * b // math.gcd(a, b)
    return n - (n // a + n // b - n // ab)

---

6. 时间处理

求某一天是星期几

import datetime
date = datetime.date(2024, 4, 11)
print(date.weekday())  # 0 表示星期一，6 表示星期日

日期加减

today = datetime.date.today()
delta = datetime.timedelta(days=3)
print(today + delta)  # 三天后

---

7. 对角线格子统计

问题描述

给定一个 N×M 的网格，统计左上角到右下角一条斜线穿过了多少个格子。

解法

def count_crossed_cells(n, m):
    from math import gcd
    return n + m - gcd(n, m)

---

Basic

class basics:

    # 一、获取多行输入组成二维数组
    n = 3  # 表示接下来有 3 行输入
    arr = [list(map(int, input().split())) for _ in range(n)]

    """
    说明：
    - input().split()：把一行字符串按空格切分成列表，例如 "1 2 3" -> ["1", "2", "3"]
    - map(int, ...)：将列表中的每个字符串转成整数
    - list(...)：将 map 返回的迭代器转为列表
    - [ ... for _ in range(n)]：执行 n 次输入，构成二维列表
    - _ 是变量名的占位符，表示“我不关心这个变量”，也可写成 i 或 line 等
    """

    # 二、获取一行输入并分别赋值给多个变量
    a, b = map(int, input().split())

    """
    说明：
    - input()：获取如 "3 5" 的输入
    - .split()：分割为 ["3", "5"]
    - map(int, ...)：转换为整数 [3, 5]
    - a, b = ...：拆包赋值给变量
    """

    # 三、map 是什么？
    """
    map 是 Python 的内置函数，用法为 map(function, iterable)
    - 会将 function 作用于 iterable 的每个元素
    - 返回一个“懒计算”的迭代器对象（map 类型）

    例如：
    nums = ["1", "2", "3"]
    mapped = map(int, nums)      # 返回 map 对象
    print(list(mapped))          # 输出 [1, 2, 3]
    """


class algorizm:
    # 冒泡排序
    def bubble(nums):
        """
        一层循环用于确定循环次数
        每次循环中，两两确认大小直至将最大的元素放在末尾
        每放一个元素到末尾，下次两两确认循环就不需要遍历到最后面已经排序号的区间
        :param nums:
        :return:
        """
        for i in range(len(nums) - 1):
            for j in range(len(nums) - i - 1):
                if nums[j] > nums[j+1]: nums[j], nums[j + 1] = nums[j+1], nums[j]
        return nums

    # 选择排序
    def select(nums):
        """
        分两侧，一侧是排序完的，一侧没有
        先将第一个元素默认当成最小的，取其索引赋值为 min_i
        遍历当前 i 元素右侧全部元素，找有没有比这个更小的值，有则这两个交换位置
        :param nums:
        :return:
        """
        for i in range(len(nums) - 1):
            min_i = i  # 开始记录当前索引
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[min_i]: min_i = j  # 出现更小的值，重新把更小值的索引给到 min_i
            if i != min_i:  # 发现跟当前索引不同，说明有更小值，需要进行交换
                nums[i], nums[min_i] = nums[min_i], nums[i]  # 交换两者位置
        return nums

Task

import os
import sys

from datetime import datetime, timedelta

def last_bell_time():
    """
    某个设备每隔 x 分钟响一次铃，问在给定时间前最后一次响铃的具体时间。

    【输入说明】
    - 第一行输入一个整数 T，表示有 T 组测试数据
    - 每组测试数据输入一行：一个时间字符串 + 一个整数 x（分钟）

    【输出说明】
    - 每组输出最近一次响铃的时间，格式为 yyyy-MM-dd HH:MM:SS

    【样例输入】
    2
    1973-12-06 00:08:38 5
    2001-01-01 00:00:01 1

    【样例输出】
    1973-12-06 00:05:00
    2001-01-01 00:00:00

    【解题思路】
    - 目标是找到当前时间之前最近一次响铃的时间。
    - 可以将时间统一转化为“从1970-01-01 00:00:00开始的总秒数”
    - 时间间隔为 x 分钟，即 x × 60 秒
    - 使用整除运算 `(totalsec // interval) * interval` 找到最近一次响铃的秒数
    - 然后将这个秒数再转回时间格式并输出

    【重点函数】
    - datetime.strptime(str, fmt)：将字符串转换为 datetime 对象
    - datetime.strftime(fmt)：将 datetime 对象格式化为字符串
    - timedelta(seconds=n)：创建一个时间差（可加减时间）
    - total_seconds()：计算两个时间对象之间的差值，返回秒数

    【完整代码】
    """

    T = int(input())
    for _ in range(T):
        line = input()
        strtime, x = line.rsplit(" ", 1)  # 拆分出时间字符串 和 响铃间隔分钟数

        start = datetime(1970, 1, 1, 0, 0, 0)  # 以 1970年为基准
        objtime = datetime.strptime(strtime, "%Y-%m-%d %H:%M:%S")  # 字符串 -> 时间对象
        totalsec = int((objtime - start).total_seconds())  # 当前时间距离1970的总秒数

        interval = int(x) * 60  # 响铃间隔（单位：秒）
        lasttimesec = (totalsec // interval) * interval  # 上一次响铃时刻的秒数

        lasttime = start + timedelta(seconds=lasttimesec)  # 秒数转回时间对象
        print(lasttime.strftime("%Y-%m-%d %H:%M:%S"))  # 输出格式化后的时间字符串

# 对角线格子值相同的对数统计

def count_diagonal_pairs():
    """
    小蓝正在和朋友们玩一种新的连连看游戏。

    在一个 n × m 的矩形网格中，每个格子中都有一个整数，第 i 行第 j 列上的整数为 A[i][j]。
    玩家需要寻找一对格子 (a,b)-(c,d)，使得：
        1. A[a][b] == A[c][d]
        2. |a - c| == |b - d| > 0

    问有多少对格子满足以上条件。

    ---------------------------------------
    ✅ 条件转化为：
    满足 |a - c| == |b - d| 的点，表示它们在 ↘ 或 ↙ 方向上的对角线上。
    所以我们按如下方式判断是否在同一对角线上：
        - ↘ 方向：i - j 相同（从左上到右下）
        - ↙ 方向：i + j 相同（从右上到左下）

    ---------------------------------------
    解题思路：
    - 用两个字典 diag1, diag2，分别记录 ↘ 和 ↙ 对角线上每个数字 val 出现的次数。
    - 遍历每个格子，如果当前数值 val 在该对角线上已出现 k 次，就可以与前面 k 个 val 组成 k 个合法格子对。
    - 每次发现就累计 k，之后把 val 的出现次数 +1。

    数据结构：
    diag1[i - j][val] -> 统计↘方向上该值出现次数
    diag2[i + j][val] -> 统计↙方向上该值出现次数

    注意：只能使用 os 和 sys 标准库，所以不用 collections.defaultdict
    """

    import sys
    input = sys.stdin.readline

    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]

    diag1 = {}  # ↘：i - j 为键
    diag2 = {}  # ↙：i + j 为键
    ans = 0

    for i in range(n):
        for j in range(m):
            val = grid[i][j]

            # 处理 ↘ 方向 (i - j)
            key1 = i - j
            if key1 not in diag1:
                diag1[key1] = {}
            if val in diag1[key1]:
                ans += diag1[key1][val]
                diag1[key1][val] += 1
            else:
                diag1[key1][val] = 1

            # 处理 ↙ 方向 (i + j)
            key2 = i + j
            if key2 not in diag2:
                diag2[key2] = {}
            if val in diag2[key2]:
                ans += diag2[key2][val]
                diag2[key2][val] += 1
            else:
                diag2[key2][val] = 1

    print(ans * 2)


# 数字字符串计数（包含3和7）
def count_valid_strings():
    """
    小蓝要构造一个长度为 10000 的数字字符串，有以下要求：

    1. 不能出现数字 0；
    2. 必须包含数字 3 和数字 7。

    求满足要求的字符串个数，结果对 10^9 + 7 取模。

    解题思路：
    - 所有可能的字符串总数为 9^10000（每位可选1~9）
    - 使用容斥原理排除不合法情况：
        - 不含3的有 8^10000 种
        - 不含7的有 8^10000 种
        - 同时不含3和7的有 7^10000 种
    - 合法数量 = 9^10000 - 2 * 8^10000 + 7^10000
    - 使用快速幂计算大指数，最后对 10^9 + 7 取模
    """
    MOD = 10 ** 9 + 7

    total = pow(9, 10000, MOD)  # 所有字符串
    no_3 = pow(8, 10000, MOD)  # 不包含3
    no_7 = pow(8, 10000, MOD)  # 不包含7
    no_3_and_7 = pow(7, 10000, MOD)  # 同时不包含3和7

    # 使用容斥原理计算合法数量
    result = (total - 2 * no_3 + no_3_and_7) % MOD

    print(result)


# 硬币兑换
def max_coin_count():
    """
    小蓝手中有 2023 种不同面值的新版硬币，
    第 i 种硬币面值为 i，数量也为 i。
    可以使用两个新版硬币兑换一个面值为 coin1 + coin2 的旧版硬币。
    问：通过任意兑换后，某个面值的硬币最多能有多少个？
    """
    # 初始化一个结果数组，result[x] 表示面值为 x 的旧硬币最多能获得多少个
    result = [0 for _ in range(4047)]  # 最大面值是 2023 + 2023 = 4046

    # 枚举所有面值的组合 i 和 j（i < j），避免重复组合
    for i in range(1, 2024):
        for j in range(i + 1, 2024):
            # 由于第 i 面值有 i 个硬币，所以可以和 j 面值的硬币兑换 i 次
            result[i + j] += i

    # 最终取兑换后任意面值中数量最多的那个
    print(max(result))


# 2023
"""
12345678 到 98765432 有多少个数完全不包含2023
def findIt(i):
  find01 = i.find('2')
  if find01 == -1: return 0

  find02 = i.find('0', find01+1)
  if find02 == -1: return 0

  find03 = i.find('2', find02+1)
  if find03 == -1: return 0

  find04 = i.find('3', find03+1)
  if find04 == -1: return 0

  return 1

count = 0
for i in range(12345678, 98765432 + 1):
  if findIt(str(i)) == 0: count += 1
print(count)
"""

# 轮转数组
def rotate(self, nums, k: int) -> None:
    """
    给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
    """
    def reverse(left: int, right: int):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
    n = len(nums)
    k %= n  # 防止轮转次数超过元素数量
    reverse(0, n-1)  # 先整体翻转
    reverse(0, k-1)  # 再把前 k 个翻转
    reverse(k, n-1)  # 再反转后面几个

# 加一
def plusOne(self, digits):

    for i in range(len(digits) - 1, -1, -1):  # 倒叙遍历到 0
        if digits[i] < 9:  # 如果小于9直接加1返回
            digits[i] += 1
            return digits
        digits[i] = 0  # 否则进一位
        return [1] + [0] * len(digits)

# 寻找数组的中心下标
def pivotIndex(self, nums) -> int:
    """
    给你一个整数数组 nums ，请计算数组的 中心下标 。
    数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
    如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
    如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
    """
    suml, sumr = 0, sum(nums)
    for i in range(len(nums)):
        sumr -= nums[i]
        if sumr == suml:
            return i
        suml += nums[i]
    return -1

# 前后缀
def prefixSuffix(nums):
    """
    给你一个整数数组 nums，返回一个新的数组 answer，其中 answer[i] 等于 nums 中 左侧所有元素的和 与 右侧所有元素的和 之和。
    要求：不要使用额外的数组（即 O(1) 额外空间，除了 answer 本身）。时间复杂度为 O(n)。
    """
    n = len(nums)
    pre = [0] * n
    suf = [0] * n
    for i in range(1, n):
        pre[i] = pre[i - 1] + nums[i - 1]
    for i in range(n - 2, -1, -1):
        suf[i] = suf[i + 1] + nums[i + 1]
    return [p + s for p, s in zip(pre, suf)]