【蓝桥杯】每日一题冲刺国赛

今日学习📃

🍭1、排他平方数

🌯2、买不到的数目

🥗3、回文日期

🍱4、约瑟夫环

🍭1、排他平方数

🎯题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小明正看着 203879203879 这个数字发呆。原来，203879 * 203879 = 41566646641203879∗203879=41566646641。这有什么神奇呢？仔细观察，203879203879 是个 66 位数，并且它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字。具有这样特点的 66 位数还有一个，请你找出它！再归纳一下筛选要求：

1. 66 位正整数；
2. 每个数位上的数字不同；
3. 其平方数的每个数位不含原数字的任何组成数位。

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

package Day_Day_work;

import java.util.HashSet;
import java.util.Set;

/**
 * @author yx
 * @date 2022-03-09 14:16
 */
/*
1、HashSet去重
2、Set.retailAll(s2)方法判断两数中是否存在有重复的数
3、注意强制类型的转换
 */
public class 排它平方数
{
    public static void main(String[] args) {
        for (int i=100000;i<1000000;i++){
            if(B(i)){
                if(i!=203879 ) System.out.println(i);
            }
        }
    }
    public static Set A(long m){//去重
        String s=""+m;
        Set h=new HashSet<>();
        for (int i=0;i<s.length();i++){
            h.add(s.charAt(i));
        }
        return h;
    }
    public static boolean B(int n){
        Set s1=A(n);
        Set s2=A((long)n*n);//强制转换成long
        if(s1.size()!=6)return false;
        s1.retainAll(s2);
        return s1.isEmpty();
    }
}

题解分析：

主要将题目拆分成两个部分：

（1）使用HashSet定义一个去重函数

（2）分别对n和n*n去重，再比较两者中是否有重复的数字

难点分析：

（1）熟练使用HashSet去重

（2）使用Set.retailAll(s2)方法判断n和n*n中是否存在有重复的数

（3）因为数据量过大，所以注意强制类型long的转换

🌯2、买不到的数目

🎯题目描述

小明开了一家糖果店。他别出心裁：把水果糖包成 4 颗一包和 7 颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是 17。大于 17 的任何数字都可以用 4 和 7 组合出来。本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入描述

输入两个正整数，表示每种包装中糖的颗数(都不多于 1000 )。

输出描述

输出一个正整数，表示最大不能买到的糖数。

不需要考虑无解的情况

输入输出样例

示例

输入

4 7

输出

17

运行限制

• 最大运行时间：3s
• 最大运行内存: 64M

🎪解法一：

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();
        System.out.println(a*b-a-b);
        
    }

🎪解法二：

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int s[] = new int[1000000];
        for (int i = 0; i < a * b; i++) {
            for (int j = 0; j < a * b; j++) {
                if (a * i + b * j >= 1000000)//超过数组范围时退出
                    break;
                s[a * i + b * j]++;
            }
        }
        int k = 0;
        for (int i = a * b - 1; i >= 0; i--)
            if (s[i] == 0) {
                k = i;
                break;
            }
        System.out.println(k);
    }
}

题解分析：

主要将题目拆分成两种解法：

（1）数论知识秒解（点击链接有证明过程）

（2）暴力求解

难点分析：

（1）数论知识证明ax+by不能表示ab-a-b

（2）最大不能组合的数的范围一定小于ab（这位博主有详细证明过程）

🥗3、回文日期

🎯题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。算不上 “千年一遇”，顶多算 “千年两遇”。给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入描述

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

对于所有评测用例，10000101 \leq N \leq 8999123110000101≤N≤89991231，保证 NN 是一个合法日期的 8 位数表示。

输出描述

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

输入输出样例

示例

输入

20200202

输出

20211202
21211212

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

package Day_Day_work;

import jdk.nashorn.internal.ir.ReturnNode;

import java.util.Scanner;

/**
 * @author yx
 * @date 2022-03-09 19:59
 */
public class 回文日期 {
    public static void main(String[] args) {
        String[] B=A();
        System.out.println(B[0]);
        System.out.println(B[1]);
    }
    public static String []A(){
        Scanner scanner = new Scanner(System.in);
        int n =scanner.nextInt();
        String A[]=new String[2];
        int ans=0;
        int ans1=0;
        for (int i=n+1;i<=89991231;i++){
            String s=""+i;
            if(i%100<=31&&((i/100)%100==1||(i/100)%100==3||(i/100)%100==5||(i/100)%100==7||(i/100)%100==8||(i/100)%100==10||(i/100)%100==12)) {
                if (s.charAt(0) == s.charAt(7) && s.charAt(1) == s.charAt(6) && s.charAt(2) == s.charAt(5) && s.charAt(3) == s.charAt(4)) {
                    ans++;
                    if (ans == 1) A[0] = s;
                    if (s.charAt(0) == s.charAt(2) && s.charAt(1) == s.charAt(3)) {
                        ans1++;
                        if (ans1 == 1) A[1] = s;
                    }
                }
            }
            if(i%100<=27&&((i/100)%100<=12)) {
                if (s.charAt(0) == s.charAt(7) && s.charAt(1) == s.charAt(6) && s.charAt(2) == s.charAt(5) && s.charAt(3) == s.charAt(4)) {
                    ans++;
                    if (ans == 1) A[0] = s;
                    if (s.charAt(0) == s.charAt(2) && s.charAt(1) == s.charAt(3)) {
                        ans1++;
                        if (ans1 == 1) A[1] = s;
                    }
                }
            }
        }
        return A;
    }
}

难点分析：

（1）首先要保证该数一定是符合年月日的（月份<=12;日子<=31）,该题不用判断闰年，因为xxxx0229对应的回文9220xxxx超出范围，所以这这题不必考虑

（2）判断1、3、5、7、8、10、12为月份最大的时候，有个31号需要注意一下

🍱4、约瑟夫环

题目描述

nn 个人的编号是 1 ~ nn，如果他们依编号按顺时针排成一个圆圈，从编号是 1 的人开始顺时针报数。（报数是从 1 报起）当报到 kk 的时候，这个人就退出游戏圈。下一个人重新从 1 开始报数。求最后剩下的人的编号。这就是著名的约瑟夫环问题。本题目就是已知 n，kn，k 的情况下，求最后剩下的人的编号。

输入描述

输入是一行，2 个空格分开的整数 n, k\ (0 < n,k < 10^7)n,k (0<n,k<107)。

输出描述

要求输出一个整数，表示最后剩下的人的编号。

输入输出样例

示例

输入

10 3

输出

4

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

int A(int n,int m)
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        p=(p+m)%i;
    }
    return p+1;
}

题解分析：

（1）博主刚开始做的时候也有点无从下手，不过看完这篇关于约瑟夫环的博客后，恍然大悟，也算是涨知识la！

💦写在最后

因为今天事情有一些多，所以更新的比较晚！

但是我们坚信：“心若有所向往，何惧道阻且长，各位有志青年，一起加油 ！”

欢迎一起交流讨论！