算法题贪心

1.P12870 [蓝桥杯 2025 国 Python A] 铺设能源管道

题目描述

能源公司正着手建立新的基地。为了确保基地的能源供应，公司计划铺设一条长度至少为 $n$ 公里的能源管道。铺设管道的成本并非简单地与管道长度成正比，而是由管道长度的各位数字之和决定。例如，铺设 $123$ 公里的管道，实际成本为 $1 + 2 + 3 = 6$ 。

为了尽可能降低成本，公司希望找到一个长度为 $m$ 公里的铺设方案，使得 $m$ 不小于 $n$，并且 $m$ 的数位和最小。如果存在多个满足条件的 $m$，则选择数值最小的方案，以确保在成本相同的情况下，尽可能减少资源浪费。

现在，请你帮助能源公司计算出最优的管道铺设长度 $m$。

输入格式

输入一行包含一个整数 $n$，表示需要铺设的最低管道长度。

输出格式

输出一行包含一个整数 $m$，表示最优的管道铺设长度。

输入输出样例 #1

输入 #1

9

输出 #1

10

说明/提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \leq n \leq 100$。

对于所有的评测用例，$1 \leq n \leq 10^9$。

题解

数位和最小的永远是1，10，100，1000，……，所以要找的就是这些数中比输入数字大的

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();

            int ans=1;
            while(ans<n)
                {
                    ans=ans*10;
                }
            System.out.print(ans);
            
        }
    }

2.P8597 [蓝桥杯 2013 省 B] 翻硬币

题目背景

小明正在玩一个“翻硬币”的游戏。

题目描述

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零），比如可能情形是 **oo***oooo，如果同时翻转左边的两个硬币，则变为 oooo***oooo。现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币，那么对特定的局面，最少要翻动多少次呢？

输入格式

两行等长字符串，分别表示初始状态和要达到的目标状态，每行长度小于 $1000$。

数据保证一定存在至少一种方案可以从初始状态和要达到的目标状态。

输出格式

一个整数，表示最小操作步数。

输入输出样例 #1

输入 #1

**********
o****o****

输出 #1

5

输入输出样例 #2

输入 #2

*o**o***o***
*o***o**o***

输出 #2

1

题解

用贪心来做，每次遇到和答案不同的就翻转当前位置及其后一个位置

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);

            String linestart=scan.next();
            char[] start=linestart.toCharArray();

            String lineend=scan.next();
            char[] end=lineend.toCharArray();

            int ans=0;
            for(int i=0;i<start.length-1;i++)
                {
                    if(start[i]!=end[i])
                    {
                        if(start[i]=='*')
                        {
                            start[i]='o';
                        }
                        else
                        {
                            start[i]='*';
                        }
                        if(start[i+1]=='*')
                        {
                            start[i+1]='o';
                        }
                        else
                        {
                            start[i+1]='*';
                        }
                        ans++;
                    }
                }

            System.out.print(ans);
        }
    }

3.P8697 [蓝桥杯 2019 国 C] 最长子序列

题目描述

我们称一个字符串 $S$ 包含字符串 $T$ 是指 $T$ 是 $S$ 的一个子序列，即可以从字符串 $S$ 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 $T$ 完全一样。给定两个字符串 $S$ 和 $T$，请问 $T$ 中从第一个字符开始最长连续多少个字符被 $S$ 包含？

输入格式

输入两行，每行一个字符串。第一行的字符串为 $S$，第二行的字符串为 $T$。两个字符串均非空而且只包含大写英文字母。

输出格式

输出一个整数，表示答案。

输入输出样例 #1

输入 #1

ABCDEABCD
AABZ

输出 #1

3

说明/提示

对于 $20\%$ 的评测用例，$1 \le |T| \le |S| \le 20$；

对于 $40\%$ 的评测用例，$1 \le |T| \le |S| \le 100$；

对于所有评测用例，$1 \le |T| \le |S| \le 1000$。

题解

类似于lcs最长公共子序列，但是不完全一样，这道题固定了一个开头，所以双指针。

代码

import java.util.*;

public class Main 
{

    public static void main(String[] args) 
    {
        Scanner scan=new Scanner(System.in);
        String a=scan.nextLine();
        char[] aa=a.toCharArray();

        String b=scan.nextLine();
        char[] bb=b.toCharArray();


        int i=0;
        int j=0;
        while(i<aa.length&&j<bb.length)
            {
                if(aa[i]==bb[j])
                {
                    j++;
                }
                i++;
            }
        
        System.out.print(j);
        
    }
}

4.P8739 [蓝桥杯 2020 国 C] 重复字符串

题目描述

如果一个字符串 $S$ 恰好可以由某个字符串重复 $K$ 次得到，我们就称 $S$ 是 $K$ 次重复字符串。例如 abcabcabc 可以看作是 abc 重复 $3$ 次得到，所以 abcabcabc 是 $3$ 次重复字符串。

同理 aaaaaa 既是 $2$ 次重复字符串、又是 $3$ 次重复字符串和 $6$ 次重复字符串。

现在给定一个字符串 $S$，请你计算最少要修改其中几个字符，可以使 $S$ 变为一个 $K$ 次字符串？

输入格式

输入第一行包含一个整数 $K$。

第二行包含一个只含小写字母的字符串 $S$。

输出格式

输出一个整数代表答案。如果 $S$ 无法修改成 $K$ 次重复字符串，输出 $−1$。

输入输出样例 #1

输入 #1

2
aabbaa

输出 #1

2

说明/提示

其中，$1 \le K \le 10^5$，$1 \le |S| \le 10^5$。其中 $|S|$ 表示 $S$ 的 长度。

题解

首先要确定的是，S一定是能被K所整除的，否则输出-1。

然后将整个字符串分组，先按照输入给出的K，分成K组，然后再按照这K组中应该重复的位置分组，也就是将每一组中的第i个位置分为一组。然后统计这样的每一组中，出现最多的元素的次数，这个次数就不需要修改的，那么要修改的次数就是K-这个次数，然后把要修改的次数累加。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int K=scan.nextInt();
            String line=scan.next();
            char[] str=line.toCharArray();
            

            if(str.length%K!=0)
            {
                System.out.print(-1);
            }
            else
            {
                int ans=0;
                for(int i=0;i<str.length/K;i++)
                    {
                        int[] cnt=new int[26];
                        for(int j=0;j<K;j++)
                            {
                                cnt[str[i+j*(str.length/K)]-'a']++;
                            }
                        int max=0;
                        for(int k=0;k<26;k++)
                            {
                                if(cnt[k]>max)
                                {
                                    max=cnt[k]; 
                                }
                            }
                        ans=ans+K-max;
                    }
                System.out.print(ans);
            }
            
        }
    }

5.P10902 [蓝桥杯 2024 省 C] 回文数组

题目描述

小蓝在无聊时随机生成了一个长度为 $n$ 的整数数组，数组中的第 $i$ 个数为 $a_i$，他觉得随机生成的数组不太美观，想把它变成回文数组，也是就对于任意 $i\in [1,n]$ 满足 $a_i=a_{n-i+1}$。小蓝一次操作可以指定相邻的两个数，将它们一起加 $1$ 或减 $1$；也可以只指定一个数加 $1$ 或减 $1$，请问他最少需要操作多少次能把这个数组变成回文数组？

输入格式

输入的第一行包含一个正整数 $n$。

第二行包含 $n$ 个整数 $a_1, a_2,\cdots, a_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

4
1 2 3 4

输出 #1

3

说明/提示

【样例说明】

第一次操作将 $a_1, a_2$ 加 $1$，变为 $2, 3, 3, 4$；

后面两次操作将 $a_1$ 加 $1$，变为 $4,3,3,4$。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$1 \le n \le 10$；

对于所有评测用例，$1 \le n \le 10^5$，$-10^6 \le a_i \le 10^6$。

题解

对于回文数组来说，是前后对称的，所以只需要关注前一半。先算出前一半的数字和后一半的差值，存为数组。然后对这个数组进行判断，如果第i个元素是0，有就是不用调整，那么就是跳过，如果这个元素和其后一个元素同号，那么就在操作数上加上当前元素的大小，并且调整下一个元素的大小。如果不同号就是要单独调整就只需要在操作数上加上当前元素的大小

代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long[] a = new long[(int) n + 1];
        long[] s = new long[(int) n + 1];
        long ans = 0;

        for (int i = 1; i <= n; i++) 
        {
            a[i] = sc.nextLong();
        }

        for (int i = 1; i <= n / 2; i++) 
        {
            s[i] += (a[i] - a[(int) (n - i + 1)]);
        }

        for (int i = 1; i <= n / 2; i++) 
        {
            if (s[i] == 0) continue;
            if (s[i] >= 0 && s[i + 1] >= 0) 
            {
                ans += s[i];
                s[i + 1] -= s[i];
                s[i + 1] = Math.max(s[i + 1], 0);
            } 
            else if (s[i] <= 0 && s[i + 1] <= 0) 
            {
                ans += -s[i];
                s[i + 1] -= s[i];
                s[i + 1] = Math.min(s[i + 1], 0);
            } 
            else 
            {
                ans += Math.abs(s[i]);
            }
        }
        System.out.println(ans);
    }
}

6.P10910 [蓝桥杯 2024 国 B] 最小字符串

题目描述

给定一个长度为 $N$ 且只包含小写字母的字符串 $S$，和 $M$ 个小写字母 $c_1, c_2, \cdots, c_M$。现在你要把 $M$ 个小写字母全部插入到字符串 $S$ 中，每个小写字母都可以插入到任意位置。

请问能得到的字典序最小的字符串是什么？

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含一个长度为 $N$ 的字符串 $S$。第三行包含 $M$ 个小写字母 $c_1, c_2, \cdots, c_M$。

输出格式

输出一个长度为 $N + M$ 的字符串代表答案。

输入输出样例 #1

输入 #1

4 3
abbc
cba

输出 #1

aabbbcc

输入输出样例 #2

输入 #2

7 3
lanqiao
bei

输出 #2

beilanqiao

说明/提示

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$M = 1$。
对于 $100\%$ 的评测用例，$1 \le N, M \le 10^5$。

题解

获取输入之后先把第二个字符串用Arrays.sort(s2);进行一个排序。然后用两个变量对两个数组进行操作，如果第一个小于等于第二则选取第一个（等于的时候也要选第一个，因为第二个字符串排序后一定是递增的，但是第一个字符串后面可能还有更小的），否则选择第二个。然后，在某一个字符串选完之后，对剩下的一个字符串全选。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int N=scan.nextInt();
            int M=scan.nextInt();

            String line1=scan.next();
            String line2=scan.next();
            char[] s1=line1.toCharArray();
            char[] s2=line2.toCharArray();
            Arrays.sort(s2);

            StringBuilder sb=new StringBuilder();
            int i=0;
            int j=0;
            while(i<N&&j<M)
                {
                    if(s1[i]<=s2[j])
                    {
                        sb.append(s1[i]);
                        i++;
                    }
                    else
                    {
                        sb.append(s2[j]);
                        j++;
                    }
                }
            while(i<N)
                {
                    sb.append(s1[i]);
                    i++;
                }
            while(j<M)
                {
                    sb.append(s2[j]);
                    j++;
                }
            System.out.print(sb.toString());
        }
    }

7.P12165 [蓝桥杯 2025 省 C/Java A] 最短距离

题目描述

在一条一维的直线上，存在着 $n$ 台显示器和 $n$ 个电源插座。老师给小蓝布置了个任务：负责将每台显示器通过电源线与一个插座相连接（每个插座最多只能给一台显示器供电）；同时，老师希望所消耗的电源线的长度尽可能的少，请你帮小蓝计算下电源线的最小消耗长度为多少？

为了便于计算，你只需要考虑直线距离即可。

输入格式

输入的第一行包含一个正整数 $n$。

接下来 $n$ 行，每行包含一个整数 $x_i$，依次表示每台显示器的坐标。

接下来 $n$ 行，每行包含一个整数 $y_i$，依次表示每个插座的坐标。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

2
0
1
2
3

输出 #1

4

说明/提示

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$1 \leq n \leq 10$，$0 \leq x_i, y_i \leq 100$；

• 对于 $40\%$ 的评测用例，$1 \leq n \leq 100$，$0 \leq x_i, y_i \leq 10^3$；

• 对于 $60\%$ 的评测用例，$1 \leq n \leq 1000$，$0 \leq x_i, y_i \leq 10^5$；

• 对于 $80\%$ 的评测用例，$1 \leq n \leq 10000$，$0 \leq x_i, y_i \leq 10^9$；

• 对于所有评测用例，$1 \leq n \leq 50000$，$0 \leq x_i, y_i \leq 10^9$。

题解

获取数据后进行排序，然后第i个电脑对应第i个电源是最优解。问题是能不能证明不存在反例。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();

            int[] c=new int[n];
            int[] b=new int[n];

            for(int i=0;i<n;i++)
                {
                    c[i]=scan.nextInt();
                }
            for(int i=0;i<n;i++)
                {
                    b[i]=scan.nextInt();
                }
            Arrays.sort(c);
            Arrays.sort(b);
            long ans=0;
            for(int i=0;i<n;i++)
                {
                    ans=ans+Math.abs(c[i]-b[i]);
                }
            System.out.print(ans);
        }
    }

8.P12173 [蓝桥杯 2025 省 Python B] 最多次数

题目描述

小蓝有一个字符串 $s$，他特别喜欢由以下三个字符组成的单词：$\tt {l}, \tt{q}, \tt{b}$，任意顺序都可以，一共有 $6$ 种可能：$\tt{lqb}$、$\tt{lbq}$、$\tt{qlb}$、$\tt{qbl}$、$\tt{blq}$、$\tt{bql}$。

现在他想从 $s$ 中，尽可能切割出多个他喜欢的单词，请问最多能切割出多少个？单词指的是由若干个连续的字符组成的子字符串。

输入格式

输入一行包含一个字符串 $s$。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

lqbblqblqlxqb

输出 #1

3

说明/提示

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$1 \leq |s| \leq 10$；

• 对于 $40\%$ 的评测用例，$1 \leq |s| \leq 20$；

• 对于 $60\%$ 的评测用例，$1 \leq |s| \leq 100$；

• 对于 $70\%$ 的评测用例，$1 \leq |s| \leq 10^3$；

• 对于 $80\%$ 的评测用例，$1 \leq |s| \leq 10^4$；

• 对于所有评测用例，$1 \leq |s| \leq 10^5$，$s$ 中只包含小写字母。

题解

对每个元素进行判断，如果当前元素与其后的两个元素能构成，则计数器++，并且跳过下两个元素。用substring截取当前元素到后两个元素。在判断部分，先将字符串传入，转化成字符数组，再对其进行排序比较是否正确。

代码

import java.util.*;

public class Main
    {
        static int ans=0;
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            String line=scan.next();
            int n=line.length();
            check(line,n);
            System.out.print(ans);
            
        }

        public static boolean isValid(String str)
        {
            char[] s=str.toCharArray();
            Arrays.sort(s);
            return new String(s).equals("blq");
        }

        public static void check(String s,int n)
        {
            for(int i=0;i<n-2;i++)
                {
                    String str=s.substring(i,i+3);
                    if(isValid(str))
                    {
                        ans++;
                        i=i+2;
                    }
                }
        }
    }

9.P12176 [蓝桥杯 2025 省 Python B] 书架还原

题目描述

在一个偏远的图书馆里，有个书架上放着 $n$ 本书，每本书上都标有一个从 $1$ 到 $n$ 的唯一编号。

按照规矩，这些书应该按编号从小到大依次排列：$1$ 号书位于最左端，$2$ 号书紧随其后，以此类推，直到 $n$ 号书在最右端。这样的顺序不仅看起来整齐，也方便读者快速找到想借的书。

可昨天店里人来人往，借书还书忙得不可开交，书架上的顺序出现了错乱。现在，书架上的书变成了 $a = (a_1, a_2, \ldots, a_n)$，其中 $a_i$ 表示第 $i$ 个位置上的书编号。

管理员决定动手整理书架，但时间有限，他希望用最少的操作把书的顺序恢复到正确的排列。每次操作，他可以挑选书架上任意两本书，交换它们的位置。例如，如果当前排列是 $(3, 1, 2)$，他可以交换第 $1$ 本和第 $2$ 本，得到 $(1, 3, 2)$，再交换第 $2$ 本和第 $3$ 本，得到 $(1, 2, 3)$。

你的任务是帮助管理员计算，最少需要进行多少次操作，才能让书架上的书的编号排列变为 $(1, 2, \ldots, n)$。

输入格式

输入的第一行包含一个正整数 $n$，表示书架上书的总数。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，相邻整数之间使用一个空格分隔，依次表示当前书架上每本书的编号。$a_1, a_2, \ldots, a_n$ 是一个 $1$ 到 $n$ 的排列。

输出格式

输出一行包含一个整数表示答案，即将书架上的书恢复到正确排列所需的最少操作次数。

输入输出样例 #1

输入 #1

3
3 1 2

输出 #1

2

说明/提示

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1 \leq n \leq 10^3$，$1 \leq a_i \leq n$，$a_1, a_2, \dots, a_n$ 各不相同；

• 对于所有评测用例，$1 \leq n \leq 10^6$，$1 \leq a_i \leq n$，$a_1, a_2, \dots, a_n$ 各不相同。

题解

对于每个元素，如果不在对应位置，则去找到其应该在的位置上的元素，再对这个元素找其应该在的位置，依次循环，直到找到的元素成环，记录找到的元素个数，然后开始下一个循环，最后统计找到的元素个数-1

代码

import java.util.*;

public class Main
    {
        static int ans=0;
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            int[] a=new int[n];
            for(int i=0;i<n;i++)
                {
                    a[i]=scan.nextInt();
                }
            boolean[] visited=new boolean[n];
            for(int i=0;i<n;i++)
                {
                    if(visited[i])
                       {
                        continue;
                       }

                    int cnt=0;
                    int cur=i;
                    
                    while(!visited[cur])
                    {
                        visited[cur]=true;
                        cur=a[cur]-1;
                        cnt++;
                    }
                    if(cnt>1)
                    {
                        ans=ans+cnt-1;
                    }
                }
            System.out.print(ans);
        }
    }

10.P12218 [蓝桥杯 2023 国 Java B] 玩具

题目描述

小明的妈妈给他买了 $n$ 个玩具，但是为了同时考察他的智力，只给了他 $2 \times n$ 个零件，第 $i$ 个零件的重量为 $w_i$（$1 \leq i \leq 2 \times n$）。

其中任意两个零件都可以拼接成一个玩具，这个玩具的权重就等于拼接所用的 两个零件的重量的乘积。小明的妈妈希望小明能够使用这 $2 \times n$ 个零件拼接出 $n$ 个玩具（每个零件必须使用且只能用一次），使得所有玩具的权重的和最小。小明希望你帮帮他计算出最小的权重和。

输入格式

输入共 $2$ 行。

第一行为一个正整数 $n$。

第二行为 $2 \times n$ 个由空格隔开的整数 $w_1, w_2, \ldots, w_{2 \times n}$。

输出格式

输出共 $1$ 行，一个整数。

输入输出样例 #1

输入 #1

2
2 2 3 4

输出 #1

14

说明/提示

样例说明

由于有两个零件的重量都为 $2$，所以一共有两种结果:

• $(2 \times 2) + (3 \times 4) = 16$;

• $(2 \times 3) + (2 \times 4) = 14$。

评测用例规模与约定

• 对于 $20\%$ 的数据，保证 $n \leq 10^3$。

• 对于 $100\%$ 的数据，保证 $n \leq 10^5$，$0 \leq w_i \leq 10^5$。

题解

先排序，然后前后搭配的贪心。得开long

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            long n=scan.nextLong();
            long[] w=new long[(int)(2*n)];
            for(int i=0;i<2*n;i++)
                {
                    w[i]=scan.nextLong();
                }
            Arrays.sort(w);
            long ans=0;
            for(int i=0;i<n;i++)
                {
                    ans=ans+(w[(int)(i)]*w[(int)(2*n-i-1)]);
                }
            System.out.print(ans);
        }
    }

11.P12268 [蓝桥杯 2024 国 Python B] 球衣号码

题目描述

在篮球之都，有一支传奇的篮球队，名为“坤之队”。这支球队由 $n$ 位才华横溢的球员组成，编号分别为 $1, 2, \ldots, n$。

今年，坤之队共参加了 $m$ 场激烈的比赛。在每场比赛前，坤之队的教练阿坤都会举行一个出征仪式。他会指定其中一名球员为队长，并将其球衣的号码设为 $0$。同时，为了保持队员之间的秩序和团结，教练还会对其他球员的球衣号码进行调整。具体来说，站在队长右边的每个球员的球衣号码将比他左边球员的球衣号码大 $1$，而站在队长左边的每个球员的球衣号码将比他右边球员的球衣号码大 $1$。球队中可能会有相同的球衣号码。

举个例子，假设坤之队有 $n = 5$ 名球员，阿坤在一场比赛前指定编号为 $3$ 的球员为队长，那么球员们球衣的号码就会变为 $[2, 1, 0, 1, 2]$。

经过 $m$ 轮比赛的激烈角逐后，阿坤希望你能帮助他确定，每个球员所拥有过的最大球衣号码是多少。

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$，用一个空格分隔，分别表示球员数量和比赛场次数。

第二行包含 $m$ 个整数 $p_1, p_2, \ldots, p_m$，表示每场比赛前被指定为队长的球员的编号。

输出格式

输出一行包含 $n$ 个整数，相邻整数之间使用一个空格分隔，依次表示每个球员所拥有过的最大球衣编号。

输入输出样例 #1

输入 #1

6 2
1 3

输出 #1

2 1 2 3 4 5

说明/提示

样例说明

• 在第一场比赛的出征仪式中，阿坤指定了编号为 1 的球员为队长。此时球员们的球衣号码为：

$$[0,1,2,3,4,5]$$

• 在第二场比赛的出征仪式中，阿坤指定了编号为 3 的球员为队长。此时球员们的球衣号码为：

$$[2,1,0,1,2,3]$$

• 因此，每个球员所拥有过的最大球衣号码为：

$$[2,1,2,3,4,5]$$

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$1 \leq m \leq n \leq 100$，$1 \leq p_i \leq n$，$p_1, p_2, \ldots, p_m$ 各不相同。

• 对于 $50\%$ 的评测用例，$1 \leq m \leq n \leq 10^3$，$1 \leq p_i \leq n$，$p_1, p_2, \ldots, p_m$ 各不相同。

• 对于所有评测用例，$1 \leq m \leq n \leq 10^5$，$1 \leq p_i \leq n$，$p_1, p_2, \ldots, p_m$ 各不相同。

题解

可以直接暴力枚举，但是超时。实际上只需要找出这个队长的位置的最大最小值，通过这个值再去求其他队员的最大值。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            int m=scan.nextInt();

            int[] p=new int[m];
            for(int i=0;i<m;i++)
                {
                    p[i]=scan.nextInt();
                }
            Arrays.sort(p);

            int[] max=new int[n];
            for(int i=0;i<n;i++)
                {
                    max[i]=Math.abs(i-(p[0]-1));
                }
            for(int i=0;i<n;i++)
                {
                    max[i]=Math.max(max[i],Math.abs(i-(p[m-1]-1)));
                }
            /*
            for(int x:p)
                {
                    x--;
                    for(int i=0;i<n;i++)
                        {
                            int num=0;
                            if(i<x)
                            {
                                 num=x-i; 
                            }
                            else if(i>x)
                            {
                                num=i-x;
                            }
                            else
                            {
                                num=0;
                            }
                            max[i]=Math.max(max[i],num);
                        }
                }
            */
            for(int i=0;i<n-1;i++)
                {
                    System.out.print(max[i]+" ");
                }
            System.out.print(max[n-1]);
        }
    }

12.P12277 [蓝桥杯 2024 国 Python A] 床底取牌

题目背景

原题题面存在歧义，洛谷题面明确了是一定能凑齐六张卡牌最少从床底下取出多少张卡牌。

题目描述

最近，小蓝对拼单词的游戏特别着迷。他有一盒专门用于拼单词的字母卡片，其中每张卡片上分别印有 $\tt l$、$\tt a$、$\tt n$、$\tt q$、$\tt i$、$\tt o$ 中的一个字母，并且每种字母对应的卡牌都有 $5$ 张。

小蓝给自己设定了一个目标，即拼出单词 $\tt{lanqiao}$。对此，他需要 $2$ 张 $\tt a$ 以及 $\tt l$、$\tt n$、$\tt q$、$\tt i$、$\tt o$ 各 $1$ 张。

然而，很不幸的是，小蓝在玩耍时不小心把卡片盒打翻了，所有的卡片一下子都掉进了床底下。因为床底下光线非常暗，小蓝根本无法看清卡片上的字母。

那么请问，要想一定能凑齐 $\tt l$、$\tt a$、$\tt n$、$\tt q$、$\tt i$、$\tt a$、$\tt o$ 这 $6$ 张卡牌，小蓝最少需要从床底下取出几张卡牌呢？

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只需要编写一个程序输出这个整数，输出多余的内容将无法得分。

题解

要求一定能凑齐，那么就是考虑最坏情况下要抽多少次，也就是除了a以外的卡都抽完了，最后再抽出来两张a

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            System.out.print(27);
        }
    }

13.P12342 [蓝桥杯 2025 省 B/Python B 第二场] 数列差分

题目描述

小蓝有两个长度均为 $n$ 的数列 $A=\{a_1, a_2, \cdots, a_n\}$ 和 $B=\{b_1, b_2, \cdots, b_n\}$，将两个数列作差定义为 $C=A-B=\{c_1=a_1-b_1, c_2=a_2-b_2, \cdots, c_n=a_n-b_n\}$。小蓝将对数列 $B$ 进行若干次操作，每次操作可以将数列 $B$ 中的任意一个数更改为任意一个整数。在进行完所有操作后，小蓝可以按任意顺序将数列 $B$ 重排，之后再计算数列 $C$。小蓝想知道，最少操作多少次可以使得数列 $C$ 中的所有数都为正整数。

输入格式

输入的第一行包含一个正整数 $n$；

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，相邻整数之间使用一个空格分隔。

第三行包含 $n$ 个整数 $b_1, b_2, \cdots, b_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

4
22 31 12 14
3 19 27 44

输出 #1

1

说明/提示

样例说明

其中一种方案：将 $44$ 改为 $0$，重新排列 $B$ 为 $\{19, 27, 3, 0\}$，使得数列 $C=\{3, 4, 9, 14\}$ 均为正整数。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$n \leq 10$；

• 对于所有评测用例，$1 \leq n \leq 10^5$，$-10^9 \leq a_i \leq 10^9$，$-10^9 \leq b_i \leq 10^9$。

题解

因为可以修改B的顺序，所以就是要尽可能的先匹配，再去做修改。先把两个数组进行一个排序，然后再从头开始找，能不能匹配，当前的a不能匹配就跳过到下一个a，再与当前的b匹配。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            long[] a=new long[n];
            long[] b=new long[n];
            for(int i=0;i<n;i++)
                {
                    a[i]=scan.nextInt();
                }
            for(int i=0;i<n;i++)
                {
                    b[i]=scan.nextInt();
                }
            Arrays.sort(a);
            Arrays.sort(b);
            int ans=0;
            int i=0;
            int j=0;
            while(i<n&&j<n)
                {
                    if(a[i]>b[j])
                    {
                        i++;
                        j++;
                    }
                    else
                    {
                        ans++;
                        i++;
                    }
                }
            System.out.print(ans);
        }
    }

14.P12341 [蓝桥杯 2025 省 A/Python B 第二场] 消消乐

题目描述

小蓝正在玩一个叫“一维消消乐”的游戏。游戏初始时给出一个长度为 $n$ 的字符串 $S = S_0S_1\ldots S_{n-1}$，字符串只包含字符 $\text{A}$ 和 $\text{B}$。小蓝可以对这个字符串进行若干次操作，每次操作可以选择两个下标 $i, j \in [0, n-1]$，如果 $i < j$ 且 $S_i = \text{A}$ 且 $S_j = \text{B}$，小蓝就可以把它们同时消掉。小蓝想知道在经过若干次操作后，直到无法对字符串继续进行操作时，字符串最多剩下多少个字符。

输入格式

输入一行包含一个长度为 $n$ 的字符串 $S$。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

BABAABBA

输出 #1

4

说明/提示

样例说明

先消掉 $(S_1, S_6)$，再消掉 $(S_4, S_5)$，此时剩下 $\text{BBAA}$，无法继续进行操作。

评测用例规模与约定

• 对于 $10\%$ 的评测用例，$1 \leq n \leq 20$；

• 对于 $20\%$ 的评测用例，$1 \leq n \leq 100$；

• 对于 $50\%$ 的评测用例，$1 \leq n \leq 10000$；

• 对于所有评测用例，$1 \leq n \leq 10^6$。

题解

从头开始匹配A，从尾开始匹配B，前面匹配不上就往后走，后面匹配不上就往前走。都匹配上了就同时向中间走

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            String line=scan.next();
            char[] str=line.toCharArray();
            int i=0;
            int j=str.length-1;
            int ans=0;
            while(i<j)
                {
                    while(i<j&&str[i]!='A')
                        {
                            i++;
                        }
                    while(i<j&&str[j]!='B')
                        {
                            j--;
                        }
                    if(i<j&&str[i]=='A'&&str[j]=='B')
                    {
                        ans=ans+2;
                        i++;
                        j--;
                    }
                    
                }
            System.out.print(str.length-ans);
        }
    }

15.P12344 [蓝桥杯 2025 省 B/Python B 第二场] 破解信息

题目描述

在遥远的未来，星际旅行已经成为常态。宇航员小蓝在一次探险任务中，意外发现了一个古老的太空遗迹。遗迹中存放着一个数据存储器，里面记录着一段加密的信息。经过初步分析，小蓝发现这段信息可以被表示为一个字符串 $S$，而解密的关键，在于找出 $S$ 中字典序最大的回文子序列。

• 子序列：指从原字符串中抽取若干个字符（可以不连续），按照它们在原字符串中的相对顺序排列所形成的新序列。例如，对于字符串 abc，其子序列包括 a、b、c、ab、ac、bc 和 abc。

• 字典序：指字符串按照字典中的排序规则比较大小的方式。对于两个字符串，从左到右逐字符比较，先出现较大字符的字符串字典序更大；若比较到某个字符串结束仍未找到不同的字符，则较短的字符串字典序较小。例如，abc < abd，而 ab < abc。

现在，请你从字符串 $S$ 中，找出字典序最大的回文子序列，帮助小蓝解开这段来自星际文明的信息。

输入格式

输入一行包含一个字符串 $S$，表示加密的信息。

输出格式

输出一行包含一个字符串，表示 $S$ 中字典序最大的回文子序列。

输入输出样例 #1

输入 #1

abcd

输出 #1

d

输入输出样例 #2

输入 #2

abab

输出 #2

bb

说明/提示

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1 \leq |S| \leq 300$，其中 $|S|$ 表示字符串 $S$ 的长度；

• 对于所有评测用例，$1 \leq |S| \leq 10^5$，$S$ 中只包含小写英文字母。

题解

因为要按字典序所以其实就是统计最大的字符出现了几次。所以直接用一个排序，然后循环，但是要先用短路判断i合不合法，不然会导致部分re。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            String line=scan.next();
            char[] str=line.toCharArray();
            Arrays.sort(str);
            int i=str.length-1;
            int count=0;
            while(i>=0&&str[i]==str[str.length-1])
                {
                    i--;
                    count++;
                }
            for(int j=0;j<count;j++)
                {
                    System.out.print(str[str.length-1]);
                }
        }
    }

16.P12879 [蓝桥杯 2025 国 C] 打破规则

题目描述

蓝桥小镇的钟表铺里，工匠小蓝正在修复一座三针时钟。其中，时针的长度为 $A$，分针的长度为 $B$，秒针的长度为 $C$，均为正整数。制造商为追求独特的设计，设定了以下规则：

• 三根指针的长度互不相同，即 $A \neq B$，$A \neq C$，$B \neq C$；

• 将三根指针的长度从大到小排序后，第二长的指针必须是时针（长度 $A$）或秒针（长度 $C$）。

然而，这些规则会导致指针运行时相互干扰，影响时钟的稳定性。于是，小蓝决定调整指针长度，打破上述规则：要么三根指针的长度不互不相同（存在至少两根指针的长度相同），要么第二长的指针不是 $A$ 或 $C$。他可以执行以下三种操作：

• 将时针的长度 $A$ 减少 1；

• 将分针的长度 $B$ 减少 1；

• 将秒针的长度 $C$ 减少 1。

调整后的指针长度必须为正整数，即 $A, B, C > 0$。

现在，请你帮助小蓝计算，打破制造商规则所需的最小操作次数。

输入格式

输入一行包含三个正整数 $A, B, C$，相邻整数之间使用一个空格分隔，分别表示时针、分针和秒针的初始长度。

输出格式

输出一行包含一个整数，表示打破制造商规则所需的最小操作次数。

输入输出样例 #1

输入 #1

1 2 3

输出 #1

0

输入输出样例 #2

输入 #2

5 9 2

输出 #2

3

输入输出样例 #3

输入 #3

5 6 5

输出 #3

0

说明/提示

【评测用例规模与约定】

对于 $50\%$ 的评测用例，$1 \leq A, B, C \leq 100$；

对于所有评测用例，$1 \leq A, B, C \leq 10^5$。

题解

首先进行排序，判断是否已经打破规则，如果没有那么将两个指针相等是最优解。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int[] s=new int[3];
            for(int i=0;i<3;i++)
                {
                    s[i]=scan.nextInt();
                }
            int a=s[0];
            int b=s[1];
            int c=s[2];
            Arrays.sort(s);
            if(s[1]==b||a==b||b==c||a==c)
            {
                System.out.print(0);
            }
            else
            {
                int ans=Math.min(Math.abs(a-b),Math.min(Math.abs(a-c),Math.abs(b-c)));
                System.out.print(ans);
            }
        }
    }

17.P12887 [蓝桥杯 2025 国 Java B] 答题数量

题目描述

小蓝从一间空荡的房间中醒来，眼前放着一张木桌，桌上摆放着两份密封的答案纸，一份属于他，另一份属于他的朋友。每张纸上都写着一个长度为 $N$ 的字符串，仅包含字符 $\tt T$ 和 $\tt F$ ——这是他们昨晚参加一场判断题考试后的答题记录。

考试共有 $N$ 道题目，每题的答案只有两种可能：

• $\tt T$ 表示 $\text{True}$（正确）

• $\tt F$ 表示 $\text{False}$（错误）

两人在相互隔离、无法交流的情况下各自完成了作答，并提交了自己的答案。

今早，小蓝收到了一条神秘信息：

“你的朋友恰好答对了 $M$ 道题。”

标准答案尚未公布，小蓝无法直接判断自己答对了多少题。然而，基于已知信息，小蓝希望评估出，在所有可能的标准答案中，他自己最多能答对多少题。现在，请你计算小蓝至多能答对的题目数量。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示题目数量和朋友答对的题目数量。

第二行包含一个长度为 $N$、仅由字符 $\text{T}$ 和 $\text{F}$ 组成的字符串 $S$，表示小蓝的答案。

第三行包含一个长度为 $N$、仅由字符 $\text{T}$ 和 $\text{F}$ 组成的字符串 $T$，表示朋友的答案。

输出格式

输出一个整数，表示在所有可能的标准答案中，小蓝最多能答对的题目数量。

输入输出样例 #1

输入 #1

4 2
TTFF
FTTF

输出 #1

4

说明/提示

【评测用例规模与约定】

对于 $100\%$ 的评测用例，$2 \leq M \leq N \leq 10^5$。

题解

先统计一共有多少题答案一样，在这么多答案一样的中再算与M的差值，最后用N减去这个差值就是。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int N=scan.nextInt();
            int M=scan.nextInt();

            String line1=scan.next();
            String line2=scan.next();
            char[] str1=line1.toCharArray();
            char[] str2=line2.toCharArray();
            int count=0;
            for(int i=0;i<N;i++)
                {
                    if(str1[i]==str2[i])
                    {
                        count++;
                    }
                }
            System.out.print(N-Math.abs(count-M));
        }
    }

18.P12889 [蓝桥杯 2025 国 Java B] 情绪链路

题目描述

在数字社交媒体的浩瀚世界中，运营者小蓝负责维护一条情绪链路。这条链路由 $n$ 个用户节点依次排列而成，每个节点上记录着一个情绪值。具体地，第 $i$ 个节点的情绪值为 $a_i$，其中 $a_i$ 是一个整数，可能为正，也可能为负。

为了改善整体情绪氛围，小蓝购买了一种名为“情绪放大器”的工具。该工具允许他选择一段至少包含一个用户节点的连续区间，并将这个区间内所有用户节点的情绪值都乘以一个整数 $k$。只是，工具启动成本高昂，小蓝只能使用它一次。

现在，请你帮助小蓝计算，在经过这样一次操作后（一定要操作），所有用户节点的情绪值之和最大会是多少。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示情绪链路的长度和放大器的倍数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每个用户节点的情绪值。

输出格式

输出一行，包含一个整数，表示经过一次操作后，所有用户节点情绪值之和的最大可能值。

输入输出样例 #1

输入 #1

5 2
-1 2 -3 4 -5

输出 #1

1

说明/提示

【样例说明】

最优的做法是选择区间 $[4]$ 并使用工具。使用后这 $n$ 个用户节点的情绪值依次为 $[-1, 2, -3, 8, -5]$，总和为 $1$。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$2 \leq n \leq 10^3$，$1 \leq k \leq 10^3$，$-10^3 \leq a_i \leq 10^3$。

对于 $100\%$ 的评测用例，$2 \leq n \leq 10^5$，$1 \leq k \leq 10^5$，$-10^5 \leq a_i \leq 10^5$。

题解

找出最大子区间即可。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            int k=scan.nextInt();
            int[] a=new int[n];
            for(int i=0;i<n;i++)
                {
                    a[i]=scan.nextInt();
                }
            long sum=0;
            long max=Integer.MIN_VALUE;
            long x=Integer.MIN_VALUE;
            for(int i=0;i<n;i++)
                {
                    sum=sum+a[i];
                    max=Math.max(max+a[i],a[i]);
                    x=Math.max(max,x);
                }
            System.out.print(sum+x*(k-1));
            
        }
    }

19.P13894 [蓝桥杯 2023 省 C] 填充

题目描述

有一个长度为 $n$ 的 01 串，其中有一些位置标记为 ?，这些位置上可以任意填充 0 或者 1，请问如何填充这些位置使得这个 01 串中出现互不重叠的 00 和 11 子串最多，输出子串个数。

输入格式

输入一行包含一个字符串。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

1110?0

输出 #1

2

说明/提示

【样例说明】

如果在问号处填 $0$，则最多出现一个 $00$ 和一个 $11$：$111000$。

【评测用例规模与约定】

对于所有评测用例，$1 \leq n \leq 1000000$。

题解

只有出现三种情况的时候才会要答案++，并且跳过下一个

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            String line=scan.next();
            char[] str=line.toCharArray();
            int ans=0;
            for(int i=1;i<str.length;i++)
                {
                    if(str[i]==str[i-1])
                    {
                        ans++;
                        i++;
                        continue;
                    }
                    if(str[i]=='?')
                    {
                        ans++;
                        i++;
                        continue;
                    }
                    if(str[i-1]=='?')
                    {
                        ans++;
                        i++;
                        continue;
                    }
                }
            System.out.print(ans);
        }
    }

20.P15433 [蓝桥杯 2025 国 Python B] 灯塔

题目描述

在一片海岸线上，有 $n$ 个灯塔排成一排，从左到右编号为 $1$ 到 $n$。你需要点亮其中的一些灯塔以指引船只航行。给定一个长度为 $m$ 的点亮序列 $a_1, a_2, \dots, a_m$，其中第 $i$ 个操作表示尝试点亮编号为 $a_i$ 的灯塔。然而为了节约能源，如果灯塔 $a_i - 1$ 或灯塔 $a_i + 1$ 已经被点亮，则灯塔 $a_i$ 无法被点亮，该操作将被跳过。当然，同一个灯塔只会被点亮一次。

你可以从给定的点亮序列中挑选一个子序列（保持操作的相对顺序），按照子序列的顺序依次执行点亮操作。请问，最多能成功点亮多少个灯塔？

输入格式

输入的第一行包含两个正整数 $n, m$，用一个空格分隔。

第二行包含 $m$ 个正整数 $a_1, a_2, \dots, a_m$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

10 9
1 3 2 5 2 10 9 6 5

输出 #1

4

说明/提示

样例说明

其中一种方案：保留子序列 $1, 3, 5, 9$，可以点亮四个灯塔。

评测用例规模与约定

对于 $40\%$ 的评测用例，$1 \le n, m \le 5000$；

对于所有评测用例，$1 \le n, m \le 10^6$，$1 \le a_i \le n$。

题解

排序后对其进行挑选

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            int m=scan.nextInt();
            int[] a=new int[m+1];
            for(int i=1;i<=m;i++)
                {
                    a[i]=scan.nextInt();
                }
            Arrays.sort(a);
            boolean[] visited=new boolean[n+2];
            int ans=0;
            for(int i=1;i<=m;i++)
                {
                    if(!visited[a[i]-1]&&!visited[a[i]+1]&&!visited[a[i]])
                    {
                        ans++;
                        visited[a[i]]=true;
                    }
                }
            System.out.print(ans);
        }
    }

21.P8669 [蓝桥杯 2018 省 B] 乘积最大

题目描述

给定 $N$ 个整数 $A_1, A_2,\cdots, A_N$。请你从中选出 $K$ 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 $1000000009$（即 $10^9+9$）的余数。

注意，如果 $X<0$， 我们定义 $X$ 除以 $1000000009$ 的余数是 $0-((0-x)\bmod 1000000009)$。

输入格式

第一行包含两个整数 $N$ 和 $K$。

以下 $N$ 行每行一个整数 $A_i$。

输出格式

一个整数，表示答案。

输入输出样例 #1

输入 #1

5 3 
-100000   
-10000   
2   
100000  
10000

输出 #1

999100009

输入输出样例 #2

输入 #2

5 3 
-100000   
-100000   
-2   
-100000  
-100000

输出 #2

-999999829

说明/提示

对于 $40\%$ 的数据，$1\le K\le N\le 100$。

对于 $60\%$ 的数据，$1\le K \le 1000$。

对于 $100\%$ 的数据，$1\le K\le N\le 10^5$，$-10^5\le A_i\le 10^5$。

题解

先将数据进行排序，然后判断K的奇偶，如果是奇数就先把一个最大数选出来，如果这个最大数是小于0就将f设置为-1。然后开始选择。主要是数值的数据类型范围。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int N=scan.nextInt();
            int K=scan.nextInt();
            int[] a=new int[N];
            for(int i=0;i<N;i++)
                {
                    a[i]=scan.nextInt();
                }
            Arrays.sort(a);
            int f=1;
            long ans=1;
            if(K%2==1)
            {
                ans=ans*a[N-1];
                N--;
                K--;
                if(ans<0)
                {
                    f=-1;
                }
            }
            int l=0;
            int r=N-1;
            while(K!=0)
                {
                    long x=1L*a[l]*a[l+1];
                    long y=1L*a[r]*a[r-1];
                    if(x*f<=y*f)
                    {
                        ans=((y%1000000009)*ans)%1000000009;
                        r=r-2;
                    }
                    else
                    {
                        ans=((x%1000000009)*ans)%1000000009;
                        l=l+2;
                    }
                    K=K-2;
                }
            System.out.print(ans%1000000009);
        }
    }

22.P12135 [蓝桥杯 2025 省 B] 水质检测

题目描述

小明需要在一条 $2 \times n$ 的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或者左右相邻，那么这两个检测器就是互相连通的。连通具有传递性，即如果 $A$ 和 $B$ 连通，$B$ 和 $C$ 连通，那么 $A$ 和 $C$ 也连通。现在他需要在河床上增加铺设一些检测器使得所有的检测器都互相连通。他想知道最少需要增加铺设多少个检测器？

输入格式

输入共两行，表示一个 $2 \times n$ 的河床。

每行一个长度为 $n$ 的字符串，仅包含 # 和 .，其中 # 表示已经存在的检测器，. 表示空白。

输出格式

输出共 $1$ 行，一个整数表示答案。

输入输出样例 #1

输入 #1

.##.....#
.#.#.#...

输出 #1

5

说明/提示

样例说明

其中一种方案：

.###....#
.#.######

增加了 5 个检测器。

评测用例规模与约定

对于 $100\%$ 的评测用例，保证 $n \leq 1000000$。

题解

用dp来做，注意如果全部都是.的情况要特判，不然会有一个点re

代码

import java.util.*;

public class Main
    {
        static final int INF = 1_000_000_000;
        public static void main(String[] args)throws Exception
        {
            Scanner scan=new Scanner(System.in);
            String line1=scan.next();
            String line2=scan.next();
            char[] a=line1.toCharArray();
            char[] b=line2.toCharArray();

            int L=a.length;
            int R=-1;
            for(int i=0;i<a.length;i++)
                {
                    if(a[i]=='#'||b[i]=='#')
                    {
                        L=Math.min(L,i);
                        R=Math.max(R,i);
                    }
                }
            if (R == -1) 
            {
                System.out.println(0);
                return;
            }
            int dp0 = cost(a, b, L, 0);
            int dp1 = cost(a, b, L, 1);
            int dp2 = cost(a, b, L, 2);

            for (int i = L + 1; i <= R; i++) 
            {
                int c0 = cost(a, b, i, 0);
                int c1 = cost(a, b, i, 1);
                int c2 = cost(a, b, i, 2);

                int ndp0 = Math.min(dp0, dp2) + c0;
                int ndp1 = Math.min(dp1, dp2) + c1;
                int ndp2 = Math.min(Math.min(dp0, dp1), dp2) + c2;

                dp0 = ndp0;
                dp1 = ndp1;
                dp2 = ndp2;
            }

            System.out.println(Math.min(dp0, Math.min(dp1, dp2)));
        }

        static int cost(char[] a, char[] b, int i, int state) 
        {
            if (state == 0) 
            { 
                if (b[i] == '#') return INF; 
                if (a[i] == '#') return 0;
                return 1;
            }

            if (state == 1) 
            { 
                if (a[i] == '#') return INF; 
                if (b[i] == '#') return 0;
                return 1;
            }

            int cnt = 0;
            if (a[i] == '.') cnt++;
            if (b[i] == '.') cnt++;
            return cnt;
        }
    }

23.P11006 [蓝桥杯 2024 省 Python B] 纯职业小组

题目描述

在蓝桥王国，国王统治着一支由 $n$ 个小队组成的强大军队。每个小队都由相同职业的士兵组成。具体地，第 $i$ 个小队包含了 $b_i$ 名职业为 $a_i$ 的士兵。

近日，国王计划在王宫广场举行一场盛大的士兵检阅仪式，以庆祝王国的繁荣昌盛。然而，在士兵们入场的过程中，一场突如其来的风暴打乱了他们的行列，使得不同小队的士兵混杂在一起，次序乱成一团，

尽管国王无法知道每个士兵的具体职业，但为了确保仪式能顺利进行，国王打算从这些混乱的士兵中选出一部分，组成 $k$ 个“纯职业小组”进行检阅。一个“纯职业小组”定义为由 $3$ 名同职业的士兵组成的队伍。

请问，国王至少需要选择多少名士兵，才能确保这些士兵可以组成 $k$ 个“纯职业小组”？

输入格式

输入的第一行包含一个整数 $T$，表示每次输入包含 $T$ 组数据。

接下来依次描述 $T$ 组数据。

每组数据的第一行包含两个整数 $n_t$ 和 $k$ ，用一个空格分隔，表示小队的数量和要组成的纯职业小组的数量。

接下来的 $n_t$ 行，每行包含两个整数 $a_i$ 和 $b_i$，用一个空格分隔，表示第 $i$ 个小队中士兵的职业和数量。

输出格式

输出 $T$ 行，每行包含一个整数，依次表示每组数据的答案，即为了组成 $k$
个“纯职业小组”，国王至少需要选择的士兵数量。如果无论如何也无法组成 $k$ 个“纯职业小组”，则输出 $-1$。

输入输出样例 #1

输入 #1

2
3 2
1 3
2 3
3 3
3 5
1 3
2 3
3 3

输出 #1

8
-1

说明/提示

对于 $50\%$ 的评测用例，$1\le T \le 10，1 \le \sum_{t=1}^Tn_t \le 2 \times 10^3,1 \le a_i , b_i \le 10^5,1 \le k \le 10^7$。

对于所有评测用例，$1\le T \le 100，1 \le \sum_{t=1}^Tn_t \le 2 \times 10^5,1 \le a_i , b_i \le 10^9,1 \le k \le 10^{13}$。

样例解释

在第一个样例中，要想组成 $2$ 个“纯职业小组”，国王至少需要选择 $8$ 名士兵。若只选择了 $7$ 名士兵，则这 7 名士兵的职业可能为 $1, 1, 1, 2, 2, 3, 3$，无法组成 $2$ 个“纯职业小组”。

在第二个样例中，即使选择了所有士兵，也无法组成 $5$ 个“纯职业小组”，因此输出 $−1$。

题解

这题本质是把保证至少有 k 个三人组转化为，在最多只能有 k−1 个三人组的情况下，最多能选多少人，然后答案就是这个最大人数再加 1；而为了让人数尽量多、组三人组尽量少，策略是：每个职业先选最多 2 人（完全不成组），然后优先用完整的 3 人块（每次消耗 1 个组三人组额度但能多拿 3 人），最后再用剩余的 2 或 1 人补充（同样消耗 1 个组但收益更低），按3 → 2 → 1的优先级贪心分配，直到用完 k−1 次组三人组额度，就能得到最坏情况下的最大可选人数。

代码

import java.util.*;

public class Main {
    static long n, k, sum, cnt, res;
    static long[] f = new long[3];
    static HashMap<Long, Long> t = new HashMap<>();

    static void sol(Scanner sc) {
        n = sc.nextLong();
        k = sc.nextLong();
        k--; 

        sum = 0;
        cnt = 0;
        res = 0;
        f[1] = 0;
        f[2] = 0;
        t.clear();

        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            t.put(x, t.getOrDefault(x, 0L) + y);
        }

        for (long x : t.values()) {
            sum += x / 3;

            if (x <= 2) {
                res += x;
            } else {
                res += 2;
                cnt += (x - 2) / 3;
                f[(int)((x - 2) % 3)]++;
            }
        }

        if (sum < k) {
            System.out.println(-1);
            return;
        }

        cnt = Math.min(cnt, k);
        res += cnt * 3;
        k -= cnt;

        for (int i = 2; i >= 1; i--) {
            long tx = Math.min(f[i], k);
            k -= tx;
            res += tx * i;
        }

        System.out.println(res + 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            sol(sc);
        }
    }
}

24.P13888 [蓝桥杯 2023 省 Python A] 翻转

题目描述

小蓝用黑白棋的 $n$ 个棋子排成了一行，他在脑海里想象出了一个长度为 $n$ 的 01 串 $T$，他发现如果把黑棋当做 $1$，白棋当做 $0$，这一行棋子也是一个长度为 $n$ 的 01 串 $S$。

小蓝决定，如果在 $S$ 中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。也就是说，如果 $S$ 中存在子串 $101$ 或者 $010$，就可以选择将其分别变为 $111$ 和 $000$，这样的操作可以无限重复。

小蓝想知道最少翻转多少次可以把 $S$ 变成和 $T$ 一模一样。

输入格式

输入包含多组数据。

输入的第一行包含一个正整数 $D$ 表示数据组数。

后面 $2D$ 行每行包含一个 01 串，每两行为一组数据，第 $2i-1$ 行为第 $i$ 组数据的 $T_i$，第 $2i$ 行为第 $i$ 组数据的 $S_i$，$S_i$ 和 $T_i$ 长度均为 $n_i$。

输出格式

对于每组数据，输出一行包含一个整数，表示答案，如果答案不存在请输出 $-1$。

输入输出样例 #1

输入 #1

2
1000111
1010101
01000
11000

输出 #1

2
-1

说明/提示

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$1 \leq \sum \limits_{i=1}^{D} n_i \leq 10$；

对于所有评测用例，保证 $1 \leq \sum \limits_{i=1}^{D} n_i \leq 10^6$，$n_i > 0$。

题解

先判断两个字符串的首尾是否相同，如果不相同那就直接输出-1。然后再对中间部分进行逐个判断，如果有不相同的，就继续判断是否两边的也不相同，如果是就答案++，并且把当前位置翻转。如果两边不符合条件则直接跳出大循环。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int D=scan.nextInt();
            loop:for(int i=0;i<D;i++)
                {
                    String line1=scan.next();
                    char[] str1=line1.toCharArray();
                    String line2=scan.next();
                    char[] str2=line2.toCharArray();

                    if(str1[0]!=str2[0]||str1[str1.length-1]!=str2[str2.length-1])
                    {
                        System.out.println(-1);
                    }
                    else
                    {
                        int ans=0;
                        for(int j=1;j<str1.length-1;j++)
                            {
                                if(str2[j]!=str1[j])
                                {
                                    if(str2[j-1]!=str2[j]&&str2[j+1]!=str2[j])
                                    {
                                        ans++;
                                        if(str2[j]=='1')
                                        {
                                            str2[j]='0';
                                        }
                                        else
                                        {
                                            str2[j]='1';
                                        }
                                    }
                                    else
                                    {
                                        System.out.println(-1);
                                        continue loop;
                                    }
                                }

                            }
                        System.out.println(ans);
                    }
                }
        }
    }

25.P12834 [蓝桥杯 2025 国 B] 项链排列

题目描述

小蓝有 $A$ 颗蓝珠（用字符 ‘L’ 表示）和 $B$ 颗桥珠（用字符 ‘Q’ 表示），他打算用这些珠子串成一条项链。他认为项链的美感主要体现在其视觉“变化”上：当项链中任意两个相邻的珠子种类不同时，就记为产生了一次“变化”。

为了系统地研究不同排列的美感，小蓝将每一种项链的排列方式表示为一个长度为 $A + B$ 的字符串。这个字符串由 $A$ 个字符 ‘L’ 和 $B$ 个字符 ‘Q’ 组成。相应地，一条项链的“变化次数”即为这个字符串中，所有相邻且不相同的字符对的数目。

例如，如果项链的排列是“LLQLQ”，那么：

• 第 1 个 ‘L’ 和第 2 个 ‘L’ 相同，无变化。

• 第 2 个 ‘L’ 和第 3 个 ‘Q’ 不同，产生了 1 次变化。

• 第 3 个 ‘Q’ 和第 4 个 ‘L’ 不同，产生了 1 次变化。

• 第 4 个 ‘L’ 和第 5 个 ‘Q’ 不同，产生了 1 次变化。

排列“LLQLQ”的总“变化次数”为 3。

现在，小蓝希望找到一种项链排列，使其总“变化次数”恰好为 $C$。对此，请你帮他在所有满足这一条件的排列中，找出字典序最小的那一个。如果不存在任何满足条件的排列方式，则输出 -1。

输入格式

输入仅一行，包含三个整数 $A，B$ 和 $C$，分别表示蓝珠数量、桥珠数量和目标变化次数。

输出格式

输出一个长度为 $A + B$ 的字符串，表示字典序最小的满足条件的排列。如果不存在这样的排列，则输出 $-1$。

输入输出样例 #1

输入 #1

2 2 2

输出 #1

LQQL

输入输出样例 #2

输入 #2

2 2 3

输出 #2

LQLQ

输入输出样例 #3

输入 #3

2 2 4

输出 #3

-1

说明/提示

【评测用例规模与约定】

对于 20% 的评测用例，$0 \leq A, B, C \leq 100$，$1 \leq A + B \leq 200$。

对于 100% 的评测用例，$0 \leq A, B, C \leq 10^6$，$1 \leq A + B \leq 2 \times 10^6$。

题解

这道题要求变化的子串，所以先求出子串来，一共有两种情况，以L开头后交替出现，以及以Q开头后交替出现。按照字典序优先选择以L开头的。优先计算出这个子串的长度，那么剩下的就是纯L和纯Q，分别放在最前面和最后面。对于以L开头的子串，在放剩下的Q的时候要注意如果这个子串是以L结尾的那么就应该把Q放在这个子串的最后一个Q的后面，然后最后加上L。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int A=scan.nextInt();
            int B=scan.nextInt();
            int C=scan.nextInt();
            StringBuilder sb=new StringBuilder();

            if(C==0)
            {
                if(A==0&&B!=0)
                {
                    for(int i=0;i<B;i++)
                        {
                            sb.append('Q');
                        }
                    System.out.print(sb.toString());
                    return;
                }
                else if(A!=0&&B==0)
                {
                    for(int i=0;i<A;i++)
                        {
                            sb.append('L');
                        }
                    System.out.print(sb.toString());
                    return;
                }
                else
                {
                    System.out.print(-1);
                    return;
                }
                
            }

            if(A == 0 || B == 0)
            {
                System.out.print(-1);
                return;
            }
            
            int needL1=C/2+1;
            int needQ1=(C+1)/2;

            int needQ2=C/2+1;
            int needL2=(C+1)/2;

            if(A>=needL1&&B>=needQ1)
            {
                int extraL=A-needL1;
                int extraQ=B-needQ1;
                for(int i=0;i<extraL;i++)
                    {
                        sb.append('L');
                    }
                if(C%2==1)
                {
                    for(int i=0;i<C+1;i++)
                    {
                        if(i%2==0)
                        {
                            sb.append('L');
                        }
                        else
                        {
                            sb.append('Q');
                        }
                    }
                    for(int i=0;i<extraQ;i++)
                    {
                        sb.append('Q');
                    }
                }
                else
                {
                    for(int i=0;i<C;i++)
                        {
                            if(i%2==0)
                            {
                                sb.append('L');
                            }
                            else
                            {
                                sb.append('Q');
                            }
                        }
                        for(int i=0;i<extraQ;i++)
                        {
                            sb.append('Q');
                        }
                    sb.append('L');
                }
                
                System.out.print(sb.toString());
            }
            else if(A>=needL2&&B>=needQ2)
            {
                int extraQ=B-needQ2;
                for(int i=0;i<C+1;i++)
                    {
                        if(i%2==1)
                        {
                            sb.append('L');
                        }
                        else
                        {
                            sb.append('Q');
                        }
                    }
                for(int i=0;i<extraQ;i++)
                    {
                        sb.append('Q');
                    }
                System.out.print(sb.toString());
            }
            else
            {
                System.out.print(-1);
            }
        }
    }

26.P12161 [蓝桥杯 2025 省 Java B] 研发资源分配

题目描述

在蓝桥科技公司，$A$ 部门和 $B$ 部门正在竞争一种新型 AI 芯片的研发资源。

为了公平分配资源，公司设计了一个为期 $N$ 天的分配方案：

每天早上，$A$ 部门和 $B$ 部门各自提交一个需求等级（从 $1$ 到 $N$ 的整数）。提交等级较高的部门获得当天的资源，资源份额等于当天的日期编号（第 $1$ 天为 $1$ 单位，第 $2$ 天为 $2$ 单位，依次递增）。若两部门提交的等级相同，则当天资源作废，双方均无法获得资源。

每个部门必须在 $N$ 天内使用 $1$ 到 $N$ 的所有等级，且每个等级只能使用一次。

有趣的是，$A$ 部门在 $B$ 部门内部安插了一名 “间谍”，提前获知了 $B$ 部门的需求等级提交顺序，记为排列 ($P_1, P_2, \dots , P_N$)，其中 $P_i$ 表示 $B$ 部门在第 $i$ 天提交的需求等级。

现在，请你帮助 $A$ 部门分析，在已知 $B$ 部门需求等级顺序的情况下，$A$ 部门的总资源份额减去 $B$ 部门的总资源份额的差值最大可以是多少？

输入格式

第一行包含一个整数 $N$，表示分配方案的天数。

第二行包含 $N$ 个整数 $P_1, P_2, \dots , P_N$，表示 $B$ 部门在第 $1$ 天到第 $N$ 天提交的需求等级。

输出格式

输出一个整数，表示 $A$ 部门的总资源份额减去 $B$ 部门的总资源份额的最大差值。

输入输出样例 #1

输入 #1

3
1 3 2

输出 #1

2

说明/提示

样例说明

$A$ 部门可以选择排列 $[2, 1, 3]$：

• 第 $1$ 天：$A(= 2) > B(= 1)$，$A$ 获得 $1$ 单位资源；

• 第 $2$ 天：$A(= 1) < B(= 3)$，$B$ 获得 $2$ 单位资源；

• 第 $3$ 天：$A(= 3) > B(= 2)$，$A$ 获得 $3$ 单位资源。

两者的差值为 $4 - 2 = 2$。

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$1 \leq N \leq 11$，$1 \leq P_i \leq N$，$P_1, P_2, \dots , P_N$ 各不相同。

• 对于 $100\%$ 的评测用例，$1 \leq N \leq 10^5$，$1 \leq P_i \leq N$，$P_1, P_2, \dots , P_N$ 各不相同。

题解

田忌赛马，要实现A赢的天数累加减去B赢的天数累加最大

代码

import java.util.*;

public class Main {
    static class Node {
        int id;
        int x;

        Node(int id, int x) {
            this.id = id;
            this.x = x;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long ans = 0;
        long sum = (long) n * (n + 1) / 2;

        Node[] a = new Node[n];
        for (int i = 0; i < n; i++) {
            int x = scan.nextInt();
            a[i] = new Node(i + 1, x);
        }

        Arrays.sort(a, (o1, o2) -> o2.x - o1.x);

        for (int i = 0; i < n; i++) {
            sum -= a[i].id;
            ans = Math.max(ans, sum - a[i].id);
        }

        System.out.println(ans);
    }
}