浅念づ昔夜's Blog

Like author, like book.

0%

2024 蓝桥杯省赛 python A组 解题报告

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 7 分钟

题目传送门

A 拼正方形

Solution

二分答案。根据题目所求为满足条件的最大值，因此二分枚举所得正方形的最大边长，并检验是否能拼成。

又因为二分答案时，边长分别为奇偶时才各自有单调性。所以分开两类讨论，得出两个答案，取最大值即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import math

n = 7385137888721
m = 10470245
L = 1
R = 10**9
ansa = ansb = 0

def check(x):
    if x & 1 == 0:
        if n * 4 + m >= x**2:
            return 1
        else:
            return 0
    else:
        for i in range(1, 1000, 2):
            if x < i:
                return 0
            if n * 4 >= (x - i)**2 and m >= x**2 - (x - i)**2:
                return 1
        
l = L
r = R
while l <= r:
    mid = (l + r) >> 1
    if check(2 * mid):
        l = mid + 1
        ansa = mid
    else:
        r = mid - 1

l = L
r = R
while l <= r:
    mid = (l + r) >> 1
    if check(2 * mid - 1):
        l = mid + 1
        ansb = mid
    else:
        r = mid - 1

print(max(ansa * 2, ansb * 2 - 1))

B 召唤数字精灵

Solution

对 1∼10001\sim 1000 的 B(i)−A(i)B(i)-A(i) 进行打表，得到如下满足条件的数字，共有 2222 个，且有明显的规律。

1
1 3 24 175 199 200 224 375 399 400 424 575 599 600 624 775 799 800 824 975 999 1000

但是 11 和 33 为其中的特例，所以独立计算。

设 M=2024041331404202M=2024041331404202，最后三位为 202202，打表计算得到 1∼2021\sim 202 的答案为 66，因此答案为

⌊M1000⌋×20+6\lfloor \dfrac{M}{1000} \rfloor \times 20 + 6

Code

打表代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import math

M = 2024041331404202
a = 0
b = 1
ans = 0

for i in range(1, 1001):
    a += i
    if b % 100:
        b *= i
    if b % 100 == a % 100:
        ans += 1
        print(i)
print(ans)

C 数字诗意

Solution

若 ai=2ma_i=2^m，mm 为任意正整数，则 aia_i 只能分解成两个偶因数相乘。反之， aia_i 必定能分解为一个偶数乘以一个奇数。

设 aia_i 为 n（n≥2)n（n\ge 2) 个连续正整数的和。由首尾相加法可得：

  1. 若 nn 为奇数，则 aia_i 等于奇数个 nn 的和；
  2. 若 nn 为偶数，则 aia_i 等于若干个中间两元素之和的和。又因为中间两元素相加一定为奇数，所以 nn 必有奇因数。

所以若 ai=2ma_i=2^m，则 aia_i 一定不能表示为连续的两个以上的正整数之和。

若 aia_i 不是 22 的若干次幂，若 aia_i 为奇数，显然为两个连续的正整数之和。若 aia_i 为偶数，设其可分解为 xx 和 yy 的积，其中 xx 为奇数，yy 为偶数。

  1. 若 x<yx<y，则 yy 为中间的元素，元素数量为 xx。
  2. 若 x>yx>y，则 y−12\dfrac{y-1}{2} 和 y+12\dfrac{y+1}{2} 为中间的两个元素，元素数量为 2y2y。

这样，我们就得到了一定能构造出和为 aia_i 的连续正整数组的方法。

综上，在本题中，我们只用删除 22 的若干次幂即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import math

n = int(input())
a = list(map(int, input().split()))
ans = 0

for i in range(n):
    while a[i] != 1:
        if a[i] & 1:
            break
        else:
            a[i] //= 2
    if a[i] == 1:
        ans += 1
print(ans)

D 回文数组

Solution

贪心。从最左边开始枚举 ii，如果 aia_i 和 ai+1a_{i + 1} 能一起增减，就在满足 aia_i 一步到位的前提下顺带更改 ai+1a_{i+1}。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys

n = int(input())
a = list(map(int, input().split()))

if n == 1:
    sys.exit()

ans = 0
for i in range(n - 1):
    dif1 = a[i] - a[n - i - 1]
    dif2 = a[i + 1] - a[n - i - 2]
    ans += abs(dif1)
    a[i] = a[n - i - 1]
    if dif1 * dif2 > 0:
        if abs(dif1) >= abs(dif2):
            a[i + 1] = a[n - i - 2]
        elif dif2 < 0:
            a[i + 1] = a[n - i - 2] - (abs(dif2) - abs(dif1))
        else:
            a[i + 1] = a[n - i - 2] + (abs(dif2) - abs(dif1))
print(ans + abs(a[n - 1] - a[0]))

E 吊坠

Solution

两两枚举字符串，求他们之间的边长。使用破环为链的技巧，将字符串的长度变为 2m−12m-1，然后 dp 求解最大公共子串。

设 fx,yf_{x,y} 表示考虑 aa 串的前 xx 个字符和 bb 串的前 yy 个字符，最长公共子串的长度。其中该公共子串的最后一位为 aa 串的第 xx 位和 bb 串的第 yy 位。有转移方程

{fx,y=fx−1,y−1+1(ax=by)fx,y=0(ax≠by) \left\{ \begin{aligned} f_{x,y} & =f_{x-1,y-1}+1 & & {(a_x=b_y)}\\ f_{x,y} & =0 & & {(a_x\neq b_y)}\\ \end{aligned} \right.

所求长度即为 ff 数组的最大值。至此我们得到了图中边的长度，用 kruskal 求最大生成树即可。

时间复杂度 O(n2m2)O(n^2m^2)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import sys

n, m = map(int, input().split())
dis = [[0 for _ in range(205)] for _ in range(205)]
edge = []
ans = 0

s = [input().strip() for _ in range(n)]

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

fa = list(range(n))

for i in range(n):
    for j in range(i + 1, n):
        str1 = s[i] + s[i][:m - 1]
        str2 = s[j] + s[j][:m - 1]
        
        for k in range(m):
            for l in range(m):
                tmp = 0
                while str1[k + tmp] == str2[l + tmp]:
                    tmp += 1
                    if tmp >= m:
                        break
                dis[i][j] = max(dis[i][j], min(m, tmp))

for i in range(n):
    for j in range(i + 1, n):
        edge.append((dis[i][j], i, j))

edge.sort(reverse=True)

for w, u, v in edge:
    fx = find(u)
    fy = find(v)
    if fx != fy:
        fa[fx] = fy
        ans += w

print(ans)

F 砍柴

Solution

先用线性筛预处理求出 1∼1051\sim 10^5 的所有质数。

对从 0∼1050\sim 10^5 的长度，求出它们是否先手必胜。设 fif_i 为 11 代表长度为 ii 时先手必胜，初始化 f0=f1=0f_0=f_1=0。

接下来从 0∼1050\sim 10^5 枚举，若 fi=1f_i=1 则跳过，若 fi=0f_i=0，则长度 ii 经过一次操作后只能变成先手必胜态，所以当下是先手必败态。由此上一次操作前也一定是是先手必胜态。因此枚举预处理求出的质数 pp，令 fi+p=1f_{i+p}=1。正确性是显然的。

实测如果提交计算 fif_i 的代码会超时。所以选择将 fi=0f_i=0 的数打表，询问时判断该长度是否在数组中即可。

Code

打表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import os

MAXN = 10**5 + 10
M = 10**5
f = [0 for _ in range(MAXN)]
isPri = [0 for _ in range(MAXN)]
pri = []

def Prime():
    isPri[1] = isPri[0] = 0
    for i in range(2, M + 1):
        if isPri[i] == 0:
            pri.append(i)
        for j in pri:
            if i * j > M:
                break
            isPri[i * j] = 1
            if i % j == 0:
                break  

if __name__ == '__main__':
    Prime()
    for i in range(M + 1):
        if i == 0 or i == 1:
            f[i] = 0
        if f[i] == 0:
            for j in pri:
                if i + j > 10**5:
                    break
                f[i + j] = 1
    
    with open(os.path.abspath("C:\\Users\\31546\\Desktop\\output.txt"), "w") as file:
        for i in range(M + 1):
            if f[i] == 0:
                print(i, ', ', sep='', end='', file=file)

AC

1
2
3
4
5
6
7
8
9
10
11
ans = [0, 1, 9, 10, 25, 34, 35, 49, 55, 85, 91, 100, 115, 121, 125, 133, 145, 155, 169, 175, 187, 195, 205, 217, 235, 247, 253, 259, 265, 289, 295, 301, 309, 310, 319, 325, 335, 343, 355, 361, 375, 385, 391, 395, 403, 415, 425, 445, 451, 469, 475, 481, 485, 493, 505, 511, 515...]
# 此处省略

if __name__ == '__main__':
    T = int(input())
    for i in range(T):
        x = int(input())
        if x in ans:
            print(0)
        else:
            print(1)

G 智力测试

智力不够，暂时咕咕咕

H 最大异或结点

Solution

弱化版题目

如果没有思路，则推荐先做上面的弱化版题目，会有很大的启发。

本题使用字典树求解。注意，线性基求解的是集合内任意数量的元素的异或最大值。而求两个元素的异或最大值只能用 01 字典树。

先 O(n)O(n) 预处理出每个点直接相连的结点。然后枚举点 1∼n1\sim n，在字典树上深搜出异或值与其最大的点。如果最后搜到的是直接相连的点，那么回溯继续查找。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
n = int(input())
a = list(map(int, input().split()))
fa = list(map(int, input().split()))
e = [[] for _ in range(10 ** 5 + 10)]
tr = [[0 for _ in range(2)] for _ in range(10 ** 5 * 32 + 10)]
id = [0 for _ in range(10 ** 5 * 32 + 10)]
cnt = 0

def dfs(k, p, q):

    if q == -1:
        if id[p] in e[k]:
            return -1
        else:
            return a[id[p]]
    
    x = (a[k] >> q) & 1
    if tr[p][x ^ 1]:
        res = dfs(k, tr[p][x ^ 1], q - 1)
        if res != -1:
            return res
    if tr[p][x]:
        res = dfs(k, tr[p][x], q - 1)
        if res != -1:
            return res
    return -1
    

if __name__ == '__main__':

    for i in range(n):
        if fa[i] == -1:
            root = i
            break
        e[fa[i]].append(i)
        e[i].append(fa[i])
                
    for i in range(n):
        p = 0
        for j in range(32, -1, -1):
            x = (a[i] >> j) & 1
            if tr[p][x] == 0:
                cnt += 1
                tr[p][x] = cnt
            p = tr[p][x]
            if j == 0:
                id[p] = i
    
    ans = 0
    for i in range(n):
        res = dfs(i, 0, 32)
        if res != -1:
            ans = max(ans, res ^ a[i])
    print(ans)