算法题枚举

1.P12138 [蓝桥杯 2025 省 A] 寻找质数

题目背景

本站蓝桥杯 2025 省赛测试数据均为洛谷自造，与官方数据可能存在差异，仅供学习参考。

题目描述

如果一个正整数只能被 $1$ 和它本身两个数整除，就称为一个质数。最小的几个质数依次是 $2,3,5,7,11,13,\cdots$

请问，第 $2025$ 个质数是多少？

输入格式

无

输出格式

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

题解

直接欧拉筛法打表。

正常求素数就是循环用试除法。但是欧拉筛法，是把一个素数的倍数都去除掉。但是同一个数可能会是多个素数的倍数，就会导致被筛很多次，所以只允许用最小的来筛

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            int[] is_prime=new int[20000];
            int[] a=new int[2025];
            is_prime[0]=is_prime[1]=1;
            int i=2;
            int cnt=0;
            while(a[2024]==0)
                {
                    if(is_prime[i]==0)
                    {
                        a[cnt]=i;
                        cnt++;
                    }
                    for(int j=0;j<cnt;j++)
                        {
                            if(i*a[j]>=20000)
                            {
                                break;
                            }
                            is_prime[i*a[j]]=1;
                            if(i%a[j]==0)
                            {
                                break;
                            }
                        }
                    i++;
                }
            System.out.print(a[2024]);
        }
    }

2.P8680 [蓝桥杯 2019 省 B] 特别数的和

题目描述

小明对数位中含有 $2$、$0$、$1$、$9$ 的数字很感兴趣（不包括前导 $0$），在 $1$ 到 $40$ 中这样的数包括 $1$、$2$、$9$、$10$ 至 $32$、$39$ 和 $40$，共 $28$ 个，他们的和是 $574$。

请问，在 $1$ 到 $n$ 中，所有这样的数的和是多少？

输入格式

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

输出格式

输出一行，包含一个整数，表示满足条件的数的和。

输入输出样例 #1

输入 #1

40

输出 #1

574

说明/提示

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

对于 $50\%$ 的评测用例，$1 \le n \le 100$。

对于 $80\%$ 的评测用例，$1 \le n \le 1000$。

对于所有评测用例，$1 \le n \le 10000$。

题解

枚举判断，如果其中一位是就直接跳过当前大循环

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            int sum=0;
            loop:for(int i=0;i<=n;i++)
                {
                    int t=i;
                    while(t!=0)
                        {
                            if(t%10==2||t%10==0||t%10==1||t%10==9)
                            {
                                sum=sum+i;
                                continue loop;
                            }
                            t=t/10;
                        }
                }
            System.out.print(sum);
        }
    }

3.P10984 [蓝桥杯 2023 国 Python A/Java A] 残缺的数字

题目描述

七段码显示器是一种常见的显示数字的电子元件，它有七个发光管组成：

上图依次展示了数字 $0\sim 9$ 用七段码来显示的状态，其中灯管为黄色表示点亮，灰色表示熄灭。根据灯管的亮暗状态，我们可以用一个状态码（状态码是一个 $7$ 位的二进制数字）来表示一个七段码，令灯管点亮时状态为 $1$，灯管熄灭时状态为 $0$，按照灯管 $\rm ABCDEFG$ 的顺序标识一个七段码，则数字 $0 \sim 9$ 的状态码为：

数字	状态码	数字	状态码
$0$	$1111110$	$5$	$1011011$
$1$	$0110000$	$6$	$1011111$
$2$	$1101101$	$7$	$1110000$
$3$	$1111001$	$8$	$1111111$
$4$	$0110011$	$9$	$1111011$

小蓝有一个喜爱的数字，长度为 $18$ 位，每一位用一个七段码显示器来展示
（每位只能是 $0 \sim 9$，可以包含前导零），由于灯管故障，一些本该点亮的灯管
处于了熄灭状态。例如，对于一个长度为 $2$ 的数字来说，当两个七段码对应的
状态码分别为：$1011111$（高位）、$1110011$（低位）时，原本的数字可能会是：
$68$、$69$、$88$、$89$，有 4 种可能的值。

$18$ 个七段码显示器对应的状态码分别为：

$0000011$，$1001011$，$0000001$，$0100001$，$0101011$，$0110110$，
$1111111$，$0010110$，
$0101001$，$0010110$，
$1011100$，$0100110$，
$1010000$，$0010011$，
$0001111$，$0101101$，
$0110101$，$1101010$。

其中每个表示一个七段码对应的的状态码（按照数字的高位到低位给出）。请你
判断下小蓝喜爱的数字有多少种可能的值。

输入格式

无

输出格式

一行一个整数表示答案。

题解

算出每一个七段码的可能情况再相乘

代码

import java.util.*;

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

4.P12154 [蓝桥杯 2025 省 Java B] 逃离高塔

题目背景

本站蓝桥杯 2025 省赛测试数据均为洛谷自造，与官方数据可能存在差异，仅供学习参考。

题目描述

小蓝一觉醒来，发现自己被困在一座高耸的塔中。这座塔共有 $2025$ 层，每一层都刻有一个数字的立方值，从底层的 $1^3,2^3,3^3,\dots$ 一直到顶层的 $2025^3$，层层叠叠，直入云霄。塔顶有一扇门，门旁刻着一行字：“若想离开此塔，需找出这些立方数中个位数字为 $3$ 的数的个数。”

小蓝非常着急，因为他需要尽快离开这座塔，去参加即将到来的蓝桥杯比赛。时间紧迫，请你帮助他解答这个问题。

输入格式

无

输出格式

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

题解

纯枚举，但是要改成long来计算

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            long ans=0;
            for(long i=1;i<=2025;i++)
                {
                    long a=i*i*i;
                    if(a%10==3)
                    {
                        ans++;
                    }
                }
            System.out.print(ans);
        }
    }

5.P15430 [蓝桥杯 2025 国 Python B] 等差数列计数

题目描述

等差数列是一种常见的数学数列，其任意相邻两项的差均为固定常数，称为公差。例如，$\{1, 3, 5\}$ 是一个公差为 $2$ 的等差数列，而 $\{2, 3, 5\}$ 不是等差数列。现在，小蓝想知道，如果从 $1$ 到 $2025$ 的整数中选取 $3$ 个不同的数，那么可以组成多少种不同的、长度为 $3$ 的等差数列？两个等差数列不同当且仅当它们至少有一项不同。例如，$\{1, 2, 3\}$ 和 $\{2, 3, 4\}$ 是不同的等差数列，$\{1, 2, 3\}$ 和 $\{3, 2, 1\}$ 也是不同的等差数列。

输入格式

无

输出格式

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

题解

枚举a，a+d，a+2×d，同时还有反向的等差数列

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            int ans=0;
            for(int i=1;i*2<2025;i++)
                {
                    int cnt=2025-i*2;
                    ans=ans+cnt*2;
                }
            System.out.print(ans);
        }
    }

6.P12184 [蓝桥杯 2025 省 Python A] 偏蓝

题目背景

本站蓝桥杯 2025 省赛测试数据均为洛谷自造，与官方数据可能存在差异，仅供学习参考。

题目描述

小蓝特别喜欢蓝色。最近，小蓝学习了颜色在计算机中的一种表示方法：用三个 $0$ 至 $255$ 之间的整数（包含 $0$ 和 $255$）分别表示颜色的红、绿、蓝三个分量。

在这种颜色的表示方法下，小蓝定义了一种颜色是偏蓝的，是指蓝色分量大于红色分量，且蓝色分量大于绿色分量。例如，红、绿、蓝分别为 $10$、$10$、$11$ 时是偏蓝的；红、绿、蓝分别为 $100$、$200$、$200$ 时不是偏蓝的。

小蓝想知道，有多少种不同的颜色是偏蓝的。两种颜色如果在红、绿、蓝中至少有一个分量值不同，就认为是不同的。

输入格式

无

输出格式

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

题解

纯枚举

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            int ans=0;
            for(int i=0;i<=255;i++)
                {
                    for(int j=0;j<=255;j++)
                        {
                            for(int k=0;k<=255;k++)
                                {
                                    if(i>j&&i>k)
                                    {
                                        ans++;
                                    }
                                }
                        }
                }
            System.out.print(ans);
        }
    }

7.P12377 [蓝桥杯 2023 省 Python B] 2023

题目描述

请求出在 $12345678$ （含）至 $98765432$ （含）中，有多少个数中完全不包含 $2023$。

完全不包含 $2023$ 是指无论将这个数的哪些数位移除都不能得到 $2023$。

例如 $20322175$，$33220022$ 都完全不包含 $2023$，而 $20230415$，$20193213$ 则含有 $2023$（后者取第 $1,2,6,8$ 个数位）。

输入格式

无

输出格式

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

题解

对于每一个数进行判断，先将其转化为字符串，然后用两个指针，一个对字符串从0开始无论当前位是否相等后向后一位，另一个从2023的第一位开始，如果相等则当前指针向后一位

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            int ans=0;
            for(int i=12345678;i<=98765432;i++)
                {
                    String str=String.valueOf(i);
                    if(!contains(str))
                    {
                        ans++;
                    }
                }
            System.out.print(ans);
        }

        public static boolean contains(String str)
        {
            String target="2023";
            int index=0;
            for(int i=0;i<str.length();i++)
                {
                    if(str.charAt(i)==target.charAt(index))
                    {
                        index++;
                        if(index==4)
                        {
                            return true;
                        }
                    }
                }
            return false;
        }
    }

8.P8641 [蓝桥杯 2016 国 C] 赢球票

题目描述

某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。

主持人拿出 $N$ 张卡片（上面写着 $1 \sim N$ 的数字），打乱顺序，排成一个圆圈。

你可以从任意一张卡片开始顺时针数数 $:1,2,3 \cdots $。

如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一个卡片重新数数。

直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。

比如：

卡片排列是：$1,2,3$。

我们从 $1$ 号卡开始数，就把 $1$ 号卡拿走。再从 $2$ 号卡开始，但数的数字无法与卡片对上，

很快数字越来越大，不可能再拿走卡片了。因此这次我们只赢得了 $1$ 张球票。

还不算太坏！如果我们开始就傻傻地从 $2$ 或 $3$ 号卡片数起，那就一张卡片都拿不到了。

如果运气好，卡片排列是 $2,1,3$。

那我们可以顺利拿到所有的卡片！

本题的目标就是：已知顺时针卡片序列。

随便你从哪里开始数，求最多能赢多少张球票（就是收入囊中的卡片数字之和）

输入格式

第一行一个整数 $N(N<100)$，表示卡片数目。

第二行 $N$ 个整数，表示顺时针排列的卡片。

输出格式

一行，一个整数，表示最好情况下能赢得多少张球票。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

1

输入输出样例 #2

输入 #2

3
2 1 3

输出 #2

6

说明/提示

时限 1 秒, 256M。蓝桥杯 2016 年第七届国赛

题解

从 1 到 N 中任意选择一个数开始，从 1 顺时针计数，当计数数值与卡片上的数值也就是 1 到 N 中的数值相等时，就拿走这个卡片，从下一张卡片重新从 1 开始计数。

代码

import java.util.*;

public class Main
    {
        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();
                }
            int max=0;
            for(int i=0;i<N;i++)
                {
                    int[] t=new int[N];
                    for(int k=0;k<N;k++)
                        {
                            t[k]=a[k];
                        }
                    int sum=0;
                    int cnt=1;
                    int start=i;
                    while(true)
                        {
                            boolean flag=true;
                            for(int q=0;q<N;q++)
                                {
                                    if(t[q]>=cnt)
                                    {
                                        flag=false;
                                        break;
                                    }
                                }
                            if(flag)
                            {
                                break;
                            }
                            int j=start;
                            if(cnt==t[j])
                            {
                                sum=sum+cnt;
                                t[j]=-1;
                                cnt=1;
                            }
                            else
                            {
                                cnt++;
                            }
                            start=(start+1)%N;
                            int num=0;
                            while(t[start]==-1)
                                {
                                    start=(start+1)%N;
                                    num++;
                                    if(num>N)
                                    {
                                        break;
                                    }
                                }
                        }
                    max=Math.max(sum,max);
                }
            System.out.print(max);
        }
    }

9.P8635 [蓝桥杯 2016 省 AB] 四平方和

题目描述

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多 $4$ 个正整数的平方和。

如果把 $0$ 包括进去，就正好可以表示为 $4$ 个数的平方和。

比如：

$5=0^2+0^2+1^2+2^2$。

$7=1^2+1^2+1^2+2^2$。

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 $4$ 个数排序使得 $0 \le a \le b \le c \le d$。

并对所有的可能表示法按 $a,b,c,d$ 为联合主键升序排列，最后输出第一个表示法。

输入格式

程序输入为一个正整数 $N(N<5\times10^6)$。

输出格式

要求输出 $4$ 个非负整数，按从小到大排序，中间用空格分开。

输入输出样例 #1

输入 #1

5

输出 #1

0 0 1 2

输入输出样例 #2

输入 #2

12

输出 #2

0 2 2 2

输入输出样例 #3

输入 #3

773535

输出 #3

1 1 267 838

说明/提示

时限 3 秒, 256M。蓝桥杯 2016 年第七届省赛

蓝桥杯 2016 年省赛 A 组 H 题（B 组 H 题）。

题解

枚举前三个数字，然后最后一个数字就是n减去前三个数字的平方和再开方，如果开方后的这个数再乘方还是原来那个数，那么说明是正确的

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int N=scan.nextInt();
            for(int i=0;i<=N;i++)
                {
                    for(int j=0;i*i+j*j<=N;j++)
                        {
                             for( int k=0;i*i+j*j+k*k<=N;k++)
                                 {
                                     int t=N-i*i-j*j-k*k;
                                     int m=(int)Math.sqrt(t);
                                     if(m*m==t)
                                     {
                                         System.out.print(i+" "+j+" "+k+" "+m);
                                         return;
                                     }
                                 }
                        }
                }
        }
    }

10.P8651 [蓝桥杯 2017 省 B] 日期问题

题目描述

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在 1960 年 1 月 1 日至 2059 年 12 月 31 日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

比如 02/03/04，可能是 2002 年 03 月 04 日、2004 年 02 月 03 日或 2004 年 03 月 02 日。

给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入格式

一个日期，格式是 AA/BB/CC。($0\le A, B, C\le 9$)

输出格式

输出若干个不相同的日期，每个日期一行，格式是 yyyy-MM-dd。多个日期按从早到晚排列。

输入输出样例 #1

输入 #1

02/03/04

输出 #1

2002-03-04  
2004-02-03  
2004-03-02  

题解

要判断是否是闰年的问题，还要判断一个数字出现在日和月和年上的时候是否合理，并且是否在范围内

代码

import java.util.*;

public class Main {

    // 定义开始年份和结束年份
    static final int StartYear = 1960;
    static final int EndYear = 2059;

    // 每个月的天数
    static int[] daysOfMonth = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    // 判断是否是闰年
    public static boolean isLeapYear(int year) {
        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        String input = scanner.nextLine();
        String[] parts = input.split("/");
        int a = Integer.parseInt(parts[0]);  // 年份的后两位
        int b = Integer.parseInt(parts[1]);  // 月
        int c = Integer.parseInt(parts[2]);  // 日
        
        // 遍历所有年份
        for (int year = StartYear; year <= EndYear; ++year) {
            // 根据是否为闰年调整二月的天数
            daysOfMonth[2] = isLeapYear(year) ? 29 : 28;
            
            // 遍历月份
            for (int month = 1; month <= 12; ++month) {
                // 遍历该月的日期
                for (int day = 1; day <= daysOfMonth[month]; ++day) {
                    // 判断是否符合输入的日期格式
                    if ((a == year % 100 && b == month && c == day) || 
                        (a == month && b == day && c == year % 100) || 
                        (a == day && b == month && c == year % 100)) {
                        
                        // 输出符合条件的日期
                        System.out.printf("%d-%02d-%02d\n", year, month, day);
                    }
                }
            }
        }
    }
}

11.P9244 [蓝桥杯 2023 省 B] 子串简写

题目描述

程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n，Kubernetes（注意连字符不是字符串的一部分）简写成 K8s，Lanqiao 简写成 L5o 等。

在本题中，我们规定长度大于等于 $K$ 的字符串都可以采用这种简写方法(长度小于 $K$ 的字符串不配使用这种简写)。

给定一个字符串 $S$ 和两个字符 $c_{1}$ 和 $c_{2}$，请你计算 $S$ 有多少个以 $c_{1}$ 开头 $c_{2}$ 结尾的子串可以采用这种简写？

输入格式

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

第二行包含一个字符串 $S$ 和两个字符 $c_{1}$ 和 $c_{2}$。

输出格式

一个整数代表答案。

输入输出样例 #1

输入 #1

4
abababdb a b

输出 #1

6

说明/提示

【样例说明】

符合条件的子串如下所示，中括号内是该子串：

[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]

【评测用例规模与约定】

对于 $20 \%$ 的数据，$2 \leq K \leq|S| \leq 10^4$。

对于 $100 \%$ 的数据，$2 \leq K \leq|S| \leq 5 \times 10^{5}$。$S$ 只包含小写字母。$c_{1}$ 和 $c_{2}$ 都是小写字母。

$|S|$ 代表字符串 $S$ 的长度。

蓝桥杯 2023 省赛 B 组 G 题。

题解

要开long不然会有一个点wa。用两个指针，起始时的位置相隔K，同时后一个指针到尾时为截止条件。维护两个变量，一个变量cnt记录c1的出现的次数，即是符合条件的起始位置。然后后一个指针找c2的出现，只要出现就可以包含前面所有的c1组成一个符合要求的字符串

代码

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 c1=scan.next().charAt(0);
            char c2=scan.next().charAt(0);
            char[] str=line.toCharArray();
            int cnt=0;
            long ans=0;
            for(int i=0,j=K-1;j<str.length;i++,j++)
                {
                    if(str[i]==c1)
                    {
                        cnt++;
                    }
                    if(str[j]==c2)
                    {
                        ans=ans+cnt;
                    }
                }
            System.out.print(ans);
        }
    }

12.P11004 [蓝桥杯 2024 省 Python B] 魔法巡游

题目背景

本题题意存在很大歧义。以下为洛谷与蓝桥杯官网数据对比：

• 洛谷：仅要求存在数字 $0,2,4$ 即可共鸣；
• 蓝桥杯官网：需要两个数字存在一对的 $0,2,4$ 才能共鸣；

由于题面存在歧义，本题数据仅供参考。

题目描述

在蓝桥王国中，两位魔法使者，小蓝与小桥，肩负着维护时空秩序的使命。他们每人分别持有 $N$ 个符文石，这些石头被赋予了强大的力量，每一块上都刻
有一个介于 $1$ 到 $10^9$ 之间的数字符号。小蓝的符文石集合标记为 $s_1, s_2, \cdots , s_N$，小桥的则为 $t_1, t_2, \cdots , t_N$。

两位魔法使者的任务是通过使用符文石，在各个时空结点间巡游。每次巡游遵循这样一条法则：当小蓝使用了符文石 $s_i$ 到达新的结点后，小桥必须选用一个序号更大的符文石（即某个 $t_j$ 满足 $j > i$）前往下一个结点。同理，小桥抵达之后，小蓝需要选择一个序号 $k > j$ 的符文石 $s_k$ 继续他们的巡游。

为了成功地穿梭时空，两个连续使用的符文石上的数字符号必须有共鸣，这种共鸣只有当数字符号中至少包含一个特定的元素——星火（数字 $0$）、水波（数字 $2$）或者风语（数字 $4$）时，才会发生。例如，符号序列 $126, 552, 24, 4$ 中的每对连续符文都包含了至少一个共鸣元素，则它们是一系列成功的巡游；而如果是 $15, 51, 5$，则不成立，因为它们之间的共鸣元素不包含星火、水波或风语
中的任意一个。

小蓝总是先启程，使用他的符文石开启巡游。

你的任务是计算这对魔法使者能够执行的最长时空巡游序列的长度。这样
的序列形式为 $s_{i_1}, t_{i_2}, s_{i_3}, t_{i_4}, \cdots$，其中序列索引满足 $i_1 < i_2 < i_3 < i_4 < \cdots$，并且序列中每一对相邻的符文石都至少包含一个共鸣元素。

输入格式

输入的第一行包含一个整数 $N$，表示每位魔法使者持有的符文石数量。

第二行包含 $N$ 个整数 $s_1, s_2, \cdots , s_N$，相邻整数之间使用一个空格分隔，表示小蓝的符文石上刻有的数字符号。

第三行包含 $N$ 个整数 $t_1, t_2, \cdots , t_N$ ，相邻整数之间使用一个空格分隔，表示小桥的符文石上刻有的数字符号。

输出格式

输出一行包含一个整数，表示小蓝和小桥在遵守所有规则的情况下，最多能进行多少次时空巡游。

输入输出样例 #1

输入 #1

5
126 393 581 42 44
204 990 240 46 52

输出 #1

4

说明/提示

对于 $30\%$ 的评测用例，$1 \le N \le 10^3,1 \le s_i , t_i \le 10^5$。

对于所有评测用例，$1 \le N \le 10^5,1 ≤ s_i , t_i \le 10^9$。

样例解释

这里，数字 $2$ 作为共鸣元素连接了 $s_1$ 和 $t_3$、$s_4$ 和 $t_5$，数字 $2$、$4$ 作为共鸣元素
连接了 $t_3$ 和 $s_4$。

题解

先对获取的数据进行排序，如何对排序完的两个数组中的各个元素进行判断，是否能共鸣，然后开始轮流选择

代码

import java.util.*;

public class Main {
    static long n, cnt = 0, k = 0;
    static long[] a = new long[100010];
    static long[] b = new long[100010];

    public static boolean check(long x) {
        if (x == 0) return true;
        while (x > 0) {
            if (x % 10 == 0 || x % 10 == 2 || x % 10 == 4) {
                return true;
            }
            x /= 10;
        }
        return false;
    }

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

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

        for (long i = 1; i <= n; i++) {
            b[(int) i] = scan.nextLong();
        }

        for (long i = 1; i <= n; i++) {
            if (k == 0) {
                if (check(a[(int) i])) {
                    cnt++;
                    k = (k + 1) % 2;
                }
            } else {
                if (check(b[(int) i])) {
                    cnt++;
                    k = (k + 1) % 2;
                }
            }
        }

        System.out.println(cnt);
    }
}

13.P12210 [蓝桥杯 2023 国 Python B] 背包问题

题目描述

小蓝是一位狂热的积木爱好者，家里堆满了自己用积木组装的建筑模型。最近，有两款新出的积木组件上市，小蓝自然不会错过，他带上了自己的三个背包来到了积木商城，打算将尽可能多的积木组件带回家，每个背包都有一个固定的空间大小。小蓝只会购买这两种新出的积木组件 $A$ 和 $B$，$A$ 和 $B$ 各自会占用背包的一部分空间，但对于同一种类型的积木占用的空间是相同的。小蓝想知道自己最多能带走多少数量的积木组件。

可以认为小蓝有足够的货币，只要背包可以装下的积木他都有能力购买。商场内的积木数量也是有限制的。

输入格式

输入的第一行包含一个整数 $T$，表示有 $T$ 组独立的询问。

每一组询问由三行组成。

每组询问的第一行包含三个整数 $B_{1}, B_{2}, B_{3}$，相邻的整数之间使用一个空格分隔，表示三个背包的空间大小。

每组询问的第二行包含两个整数 $cnt_{A}, cnt_{B}$，用一个空格分隔，分别表示商场内积木组件 $A$ 和 $B$ 的总量。

每组询问的第三行包含两个整数 $V_{A}, V_{B}$，用一个空格分隔，分别表示每个积木组件 $A$ 和 $B$ 所占用的空间大小。

输出格式

输出 $T$ 行，每行包含一个整数表示答案。

输入输出样例 #1

输入 #1

3
2 2 3
1 2
1 2
3 8 3
3 4
4 2
6 8 7
10 10
5 1

输出 #1

3
5
12

说明/提示

样例说明

对于第一组询问，第一个背包装一个 $B$ 积木，无剩余空间；第二个背包装一个 $B$ 积木，无剩余空间；第三个背包装一个 $A$ 积木，剩余 $2$ 空间，但积木已经没有了；最终答案是 $3$，可以带走所有的积木。

对于第二组询问，第一个背包和第三个背包各自装一个 $B$ 组件，第二个背包装两个 $B$ 组件和一个 $A$ 组件，答案是 $5$。

对于第三组询问，第一个背包： $1 \mathrm{~A}+1 \mathrm{~B}$；第二个背包： $8 \mathrm{~B}$ ；第三个背包： $1 \mathrm{~A}+1 \mathrm{~B}$。答案是 $12$。

评测用例规模与约定

• 对于 $30 \%$ 的评测用例， $1 \leq cnt_{A}, cnt_{B} \leq 100$；
• 对于所有评测用例， $1 \leq T \leq 100$，$1 \leq B_{1}, B_{2}, B_{3} \leq 10^{9}$，$1 \leq V_{A}, V_{B} \leq 10^{9}$，$1 \leq cnt_{A}, cnt_{B} \leq 1,000$。

题解

无法证明贪心无反例，并且数据量也小就直接枚举。先枚举每个背包能放入的A的个数，然后再贪心B。枚举出来每种组合的总计，然后取最大值

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int T=scan.nextInt();
            for(int q=0;q<T;q++)
                {
                    int[] B=new int[3];
                    for(int i=0;i<3;i++)
                        {
                            B[i]=scan.nextInt();
                        }
                    int cnta=scan.nextInt();
                    int cntb=scan.nextInt();
                    int va=scan.nextInt();
                    int vb=scan.nextInt();
                    int ans=0;
                    for(int i=0;i<=cnta&&i*va<=B[0];i++)
                        {
                            int b1=Math.min(cntb,(B[0]-i*va)/vb);
                            for(int j=0;j<=cnta-i&&j*va<=B[1];j++)
                                {
                                    int b2=Math.min(cntb-b1,(B[1]-j*va)/vb);
                                    for(int k=0;k<cnta-i-j&&k*va<=B[2];k++)
                                        {
                                            int b3=Math.min(cntb-b1-b2,(B[2]-k*va)/vb);
                                            int cnt=i+j+k+b1+b2+b3;
                                            ans=Math.max(cnt,ans);    
                                        }
                                }
                        }
                    System.out.println(ans);
                }
        }
    }

14.P12242 [蓝桥杯 2023 国研究生组] 钉板上的正方形

题目描述

小蓝有一个大小为 $10 \times 10$ 钉板，如下图所示，上面等距分布着 $10 \times 10$ 个钉槽（上下/左右相邻的钉槽之间的距离均相同）。其中有一些钉槽上面有钉子，在图中用红色来进行标注，白色则表示此处没有钉子。小蓝喜欢用橡皮筋在钉子上围出正方形图案，即选择钉板上的四个钉子，将其作为正方形的四个顶点，从而把橡皮筋拉伸为一个正方形。

现在，小蓝想要知道在这个钉板上，可以围出多少种边长不同的正方形？（相同边长的正方形均视作是同一种，不用考虑正方形的位置）。图中展示了三种不同边长的正方形，其中蓝色线条表示橡皮筋。

输入格式

无

输出格式

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

题解

可以直接画图，但是容易漏判。直接四层循环枚举两个点，判断是否可行

• HashMap：这个是键值对的集合

  • put(key, value)：将键值对添加到 HashMap。
  • get(key)：通过键获取值。
  • remove(key)：移除指定的键值对。
  • containsKey(key)：判断是否包含某个键。

• HashSet：这个是不允许重复元素的集合

  • add(element)：将元素添加到 HashSet。
  • remove(element)：移除某个元素。
  • contains(element)：检查是否包含某个元素。

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            HashSet<Double> map=new HashSet<>();
            int[][] s = 
            {
            	{1,1,0,1,0,1,1,1,1,1},
            	{1,1,1,0,0,1,1,1,1,0},
            	{1,1,0,0,1,0,1,1,1,1},
            	{1,0,1,1,0,1,1,1,1,0},
            	{1,0,1,0,1,1,1,1,0,0},
            	{1,0,0,1,0,1,0,1,0,1},
            	{1,1,1,1,1,1,1,1,1,0},
            	{0,1,1,1,1,1,1,1,1,0},
            	{0,1,1,0,1,0,1,1,1,1},
                {1,0,1,0,0,1,0,1,0,0}
            };
            for(int i=0;i<10;i++)
                {
                    for(int j=0;j<10;j++)
                        {
                            if(s[i][j]==1)
                            {
                                for(int k=0;k<10;k++)
                                {
                                    for(int q=0;q<10;q++)
                                        {
                                            if(s[k][q]==1&&(k!=i||q!=j))
                                            {
                                                double b=Math.sqrt(Math.pow(i-k,2)+Math.pow(j-q,2));
                                                int x3 = i + (q - j);
                                                int y3 = j - (k - i);
                                                int x4 = k + (q - j);
                                                int y4 = q - (k - i);
                                                if (x3 >= 0 && x3 < 10 && y3 >= 0 && y3 < 10 && s[x3][y3] == 1 &&
                                    x4 >= 0 && x4 < 10 && y4 >= 0 && y4 < 10 && s[x4][y4] == 1)
                                                {
                                                    map.add(b);
                                                }
                                            }
                                        }
                                }
                            }
                            
                        }
                }
            System.out.print(map.size());
            
        }
    }

15.P12243 [蓝桥杯 2023 国研究生组] 混乘数字

题目描述

混乘数字的定义如下: 对于一个正整数 $n$，如果存在正整数 $a, b$，使得 $n = a \times b$，而且 $a$ 和 $b$ 的十进制数位中每个数字出现的次数之和与 $n$ 中对应数字出现次数相同，则称 $n$ 为混乘数字。

例如，对于正整数 $n = 126$，存在 $a = 6, b = 21$ 满足条件，因此 $126$ 是一个混乘数字。

又如，对于正整数 $n = 180225$，存在 $a = 225, b = 801$ 满足条件，因此 $180225$ 是一个混乘数字。

请你帮助计算出，$1 \sim 1000000$ (含)之间一共有多少个数字是混乘数字。

输入格式

无

输出格式

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

题解

枚举a*b，超时了

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            /*HashSet<Integer> set=new HashSet<>();
            for(int i=1;i<=1000000;i++)
                {
                    loop:for(int j=i;j<=1000000;j++)
                        {
                            if(i*j<=1000000)
                            {
                                int[] a=new int[10];
                                int t=i*j;
                                while(t!=0)
                                    {
                                        a[t%10]++;
                                        t=t/10;
                                    }
                                int ti=i;
                                int tj=j;
                                while(ti!=0)
                                    {
                                        a[ti%10]--;
                                        ti=ti/10;
                                    }
                                while(tj!=0)
                                    {
                                        a[tj%10]--;
                                        tj=tj/10;
                                    }
                                for(int k=0;k<10;k++)
                                    {
                                        if(a[k]!=0)
                                        {
                                            continue loop;
                                        }
                                    }
                                set.add(i*j);
                            }
                        }
                }
            System.out.print(set.size());*/
            System.out.print(590);
        }
    }

16.P12378 [蓝桥杯 2023 省 Python B] 硬币兑换

题目描述

小蓝手中有 $2023$ 种不同面值的硬币，这些硬币全部是新版硬币，其中第 $i(1 \leq i \leq 2023)$ 种硬币的面值为 $i$，数量也为 $i$ 个。硬币兑换机可以进行硬币兑换，兑换规则为：交给硬币兑换机两个新版硬币 $coin_1$ 和 $coin_2$，硬币兑换机会兑换成一个面值为 $coin_1 + coin_2$ 的旧版硬币。

小蓝可以用自己已有的硬币进行任意次数兑换，假设最终小蓝手中有 $K$ 种不同面值的硬币（只看面值，不看新旧）并且第 $i(1 \leq i \leq K)$ 种硬币的个数为 $sum_i$。小蓝想要使得 $\max\{sum_1, sum_2, \cdots, sum_K\}$ 的值达到最大，请你帮他计算这个值最大是多少。

注意硬币兑换机只接受新版硬币进行兑换，并且兑换出的硬币全部是旧版硬币。

输入格式

无

输出格式

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

题解

枚举每一种面值

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        long ans = 0;  
        for (int i = 1; i <= 4046; ++i) {  
            long p = 0;  
            int k = Math.min(2024, i);  
            for (int j = 1; j < k; ++j) {  
                if (i - j > 2023) continue;  
                long t;
                if (i - j == j) {
                    t = j / 2;  
                } else {
                    t = Math.min(j, i - j);  
                }
                p += t; 
            }
            p /= 2;  
            if (i <= 2023) p += i;  
            ans = Math.max(ans, p); 
        }
        System.out.println(ans); 
    }
}

17.P13876 [蓝桥杯 2023 省 Java/Python A] 特殊日期

题目描述

记一个日期为 $yy$ 年 $mm$ 月 $dd$ 日，统计从 2000 年 1 月 1 日（含）到 2000000 年 1 月 1 日（含），有多少个日期满足年份 $yy$ 是月份 $mm$ 的倍数，同时也是 $dd$ 的倍数。

当年份是 4 的倍数而不是 100 的倍数或者年份是 400 的倍数时，这一年是闰年，其他的年份都不是闰年。

输入格式

无

输出格式

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

题解

就枚举每一天，但是2000000 年 1 月 1 日这个日期也是符合条件的，所以最开始的答案的初值就设定为1

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            int[] a={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
            int[] b={31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
            int ans=1;

            for(int i=2000;i<2000000;i++)
                {
                    for(int j=1;j<=12;j++)
                        {
                            int d=0;
                            if(i%400==0||(i%4==0&&i%100!=0))
                            {
                                d=b[j-1];
                            }
                            else
                            {
                                d=a[j-1];
                            }
                            for(int k=1;k<=d;k++)
                                {
                                    if(i%j==0&&i%k==0)
                                    {
                                        ans++;
                                    }
                                }
                        }
                }
            System.out.print(ans);
        }
        
    }

18.P15432 [蓝桥杯 2025 国 Python B] 修改密码

题目描述

小蓝是蓝桥云课的忠实用户，他在平台上注册了 $n$ 个账号，每个账号的密码都是一串仅由大小写字母、数字构成的字符串。最近，蓝桥云课为了提升账户安全性，强制要求所有用户修改密码以符合新的安全策略：密码必须至少包含一个小写字母、一个大写字母和一个数字。

小蓝不想大幅修改他常用的密码，因为他已经非常习惯了。于是，他打算进行一些简单的替换操作来修改密码，以尽可能保留原密码的结构。具体来说，每次操作，他可以将密码中的大写字母 O、小写字母 o 和数字 0 做一次互相替换，即一次操作可以是以下操作之一：

• 将其中的一个大写字母 O 改成小写字母 o；
• 将其中的一个大写字母 O 改成数字 0；
• 将其中的一个小写字母 o 改成大写字母 O；
• 将其中的一个小写字母 o 改成数字 0；
• 将其中的一个数字 0 改成大写字母 O；
• 将其中的一个数字 0 改成小写字母 o。

现在，小蓝希望你帮助他计算每个账号的密码至少需要多少次替换操作才能符合新的安全策略。如果无论如何替换都无法满足新策略，则输出 $-1$，表示该密码无法通过替换操作变得有效。

输入格式

输入的第一行包含一个整数 $n$，表示小蓝的账号数量。

接下来 $n$ 行，每行包含一个仅由大小英文字母、数字构成的字符串 $S$，表示一个密码。

输出格式

输出 $n$ 行，每行包含一个整数，表示修改对应密码所需的最小操作次数。如果无法满足新策略，则输出 $-1$。

输入输出样例 #1

输入 #1

3
zxcvbn12
oooooooo
123abcABC

输出 #1

-1
2
0

说明/提示

评测用例规模与约定

对于所有评测用例，$1 \le n \le 100$，$8 \le |S| \le 16$，其中 $|S|$ 表示字符串 $S$ 的长度。

题解

统计三种类型的字符的个数以及三种可以用于替换的字符的个数

代码

import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            for(int i=0;i<n;i++)
                {
                    String line=scan.next();
                    char[] str=line.toCharArray();
                    int n0=0;
                    int cntn=0;
                    int uO=0;
                    int cntu=0;
                    int lo=0;
                    int cntl=0;
                    for(int j=0;j<str.length;j++)
                        {
                            if(Character.isDigit(str[j]))
                            {
                                if(str[j]=='0')
                                {
                                    n0++;
                                }
                                cntn++;
                            }
                            if('a'<=str[j]&&str[j]<='z')
                            {
                                if(str[j]=='o')
                                {
                                    lo++;
                                }
                                cntl++;
                            }
                            if('A'<=str[j]&&str[j]<='Z')
                            {
                                if(str[j]=='O')
                                {
                                    uO++;
                                }
                                cntu++;
                            }
                           
                            
                        }
                        cntn=cntn-n0;
                        cntu=cntu-uO;
                        cntl=cntl-lo;
                    if(cntn==0&&n0!=0)
                    {
                        cntn++;
                        n0--;
                    }
                    if(cntu==0&&uO!=0)
                    {
                        cntu++;
                        uO--;
                    }
                    if(cntl==0&&lo!=0)
                    {
                        cntl++;
                        lo--;
                    }
                        int need=0;
                        if(cntn==0)
                        {
                            need++;
                        }
                        if(cntl==0)
                        {
                            need++;
                        }
                        if(cntu==0)
                        {
                            need++;
                        }
                        int replace=n0+uO+lo;
                        if(replace<need)
                        {
                            System.out.println(-1);
                        }
                        else
                        {
                            System.out.println(need);
                        }
                }
        }
    }

19.P12869 [蓝桥杯 2025 国 Python A] 特殊整数对的数量

题目描述

我们称一对正整数 $(a, b)$ 是 “特别互素对”，如果满足以下条件：

1. $1 \leq a < b \leq 10^6$ 。
2. $a$ 与 $b$ 互素，即 $a$ 和 $b$ 的最大公约数为 $1$ 。
3. $a + b$ 是 $2025$ 的倍数。

请计算一共有多少对 $(a, b)$ 是 “特别互素对”。

输入格式

无

输出格式

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

题解

只枚举2025的倍数，而不是枚举所有的数字。但是就算这样枚举也还是会超时，在idea里也要跑很久

代码

import java.util.*;

public class Main
    {
        /*
        public static void main(String[] args)
        {
            int ans=0;
            for(int i=1;i<=987;i++)
                {
                    int sum=2025*i;
                    for(int j=1;j<=1000000;j++)
                        {
                            int a=j;
                            int b=sum-j;
                            if(gcd(a,b)==1&&a<b&&b<=1000000)
                            {
                                ans++;
                            }
                        }
                }
            System.out.print(ans);
            
        }
        public static int gcd(int x, int y) 
        {
            if(y==0)
            {
                return x;
            }
            else
            {
                return gcd(y, x % y);
            }
        }*/
        public static void main(String[] args)
        {
            System.out.print(93816892);
        }
    }

20.P12842 [蓝桥杯 2025 国 A] 土地整平计划

题目描述

小蓝作为一个二维生物快乐地生活在二维坐标系中，他最近得到了一块土地，他想把这块土地整平用于修建花园。具体来说，这块土地从左到右长度为 $n$ 格，第 $i$ 格的高度为 $h_i (i \in [1, n])$。小蓝每次可以花费代价 $w$ 将一段连续的区间 $[l, r]$ 中的土地高度都变为 $w$，其中 $l \leq r$，这段区间需要满足以下三组条件之一：

1. $l = 1$, $r < n$，且对于 $i \in [l, r]$ 有 $h_i \neq h_{r+1}$，此时代价 $w = h_{r+1}$；
2. $l > 1$, $r = n$，且对于 $i \in [l, r]$ 有 $h_i \neq h_{l-1}$，此时代价 $w = h_{l-1}$；
3. $1 < l \leq r < n$，$h_{l-1} = h_{r+1}$，且对于 $i \in [l, r]$ 有 $h_i \neq h_{l-1}$，此时代价 $w = h_{l-1} = h_{r+1}$。

小蓝希望在若干次操作之后将这块土地整平，即所有格子的高度都相等，并且花费的代价总和最小。请你帮助他计算一下最小花费。

输入格式

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

第二行包含 $n$ 个正整数 $h_1, h_2, \ldots, h_n$，相邻整数之间使用一个空格分隔。

输出格式

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

输入输出样例 #1

输入 #1

8
5 4 10 4 20 5 4 5

输出 #1

10

说明/提示

【样例说明】

选择将土地高度都变为 $5$，只需操作两次：将 $[2,5]$ 和 $[7,7]$ 的高度都变为 $5$，代价总和为 $10$。

【评测用例规模与约定】

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

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

题解

获取数组的时候同时对其进行去重的操作，去掉连续重复的部分。统计每个高度出现的次数，然后对所有可能的大小的高度计算其代价

代码

import java.util.*;

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

        int n = sc.nextInt();
        int[] h = new int[n + 1];  
        int[] a = new int[1000001]; 
        boolean[] f = new boolean[1000001]; 
        int cnt = 0;

        for (int i = 1; i <= n; i++) {
            int x = sc.nextInt();
            if (x != h[cnt]) {
                h[++cnt] = x;  
            }
        }

        if (cnt == 1) {
            System.out.println(0);
            return;
        }

        for (int i = 1; i <= cnt; i++) {
            f[h[i]] = true;
            a[h[i]]++;
        }
        a[h[1]]--;  
        a[h[cnt]]--; 

        int ans = Integer.MAX_VALUE - 1;

        for (int i = 1; i <= 1000000; i++) {
            if (!f[i]) continue;  
            ans = Math.min(ans, i * (a[i] + 1));  
        }

        System.out.println(ans);
    }
}

21.P8716 [蓝桥杯 2020 省 AB2] 回文日期

题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 yyyymmdd 的格式写成一个 $8$ 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 20200202 是“千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。

也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 $100$ 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年12 月12 日。算不上“千年一遇”，顶多算“千年两遇”。

给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入格式

输入包含一个八位整数 $N$，表示日期。

输出格式

输出两行，每行 $1$ 个八位数。第一行表示下一个回文日期，第二行表示下
一个 ABABBABA 型的回文日期。

输入输出样例 #1

输入 #1

20200202

输出 #1

20211202
21211212

说明/提示

对于所有评测用例，$10000101 \le N \le 92200229$，保证 $N$ 是一个合法日期的 $8$ 位数表示。

蓝桥杯 2020 第二轮省赛 A 组 G 题（B 组 G 题）。

题解

需要几个函数，首先检查一个日期是否合法，需要要对闰年进行判断。然后需要一个函数用于判断是否是回文日期。最后再用一个函数判断是否是abab型，先要调用函数判断是否是回文，然后再判断第一位和第三位是否相等，第二位和第四位是否相等，同时第一位和第二位不等。然后在主函数中枚举从当前数字开始的日期。

代码

import java.util.*;

public class Main
    {
        static int[] months={31,28,31,30,31,30,31,31,30,31,30,31};
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int num=scan.nextInt();
            int flag=0;
            for(int i=num+1;i<=92200229;i++)
                {
                    if(check_valid(i))
                    {
                        if(check_hui(i)&&flag==0)
                        {
                            System.out.println(i);
                            flag=1;
                        }
                        if(check_abab(i))
                        {
                            System.out.print(i);
                            return;
                        }
                    }
                }
            
        }

        public static boolean check_valid(int s)
        {
            int year=s/10000;
            int month=s%10000/100;
            int day=s%100;
            if(day==0||month<=0||month>12)
            {
                return false;
            }
            if(month!=2&&day>months[month-1])
            {
                return false;
            }
            if(month==2)
            {
                if((year%4==0&&year%100!=0)||(year%400==0))
                {
                    if(day>29)
                    {
                        return false;
                    }
                }
                else if(day>28)
                {
                    return false;
                }
            }
            return true;
        }

        public static boolean check_hui(int s)
        {
            String str=Integer.toString(s);
            char[] num=str.toCharArray();
            for(int i=0;i<4;i++)
                {
                    if(num[i]!=num[7-i])
                    {
                        return false;
                    }
                }
            return true;
        }
        public static boolean check_abab(int s)
        {
            String str=Integer.toString(s);
            char[] num=str.toCharArray();
            if(check_hui(s))
            {
                if(num[0]!=num[2]||num[1]!=num[3]||num[0]==num[1])
                {
                    return false;
                }
                return true;
            }
            return false;
        }
    }

22.P8695 [蓝桥杯 2019 国 AC] 轨道炮

题目描述

小明在玩一款战争游戏。地图上一共有 $N$ 个敌方单位，可以看作 2D 平面上的点。其中第 $i$ 个单位在 $0$ 时刻的位置是 $(X_i, Y_i)$，方向是 $D_i$ (上下左右之一, 用 U/D/L/R 表示)，速度是 $V_i$。小明的武器是轨道炮，只能使用一次，不过杀伤力巨大。小明可以选择在某个非负整数时刻释放轨道炮，轨道炮一次可以消灭在一条直线 (平行于坐标轴) 上的所有敌方单位。请你计算小明最多能消灭多少敌方单位。

输入格式

输入第一行包含一个整数 $N$。
以下 $N$ 行每行包含 $3$ 个整数 $X_i$, $Y_i$, $V_i$，以及一个大写字符 $D_i$。

输出格式

输出一个整数代表答案。

输入输出样例 #1

输入 #1

4
0 0 1 R
0 10 1 R
10 10 2 D
2 3 2 L

输出 #1

3

说明/提示

对于所有评测用例，$1 \le N \le 1000$，$-10^6 \le X_i, Y_i \le 10^6$，$0 \le V_i \le 10^6$。

蓝桥杯 2019 年国赛 A 组 H 题（C 组 J 题）

题解

难

代码

import java.io.*;
import java.util.*;

public class Main {
    static int ans;

    static void calc(int[] X, int[] vx, int n) {
        for (int i = 1; i <= n; i++) {
            HashMap<Integer, Integer> map = new HashMap<>();
            int cnt = 1; 

            for (int j = 1; j <= n; j++) {
                if (i == j) continue;

                if (vx[i] == vx[j]) {
                    if (X[i] == X[j]) {
                        cnt++;
                    }
                    continue;
                }

                int dx = X[i] - X[j];
                int dv = vx[j] - vx[i];

                if (dx % dv != 0) continue;

                int t = dx / dv;
                if (t < 0) continue;

                int val = map.getOrDefault(t, 0) + 1;
                map.put(t, val);
            }

            ans = Math.max(ans, cnt);

            for (int val : map.values()) {
                ans = Math.max(ans, val + cnt);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);

        int n = fs.nextInt();
        int[] X = new int[n + 1];
        int[] Y = new int[n + 1];
        int[] vx = new int[n + 1];
        int[] vy = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            X[i] = fs.nextInt();
            Y[i] = fs.nextInt();
            int v = fs.nextInt();
            char d = fs.nextChar();

            switch (d) {
                case 'R':
                    vx[i] = v;
                    break;
                case 'L':
                    vx[i] = -v;
                    break;
                case 'U':
                    vy[i] = v;
                    break;
                case 'D':
                    vy[i] = -v;
                    break;
            }
        }

        ans = 0;
        calc(X, vx, n);
        calc(Y, vy, n);

        System.out.println(ans);
    }

    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len == -1) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ');

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            int val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }

        char nextChar() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ');
            return (char) c;
        }
    }
}