蓝桥杯·3月份刷题集训Day07

在这里插入图片描述

本篇博客旨在记录自已打卡蓝桥杯3月份刷题集训,同时会有自己的思路及代码解答希望可以给小伙伴一些帮助。本人也是算法小白,水平有限,如果文章中有什么错误之处,希望小伙伴们可以在评论区指出来,共勉💪。

文章目录

    • 集训A
      • A1、约数个数
      • A2、质数拆分
    • 集训B
      • B1、路径之谜
      • B2、分考场
    • 集训C
      • C1、修改数组
      • C2、通电
    • 最后

集训A

A1、约数个数

题目

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

1200000 有多少个约数(只计算正约数)。

运行限制:

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

解题代码:

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
      int n = 1200000;
      int count = 0;
      for (int i = 1;i <= 1200000; i++) {
        if (n % i == 0) {
          count++;
        }
      }
      System.out.println(count);
    }
}

A2、质数拆分

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

将 2019 拆分为若干个两两不同的质数之和,一共有多少种不同的方法?

注意交换顺序视为同一种方法,例如2+2017=2019 与 2017+2=2019 视为同一种方法。

运行限制:

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

解题代码:

import java.util.*;

/**
 * @Descrption  填空题  2019  国赛
 * @version 质数拆分
 * @author QIA27
 * @date 2023年4月2日 上午12:41:33
 */
public class Main {
    public static void main(String[] args) {
        int n = 2019;
        boolean[] f = new boolean[n + 1];
        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (!f[i]) {
                primes.add(i);
                for (int j = i + i; j <= n; j += i) {
                    f[j] = true;
                }
            }
        }
        long[] dp = new long[n+1];
        dp[0] = 1;
        for(int i = 0; i < primes.size(); i++){
            int a = primes.get(i);
            for(int j = n; j >= a; j--){
                dp[j] += dp[j - a];
            }
        }
        System.out.println(dp[n]);
    }
}

集训B

B1、路径之谜

题目:小明冒充 X 星球的骑士,进入了一个奇怪的城堡。

城堡里边什么都没有,只有方形石头铺成的地面。

假设城堡地面是 n×n 个方格。如下图所示。

图1

按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不能跳跃。每走到一个新方格,就要向正北方和正西方各射一箭。(城堡的西墙和北墙内各有 n 个靶子)同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?有时是可以的,比如上图中的例子。

本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)

输入格式:

第一行一个整数 N (0≤N≤20),表示地面有 N×N 个方格。

第二行 N 个整数,空格分开,表示北边的箭靶上的数字(自西向东)

第三行 N 个整数,空格分开,表示西边的箭靶上的数字(自北向南)

输出格式:

输出一行若干个整数,表示骑士路径。

为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号: 0,1,2,3 ⋯⋯

比如,上图中的方块编号为:

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

输入输出样例:

输入

4
2 4 3 4
4 3 3 3

输出

0 4 5 1 2 3 7 11 10 9 13 14 15

运行限制:

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

解题代码:

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

/**
 * @Descrption  DFS  2016  国赛
 * @version 路径之谜
 * @author QIA27
 * @date 2023年4月2日 上午1:20:29
 */
public class Main {
    static int row[];//x轴各箭靶上的箭
    static int col[];//y轴各箭靶上的箭
    static int n;
    static int flag[][];//判断有没有走过
    static int dir[][]={{0,1},{1,0},{-1,0},{0,-1}};//控制方向
    static ArrayList<Integer> path = new ArrayList<>();//记录路径
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        flag = new int[n][n];
        
        row = new int[n];
        col = new int[n];
        for(int i=0;i<n;i++){
            row[i] = sc.nextInt();
        }
        for(int i=0;i<n;i++){
            col[i] = sc.nextInt();
        }
        int k = 0;
        row[0]--;
        col[0]--;
        flag[0][0] = 1;
        path.add(0);//先存入0
        dfs(0,0);
    }
    private static void dfs(int x,int y){
        if(check(x,y)){//检查是否到达终点且各箭靶上的箭均为0
            return;
        }else{
            for(int k =0;k<4;k++){
                int nx = x +dir[k][0];
                int ny = y +dir[k][1];
                if(pd(nx,ny)) {//判断是否,下标越界、已经走过、箭靶数为负数
                    row[nx] --;
                    col[ny] --;//拔出箭
                    flag[nx][ny] = 1;//标记为1
                    path.add(ny*n +nx);//将对应路径记录
                    dfs(nx,ny);
                    path.remove(path.size()-1);//恢复,删除记录最后一个
                    flag[nx][ny] = 0;
                    row[nx] ++;
                    col[ny] ++;
                }
            }
        }
    }
    public static boolean check(int x,int y){
        if(x !=n-1 || y!=n-1){//没到终点,退出
            return false;
        }
        for(int i=0;i<n;i++){//箭靶有不为0的,退出
          if(row[i]!= 0 || col[i] != 0){
              return false;
          }
        }
        for(int i =0;i<path.size();i++){//输出路径
          System.out.print(path.get(i) +" ");
        }
        System.out.println();
        return false;//成功终止、
    }
    public static boolean pd(int x2,int y2){
        
        if(x2>=n || x2<0 || y2>=n ||y2<0){
            return false;
        }
        if(flag[x2][y2] ==1||row[x2]<=0 || col[y2]<=0){
            return false;
        }
        return true;
    }
}

B2、分考场

题目n 个人参加某项特殊考试。

为了公平,要求任何两个认识的人不能分在同一个考场。

求最少需要分几个考场才能满足条件。

输入格式:

输入格式:

第一行,一个整数 n (1≤n≤100),表示参加考试的人数。

第二行,一个整数 m,表示接下来有 m 行数据。

以下 m 行每行的格式为:两个整数 a,b,用空格分开 ( 1≤a,bn )表示第 a 个人与第 b 个人认识。

输出格式:

输出一行一个整数,表示最少分几个考场。

输入输出样例:

输入

5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

输出

4

运行限制:

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

解题代码:

测试用例:4/5

import java.util.Scanner;

/**
 * @Descrption  搜索  2017  国赛
 * @version 分考场
 * @author QIA27
 * @date 2023年4月2日 上午2:14:44
 */
public class Main {
       static int n,m,num=0,min=140;
       static boolean[][] arr; // 存储学生关系
       static int[][] con; 
    
       public static void main(String[] args){
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            m = scanner.nextInt();
            arr = new boolean[105][105];
            con = new int[105][105];
            for (int i=0; i<m; i++) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                arr[a][b]=true;
                arr[b][a]=true;
            }
            dfs(1); // 当前学生
        System.out.println(min);
    }
    public static void dfs(int s) { // 考虑的第S个学生
        if (num>min)return; // 剪枝 num 表示当前方案所需要的房间数,
        if (s>n){
            min = min>num ? num : min;
            return;
        }
        boolean flag=false;
        for (int i=1; i<=num; i++) {// 遍历当前已分配的房间,贪心的加入到已分配的房间
            flag=false;
            for (int j=1; j<=con[i][0]; j++) {
                int x = con[i][j];
                if (arr[x][s]) {
                    flag=true;
                    break;
                }
            }
            if (!flag) {// 如果可以加到i
                int ax = ++con[i][0];
                con[i][ax]= s;
                dfs(s+1);
                con[i][0]--;
            }
        } 
        // 开设一个新房间
        num++;
        con[num][++con[num][0]] = s;
        dfs(s+1);
        con[num][0]--;
        num--;
    }
}

集训C

C1、修改数组

题目:给定一个长度为 N 的数组 A = [A1,A2,⋅⋅⋅,AN],数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A*2,A3,⋅⋅⋅,*AN

当修改 Ai 时,小明会检查 A*i* 是否在 A1 ~ *Ai*−1 中出现过。如果出现过,则小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过,小明会持续给 Ai 加 1 ,直 到 Ai 没有在 A1 ~ *Ai*−1 中出现过。

当 AN 也经过上述修改之后,显然 A 数组中就没有重复的整数了。

现在给定初始的 A 数组,请你计算出最终的 A 数组。

输入格式:

第一行包含一个整数 N

第二行包含 N 个整数 A*1,A2,⋅⋅⋅,AN

其中,1≤N≤105,1≤*Ai*≤106

输出格式:

输出 N 个整数,依次是最终的 A*1,A2,⋅⋅⋅,AN

输入输出样例:

输入

5
2 1 1 3 4

输出

2 1 3 4 5

运行限制:

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

解题代码:

暴力解法 测试用例:4/10

import java.util.Scanner;

/**
 * @Descrption  并查集  2019  省赛
 * @version 修改数组
 * @author QIA27
 * @date 2023年4月2日 上午2:20:31
 */
public class Main {
    static int[] arr;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n+1];
        for (int i = 1; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 1; i < arr.length; i++) {
            find(i);
        }
        for (int i = 1; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    private static void find(int i) {
        boolean f = false;
        for (int j = 0; j < i; j++) {
            if(arr[j] == arr[i]) {
                f = true;
                break;
            }
        }
        if(f) {
            // 存在重复元素
            arr[i]++;
            find(i);
        }
    }
}

并查集

import java.util.Scanner;

public class Main{
    
    static int[] f = new int[2000000]; // 存放1~n个节点
    
    public static void main(String[] args) {
        // 输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        // 初始化f
        for (int i = 1; i < f.length; i++) {
            f[i] = i;
        }
        // 优化的部分
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
            // 将当前元素的根节点赋值给当前元素
            arr[i] = find(arr[i]);
            // 将当前元素的根节点往后移动一位
            f[arr[i]] = find(arr[i]+1);
        }
        // 输出
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    
    /**
     * 获取x的根节点
     * @param x
     * @return
     */
    static int find(int x) {
        if(f[x] == x) {
            return x;
        }
        f[x] = find(f[x]);
        return f[x];
    }
}

C2、通电

题目:2015 年,全中国实现了户户通电。作为一名电力建设者,小明正在帮助一带一路上的国家通电。

这一次,小明要帮助 n 个村庄通电,其中 1 号村庄正好可以建立一个发电站,所发的电足够所有村庄使用。

现在,这 n 个村庄之间都没有电线相连,小明主要要做的是架设电线连接这些村庄,使得所有村庄都直接或间接的与发电站相通。

小明测量了所有村庄的位置(坐标)和高度,如果要连接两个村庄,小明需要花费两个村庄之间的坐标距离加上高度差的平方,形式化描述为坐标为(x*1,y1) 高度为 ℎ1h1 的村庄与坐标为 (x2,y2) 高度为 ℎ2* 的村庄之间连接的费用为

( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 \sqrt{(x_1−x_2)^2 + (y_1−y_2)^2} (x1x2)2+(y1y2)2 +(h1h2)2

高度的计算方式与横纵坐标的计算方式不同。

由于经费有限,请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。

输入格式:

输入的第一行包含一个整数 n ,表示村庄的数量。

接下来 n 行,每个三个整数 x , y , h ,分别表示一个村庄的横、纵坐标和高度,其中第一个村庄可以建立发电站。

其中,1 ≤ n ≤ 1000,0 ≤ x,y,h ≤ 10000。

输出格式:

输出一行,包含一个实数,四舍五入保留 2 位小数,表示答案。

输入输出样例:

输入

4
1 1 3
9 9 7
8 8 6
4 5 4

输出

17.41

运行限制:

语言最大运行时间最大运行内存
C++1s256M
C1s256M
Java2s256M
Python33s256M

解题代码:

import java.util.Arrays;
import java.util.Scanner;
/**
 * @Descrption  最小生成树  2020 省模拟赛
 * @version 通电
 * @author QIA27
 * @date 2023年4月2日 上午2:28:44
 */
public class Main {

    static Scanner in = new Scanner(System.in);
    static boolean[] vis = new boolean[1005];
    static double[] dis = new double[1005];
    static double[][] e = new double[1005][1005];
    static int INF = 0x7f7f7f7f;
    static int n;//顶点数
    static int m;//边数
    static Node[] nodes = new Node[1002];
    static void init()
    {
        for(int i=0;i<n;i++)
            Arrays.fill(e[i],INF);
    }
    static void prim()
    {
        double cnt = 0.0;
        for(int i=0;i<n;i++)
        {
            dis[i] = e[0][i];//从下标为0的点开始遍历
        }
        vis[0] = true;
        for(int i=0;i<n-1;i++)
        {
            double min = INF;
            int index = -1;
            for(int j=0;j<n;j++)
            {
                if(!vis[j]&&min>dis[j])
                {
                    min = dis[j];
                    index = j;
                }
            }
            vis[index] = true;
            cnt += dis[index];
            //更新dis数组
            for(int j=0;j<n;j++)
            {
                if(!vis[j]&&dis[j]>e[index][j])
                {
                    dis[j] = e[index][j];
                }
            }
        }
        System.out.printf("%.2f",cnt);
    }
    static void getMap()
    {
        for(int i=0;i<n;i++)
        {
          nodes[i] = new Node();
          nodes[i].x = in.nextInt();
          nodes[i].y = in.nextInt();
          nodes[i].h = in.nextInt();
        }
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                double x = (nodes[i].x-nodes[j].x)*(nodes[i].x-nodes[j].x);
                double y = (nodes[i].y-nodes[j].y)*(nodes[i].y-nodes[j].y);
                double h = (nodes[i].h-nodes[j].h)*(nodes[i].h-nodes[j].h);
                double temp = Math.sqrt(x+y)+h;
                e[i][j] = temp;
                e[j][i] = e[i][j];
            }

        }

    }
    public static void main(String[] args) {
        n = in.nextInt();
        init();
        getMap();
        prim();

    }
}
class Node
{
    int x;//x坐标
    int y;//y坐标
    int h;//高度
}

最后

有帮助的话,希望可以点赞❤️+收藏⭐,谢谢各位大佬~~🙌🙌🙌

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/7082.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【C++修行之路】面向对象三大特性之多态

文章目录前言认识多态构成多态的必要条件虚函数的重写虚函数重写的两个例外final和override重载、覆盖、隐藏抽象类多态的原理单继承多继承重写了基类的虚函数没有重写基类的虚函数菱形继承和菱形虚拟继承的虚表补充补充继承与多态相关问题inline函数可以是虚函数吗&#xff1f…

ChatGPT这么火,我们能怎么办?

今天打开百度&#xff0c;看到这样一条热搜高居榜二&#xff1a;B站UP主发起停更潮&#xff0c;然后点进去了解一看&#xff0c;大体是因为最近AI创作太火&#xff0c;对高质量原创形成了巨大冲击&#xff01;记得之前看过一位UP主的分享&#xff0c;说B站UP主的年收入大体约等…

iptables防火墙详解

文章目录一、iptables概念1、防火墙基础1.1 防火墙概念1.2 Netfilter和iptables的区别2、Iptables的表、链结构2.1 规则链2.2 规则表2.3 规则表之间的顺序3、规则3.1 匹配条件3.2 处理动作二、iptables规则管理1、iptables规则操作1.1 iptables信息查询1.2 规则添加1.3 规则删除…

Ant Design Vue的汉化

Ant Design Vue的汉化 1. 引入依赖 import zhCN from "ant-design-vue/lib/locale-provider/zh_CN"; // 汉化 export default {data () {zhCN,} }2. 标签包裹需要汉化的组件 <a-config-provider :locale"zhCN"><a-table :row-selection"ro…

C++IO流

文章目录一、CIO流体系二、C标准IO流三、C文件IO流1.ifstream2.ofstream一、CIO流体系 C流是指信息从外部输入设备向计算机内部输入&#xff0c;从内存向外部输出设备输出的过程&#xff0c;这种输入输出的过程非常形象地被称为流的概念。IO流指的就是输入输出流。 我们平时对…

PerfEnforce Demonstration: Data Analytics with Performance Guarantees

PerfEnforce Demonstration: Data Analytics with Performance Guarantees Created by: ctur Date: April 2, 2023 2:54 PM Status: ready to start 实时响应式的扩展算法 实时响应式的扩展算法分为 1. 比例积分控制 2. 强化学习 比例积分控制方法 “We use a proportiona…

现在的年轻人真会玩,开发界面都这么时尚,不服老都不行了

文章目录一、你还在用传统的开发界面吗二、年轻人的界面1.动漫型2.偶像型3.提神型三、更换背景的操作第一步第二步第三步一、你还在用传统的开发界面吗 不比不知道&#xff0c;一比吓一跳&#xff0c;都2023年了&#xff0c;你还在用Pycharm的默认背景写代码吗&#xff1f;已经…

不同版本的JDK新特性

1.JDK9&#xff1a;模块化开发 模块化功能用的不是很多 2.JDK10&#xff1a;var局部变量推导 使用var的两个基本要求&#xff1a; 也用得不是很多 3.JDK11 (1)单文件程序 就是能够直接用java命令编译.java文件了&#xff0c;跳过了使用javac命令的步骤&#xff0c;对新人…

4年功能测试月薪9.5K,3个月时间成功进阶自动化,跳槽涨薪6k后我的路还很长...

前言 其实最开始我并不是互联网从业者&#xff0c;是经历了一场六个月的培训才入的行&#xff0c;这个经历仿佛就是一个遮羞布&#xff0c;不能让任何人知道&#xff0c;就算有面试的时候被问到你是不是被培训的&#xff0c;我还是不能承认这段历史。我是为了生存&#xff0c;…

AD14安装步骤

首先 得需要科学安软件&#xff0c;我相信你可以找到的。 第一步&#xff1a;解压完成之后哦&#xff0c;双击打开AltiumDesignerSetup14_3_15.exe 第二步&#xff1a;点击next 第三步&#xff1a;先点击我同意&#xff0c;在点击next 第四步&#xff1a;点击next 第五步&…

路径 Dijkstra 蓝桥杯 JAVA

目录题目描述&#xff1a;Dijkstra 算法 (朴素版)&#xff1a;用Dijkstra解决本题&#xff1a;题目描述&#xff1a; 小蓝学习了最短路径之后特别高兴&#xff0c;他定义了一个特别的图&#xff0c;希望找到图中的最短路径。 小蓝的图由2021 个结点组成&#xff0c;依次编号1 至…

TypeScript由浅到深(上篇)

目录 一、什么是TypeScript有什么特点&#xff1a; 二、TypeScript的编译环境&#xff1a; 三、TypeScript数据类型&#xff1a; 01_标识符的类型推导&#xff1a; 02_JS中的类型Array&#xff1a; 03_JS 中的类型Object&#xff1a; 04_函数的类型&#xff1a; 05_匿名…

C++游戏分析与破解方法介绍

1、C游戏简介 目前手机游戏直接用C开发的已经不多&#xff0c;使用C开发的多是早期的基于cocos2dx的游戏&#xff0c;因此我们这里就以cocos2d-x为例讲解C游戏的分析与破解方法。 Cocos2d-x是一个移动端游戏开发框架&#xff0c;可以使用C或者lua进行开发&#xff0c;也可以混…

SpringBoot事件的选取原理

有四个事件启动监听器&#xff1a; 事件1会被监听吗&#xff1f;答案不会 容器发布一个正在启动的事件 org.springframework.context.event.AbstractApplicationEventMulticaster#retrieveApplicationListeners 遍历我们注册的监听器&#xff0c;但这里有个判断条件&#xff…

众人围剿,GPT-5招惹了谁

目录千人呼吁暂停AI训练代表人物分析反对原因分析信息安全人身安全失业利益总结GPT-4 火爆全球&#xff0c;引发了人工智能大浪潮。过去的一个月&#xff0c;OpenAI、微软、谷歌加上百度不断释放王炸&#xff0c;所有人都相信&#xff0c;AI 的就是未来的生产力。俗话说&#x…

Android动画进阶

在Android中&#xff0c;实现动画的方式通常有两种&#xff1a;视图动画和属性动画。然而这两种方式只能实现一些较为简单动画&#xff0c;仅仅通过改变这些控件属性的方式实现一些复杂的动画效果是比较有难度的&#xff0c;那么我们该如何实现复杂的动画。这里介绍两种实现方式…

Android配置Jetpack-Compose环境

Android 配置 Jetpack Compose 环境 记录配置Jetpack Compose环境的一些坑~ 本文同步更新于博客&#xff1a; 链接 直接创建kotlin项目或创建java项目后再配置均可 根目录 build.gradle 配置kotlin环境构建脚本 buildscript {ext.kotlin_version 1.4.32dependencies {clas…

大模型时代,AI模型开源还能这么玩?模型空间内测邀请(含重磅福利)

‍人工智能学习与实训社区飞桨 AI Studio自2019年以来&#xff0c;持续吸纳众多开发者于平台内开源贡献、实训提升&#xff0c;分享项目经验、共享自研模型等。 随着 AI Studio 开发者规模的增长、开发者开发能力的提升&#xff0c;我们收到许多期待与建议&#xff0c;经过一段…

企业OA管理系统需具备哪些功能?

OA也就是办公自动化&#xff0c;是通过将计算机、通信等现代化技术运用到传统办公方式而形成的一种新型办公方式。OA办公管理系统能够更加高效优质的处理办公事务以及进行企业管理业务&#xff0c;实现对资源的高效利用&#xff0c;进而达到提高生产力&#xff0c;提升管理水平…

详解vue各种权限控制与管理的实现思路

一、 菜单权限 菜单权限&#xff1a;控制用户在系统中能够看到哪些菜单项菜单权限指的就是后台系统中的左侧的菜单栏&#xff0c;前端可以根据后端接口返回的权限数据结合element-ui菜单组件循环拼接而成即可&#xff0c;有什么权限就展示什么菜单通过vuex持久化插件(本地存储…
最新文章