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

A 拼正方形

Solution

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

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

Code

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\sim 1000$ 的 $B(i)-A(i)$ 进行打表，得到如下满足条件的数字，共有 $22$ 个，且有明显的规律。

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

但是 $1$ 和 $3$ 为其中的特例，所以独立计算。

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

$\lfloor \dfrac{M}{1000} \rfloor \times 20 + 6$

Code

打表代码如下：

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

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

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

若 $n$ 为奇数，则 $a_i$ 等于奇数个 $n$ 的和；
若 $n$ 为偶数，则 $a_i$ 等于若干个中间两元素之和的和。又因为中间两元素相加一定为奇数，所以 $n$ 必有奇因数。

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

若 $a_i$ 不是 $2$ 的若干次幂，若 $a_i$ 为奇数，显然为两个连续的正整数之和。若 $a_i$ 为偶数，设其可分解为 $x$ 和 $y$ 的积，其中 $x$ 为奇数， $y$ 为偶数。

若 $x<y$ ，则 $y$ 为中间的元素，元素数量为 $x$ 。
若 $x>y$ ，则 $\dfrac{y-1}{2}$ 和 $\dfrac{y+1}{2}$ 为中间的两个元素，元素数量为 $2y$ 。

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

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

Code

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

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

Code

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-1$ ，然后 dp 求解最大公共子串。

设 $f_{x,y}$ 表示考虑 $a$ 串的前 $x$ 个字符和 $b$ 串的前 $y$ 个字符，最长公共子串的长度。其中该公共子串的最后一位为 $a$ 串的第 $x$ 位和 $b$ 串的第 $y$ 位。有转移方程

$\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.$

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

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

Code

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\sim 10^5$ 的所有质数。

对从 $0\sim 10^5$ 的长度，求出它们是否先手必胜。设 $f_i$ 为 $1$ 代表长度为 $i$ 时先手必胜，初始化 $f_0=f_1=0$ 。

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

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

Code

打表

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

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)$ 预处理出每个点直接相连的结点。然后枚举点 $1\sim n$ ，在字典树上深搜出异或值与其最大的点。如果最后搜到的是直接相连的点，那么回溯继续查找。

Code

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)