2022年蓝桥杯Python A组省赛做题记录

做题进度，目前还剩：

H（30pts，还没de出bug）
J（还没做）

其他均已完成。

A. 裁纸刀#

题目链接：https://www.lanqiao.cn/problems/2060/learning

经过观察可以发现不管怎么切，刀数都是一样的。因此直接给出答案：

1
def solve(n, m):
2
    return 4 + n * m - 1
3

4
n, m = 20, 22
5
print(solve(n, m))

B. 寻找整数#

题目链接：https://www.lanqiao.cn/problems/2131/learning

也就是说给了一堆模的方程，求这个数最小值。

最朴素的暴力跑 $10^{17}$ （ $2^{60}$ 左右）三个小时肯定跑不完。最快的方法应该是逐步合并的CRT，但是这题通过简单优化暴力，也可以很快跑出来。

暴力的思路是，假设我们目前已经知道了一个同余方程

n \equiv A (\mod M)

那么现在 $n$ 最小肯定是 $A$ 。

现在新加入一个同余方程，要求 $n$ 也满足

n\equiv r (\mod m)

假设这个是一定能被满足的（题意，所以无需判断无解的情况），新的模数 $M'$ 很显然是 $\text{lcm} (M,m)$ 。那我们暴力以 $M$ 的步长，寻找下一个最小的同时满足前面两个方程的 $n'$ ，因为是最小的，也就是新的 $A'$ 。这样我们就得到了新的

n\equiv A' (\mod M')

然后这样跳个50次就得到了答案。不会分析这个时间复杂度，但是很显然就是能很快跑出来的，毕竟这个 $M$ 是一直在做lcm，指数级别增大的。

1
import math
2

3
def solve(data):
4
    n, step = data[0]
5
    for i in range(1, len(data)):
6
        m, r = data[i]
7
        while n % m != r:
8
            n += step
9
        step = (step * m) // math.gcd(step, m)
10
    return n
11

12
if __name__ == '__main__':
13
    data = [
14
        (2, 1), (3, 2), (4, 1), (5, 4), (6, 5), (7, 4), (8, 1), (9, 2),
15
        (10, 9), (11, 0), (12, 5), (13, 10), (14, 11), (15, 14), (16, 9),
16
        (17, 0), (18, 11), (19, 18), (20, 9), (21, 11), (22, 11), (23, 15),
17
        (24, 17), (25, 9), (26, 23), (27, 20), (28, 25), (29, 16), (30, 29),
18
        (31, 27), (32, 25), (33, 11), (34, 17), (35, 4), (36, 29), (37, 22),
19
        (38, 37), (39, 23), (40, 9), (41, 1), (42, 11), (43, 11), (44, 33),
20
        (45, 29), (46, 15), (47, 5), (48, 41), (49, 46)
21
    ]
22

23
    ans = solve(data)
24
    print(ans)

C. 质因数个数#

题目链接：https://www.lanqiao.cn/problems/2155/learning

最大运行时间 10s， $n$ 最大 1e16， $O(\sqrt n)$ 的算法应该可以过。

一开始想手写一个筛法，筛 $\sqrt n$ 以内的所有质数即可。但是马上MLE了，1e8的set是存不下的应该，虽然算了下512MB可以存的下。然后直接分解质因数，对于质因数直接把全部因子都除掉，这样可以保证下一个能取模的数一定还是质数（更小的因子已经没了）。

1
# 90 %
2
import os
3
import sys
4

5
n = int(input())
6

7
ans = 0
8

9
x = 2
10
while x * x <= n:
11
    if n % x == 0:
12
        while n % x == 0:
13
            n = n // x
14
        ans += 1
15
    x += 1
16

17
if n != 1:
18
    ans += 1
19
print(ans)

这样写只有90分，还是T了一个点。需要继续优化，进一步的优化方案逐步如下。

① 必须注意Python中for .. range比while要快得多，因为for .. range遍历底层是由C语言实现的。

这样优化后，本地测试，运行速度从 9s 可以优化到 7s，那很好了。

1
import os
2
import sys
3

4
n = int(input())
5

6
ans = 0
7

8
import math
9
lim = math.floor(math.sqrt(n)) + 1
10
for x in range(2, lim):
11
    if x * x > n:
12
        break
13
    if n % x == 0:
14
        while n % x == 0:
15
            n = n // x
16
        ans += 1
17

18
if n != 1:
19
    ans += 1
20
print(ans)

但是蓝桥杯的古董机好像还不够，还是会T一个点。

② 发现是因为引入math库好像会慢一点点，去掉math库就好了。现在可以A了。但是看时间有点极限。

1
# 100 %
2

3
import os
4
import sys
5
import math
6

7
n = int(input())
8

9
ans = 0
10

11
for x in range(2, int(n**0.5)+1):
12
# lim = math.floor(math.sqrt(n)) + 1
13
# for x in range(2, lim):
14

15
    if x * x > n:
16
        break
17
    if n % x == 0:
18
        while n % x == 0:
19
            n = n // x
20
        ans += 1
21

22
if n != 1:
23
    ans += 1
24
print(ans)

③ 继续优化的话，就是对2特判，这样后面就只需要枚举奇数即可。下面是最后时间稳过的代码，本地运行从前面的9s、7s到3.5 s。

1
import os
2
import sys
3
import math
4

5
n = int(input())
6

7
ans = 0
8

9
if n % 2 == 0:
10
    while n % 2 == 0:
11
        n = n // 2
12
    ans += 1
13

14
for x in range(3, int(n**0.5)+1, 2):
15
    if x * x > n:
16
        break
17
    if n % x == 0:
18
        while n % x == 0:
19
            n = n // x
20
        ans += 1
21

22
if n != 1:
23
    ans += 1
24
print(ans)

D. 矩形拼接#

题目链接：https://www.lanqiao.cn/problems/2154/learning

很容易想到是那种史山模拟题，有一大堆if else。只能试图比较有条理的枚举。

我的思路是，首先任意选两块拼一起，最坏情况就是随便乱放的时候，会有8条边。

一种一定能达到的更优情况，是两条边共线的情况：

这种情况可以视为一个大矩形有一个缺口。

不妨在假设第三个矩形一定填在这个叠起来的（最多6边）形的某一个边上。这样就能直接枚举了。（我三个矩形枚举所有可能排列）。

这样，每个询问，搜索的次数是 $3!\times 2^3 \times 6=36\times 8$ ，最后的时间复杂度是可以接受的。

1
try:
2
    from debug_utils import debug
3
except:
4
    def debug(*args):
5
        pass
6

7
import os
8
import sys
9

10
def solve():
11
    a1, b1, a2, b2, a3, b3 = map(int, input().split())
12
    rects = [[a1, b1], [a2, b2], [a3, b3]]
13
    ans = 8
14
    for base in rects:
15
        for s in range(2):
16
            down, near = base[s], base[1-s]
17
            for above in rects:
18
                if base is above:
19
                    continue
20
                for t in range(2):
21
                    up, left = above[t], above[1-t]
22
                    if up > down:
23
                        continue
24
                    """
25
                               up
26
                             |----|
27
                    left     |    |
28
                             |---------|
29
                    near     |         |
30
                             ----------|
31
                                down
32
                    """
33
                    if down != up:
34
                        angles = [down - up, left, up, left + near, down, near]
35
                    else:
36
                        angles = [up, left + near, down, left + near]
37
                    for rect in rects:
38
                        if rect is not base and rect is not above:
39
                            for u in range(2):
40
                                a, b = rect[u], rect[1-u]
41
                                """
42
                                    a
43
                                    |------|
44
                                b   |      |
45
                                    --------
46
                                """
47
                                normal = len(angles) + 2
48
                                now = normal
49
                                if len(angles) == 6:    # 存在270度角
50
                                    now = min(now, normal - ((2 if a == angles[0] else 0) + (2 if b == angles[1] else 0)) )
51
                                # 普通处理90度
52
                                for idx in range(len(angles)):
53
                                    if len(angles) == 6 and idx <= 1:
54
                                        continue
55
                                    c = angles[idx]
56
                                    now = min(now, normal - (2 if c == a else 0))
57
                                ans = min(now, ans)
58
    print(ans)
59

60

61
t = int(input())
62
for _ in range(t):
63
    solve()

E. 消除游戏#

题目链接：https://www.lanqiao.cn/problems/2127/learning

纯模拟题，感觉最简单的写法就是直接 $O(n)$ 模拟一个链表，初始遍历一遍找到可以删的节点，然后每次删除时把这个节点左边、右边、左边的左边、右边的右边，4个节点都纳入考虑范围。（然后就和下面的代码一样模拟成构思了，写了快一百多行）

1
import os
2
import sys
3

4
class Node:
5
    __slots__ = ('val', 'prev', 'next', 'alive')
6
    def __init__(self, val, prev = None, next = None):
7
        self.val = val
8
        self.prev = prev
9
        self.next = next
10
        self.alive = True
11
    def __repr__(self):
12
        return str(self.val)
13

14
class Linklist:
15
    def __init__(self):
16
        self.head = Node(None)  # 哨兵头尾
17
        self.tail = Node(None)
18
        self.head.next = self.tail
19
        self.tail.prev = self.head
20
    def insert(self, val, node = None):
21
        if node == None:
22
            node = self.tail.prev
23
        one = Node(val, node, node.next)
24
        node.next = one
25
        one.next.prev = one
26
        return one
27
    def remove(self, node):
28
        node.prev.next = node.next
29
        node.next.prev = node.prev
30
        node.alive = False
31

32
    def __repr__(self):
33
        line = []
34
        now = self.head.next
35
        while now is not self.tail:
36
            line.append(now.val)
37
            now = now.next
38
        ret = ''.join(line)
39
        return ret if ret != '' else 'EMPTY'
40

41

42
def solve():
43
    lines = sys.stdin.read().splitlines()
44

45
    s = lines[0]
46
    if s == '':
47
        print("EMPTY")
48
        return
49

50
    n = len(s)
51

52
    lst = Linklist()
53
    que = []
54

55
    for i in range(n):
56
        ptr = lst.insert(s[i])
57
        if  (0 < i < n-1 and ( (s[i-1] == s[i] != s[i+1]) or (s[i-1] != s[i] == s[i+1]) ) ) or \
58
            (0 <= i and i+2 < n and s[i] != s[i+1] == s[i+2]) or \
59
            (i - 2 >= 0 and i < n and s[i-2] == s[i-1] != s[i]):
60
            que.append(ptr)
61
            ptr.alive = False
62

63
    while len(que) != 0:
64
        wait = []
65
        for p in que:
66
            lst.remove(p)
67
            if p.prev.val is not None and p.prev.alive:
68
                wait.append(p.prev)
69
            if p.prev.prev is not None and p.prev.prev.val is not None and p.prev.prev.alive:
70
                wait.append(p.prev.prev)
71
            if p.next.val is not None and p.next.alive:
72
                wait.append(p.next)
73
            if p.next.next is not None and p.next.next.val is not None and p.next.next.alive:
74
                wait.append(p.next.next)
75
        new_que = []
76
        for p in wait:
77
            if p.alive == True and \
78
                ((((p.prev.val == p.val != p.next.val and p.next.val is not None) or (p.prev.val != p.val == p.next.val and p.prev.val is not None)) ) or \
79
            (p.next.next is not None and p.val != p.next.val == p.next.next.val) or \
80
            (p.prev.prev is not None and p.prev.prev.val == p.prev.val != p.val)):
81
                new_que.append(p)
82
                p.alive = False
83
        que = new_que
84
    print(lst)
85

86
solve()

F. 重新排序#

题目链接：https://www.lanqiao.cn/problems/2128/learning

（感觉是这场最简单的一题。）

第 $i$ 个元素，对最终和的贡献，取决于它处于几个区间内。如果处于 $c_i$ 个区间内，那最终贡献就是 $a_i \cdot c_i$

我们可以 $O(N)$ 预处理出来第 $i$ 个位置处于区间个数的 $c_i$ 。（这种区间叠加，直接用差分即可）

对于越大的 $c_i$ ，很显然匹配越大的 $a_i$ ，会使得结果最大。

1
import os
2
import sys
3

4
lines = sys.stdin.read().splitlines()
5

6
n = int(lines[0].strip())
7
a = list(map(int, lines[1].split()))
8
m = int(lines[2].strip())
9
cnt = [0] * (n)
10
for i in range(m):
11
    l, r = map(int, lines[i+3].split())
12
    l -= 1
13
    r -= 1
14
    cnt[l] += 1
15
    if r+1 < n:
16
        cnt[r+1] -= 1
17
for i in range(1, n):
18
    cnt[i] += cnt[i-1]
19

20
ans = 0
21
for i in range(n):
22
    ans -= cnt[i] * a[i]
23

24
cnt = sorted(cnt)
25
a = sorted(a)
26
for i in range(n):
27
    ans += cnt[i] * a[i]
28
print(ans)

G. 全排列的价值#

题目链接：https://www.lanqiao.cn/problems/2137/learning

和前面一题一样，从贡献的角度切入。数 $i$ ，在排列中对这个排列价值的贡献就是它后面所有比它大的数的个数。全排列中，对于数 $j$ （ $j>i$ ），会有多少次机会也就是有多少个排列，会排在 $i$ 后面？很显然是 $(n-2)!\cdot (C_{n-1}^2+n-1)$

也就是说所，数 $i$ 对最后我们要输出的答案的贡献是

\begin{aligned} ans[i]&=\bigl( \sum_{j=i+1}^n (n-2)!\cdot (C_{n-1}^2+n-1) \bigr)\\ &= (n-2)!\cdot (C_{n-1}^2+n-1) \cdot (n-i)\\ \end{aligned}

最后总的答案是

\begin{aligned} ans &= (n-2)!\cdot (C_{n-1}^2+n-1)\cdot \frac 1 2 n (n-1)\\ &= \frac 1 4 n!\cdot n(n-1) \end{aligned}

然后需要注意，如果不写逆元，就需要特判一下两个 2 因子消掉即可。

1
import os
2
import sys
3
import math
4

5
n = int(input())
6
m = 998244353
7

8
def fac_2(x):
9
    ret = 1
10
    for i in range(3, x + 1):
11
        ret *= i
12
        ret %= m
13
    return ret
14

15
ans = fac_2(n)
16
ans = (ans * (n * (n - 1) // 2 % m)) % m
17

18
print(ans)

H. 最长不下降子序列#

链接：https://www.lanqiao.cn/problems/2088/learning

I. 最优清零方案#

链接：https://www.lanqiao.cn/problems/2138/learning

很显然可以发现，我们只要先尽可能地 $k$ 个连续消掉，随便做，消到没办法再消，然后对剩下的逐个消除即可。

因此直接 $O(n)$ 遍历一遍，遍历到 $i$ 时，对 $[i, i+k-1]$ 消掉 $\min_{j\in [i,i+k-1]}{a_j}$ 即可。正确性是有保证的。

下面是暴力的写法，时间复杂度最坏 $O(nk)$ .

1
import os
2
import sys
3

4
n, k = map(int, input().split())
5
a = list(map(int, input().split()))
6

7
ok = -1
8
ans = 0
9
for i in range(n):
10
    if i <= ok or i+k > n:
11
        ans += a[i]
12
    else:
13
        j = i
14
        for p in range(i, i+k):
15
            if a[p] < a[j]:
16
                j = p
17
        h = a[j]
18
        ans += h
19
        for p in range(i, i+k):
20
            a[p] -= h
21
        ans += a[i]
22
        ok = j
23
print(ans)

虽然这题时间复杂度非常坏，最坏会到 $O(nk)$ ，但是蓝桥杯官网上测试这段代码，是直接100%通过……

但是还是看下怎么优化。

上述的步骤，说简单就是对于 $i$ ，我们对 $[i,i+k)$ 这一个区间，全部减去区间中最小的 $a[j]$ ，然后 $i$ 就可以跳到 $j$ 了，继续下一步即可，可以看出主要的时间复杂度的问题都在寻找这个最小的 $a[j]$ 上和区间减法上了，因为朴素的做法中，一定要遍历 $k$ 个数才能找到最小的，在不打标记的情况下，区间减法也是要一个个减掉的。所以很自然会想到用线段树来实现区间减法和最小值寻找，这样时间复杂度就变成了 $O(n\log n)$ ，对的。

除此之外我感觉也可以用双端队列来做。但是写起来可能比线段树更难调，那不如直接线段树了。但是线段树会狠狠卡常，必须尽可能不搜就不搜。

1
import sys
2

3
n, k = map(int, sys.stdin.readline().split())
4
a = list(map(int, sys.stdin.readline().split()))
5
inf = 2e9
6
ans = sum(a)
7

8
class SegmentTree:
9
    def __init__(self, data):
10
        self.n = len(data)
11
        self.tree = [[0, 0] for _ in range(4 * self.n)]
12
        self.lazy = [0] * (4 * self.n)
13
        self._build(0, 0, self.n-1, data)
14

15
    def _build(self, u, l, r, data):
16
        if l == r:
17
            self.tree[u] = [data[l], l]
18
        else:
19
            mid = (l + r) // 2
20
            self._build(2*u+1, l, mid, data)
21
            self._build(2*u+2, mid+1, r, data)
22
            left_val, left_idx = self.tree[2*u+1]
23
            right_val, right_idx = self.tree[2*u+2]
24
            if left_val < right_val:
25
                self.tree[u] = [left_val, left_idx]
26
            else:
27
                self.tree[u] = [right_val, right_idx]
28

29
    def _query(self, u, l, r, L, R):
30
        if R < l or r < L:
31
            return [inf, -1]
32
        if L <= l and r <= R:
33
            return self.tree[u]
34
        self._push(u)
35
        mid = (l + r) // 2
36
        left = self._query(2*u+1, l, mid, L, R)
37
        right = self._query(2*u+2, mid+1, r, L, R)
38
        return left if left[0] < right[0] else right
39

40
    def find_min(self, l, r):
41
        return self._query(0, 0, self.n-1, l, r)
42

43
    def _push(self, u):
44
        if self.lazy[u] != 0:
45
            self.tree[2*u+1][0] += self.lazy[u]
46
            self.lazy[2*u+1] += self.lazy[u]
47
            self.tree[2*u+2][0] += self.lazy[u]
48
            self.lazy[2*u+2] += self.lazy[u]
49
            self.lazy[u] = 0
50

51
    def _range_add(self, u, l, r, L, R, x):
52
        if R < l or r < L:
53
            return
54
        if L <= l and r <= R:
55
            self.tree[u][0] += x
56
            self.lazy[u] += x
57
            return
58
        self._push(u)
59
        mid = (l + r) // 2
60
        self._range_add(2*u+1, l, mid, L, R, x)
61
        self._range_add(2*u+2, mid+1, r, L, R, x)
62
        left_val, left_idx = self.tree[2*u+1]
63
        right_val, right_idx = self.tree[2*u+2]
64
        if left_val < right_val:
65
            self.tree[u] = [left_val, left_idx]
66
        else:
67
            self.tree[u] = [right_val, right_idx]
68

69
    def range_sub(self, l, r, x):
70
        self._range_add(0, 0, self.n-1, l, r, -x)
71

72
    def range_sum(self, u, l, r):
73
        if l == r:
74
            return self.tree[u][0]
75
        self._push(u)
76
        mid = (l + r) // 2
77
        return self.range_sum(2*u+1, l, mid) + self.range_sum(2*u+2, mid+1, r)
78

79
segtree = SegmentTree(a)
80
p = -1
81
for i in range(n):
82
    if i + k <= n and i > p:
83
        min_val, min_idx = segtree.find_min(i, i + k - 1)
84
        segtree.range_sub(i, i + k - 1, min_val)
85
        p = min_idx
86
        ans -= k * min_val
87
        ans += min_val
88
print(ans)

J. 数的拆分#

链接：https://www.lanqiao.cn/problems/2090