Python 组蓝桥杯备赛（持续更新中）
|
|
2,901
|
0
|
题解
|
admin52

1735 字
|
32 分钟
本文最后更新于 465 天前，内容如有失效请评论区留言。

第 14 届蓝桥杯 Python 开发环境：Python 3.8.6、IDLE（Python 自带编辑器）

Miniconda 环境配置

Miniconda安装及使用–小白上路

Installing on Linux

conda-forge 是一个流行且广泛使用的 community-driven channel，它包含了大量的包。

安装好 miniconda 后，

conda config --add channels conda-forge
conda create --name LanqiaoCup python=3.8.6
conda activate LanqiaoCup

Python 3.8.6 在 VSCode debug 的时候会遇到 E+00000.227: Error while enumerating installed packages. 的报错，虽然依旧可以正常调试，但是看着就很不爽，解决方案如下，来自 VSCode Python: Error while enumerating installed packages。

This solved the issue for me (from https://github.com/microsoft/debugpy/issues/1379):

Locate debugpy/common/log.py under site-packages (following the path you see in the output). Find the line in that file that says:

swallow_exception(“Error while enumerating installed packages.”)}

replace it with: swallow_exception(“Error while enumerating installed packages.”, level=”info”)

Is incredible this hasn’t been released yet.

Python 命令行添加 Tab 键自动补全

Python 算法竞赛技巧

  1. Python PerformanceTips
  2. Codeforces – For Python Coders
  3. Codeforces – Python performance tips
  4. Complexity in Python:
1. def main(), global scope expensive
2. (2-D array) do not use list of list, use index instead 
3. less loop
4. Avoid dots. Cache function lookups. (e.g. use aappend=alist.append)
5. Writing output is really expensive. 
Writting a gigantic string once, may be better than writting several small strings. 
6. Type casting is really expensive. like str to int
7. deque is faster if you don't need to random access

语言基础入门

四平方和

传送门

查看 py 版本 print(sys.version)

退出 sys.exit(0)

import os
import sys
from math import sqrt

# print(sys.version)

n = int(input())
l1 = int(sqrt(n))
for i in range(0, l1 + 1):
    l2 = int(sqrt(n - i * i))
    if l2 < i: break
    for j in range(i, l2 + 1):
        l3 = int(sqrt(n - i * i - j * j))
        if l3 < j: break
        for k in range(j, l3 + 1):
            t = int(sqrt(n - i * i - j * j - k * k))
            if t < k: break
            if i * i + j * j + k * k + t * t == n:
                print(i, j, k, t)
                sys.exit(0)

最大距离

传送门

输入一个数组 a = [int(x) for x in input().split()]

n = int(input())
a = [int(x) for x in input().split()]
# print(n, a, sep="\n")
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans = max(ans, abs(a[j] - a[i]) + (j - i))
print(ans)

前缀和

求和

传送门

1-index 读入技巧：a = [0] + list(map(int, input().split()))

n = int(input())
a = [0] + list(map(int, input().split())) # 1-index 读入
sum = [0] * (n + 1)
ans = 0
for i in range(1, n + 1):
    sum[i] = sum[i - 1] + a[i]
    ans += a[i] * sum[i - 1]
print(ans)

统计子矩阵

传送门

二维数组的创建与读入：

a = [[0] for i in range(n)]
a.insert(0, [0] * (m + 1))
for i in range(1, n + 1):  # 从 a[1][1] 开始读矩阵
    a[i].extend(map(int, input().split()))
sum = [[0] * (m + 1) for i in range(n + 1)]

python 函数内访问全局变量不应该要写 global 吗？为啥 getsum 函数内不写 global sum 后得到的结果也是正确的呢？

在 Python 中，如果你只是读取全局变量的值而不修改它，那么你不需要在函数中声明该变量为 global。在你的 getsum 函数中，你只是读取了全局变量 sum 的值，并没有修改 sum，所以不需要使用 global 关键字。

global 关键字主要用于告诉 Python，你打算在函数内部修改全局变量的值。如果没有使用 global 关键字，当你试图在函数内部给一个全局变量赋值时，Python 会将这个赋值视为在函数内部创建了一个新的局部变量，而不是修改外部的全局变量。

n, m, K = map(int, input().split())
a = [[0] for i in range(n)]
a.insert(0, [0] * (m + 1))
for i in range(1, n + 1):  # 从 a[1][1] 开始读矩阵
    a[i].extend(map(int, input().split()))
sum = [[0] * (m + 1) for i in range(n + 1)]
# 计算二维前缀和
for i in range(1, n + 1):
    for j in range(1, m + 1):
        sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]
# 双指针统计答案
def getsum(l1, l2, i, j):
    # global sum
    return sum[l2][j] - sum[l1 - 1][j] - sum[l2][i - 1] + sum[l1 - 1][i - 1]

ans = 0
for l1 in range(1, n + 1):
    for l2 in range(l1, n + 1):
        j = 0
        for i in range(1, m + 1):
            while j < m and getsum(l1, l2, i, j + 1) <= K:
                j += 1
            ans += j - i + 1
print(ans)

贪心

Python应用——自定义排序全套方案

Python3 List sort()方法

快乐司机

传送门

n, W = map(int, input().split())
a = [0, 0] * (n + 1)
# a[0]->weight a[1]->value
for i in range(1, n + 1):
    a[i] = list(map(int, input().split()))
a[1:n + 1] = sorted(a[1:n + 1], key=lambda x: x[1] / x[0], reverse=True)
ans, wsum = 0.0, 0.0
for i in range(1, n + 1):
    if wsum + a[i][0] <= W:
        wsum += a[i][0]
        ans += a[i][1]
    else:
        ans += (W - wsum) * a[i][1] / a[i][0]
        wsum += W - wsum
print("{:.1f}".format(ans))

DFS & BFS

跳蚱蜢

传送门

Python 推荐使用 deque 实现队列。去重可以使用 set。

from collections import *

def insertQ(q : deque, dir : int, now : tuple, vis : set):
    pos = now[1]; sta = list(now[0])
    npos = (pos + dir) % 9
    sta[pos], sta[npos] = sta[npos], sta[pos]
    sta_str = "".join(sta)
    if sta_str not in vis:
        vis.add(sta_str)
        q.append((sta_str, npos, now[2] + 1))

q = deque()
q.append(("012345678", 0, 0))
vis = set()
vis.add("012345678")
while q:
    now = q.popleft()
    if now[0] == "087654321":
        print(now[2])
        break
    insertQ(q, 1, now, vis)
    insertQ(q, 2, now, vis)
    insertQ(q, -1, now, vis)
    insertQ(q, -2, now, vis)

字符串

单词分析

s = input()
cnt = [0] * 520
for c in s:
    cnt[ord(c)] += 1
idx = cnt.index(max(cnt))
print(chr(idx))
print(cnt[idx])

标题统计

import os, sys
import math, collections, itertools, functools, heapq, bisect, string, random

def read(fun=int, sep=" "):
    return list(map(fun, sys.stdin.readline().split(sep)))

def main():
    s = sys.stdin.readline()
    s = s.replace(' ', '').replace('\r', '').replace('\n', '')
    print(len(s))

main()

洛谷 KMP 模板

import os
import math, functools, itertools, collections, bisect, heapq, string

def read(fun=int, sep=' '):
    return list(map(fun, input().strip().split(sep)))

def main():
    S = ['$'] + list(input().strip())
    T = ['$'] + list(input().strip())
    n = len(S) - 1
    m = len(T) - 1
    Nxt = [0 for _ in range(m + 1)]
    j = 0
    for i in range(2, m + 1):
        while j > 0 and T[j + 1] != T[i]:
            j = Nxt[j]
        if T[j + 1] == T[i]:
            j += 1
        Nxt[i] = j
    j = 0
    for i in range(1, n + 1):
        while j > 0 and T[j + 1] != S[i]:
            j = Nxt[j]
        if T[j + 1] == S[i]:
            j += 1
        if j == m:
            print(i - m + 1)
            j = Nxt[j]
    print(*Nxt[1:])

main()

高级数据结构

蓝桥幼儿园

传送门

并查集模板，Python 版本

n, m = map(int, input().split())
fa = [i for i in range(0, n + 1)]

def find(x):
    if x != fa[x]:
        fa[x] = find(fa[x])
    return fa[x]

for _ in range(m):
    op, x, y = map(int, input().split())
    f1 = find(x); f2 = find(y)
    if op == 1:
        fa[f1] = f2
    if op == 2:
        if f1 == f2:
            print("YES")
        else:
            print("NO")

图论

出差

传送门

❗ 注意：在创建图G的时候，你使用了[[]] * (n + 1)的方式来初始化邻接列表。这种方式会导致所有的子列表实际上是对同一个列表的引用，从而引发错误。正确的初始化方式应该是使用列表推导式来创建独立的子列表，如下所示：

G = [[] for _ in range(n + 1)]

这样，每个顶点的邻接列表都是独立的，修改一个列表不会影响到其他列表。

Python heapq – 堆队列算法

Python 中优先队列使用 heapq 替代（小根堆），q = [] 初始化空列表，heapq.heappush(q, item) 加入元素，heapq.heappop(q) 弹出堆顶。q[0] 可以只访问最小的元素而不弹出它。

Dijkstra 模板，Pyhton 版本。模板包含自定义小于比较（__lt__）

import heapq

class Node:
    def __init__(self, v=0, d=0):
        self.v = v
        self.d = d
    def __lt__(self, t):
        return self.d < t.d

n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
G = [[] for _ in range(n + 1)]

for i in range(1, m + 1):
    u, v, w = map(int, input().split())
    G[u].append((v, w + a[v]))
    G[v].append((u, w + a[u]))

inf = 0x3f3f3f3f
dis = [inf] * (n + 1)
dis[1] = 0
q = []
heapq.heappush(q, Node(1, 0))

while q:
    t = heapq.heappop(q)
    now, d = t.v, t.d
    if dis[now] != d:
        continue
    for v, w in G[now]:
        if dis[now] + w < dis[v]:
            dis[v] = dis[now] + w
            heapq.heappush(q, Node(v, dis[v]))

print(dis[n] - a[n])

2023 年省赛 Python A 组真题

特殊日期

注意整除（//）

Python3 中 True is 1，False is 0。

def run_year(x):
    if x % 400 == 0:
        return 1
    elif x % 100 == 0:
        return 0
    elif x % 4 == 0:
        return 1
    return 0

def dig_sum(x):
    ret = 0
    while x:
        ret += x % 10
        x //= 10
    return ret

def main():
    days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
##    print(sum(days))
    ans = 0
    for year in range(1900, 9999 + 1):
        lval = dig_sum(year)
        for month in range(1, 12 + 1):
            day_ = days[month] + (month == 2 and run_year(year))
            for day in range(1, day_ + 1):
                rval = dig_sum(month) + dig_sum(day)
                ans += lval == rval
    print(ans)
##    print("{} {}".format(dig_sum(2022), dig_sum(11) + dig_sum(13)))

main()

分糖果

好坑的一道题，有个 corner case 不容易想到。

strip() 最好都加上吧

import os
import math, collections, itertools, functools, bisect, heapq, string

def read(fun=int, seq=' '):
    return list(map(fun, input().strip().split(seq)))

def main():
    n, K = read()
    s = list(input().strip())
    s.sort()
    cnt = collections.Counter()
    for c in s:
        cnt[c] += 1
    if len(cnt) > 1:
        Ans = []
        for i in range(K):
            Ans.append(s[i])
        Ans[0] += ''.join(s[K:])
        print(max(Ans))
    else:
        ans = (n + K - 1) // K
        Ans = [s[0]] * ans
        Ans = ''.join(Ans)
        print(Ans)

main()

三国游戏

又脑残了，看了好久的题目样例以为样例错了，后来才发现是读入的顺序和想象的不一样

import os
import math, collections, itertools, functools, bisect, heapq, string

def read(fun=int, seq=' '):
    return list(map(fun, input().strip().split(seq)))

def main():
    n = read()[0]
    a = []
    a.append(read()); a.append(read()); a.append(read())
    orders = [(0, 1, 2), (1, 0, 2), (2, 0, 1)]
    ans = 0
    for order in orders:
        p = [i for i in range(n)]
        cmp = lambda i: a[order[0]][i] - a[order[1]][i] - a[order[2]][i]
        p.sort(key=cmp, reverse=True)
        res = 0
        delta = 0
        for i in p:
            delta += cmp(i)
            if delta > 0:
                res += 1
                ans = max(ans, res)
            else:
                break
    print(ans > 0 and ans or -1)


main()

翻转

水题，直接模拟就行了

import os
import math, collections, itertools, functools, bisect, heapq, string

def read(fun=int, seq=' '):
    return list(map(fun, input().strip().split(seq)))

def main():
    T = list(input().strip())
    S = list(input().strip())
    ok = 1
    ans = 0
    for i in range(len(S)):
        if S[i] != T[i]:
            if i > 0 and i + 1 < len(S) and S[i] != S[i - 1] and S[i] != S[i + 1]:
                S[i] = S[i] == '1' and '0' or '1'
                ans += 1
            else:
                ok = 0
                break
    print(ok and ans or -1)

task = read()[0]
for _ in range(task):
    main()

子矩阵

二维单调队列，Python 版单调队列

import os
import math, collections, itertools, functools, bisect, heapq, string

def read(fun=int, seq=' '):
    return list(map(fun, input().strip().split(seq)))

def Solve(A:list, cmp):
    r1 = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        q = [0] * (m + 1)
        head = 1; tail = 0
        for j in range(1, m + 1):
            while head <= tail and q[head] < j - b + 1:
                head += 1
            while head <= tail and cmp(A[i][j], A[i][q[tail]]):
                tail -= 1
            tail += 1
            q[tail] = j
            if j >= b:
                r1[i].append(A[i][q[head]])
    r2 = [[] for _ in range(m + 1)]
    ret = []
    for j in range(len(r1[1])):
        q = [0] * (n + 1)
        head = 1; tail = 0
        for i in range(1, n + 1):
            while head <= tail and q[head] < i - a + 1:
                head += 1
            while head <= tail and cmp(r1[i][j], r1[q[head]][j]):
                tail -= 1
            tail += 1
            q[tail] = i
            if i >= a:
                ret.append(r1[q[head]][j])
    return ret

def main():
    A = [[0] * (m + 1)]
    for i in range(n):
        A.append([0] + read())
    cmp1 = lambda x, y: x <= y
    cmp2 = lambda x, y: x >= y
    minv = Solve(A, cmp1)
    maxv = Solve(A, cmp2)
    ans = 0; MOD = 998244353
    for x, y in zip(minv, maxv):
        ans += x * y % MOD
        ans %= MOD
    print(ans)

n, m, a, b = read()
main()

子树的大小

初始时当前层的编号范围是 [k, k]。假设当前当前层的编号范围是 [l, r]，则下一层的编号范围是 [ml - (m - 2), mr + 1]。根据编号范围和 n 的大小关系统计一下答案即可。

import os
import math, collections, itertools, functools, bisect, heapq, string

def read(fun=int, seq=' '):
    return list(map(fun, input().strip().split(seq)))

def main():
    n, m, K = read()
    ans = 0
    l = K; r = K
    while True:
        if r <= n:
            ans += r - l + 1
        elif l <= n < r:
            ans += n - l + 1
        else:
            break
        l = m * l - (m - 2)
        r = m * r + 1
    print(ans)

tasks = read()[0]
for _ in range(tasks):
    main()

阶乘的和

好菜，其实思路已经想到正解了，但没算出复杂度是正确的。

import os
import math, collections, itertools, functools, bisect, heapq, string

def read(fun=int, seq=' '):
    return list(map(fun, input().strip().split(seq)))

def main():
    n = read()[0]
    A = read()
    A.sort()
    cnt = collections.Counter()
    for x in A:
        cnt[x] += 1
    x = A[0]
    while True:
        if cnt[x] % (x + 1) == 0:
            cnt[x + 1] += cnt[x] // (x + 1)
            cnt[x] = 0
            x += 1
        else:
            print(x)
            break

main()

奇怪的数

$55$​ 分解法。暴力记忆化搜索数位 DP。

❗ 坑点在于题目很坑的是不说清楚前导 0 算不算，实际上是可以有前导 0 的！

注意避免爆栈，需要用 sys.setrecursionlimit(n + 55) 手动增加栈空间。

import os, sys
import math, collections, itertools, functools, bisect, heapq, string

def read(fun=int, seq=' '):
    return list(map(fun, input().strip().split(seq)))

def dfs(f:list, i, x, y, z, w):
    if f[i][x][y][z][w] != -1:
        return f[i][x][y][z][w]
    if i > n:
        f[i][x][y][z][w] = 1
        return f[i][x][y][z][w]
    ret = 0
    Sum = (x + y + z + w) * 2 + 2
    for num in range(0, 9+1):
        if ((n - i + 1) & 1) != (num & 1):
            continue
        if Sum + num > m:
            continue
        ret += dfs(f, i + 1, y, z, w, num // 2)
        ret %= MOD
    f[i][x][y][z][w] = ret
    return ret

def main():
    # f[i][x][y][z][w] => from left to right, i-th bit, digits are x|y|z|w|dig(i) 
    f = [[[[[-1 for w in range(0, 4+1)] for z in range(0, 4+1)] for y in range(0, 4+1)] for x in range(0, 4+1)] for i in range(n + 2)]
    ans = 0
    for lead in range(0, 9999+1):
        nums = list(map(int, list(f'{lead}')))
        while len(nums) < 4:
            nums.insert(0, 0)
        ok = 1
        for i, num in enumerate(nums, start=1):
            if ((n - i + 1) & 1) != (num & 1):
                ok = 0
                break
        Sum = sum(nums)
        if Sum > m:
            ok = 0
        if not ok:
            continue
        nums = [x // 2 for x in nums]
        ans += dfs(f, 5, *nums)
        ans %= MOD
    print(ans)

MOD = 998244353
n, m = read()
sys.setrecursionlimit(n + 55)
main()

平均

如此大水题放在后面，居心何在？

import os
import math, collections, itertools, functools, bisect, heapq, string

def read(fun=int, seq=' '):
    return list(map(fun, input().strip().split(seq)))

def main():
    n = read()[0]
    cnt = collections.Counter()
    b = [[] for _ in range(0, 9+1)]
    for i in range(1, n + 1):
        x, w = read()
        cnt[x] += 1
        b[x].append(w)
    ans = 0
    avg = n // 10
    for x in range(0, 9 + 1):
        if cnt[x] > avg:
            k = cnt[x] - avg
            b[x].sort()
            ans += sum(b[x][0:k])
    print(ans)

main()

反异或 01 串

Mannacher，鸽了，考试懒得写了。

题解
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇