A. 攻击次数

image-20250420152350082
image-20250420152350082

这题有歧义，如果考虑三个英雄一起上，就是103，考虑一回合只能上一个伤害高的，就是181

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
// 一起上的情况
public class Main {
    public static void main(String[] args) {
        // 能一起上就一起上，不能一起上，就上攻击力高的
        int hp = 2025;
        int cnt = 0;

        while(hp > 0){
            cnt++;
            int hero1 = 5;   // 英雄 1 的固定伤害
            int hero2 = (cnt % 2 == 1) ? 15 : 2;   // 英雄 2 的回合机制伤害
            int hero3 = 0;
            if(cnt % 3 == 1){
                hero3 = 2;
            }else if(cnt % 3 == 2){
                hero3 = 10;
            }else if(cnt % 3 == 0){
                hero3 = 7;
            }

            hp -= hero1 + hero2 + hero3;
        }
        System.out.println(cnt);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 不一起上的情况
# 挑攻击力大的技能使用即可
# 可见：奇数一定使用第二个英雄的技能，然后偶数情况的话模3余1用第一个英雄技能，其他情况用第三个英雄的技能。
n = 0
i = 1
while n < 2025:
    if i & 1:
        n += 15
    else:
        if i % 3 == 2:
            n += 10
        elif i % 3 == 0:
            n += 7
        else:
            n += 5
    i += 1
print(i - 1)

B. 最长字符串

image-20250420152634843
image-20250420152634843

下载附件 words.txt

优美字符串的定义是：字符串本身存在于给定的单词列表中，并且可以通过调整顺序后由另一个更短的优美字符串扩展而来。

考的主要是文件读写，默认把 txt 附件存在和代码同级别的目录下

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package 基础算法和其他.IO读写流.P12171_蓝桥杯_2025_省_Python_B_最长字符串;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //  读取 words.txt 文件中的单词
        List<String> words = new ArrayList<>();
        try(BufferedReader br = new BufferedReader(new FileReader("D:\\WorkSpace\\JavaDemo\\IDEA\\Algorithm\\src\\字符串\\subject\\P12171_蓝桥杯2025省PythonB最长字符串\\words.txt"))){
            String line;
            while ((line = br.readLine()) != null) {
                words.add(line.trim());
            }
        }catch (IOException e){
            e.printStackTrace();
        }

        // 按长度升序、字典序升序排序（确保处理顺序正确）
        words.sort(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

        Set<String> bs = new HashSet<>();

        // 动态规划：判断每个单词是否是优美字符串
        for(String word : words){
            if(word.length() == 1){
                bs.add(word);
            }else{
                // 如果 前n-1 位的长度的字符串，我们把其和要对比的字符串按一定规律重组，那么两者就是一样的了
                String pre = sortString(word.substring(0, word.length() - 1));
                for(String sbs: bs){
                    if(sortString(sbs).equals(pre)){
                        bs.add(word);
                        break;
                    }
                }
            }
        }

        // 找到最长的优美字符串
        int maxLength = 0;
        for (String word : bs) {
            maxLength = Math.max(maxLength, word.length());
        }

        List<String> ls = new ArrayList<>();
        for (String word : bs) {
            if (word.length() == maxLength) {
                ls.add(word);
            }
        }

        // 输出字典序最小的结果
        ls.sort(Comparator.naturalOrder());
        System.out.println(ls.get(0));

        // System.out.println("afplcu");
    }

    // 字符串按字母字典序重组
    private static String sortString(String s) {
        char[] charArray = s.toCharArray();
        Arrays.sort(charArray);
        return new String(charArray);
    }
}
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
# 读取 words.txt 文件中的单词
with open("words.txt", "r") as f:
    ws = [line.strip() for line in f]

# 按长度和字典序排序
ws.sort(key=lambda x: (len(x), x))

# 初始化优美字符串集合
bs = set()

# 动态规划：判断每个单词是否是优美字符串
for w in ws:
    if len(w) == 1:
        bs.add(w)
    else:
        pre = ''.join(sorted(w[:-1]))
        if any(''.join(sorted(s)) == pre for s in bs):
            bs.add(w)

# 找到最长的优美字符串
ml = max(len(w) for w in bs)
lbs = [w for w in bs if len(w) == ml]

# 输出字典序最小的结果
print(min(lbs))

C. LQ图形

img
img
img
img

观察可发现，可以将L分为上下两个部分，上面列数少的为h行，下面列数多的为w行，上下宽度分别为w和v+w。时间复杂度O(h + w)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//package 基础算法和其他.模拟.P12172_蓝桥杯2025省PythonB_LQ图形;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int h = sc.nextInt();
        int v = sc.nextInt();
        // 先是h高w宽的Q，然后是w高v+w宽
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for(int i = 1; i <= w; i++) sb1.append('Q');
        for(int i = 1; i <= v + w; i++) sb2.append('Q');
        for(int i = 1; i <= h; i++) System.out.println(sb1);
        for(int i = 1; i <= w; i++) System.out.println(sb2);
    }
}
1
2
3
4
5
6
7
w,h,v = MII()
t = h
b = w
for i in range(t):
    print('Q' * w)
for i in range(b):
    print('Q' * (v + w))

D. 最多次数

img
img

贪心，遇到连续的三个某个顺序的 l,q,b, 就把他拿掉。时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // lqb lbq qbl qlb blq bql 可以发现题目给出的是全排列
        // 遇到连续的 lqb 三个字母拿掉就行
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] strs = {"lqb", "lbq", "qlb", "qbl", "blq", "bql"};
        int res = 0, index = 0;
        for(int i = 0; i < str.length() - 2; i++){   // 注意防止越界
            String sub = str.substring(i, i + 3);
            for(int j = 0; j < 6; j++){
                if(sub.equals(strs[j])){
                    i += 2;   // 不判断中间的内容了
                    res++;
                    break;
                }
            }
        }
        System.out.println(res);
        sc.close();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
str_input = input()
strs = ["lqb", "lbq", "qlb", "qbl", "blq", "bql"]
res = 0
i = 0
while i < len(str_input) - 2:
    sub = str_input[i:i + 3]
    for j in range(6):
        if sub == strs[j]:
            i += 2
            res += 1
            break
    i += 1

print(res)

E. A*B Problem

在这里插入图片描述
在这里插入图片描述

给定 n，求四元组 (a,b,c,d) 个数，满足 a×b+c×d≤n，且 a,b,c,d 都是正整数。

我们需要枚举所有可能的向量 A 和 B，使得它们的内积不超过 L。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int L = scanner.nextInt();
        int count = 0;

        // 枚举所有可能的 (XA, YA) 和 (XB, YB)
        for (int XA = 1; XA <= L; XA++) {
            for (int YA = 1; YA <= L; YA++) {
                for (int XB = 1; XB <= L / XA + 1; XB++) {
                    for (int YB = 1; YB <= (L - XA * XB) / YA + 1; YB++) {
                        if (XA * XB + YA * YB <= L) {
                            count++;
                        }
                    }
                }
            }
        }

        System.out.println(count);
    }
}

不行，只有80分，考虑优化

将四元组 (a,b,c,d) 的问题转化为两个部分：x=a×b和 y=c×d，使得 x+y≤n。

这样，问题转化为统计所有满足 x+y≤n 的正整数对 (x,y) 的数量，其中 x 和 y 都可以表示为两个正整数的乘积。

这样对于满足 x+y=k 的四元组个数就是 tx×ty。

考虑每个数 i，预处理其能表示为两个正整数乘积的方式数 t[i]（即 i 的因数对数）。把 x 打表打出来

使用线性筛法预处理每个数的因数个数，计算 t[i]。

计算 t[i] 的前缀和数组 s[i]，用于快速查询 y≤n−x 时的 t[y] 的总和。

对于每个 x，其贡献为 t[x]×s[n−x]

为什么求 t[y] 要使用前缀和数组，对于每个固定的 x，我们需要找到所有满足 y≤n−x 的 y 的数量，也就是 ∑y=1n−x​t[y]

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
package 数学.subject.P12174_蓝桥杯2025省Python_B_AxBProblem;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int[] t = new int[l + 1];
        Arrays.fill(t, 0);

        // 枚举所有可能的 (a,b)组合，并统计每个乘积的出现次数，打表出四元组的前两部分乘积
        for (int a = 1; a <= l; a++) {
            for(int b = 1; a * b <= l; b++){
                t[a * b]++;
            }
        }

        // 前缀和
        int[] s = new int[l + 1];
        s[0] = 0;
        for (int i = 1; i <= l; i++) {
            s[i] = s[i - 1] + t[i];
        }

        long total = 0;
        // 对于每个 x
        for(int x = 1; x < l; x++){
            // 计算其对应的 y 的最大值 l - x
            int y = l - x;
            total += (long)t[x] * s[y];   // 前缀和计算
        }

        System.out.println(total);
    }
}

F. 园艺

讲过了，在

G. 书架还原

在这里插入图片描述
在这里插入图片描述 
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
package 基础算法和其他.贪心.subject.P12176_蓝桥杯2025省PythonB_书架还原;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 1];   // 书架
        int[] p = new int[n + 1];   // p[x]表示书本编号现在所处的位置
        int res = 0;
        for(int i = 1; i <= n; i++){
            a[i] = sc.nextInt();
            p[a[i]] = i;    // 桶记录书本a[i]的正确位置，p[a[i]] 是书本应该去的位置
        }

        // 从第一个位置开始检查，如果当前数字不在正确位置，就找到它应该去的位置，把这两个位置的数字交换。
        for(int i = 1; i <= n; i++){
            if(a[i] != i){   // 不在正确位置，需要调整位置
                p[a[i]] = p[i];   // 把书本放到应该去的位置
                ++res;
                // 把正确位置p[i]上的书本和当前书本位置交换
                int temp = a[p[i]];
                a[p[i]] = a[i];
                a[i] = temp;
            }
        }

        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = II()
a = [0] + LII()
p = [0] * (n + 1)
res = 0

for i in range(1,n + 1):
    p[a[i]] = i

for i in range(1,n + 1):
    if a[i] != i:
        p[a[i]] = p[i]
        a[i],a[p[i]] = a[p[i]],a[i]
        res += 1
print(res)

H. 异或和

在这里插入图片描述
在这里插入图片描述

考虑位运算，把每个数拆成二进制然后进行统计

由于异或运算本身就是建立在位的基础上的，所以我们只需要用一层循环枚举位

只有两个数当前位不同才能产生贡献。也就是说，如果这一位是 0，那他得跟这一位为 1 的数异或才能有贡献，所以加上这一位为 1 的数的个数再乘以这一位的权值

如果先不考虑公式后面的 j−i，那么只有用两个变量统计每位 0 和 1 的个数。

现在还得乘上 j−i，这个值是不断变化的，可以发现其中 i 是不变的，j 每次只加1，开两个变量存储每位 0 和 1 的权值

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
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        BigInteger[] arr = new BigInteger[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextBigInteger();
        }
        BigInteger res = BigInteger.ZERO;

        // 只有两个数当前位不同才能产生贡献。
        for (int dig = 0; dig <= 20; dig++) {
            int[] cnt = {0, 0};   // 记录当前已处理过的数中，二进制位 k 为 0 或 1 的数的个数。
            BigInteger[] sum = {BigInteger.ZERO, BigInteger.ZERO};   // 下标差的动态和
            for (int i = 1; i <= n; i++) {
                // 提取arr[i]的二进制中第 dig 位的值
                int bit = arr[i].shiftRight(dig).and(BigInteger.ONE).intValue();
                // 取出相反位的值，这样的才可以产生贡献
                BigInteger multiplier = BigInteger.valueOf(1L << dig);
                res = res.add(sum[bit ^ 1].multiply(multiplier));
                cnt[bit]++;
                // 每次处理一个数时，所有之前记录的数的下标差会自然增加
                sum[0] = sum[0].add(BigInteger.valueOf(cnt[0]));
                sum[1] = sum[1].add(BigInteger.valueOf(cnt[1]));
            }
        }

        System.out.println(res);
    }
}    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = int(input())  # 输入数组长度
a = list(map(int, input().split()))  # 输入数组
res = 0  # 最终结果

for b in range(31):  # 遍历每一位（0到30位）
    m = 1 << b  # 当前位的掩码，用于提取该位的值
    c = [0, 0]  # 用于统计当前位为0和1的数量
    s = [0, 0]  # 用于记录当前位为0和1的索引和
    cur = 0  # 当前位的贡献值

    for i in range(n):  # 遍历数组中的每个元素
        bit = (a[i] >> b) & 1  # 提取当前元素在当前位的值（0或1）
        cur += c[1 - bit] * i - s[1 - bit]  # 计算当前位的贡献值
        c[bit] += 1  # 更新当前位的计数
        s[bit] += i  # 更新当前位的索引和

    res += cur * m  # 将当前位的贡献值乘以掩码，累加到最终结果

print(res)  # 输出最终结果