明天决赛,该准备的也都准备了,这一个月就是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
。



