第十一届蓝桥杯大赛决赛试题Java A组(试题解析)

2022年05月14日 阅读数:2
这篇文章主要向大家介绍第十一届蓝桥杯大赛决赛试题Java A组(试题解析),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

本专栏将会从基础开始,按部就班,天天刷一道算法题,也请你们多多支持。数据结构虽然难,但只要肯坚持,必定能学好,但愿你们都可以从中有所收获。
专栏地址: 每日一道算法题专栏 数据结构专栏
本专栏的全部代码都将更新在Gitee上,项目地址:项目地址
相关数据结构演示软件:连接地址
数据结构在线演示地址:https://visualgo.net/zh https://algorithm-visualizer.org/
若是文章知识点有错误的地方,请指正!你们一块儿学习,一块儿进步。
若是感受博主的文章还不错的话,还请关注、点赞、收藏三连支持一下博主哦html

准备好了吗
Let’s go!
java

image-20220508174119318

试题 A: 合数个数

问题描述git

一个数若是除了 1 和本身还有其余约数,则称为一个合数。web

例如:1, 2, 3 不是合数,4, 6 是合数。请问从 1 到 2020 一共有多少个合数。算法

思路解析数组

在1-2020这些数中,构成有3部分:质数、合数、既非质数亦非合数,既非质数亦非合数只有数字"1"。数据结构

参考代码svg

// 1:不能有packet
// 2: 类名必须Main, 不可修改
import java.util.Scanner;
 
public class Main {
   
    
    //判断一个数是否为合数
    public static boolean judge(int num){
   
   
        for(int i = 2; i <= Math.sqrt(num); i++){
   
   
          //有余数,则返回true
          if(num%i == 0){
   
   
            return true;
          }
        }
        return false;
    }
    
     public static void main(String[] args) {
   
   
      int count = 0;
         //1,2,3都不是合数,因此从4开始
        for(int i = 4; i <= 2020; i++){
   
   
          if(judge(i)){
   
   
            count++;
          }
        }
        System.out.println(count);
    }
}

试题 B: 含2天数

问题描述工具

小蓝特别喜欢 2,今年是公元 2020 年,他特别高兴,由于天天日历上均可以看到 2。学习

若是日历中只显示年月日,请问从公元 1900 年 1 月 1 日到公元 9999 年 12月 31 日,一共有多少天日历上包含 2。

即有多少天中年月日的数位中包含数字 2。

思路解析

  1. 区分闰年和平年

闰年的判断:
①整百年数除以400,无余为闰,有余为平
②非整百年数除以4,无余为闰,有余为平

  1. 依次按照判断哪些年份、月份、号数含有2
  1. 若年份中含有2,则直接加上该年总的天数(注意平年和闰年2月天数不一样)
  2. 若年份中不含有2,实际只需判断2月和12月一共有多少天(注意平年和闰年2月天数不一样),其中12月一共有31天。
  3. 若年份中不含有2,且月份中不含有2,即判断一、三、四、五、六、七、八、九、十、11这10个月中的号数一共有多少天含有2,这10个月的一共含有2的天数是固定的,即10*12天 = 120天。

参考代码

import java.util.Scanner;


public class Main {
   
   
    //判断年份y中是否含有2,如190二、2221都含有2
    public static boolean isInclude2(int year){
   
   
        while(year!=0){
   
   
            if(year%10 == 2){
   
   
                return true;
            }
            year /= 10;
        }
        return false;
    }

    //判断某年是否为闰年
    public static boolean isLeap(int y){
   
   

        //整百年数除以400,无余为闰,有余为平
        if((y%100==0) && (y%400==0)){
   
   
            return true;
        }
        //非整百年数除以4,无余为闰,有余为平
        if((y%100!=0) && (y%4==0)){
   
   
            return true;
        }

        return false;
    }

    public static void main(String[] args) {
   
   
        int startYear = 1900;   //起始年份
        int endYear = 9999;     //结束年份
        int numOneYear = 0;     //记录某年中含有2的天数
        int totals = 0;         //记录总的含有2的天数
        int numTenMonths = 120; //一、三、四、五、六、七、八、九、十、11这10个月含有2的天数
        int num12Month = 31;    //12月含有的天数

        for(int y=startYear; y<=endYear; y++){
   
   

            //判断该年份是否含有2
            if(isInclude2(y)) {
   
   

                //判断是闰年仍是平年
                if(isLeap(y)) numOneYear = 366;
                else numOneYear = 365;
            }else {
   
   

                if(isLeap(y)){
   
   

                    //是闰年则2月份为29天
                    numOneYear = num12Month + numTenMonths + 29;
                }else{
   
   

                    //是平年则2月份为28天
                    numOneYear = num12Month + numTenMonths + 28;
                }
            }
            totals += numOneYear;
        }
        System.out.println(totals);
    }
}

试题C:本质上升序列

问题描述

小蓝特别喜欢单调递增的事物。
在一个字符串中,若是取出若干个字符,将这些字符按照在字符串中的顺序排列后是单调递增的,则成为这个字符串中的一个单调递增子序列。
例如,在字符串 lanqiao 中,若是取出字符 n 和 q,则 nq 组成一个单调递增子序列。相似的单调递增子序列还有 lnq、i、ano 等等。
小蓝发现,有些子序列虽然位置不一样,可是字符序列是同样的,例如取第二个字符和最后一个字符能够取到 ao,取最后两个字符也能够取到 ao。小蓝认为他们并无本质不一样。
对于一个字符串,小蓝想知道,本质不一样的递增子序列有多少个?
例如,对于字符串 lanqiao,本质不一样的递增子序列有 21 个。它们分别
是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、
anq、lno、ano、aio。
请问对于如下字符串

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

本质不一样的递增子序列有多少个?

思路解析

设str为题目中的目标字符串,定义dp[i]为以str[i]为结尾时的递增子序列的个数。由于j<i,因此遍历j=0~i-1,有以下讨论:

  1. str[j] < str[i],此时dp[i]=dp[i]+dp[j]
  2. str[j] == str[i],此时dp[i]=dp[i]-dp[j]
  3. str[j] > str[i],此时是降序,不考虑

为了观察方便,就以数字二、一、三、八、五、七、四、5为例:

str dp[i] dp的值 递增子序列
2 dp[0] 1 2
1 dp[1] 1 1
3 dp[2] 3 3, 23, 13
8 dp[3] 6 8, 28, 18, 38, 238, 138
5 dp[4] 6 5, 25, 15, 35, 235, 135
7 dp[5] 12 7, 27, 17, 37, 237, 137, 57, 257, 157, 357, 2357, 1357
4 dp[6] 6 4, 24, 14, 34, 234, 134
5 dp[7] 6 5, 25, 15, 35, 235, 135, 45, 245, 145, 345, 2345, 1345

由上面的表格可知,当str[j]=str[i]时,会出现重复的子序列,此时就要减去这一部分,也就是1. str[j] < str[i],此时dp[i]=dp[i]+dp[j]的讨论。

参考代码

import java.util.Scanner;


public class Main {
   
   

    public static void main(String[] args) {
   
   
        String str = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
        int result = 0;
        int[] dp = new int[str.length()];
        for(int i=0; i<str.length(); i++)
            dp[i]=1;

        for(int i=0; i<str.length(); i++){
   
   
            for(int j=0; j<i; j++){
   
   
                if(str.charAt(j) < str.charAt(i)){
   
   
                    dp[i] += dp[j];
                }
                else if(str.charAt(j) == str.charAt(i)){
   
   
                    dp[i] -= dp[j];
                }
            }
        }


        for(int i=0; i<str.length(); i++){
   
   
            result += dp[i];
        }
        System.out.println(result);
    }
}

试题D:咫尺天涯

问题描述

image-20220508174958394

image-20220508175013681

image-20220508175433003

思路解析

首先,若是经过暴力打表,而后将全部相邻点差值的和累加起来,固然是不现实的。想一想空间复杂度和时间复杂度就明白了。这里咱们可以很容易获得空间复杂度是 O ( ( 3 n ) 2 ) O((3^n)^2) O((3n)2) ,估算一下当 n = 14 n=14 n=14时,内存至少须要 170445GB,因此用暴力的方式是不现实的。

这里咱们将每个n阶的图都当作一阶的,也就是说把每一个n阶的图当作9个n-1阶的图,就转化成了一阶跟二阶的关系,根据二阶的和一阶的x,y之间的关系来逐层降阶。

虽然 n=14咱们作不到,可是 n 比较小的时候仍是可以处理的嘛。好比:n=1, n=2这样的。先写一个模拟出来,再找找规律看看。

请先看下面两张图,分别为 1 阶皮亚诺曲线和 2 阶皮亚诺曲线大体走向示意图。

MnTOZP18TPSHNIm+aFmeRg_thumb_6b1

yuQ3JrzlSnSezgL+XhF%Ag_thumb_6ae

咱们发如今全部的皮亚诺曲线中,大体走向只有四个方向:↗️、↖️、↘️、↙️,依次编号为1,2,3,4.

  1. ↗️
  2. ↖️
  3. ↘️
  4. ↙️

而皮亚诺曲线升阶(好比1阶变到2阶)过程,就是对基阶皮亚诺曲线进行扩展操做。好比咱们看 11 阶升阶为 22 阶就是对↗️走向扩展为 9 个走向↗️↖️↗️ ↘️↙️↘️ ↗️↖️↗️. 到这里若是都能看明白,其余对这个题目解题就颇有帮助了。咱们接下来要作的就是将四个方向扩展出来的方向列表搞出来,这个能够从二阶扩展到三阶的皮亚诺曲线中获得。

  1. ↗️ 扩展为 ↗️↖️↗️ ↘️↙️↘️ ↗️↖️↗️ 对应编号为 121 343 121
  2. ↖️ 扩展为 ↖️↗️↖️ ↙️↘️↙️ ↖️↗️↖️ 对应编号为 212 434 212
  3. ↘️ 扩展为 ↘️↙️↘️ ↗️↖️↗️ ↘️↙️↘️ 对应编号为 343 121 343
  4. ↙️ 扩展为 ↙️↘️↙️ ↖️↗️↖️ ↙️↘️↙️ 对应编号为 434 212 434

到这里接下来就变得简单了,固然还有一点须要处理,那就是各个大体行走方向怎么接上的问题,好比:先↗️走,接下来须要↖️走,可是我应该怎样让↗️结束后的那个位置接上↖️开始的位置呢?

那么咱们对于全部可能的组合进行的表示(固然并非全部的方向组合都在这个方向中的,好比↗️接下来就不多是↙️):

J41Ora9ESyuBnG7xh9tvdg_thumb_6b7

那对于大体方向与大体方向之间的链接关系咱们也获得了。

下来就是把大体方向(↗️、↖️、↘️、↙️)表示成详细的行走方向(⬆️、⬇️、⬅️、➡️)便可。

皮亚诺曲线实现

Dir.java 详细行走方向类,后面须要用到。

public class Dir {
   
   
    public int ic;
    public int jc;

    public Dir(int _ic_, int _jc_) {
   
   
        this.ic = _ic_;
        this.jc = _jc_;
    }
}

DirUtil.java 方向处理工具类,核心部分,用于升阶扩展操做,以及将大体行走方向表示成详细的行走方向。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DirUtil {
   
   
    private static final Dir UP = new Dir(1, 0);
    private static final Dir DOWN = new Dir(-1, 0);
    private static final Dir RIGHT = new Dir(0, 1);
    private static final Dir LEFT = new Dir(0, -1);


    public static Dir[] dir1 = new Dir[]{
   
   
            UP, UP, RIGHT, DOWN, DOWN, RIGHT, UP, UP
    };


    public static Dir[] dir2 = new Dir[]{
   
   
            UP, UP, LEFT, DOWN, DOWN, LEFT, UP, UP
    };


    public static Dir[] dir3 = new Dir[]{
   
   
            DOWN, DOWN, RIGHT, UP, UP, RIGHT, DOWN, DOWN
    };


    public static Dir[] dir4 = new Dir[]{
   
   
            DOWN, DOWN, LEFT, UP, UP, LEFT, DOWN, DOWN
    };

    public static Dir[] getDir(DirTester.Point s, DirTester.Point t) {
   
   
        if (s.x < t.x && s.y < t.y) return dir1;
        if (s.x < t.x && s.y > t.y) return dir2;
        if (s.x > t.x && s.y < t.y) return dir3;
        return dir4;
    }

    public static Dir[] getDirById(int __id__) {
   
   
        switch (__id__) {
   
   
            case 1:
                return dir1;
            case 2:
                return dir2;
            case 3:
                return dir3;
            case 4:
                return dir4;
        }
        return null;
    }

    // 升阶扩展操做
    public static List<Integer> expandDirGroup(List<Integer> list) {
   
   
        List<Integer> expandedList = new ArrayList<>();

        for (int item : list) {
   
   
            switch (item) {
   
   
                case 1:
                    expandedList.addAll(Arrays.asList(1, 2, 1, 3, 4, 3, 1, 2, 1));
                    break;
                case 2:
                    expandedList.addAll(Arrays.asList(2, 1, 2, 4, 3, 4, 2, 1, 2));
                    break;
                case 3:
                    expandedList.addAll(Arrays.asList(3, 4, 3, 1, 2, 1, 3, 4, 3));
                    break;
                case 4:
                    expandedList.addAll(Arrays.asList(4, 3, 4, 2, 1, 2, 4, 3, 4));
                    break;
            }
        }

        return expandedList;
    }

    // 将大体行走方向展开为完整的行走方向
    public static List<Dir> expandAsStepList(List<Integer> dirGroupList) {
   
   
        List<Dir> dirs = new ArrayList<>();

        int prevDirId = 0;

        for (int dirGroupId : dirGroupList) {
   
   
            Dir[] dirsTmp = getDirById(dirGroupId);
            switch (prevDirId * 10 + dirGroupId) {
   
   
                case 12:
                case 21:
                    dirs.add(UP);
                    break;
                case 13:
                case 31:
                    dirs.add(RIGHT);
                    break;
                case 24:
                case 42:
                    dirs.add(LEFT);
                    break;
                case 34:
                case 43:
                    dirs.add(DOWN);
                    break;
            }
            assert dirsTmp != null;
            dirs.addAll(Arrays.asList(dirsTmp));
            prevDirId = dirGroupId;
        }

        return dirs;
    }
}

HilbertCurveTester.java 则是对曲线结果进行测试了。

import java.util.*;

public class HilbertCurveTester {
   
   

    static class Point {
   
   
        public int x, y;

        public Point() {
   
   
        }

        public Point(int x, int y) {
   
   
            this.x = x;
            this.y = y;
        }
    }


    public static int[][] genMap(int level) {
   
   
        if (level < 1) {
   
   
            return null;
        }

        int mapSize = pow(3, level);
        int[][] a = new int[mapSize][mapSize];


        List<Integer> dirGroupList = new ArrayList<>();
        dirGroupList.add(1);
        for (int i = 2; i <= level; i++) {
   
   
            dirGroupList = DirUtil.expandDirGroup(dirGroupList);
        }

        List<Dir> dirList = DirUtil.expandAsStepList(dirGroupList);

        int x = 0;
        int y = 0;

        int val = 1;
        a[x][y] = val++;

        for (Dir dir : dirList) {
   
   
            x += dir.ic;
            y += dir.jc;
            a[x][y] = val++;
        }

        return a;
    }

    public static int pow(int a, int n) {
   
   
        int ans = 1;
        for (int i = 0; i < n; i++) {
   
   
            ans *= a;
        }
        return ans;
    }

    public static void display(int[][] a) {
   
   
        for (int i = a.length - 1; i >= 0; i--) {
   
   
            for (int j = 0; j < a[i].length; j++) {
   
   
                System.out.printf("%2d ", a[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
   
   
        System.out.print("[n] > ");
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] a = genMap(n);
        int sum = 0;

        assert a != null;

        display(a);
    }
}

输出结果:

[n] > 1
 3  4  9 
 2  5  8 
 1  6  7 
    
[n] > 2
21 22 27 28 33 34 75 76 81 
20 23 26 29 32 35 74 77 80 
19 24 25 30 31 36 73 78 79 
18 13 12 43 42 37 72 67 66 
17 14 11 44 41 38 71 68 65 
16 15 10 45 40 39 70 69 64 
 3  4  9 46 51 52 57 58 63 
 2  5  8 47 50 53 56 59 62 
 1  6  7 48 49 54 55 60 61 

接下来咱们就能够对生成的皮亚诺曲线进行找规律了,咱们能够将全部距离都打了出来,造成一个 (距离,个数)(距离,个数) 表示形式。好比:

[n] > 1
(1, 8)
(5, 2)
(3, 2)

与给的样例是同样的 1×8+5×2+3×2=24

[n] > 2
(1, 80)
(3, 20)
(5, 20)
(11, 6)
(13, 6)
(31, 2)
(33, 2)
(35, 2)
(37, 2)
(39, 2)
(41, 2)

这里与给的样例计算结果也是同样的。

我发现接下去打表就更长了,规律很差找了。因而我突发奇想,我想着直接把一样个数的数值都给加起来看看。

因而就有了如下关于不一样 nn 的计算式子:

1 (24)        => 1*8      + 8*2
2 (816)       => 1*80     + 8*20     + 24*6     + 216*2
3 (23496)     => 1*728    + 8*182    + 24*60    + 216*20    + 648*6    + 5832*2
4 (647520)    => 1*6560   + 8*1640   + 24*546   + 216*182   + 648*60   + 5832*20   + 17496*6   + 157464*2
5 (17601144)  => 1*59048  + 8*14762  + 24*4920  + 216*1640  + 648*546  + 5832*182  + 17496*60  + 157464*20  + 472392*6  + 4251528*2
6 (476293776) => 1*531440 + 8*132860 + 24*44286 + 216*14762 + 648*4920 + 5832*1640 + 17496*546 + 157464*182 + 472392*60 + 4251528*20  + 12754584*6 + 114791256*2

接下来就是快乐的找规律时间了。

咱们将乘法左右给拆分出来,分红两个列表 list1list2

list1
1 (24)        => 1 8
2 (816)       => 1 8 24 216
3 (23496)     => 1 8 24 216 648 5832
4 (647520)    => 1 8 24 216 648 5832 17496 157464
5 (17601144)  => 1 8 24 216 648 5832 17496 157464 472392 4251528
6 (476293776) => 1 8 24 216 648 5832 17496 157464 472392 4251528 12754584 114791256
list2
1 (24)        => 8      2
2 (816)       => 80     20     6     2
3 (23496)     => 728    182    60    20    6    2
4 (647520)    => 6560   1640   546   182   60   20   6   2
5 (17601144)  => 59048  14762  4920  1640  546  182  60  20  6  2
6 (476293776) => 531440 132860 44286 14762 4920 1640 546 182 60 20 6 2

至此,规律就变得很容易找了。

这里就不去过多赘述了,见下面的代码吧。

参考代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
   
   

    public static long pow(long a, int n) {
   
   
        long ans = 1;
        for (int i = 0; i < n; i++) {
   
   
            ans *= a;
        }
        return ans;
    }


    public static List<Long> genList1(int n) {
   
   
        if (n < 1) {
   
   
            return new ArrayList<>();
        }

        if (n == 1) {
   
   
            List<Long> result = new ArrayList<>();
            result.add(1L);
            result.add(8L);
            return result;
        }

        List<Long> prev = genList1(n - 1);
        List<Long> result = new ArrayList<>(prev);

        result.add(result.get(result.size() - 1) * 3);
        result.add(result.get(result.size() - 1) * 9);

        return result;
    }

    public static List<Long> genList2(int n) {
   
   
        if (n < 1) {
   
   
            return new ArrayList<>();
        }

        if (n == 1) {
   
   
            List<Long> result = new ArrayList<>();
            result.add(8L);
            result.add(2L);
            return result;
        }

        List<Long> prev = genList2(n - 1);
        List<Long> result = new ArrayList<>();

        result.add(pow(9, n) - 1);
        result.add(result.get(result.size()- 1) / 4L);
        result.add(prev.get(1) * 3);
        for (int i = 1; i < prev.size(); i++) {
   
   
            result.add(prev.get(i));
        }

        return result;
    }

    public static void main(String[] args) {
   
   
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<Long> list1 = genList1(n);
        List<Long> list2 = genList2(n);

        long ans = 0;
        for (int i = 0; i < n * 2; i++) {
   
   
            ans += list1.get(i) * list2.get(i);
        }

        System.out.println(ans);

    }
}

试题E:玩具蛇

问题描述

小蓝有一条玩具蛇,一共有 16 节,上面标着数字 1 至 16。每一节都是一
个正方形的形状。相邻的两节能够成直线或者成 90 度角。
小蓝还有一个 4 × 4 的方格盒子,用于存放玩具蛇,盒子的方格上依次标着
字母 A 到 P 共 16 个字母。
小蓝能够折叠本身的玩具蛇放到盒子里面。他发现,有不少种方案能够将
玩具蛇放进去。
下图给出了两种方案:

image-20220508212407579

请帮小蓝计算一下,总共有多少种不一样的方案。若是两个方案中,存在玩
具蛇的某一节放在了盒子的不一样格子里,则认为是不一样的方案。

思路解析

一、玩具蛇长度16,就假设是1~16,那1放在不一样的格子里面就是不一样的状况,因此要暴力枚举起始点1在16个格子里面的状况

二、在dfs深度搜索里面,咱们先列举不存在的状况 if(r<0 || c<0 || r>3 || c>3) ( a [ r ] [ c ] = = 1 a[r][c]==1 a[r][c]==1) //位置已经被占

三、(number>=15) 当玩具蛇放满的时候,咱们就返回1,也就是知足的状况的一种方法。

四、每个位置有上下左右四个方向放置蛇sum1= dfs(r-1,c,a,number+1) //上+dfs(r+1,c,a,number+1) //下+dfs(r,c-1,a,number+1) //左+dfs(r,c+1,a,number+1); //右

五、 a [ r ] [ c ] = 0 a[r][c]=0 a[r][c]=0; //咱们尝试走这条路就把TA置为1,咱们尝试走其余路的时候,就要把,刚刚置为1的,从新置为0

参考代码

import java.util.Scanner; 
public class DFS1 {
   
   
	static int sum=0;    //结果:sum种方法
	static int number=0; //步数
	static int a[][]=new int[4][4];  //4*4的二维数组
	static int dfs(int r,int c,int a[][],int number) {
   
    //r行c列数组a
		if(r<0 || c<0 || r>3 || c>3)
			return 0;
		if(a[r][c]==1)    //位置已经被占
			return 0;
		if(number>=15)    //放满玩具蛇
			return 1;
		a[r][c]=1;        //=1就是被占
		int sum1=0;       //每个位置有多少种可能性
		sum1= dfs(r-1,c,a,number+1)  //上
		+dfs(r+1,c,a,number+1)  //下
		+dfs(r,c-1,a,number+1)  //左
		+dfs(r,c+1,a,number+1);  //右
		a[r][c]=0;        //置回0
		return sum1;
	}
	public static void main(String[] args) {
   
   
		// TODO Auto-generated method stub
		//暴力枚举二维数组全部的位置
		for (int i = 0; i <= 3; i++) {
   
   
			for (int j = 0; j <= 3; j++) {
   
   
				sum+=dfs(i,j,a,0);
			}
		}	
		System.out.print(sum);
	}
}

试题F:游园安排

问题描述

image-20220508175050434

image-20220508175409668

思路解析

二分求最长上升子序列板子题,咱们能够发现二分求得的最长上升队列中,保存的就是当前长度最小的数字,所以咱们只须要每覆盖一个存储它们前面一个,最后递归输出。

参考代码

import java.util.Scanner;


public class Main {
   
   

    public static int N = 1000010;
    public static String[] A = new String[N];
    public static String s = new String();
    public static String ans = new String();
    public static int [] q = new int[N];
    public static int [] pre = new int[N];
    public static int cnt;

    public static void dfs(int u)
    {
   
   
        if(u==0){
   
   
            return;
        }
        dfs(pre[u]);
        ans+=A[u];
    }

    public static void init()
    {
   
   
        int len = s.length();
        for(int i=0,j=0;i<len;i++)
        {
   
   
            if(s.charAt(i)>='A'&&s.charAt(i)<='Z')
            {
   
   
                j = i;
                while(j+1<len&&s.charAt(j+1)>='a'&&s.charAt(j+1)<='z'){
   
   
                    j++;
                }
                if(j-i+1<0){
   
   
                    A[++cnt] = s.substring(i);
                }
                else{
   
   
                    A[++cnt] = s.substring(i,j+1 );
                }
                i = j;
            }
        }
    }

    public static void solve()
    {
   
   
        int len = 0;
        for(int i=1;i<=cnt;i++)
        {
   
   
            int l = 0,r = len;
            while(l<r)
            {
   
   
                int mid = l+r+1>>1;
                if(A[q[mid]].compareTo(A[i])<0) l = mid;
                else r = mid-1;
            }
            q[r+1] = i;
            pre[i] = q[r];
            len = Math.max(r+1,len);
        }
        int idx = q[len];
        dfs(idx);
        System.out.println(ans);
    }


    public static void main(String[] args) {
   
   
        Scanner sc = new Scanner(System.in);//WoAiLanQiaoBei
        s = sc.nextLine();
        init();
        solve();
    }
}

试题G:画廊

问题描述

image-20220508175115961

image-20220508175130016

思路解析

本题是一个dp的题目,思路其实就是定义一个三维的数组,记录状态

d p [ i ] [ j ] dp[i][j] dp[i][j]表示处理完左边第1幅画和右边第j幅画所走的最小路程,可是咱们没法知道如今究竟是在是在左边仍是在右边,因此咱们还须要增长一维数组表明如今如今到达的是左边仍是右边,用0表示在左边,用1表示在右边,这样就能够肯定状态

假设咱们如今须要到达左边那么如今有两种方法到达,一种是前一个状态在左边,另外一种是前一个状态在右边,那么咱们就能够写出状态转移方程:

d p [ i ] [ j ] [ 0 ] = M a t h . m i n ( d p [ i ] [ j ] [ 0 ] , M a t h . m i n ( d p [ i − 1 ] [ j ] [ 0 ] + l e f t [ i ] − l e f t [ i − 1 ] , d p [ i − 1 ] [ j ] [ 1 ] + j s ( l e f t [ i ] , r i g h t [ j ] , l ) ) ) ; dp[i][j][0]=Math.min(dp[i][j][0],Math.min(dp[i-1][j][0]+left[i]-left[i-1], dp[i-1][j][1]+js(left[i],right[j],l))); dp[i][j][0]=Math.min(dp[i][j][0],Math.min(dp[i1][j][0]+left[i]left[i1],dp[i1][j][1]+js(left[i],right[j],l)));

为什么是i-1而不能是j-1的缘由是由于,0表示如今到达点是i也就是说在以前状态i尚未到达,因此用i-1,而不是j-1

到达点在右边同理能够写出状态转移方程

参考代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {
   
   

	public static void main(String[] args) throws IOException {
   
   
		StreamTokenizer x=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out=new PrintWriter(System.out);
		x.nextToken();
		int n=(int)x.nval;
		x.nextToken();
		int m=(int)x.nval;
		x.nextToken();
		int k=(int)x.nval;
		x.nextToken();
		int l=(int)x.nval;
		int INF = 0x3f3f3f3f;
		int left[]=new int[n+1];
		int right[]=new int[m+1];
		for(int i=1;i<=n;i++) {
   
   
			x.nextToken();
			left[i]=(int)x.nval;
		}
		for(int i=1;i<=m;i++) {
   
   
			x.nextToken();
			right[i]=(int)x.nval;
		}
		double dp[][][]=new double[n+1][m+1][2];
		double pd=(double)l/2;
		double a=js(0,left[1],pd);
		double b=js(0,right[1],pd);
		for(int i=0;i<=n;i++)//初始化,所有置为最大
			for(int j=0;j<=m;j++)
				Arrays.fill(dp[i][j], INF);
		dp[1][0][0]=a;
		dp[0][1][1]=b;
		/*for(int i=1;i<=n;i++) {
			dp[i][0][0]=a+left[i]-left[1];
			dp[i][0][1]=INF;
		}
		for(int i=1;i<=m;i++) {
			dp[0][i][0]=INF;
			dp[0][i][1]=b+right[i]-right[1];
		}*/
		for(int i=0;i<=n;i++) {
   
   
			for(int j=0;j<=m;j++) {
   
   
				if(i!=0)dp[i][j][0]=Math.min(dp[i][j][0],Math.min(dp[i-1][j][0]+left[i]-left[i-1], dp[i-1][j][1]+js(left[i],right[j],l)));
				if(j!=0)dp[i][j][1]=Math.min(dp[i][j][1],Math.min(dp[i][j-1][0]+js(left[i],right[j],l), dp[i][j-1][1]+right[j]-right[j-1]));
			}
		}
		out.printf("%.2f\n", Math.min(dp[n][m][0]+js(k,left[n],pd), dp[n][m][1]+js(k,right[m],pd)));//最后还要到达画廊中间别忘了
		out.flush();
	}
	public static double js(double a,double b,double h) {
   
   
		a=Math.abs(a-b);
		return Math.sqrt(a*a+h*h);
	}
}

试题:奇偶覆盖

问题描述

在平面内有一些矩形,它们的两条边都平行于坐标轴。。。

image-20220508175200705

image-20220508175211341

思路解析

//待补充

参考代码

//待补充

试题I:补给

问题描述

image-20220508175226327

image-20220508175238912

思路解析

状压DP + 最短路径:

w[i][j]:从村庄 i 到村庄 j 之间的最短距离;
f[i][j]:从村庄 0 走到村庄 j ,且通过通过村庄的状态为 i 的最小飞行距离(将 1 映射成 0,以此类推);

参考代码

import javafx.util.Pair;

import java.math.BigDecimal;
import java.text.DecimalFormat;
import java.util.Scanner;

class Node{
   
   
    int first;
    int second;
}

class Solution{
   
   
    int n = 200;
    int INF = 100000000;
    Node[] p = new Node[n];
   double[][] w = new double[n][n];
   double[][] f = new double[n][n];

    public Solution() {
   
   
        for(int i=0;i<n;i++){
   
   
            p[i] = new Node();
        }
    }

    double get_distance(int i, int j) {
   
   

        int x = p[i].first - p[j].first;
        int y = p[i].second - p[j].second;
        return Math.sqrt(x * x + y * y);
    }

    void solve(){
   
   
        Scanner sc = new Scanner(System.in);
        int n,d;
        n = sc.nextInt();
        d = sc.nextInt();
        for (int i = 0; i < n; i++) {
   
   
            int first = sc.nextInt();
            int second = sc.nextInt();
            p[i].first = first;
            p[i].second = second;
        }

        for (int i = 0; i < n; i ++)
            for (int j = i + 1; j < n; j ++)
            {
   
   
                w[i][j] = w[j][i] = get_distance(i, j);
                if(w[i][j] > d) {
   
   
                    w[i][j] = w[j][i] = INF;
                }
            }

        for (int k = 0; k < n; k ++){
   
   
            for (int i = 0; i < n; i ++){
   
   
                for (int j = 0; j < n; j ++){
   
   
                    w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);
                }
            }

        }


        for (int i = 0; i < 1 << n; i ++){
   
   
            for (int j = 0; j < n; j ++){
   
   
                f[i][j] = INF;
            }
        }

        f[1][0] = 0;
        for (int i = 0; i < 1 << n; i ++){
   
   
            for (int j = 0; j < n; j ++){
   
   
                if((i >> j & 1) !=0){
   
   
                    for (int k = 0; k < n; k ++){
   
   
                        if(((i - (1 << j)) >> k & 1) != 0){
   
   
                            f[i][j] = Math.min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                        }
                    }

                }

            }

        }


        double ans = INF;
        for (int i = 1; i < n; i ++){
   
   
            ans = Math.min(ans, f[(1 << n) - 1][i] + w[i][0]);
        }

        DecimalFormat df = new DecimalFormat("0.00");

        System.out.println(df.format((1.0*(ans * 100)/100) ));
        
    }


}

public class Main {
   
   


    public static void main(String[] args) {
   
   
        Solution solution = new Solution();
        solution.solve();
    }
}

试题J:蓝跳跳

问题描述

image-20220508175258981

image-20220508175310434

思路解析

动态规划+循环数组

参考代码

import java.util.Scanner;

public class Main {
   
   
	static int len;
	static int[][] arr;
	static int k;
	static int p;

	public static void main(String[] args) {
   
   
		Scanner sc = new Scanner(System.in);
		k = sc.nextInt();
		p = sc.nextInt();
		long L = sc.nextLong();
		sc.close();
		// 建立一个双层的循环数组,0层存没跳到p几回的方式个数,1层存跳至少p次的方式个数
		len = k + 1;
		arr = new int[len][2];
		int i;
		arr[0][1] = arr[0][0] = 1;
		for (i = 1; L-- > 0; i = (i + 1) % len) {
   
   
			int sum = 0;
			for (int j = 1; j < p; j++) {
   
   
				// 跳p次之内累加的是以前跳至少p次的方式个数。
				sum = (sum + arr[(len + i - j) % len][1]) % 20201114;
			}
			arr[i][0] = sum;
			for (int j = p; j <= k; j++) {
   
   
				// 跳至少p次时累加的是以前跳p次之内的方式个数。
				sum = (sum + arr[(len + i - j) % len][0]) % 20201114;
			}
			arr[i][1] = sum;
		}
		// for循环多移动了一次i,这里把i移回来。
		i = (len + i - 1) % len;
		System.out.println(arr[i][1]);
	}
}