栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

第十三届蓝桥杯javac组决赛准备

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

第十三届蓝桥杯javac组决赛准备

明天决赛,该准备的也都准备了,这一个月就是BFS+图+最短路径,然后就是刷题了,

接下来就是看状态和运气了,更新一下对于国赛的准备吧(纯个人理解,只讲思路不讲某一道题)

1.动态规划

1.1:确定dp数组,以及dp [i] 的意思

1.2:初始化dp数组

1.3往那个方向填表

前缀和:

package 刷题;

import java.util.Arrays;
import java.util.Scanner;

public class 前缀和 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int a[] = new int[N];
        int prefixSum[] = new int[N];
        for (int i=0;i

6
1 2 3 4 5 6
[1, 3, 6, 10, 15, 21]

2.DFS(深度优先搜索)

高级for ,for生成多少个分支就必须生成,DFS可以减去某些分支使其不生成,可以利用空间存储状态,低配版动态规划

斐波那契数列(space for time)

package 刷题;

import java.util.HashMap;
import java.util.Scanner;

public class 斐波那契数列 {
   static HashMap map = new HashMap<>();  //状态映射结果
    public static void main(String[] args) {
        map.put(1,1);
        map.put(2,1);
        System.out.println(DFS(new Scanner(System.in).nextInt()));
    }

    public static int DFS(int N)
    {
      if (map.containsKey(N)) return map.get(N);

      int value = DFS(N-1)+DFS(N-2);
      map.put(N,value);

      return value;
    }
}

BFS(广度优先搜索)

package 刷题;

import java.util.LinkedList;

//状态
class  Node{
    int x;
    int y;
    int step;  //层数

    public Node(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}
public class BFS {
    public static void main(String[] args) {
        //准备向量 上左下右
        int x[] = {-1,0,1,0};
        int y[] = {0,-1,0,1};
        
        LinkedList q = new LinkedList<>();
        q.offer(new Node(0,0,0));
        while (! q.isEmpty())
        {
            Node poll = q.poll();
            //把poo能去到的另外的分支构造出来依次加入队伍,构造出来的分支step = poll.step+1;
        }
       
        
    }
}

4.暴力破解

set去重,map查询,list可变数组,for的约束条件的确立,适当用250MB来打表,时间复杂度的分析,最后就是可以骗多少分

5.数学

约数定理:

对于一个数的约数个数 = Π(pi) 分解的每个质因数的指数+1

平年润年:四年一轮,百年不轮,四百年一轮

埃氏筛法与欧拉筛:对素数的倍数处理

6.图

存储:邻接矩阵,二维数组的下标代表起点和终点,值就是边权

           邻接表,list存储能到达的点,数组的下标就是起点,值就是边权

        一个空间浪费,一个不浪费

最短单源路径

package 图;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Djikstra {
    
    //很大的数
    static int INF = 100000000;

    //顶点个数,边数,起点编号
     static int N,M,start;

     //地图和最短路径集合
     static int G[][] ,d[] ;

     //查看是否已经访问
     static Boolean vis[] ;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        start = sc.nextInt();
        G = new int[N][N];
        vis = new Boolean[N];
        d = new int[N];
        
        for (int[] ints : G) {
            Arrays.fill(ints,INF);
        }

        
        for (int i=0;i 

           

。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/978205.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号