【蓝桥杯算法模板题--蓝桥题库Java】
PDF下载地址：点击即可
文章目录
- ==算法模板==
- 1 排序（ArrayList，sort）
- 题目描述
- 输入描述
- 输出描述
- 输入输出样例
- 示例 1
- 运行限制
- 2 小明的彩灯（差分）
- 输入输出样例
- 示例 1
- 运行限制
- 3 绝世武功（二阶差分算法）
- 输入输出样例
- 示例 1
- 运行限制
- 4 走迷宫（动态规划dp,bfs广度优先搜索）
- 输入输出样例
- 示例 1
- 运行限制
- 5 小明的背包1（dp，01背包）
- 输入输出样例
- 示例 1
- 运行限制
- 6 小明背包2（dp，完全背包）
- 输入输出样例
- 示例 1
- 运行限制
- 7 小明的衣服（哈夫曼树）
- 输入输出样例
- 示例 1
- 运行限制
- 8 百亿富翁(单调栈)
- 输入输出样例
- 示例 1
- 运行限制
- 9 排个序（冒泡排序）
- 输入输出样例
- 示例 1
- 运行限制
- 10 解立方根（Math.cbrt(x)）(BigDecimal)
- 输入输出样例
- 示例 1
- 运行限制
- 11 回文判定（尺取法，双指针）
- 输入输出样例
- 示例 1
- 示例 2
- 运行限制
- 12 最长公共子序列（dp，LCS）
- 输入输出样例
- 示例 1
- 运行限制
- 13 蓝桥骑士（dp，LIS）
- 输入输出样例
- 示例 1
- 运行限制
- 14 小明背包3（dp，多重背包）
- 输入输出样例
- 示例 1
- 运行限制
- 15 蓝桥幼儿园（并查集）
- 输入输出样例
- 示例 1
- 运行限制
- 16 蓝桥侦探（种类并查集）
- 输入输出样例
- 示例 1
- 运行限制
- 17 期望DP
- 输入输出样例
- 示例 1
- 运行限制
- 18 最大公约数&最小公倍数（GCD&LCM）
- 输入输出样例
- 示例 1
- 运行限制
- 19 数的次幂（快速幂）
- 输入输出样例
- 示例 1
- 运行限制
- 20 快速幂
- 输入输出样例
- 示例
- 运行限制
- 21 ST线性表
- 问题描述
- 评测用例规模与约定
- 输入输出样例
- 示例 1
- 运行限制
- 22 区间最大值（ST表）
- 输入输出样例
- 示例 1
- 运行限制
- 23 美丽的区间（尺取法）
- 输入输出样例
- 示例 1
- 运行限制
- 24 三角形的面积
- 输入输出样例
- 示例 1
- 运行限制
- 25 蓝桥公园（Floyd）
- 输入输出样例
- 示例 1
- 运行限制
- 26 递增序列
- 运行限制
- 27 点和直线的关系
- 输入输出样例
- 示例 1
- 运行限制
- 28 LCIS(最大公共递增子序列)
- 输入输出样例
- 示例 1
- 运行限制
- 29 子串分值
- 输入输出样例
- 示例
- 运行限制
- ==真题训练==
- 1 枚举、模拟
- 1.1 卡片
- 1.2 数的分解
- 2 搜索
- 2.1 大胖子走迷宫
- 输出描述
- 输入输出样例
- 示例
- 运行限制
- 2.2 七段码
- 3 动态规划
- 3.1 数字三角形
- 输入输出样例
- 示例
- 运行限制
- 3.2 左孩子右兄弟
- 输入输出样例
- 示例 1
- 评测用例规模与约定
- 运行限制
- 4 数论
- 4.1 等差数列
- 输入输出样例
- 示例
- 运行限制
- 4.2 阶乘约数（约数定理）
- 5 组合数学
- 5.1 组合数问题(数位dp)
- 输入输出样例
- 示例
- 运行限制
- 6 图论
- 6.1 路径
- 6.2 出差（dijkstra）
- 样例输入
- 样例输出
- 样例说明
- 评测用例规模与约定
- 运行限制
- 7 数据结构
- 7.1 修改数组（并查集）
- 输入输出样例
- 示例
- 运行限制
- 7.2 翻转括号序列
- 输入输出样例
- 示例
- 评测用例规模与约定
- 运行限制
- 8 计算几何
- 8.1 荒岛探测
- 输入输出样例
- 示例
- 运行限制
算法模板
1 排序（ArrayList，sort）
题目描述
给定一个长度为 N 的数组 A，请你先从小到大输出它的每个元素，再从大到小输出它的每个元素。
输入描述
第一行包含一个整数 N。
第二行包含 N 个整数 a1,…,an，表示数组 A 的元素。
1≤N≤5×105，−109≤ai≤10^9。
输出描述
输出共两行，每行包含 N 个整数，表示答案。
输入输出样例
示例 1
输入
5
1 3 2 6 5
输出
1 2 3 5 6
6 5 3 2 1
运行限制
- 最大运行时间：3s
- 最大运行内存: 128M
难度: 简单 标签: sort
import java.util.Scanner;
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int len = scan.nextInt();
ArrayList<Integer> num1 = new ArrayList<>();
for(int i = 0; i<len;i++){
num1.add(scan.nextInt());
}
//由小到大
num1.sort((o1,o2)->o1-o2);
for(int i = 0;i<len;i++) {
System.out.print(num1.get(i)+" ");
}
System.out.println();
//由大到小
num1.sort((o1,o2)->o2-o1);
for(int i = 0;i<len;i++) {
System.out.print(num1.get(i)+" ");
}
scan.close();
}
}
import java.util.Scanner;
import java.util.Arrays;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int a=scan.nextInt();
int[] b = new int[a];
for(int i =0;i<b.length;i++){
b[i]=scan.nextInt();
}
Arrays.sort(b);
for(int i =0;i<b.length;i++){
System.out.print(b[i]+" ");
}
System.out.println("\t");
for(int i=b.length-1;i>=0;i--){
System.out.print(b[i]+" ");
}
scan.close();
}
}
2 小明的彩灯（差分）
算法介绍：(2条消息) 差分算法介绍_笑看江湖路6的博客-CSDN博客_差分算法
输入输出样例
示例 1
输入
5 3
2 2 2 1 5
1 3 3
4 5 5
1 1 -100
输出
0 5 5 6 10
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
难度: 简单 标签: 差分
import java.util.Scanner;
import java.util.*;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
static int N = (int)(5*10e5+10);
static long[] a=new long[N];
static long[] b=new long[N];
public static void main(String[] args) throws IOException{
//在此输入您的代码...
String[] str = cin.readLine().split(" ");
int n=Integer.parseInt(str[0]);
int q=Integer.parseInt(str[1]);
str = cin.readLine().split(" ");
a[0] = 0;
for(int i=1;i<=n;i++){
a[i]=Long.parseLong(str[i-1]);
//差分
b[i]=a[i]-a[i-1];
}
for(int i=0;i<q;i++) {
str = cin.readLine().split(" ");
int l=Integer.parseInt(str[0]);
int r=Integer.parseInt(str[1]);
long c=Long.parseLong(str[2]);
//差分算法核心：开头＋，结尾+1后减
b[l]+=c;
if(r<n)b[r+1]-=c;
}
for(int j=1;j<=n;j++) a[j]=a[j-1]+b[j];
for(int i=1;i<=n;i++){
if(a[i]<0)a[i]=0;
cout.write(a[i]+" ");
}
cout.flush();
cin.close();
cout.close();
}
}
3 绝世武功（二阶差分算法）
算法介绍：(2条消息) 二阶差分（注意数据范围）_AC-PEACE的博客-CSDN博客
输入输出样例
示例 1
输入
6 2
1 5 2 10
2 4 1 1
输出
33
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
难度: 简单 标签: 二阶差分
import java.util.Scanner;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
static int N = (int)(1e7+10);
static long[] c = new long[N];
static long sum=0;
public static void main(String[] args) throws IOException {
String[] str = cin.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
for(int i=0;i<m;i++){
str = cin.readLine().split(" ");
int l = Integer.parseInt(str[0]);
int r = Integer.parseInt(str[1]);
int s = Integer.parseInt(str[2]);
int e = Integer.parseInt(str[3]);
//公差
int d = (int)(e-s)/(r-l);
//二阶差分核心公式
c[l] +=s;
c[l+1] += d-s;
c[r+1] -= d+e;
c[r+2] += e;
}
//求一阶的变化
for(int i=1;i<=n;i++){
c[i] += c[i-1];
}
//求原始的变化
for(int i=1;i<=n;i++){
c[i] += c[i-1];
sum += c[i];
}
cout.write(sum+"");
cout.flush();
}
}
4 走迷宫（动态规划dp,bfs广度优先搜索）
输入输出样例
示例 1
输入
5 5
1 0 1 1 0
1 1 0 1 1
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5
输出
8
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
难度: 简单 标签: bfs
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static class Node {
int x;
int y;
int path;
public Node(int x, int y, int path) {
this.x = x;
this.y = y;
//当前路径数
this.path = path;
}
}
//方向数组
static int[] r = {-1,1,0,0};
static int[] c = {0,0,-1,1};
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[][] graph = new int[n][m];
int[][] visited = new int[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
graph[i][j] = scan.nextInt();
}
}
int x1 = scan.nextInt()-1;
int y1 = scan.nextInt()-1;
int x2 = scan.nextInt()-1;
int y2 = scan.nextInt()-1;
LinkedList<Node> queue = new LinkedList<>();
//标记走过的位置
visited[x1][y1] = 1;
queue.add(new Node(x1, y1, 0));
while(!queue.isEmpty()) {
Node t = queue.poll();
int x = t.x;
int y = t.y;
int path = t.path;
if(x == x2 && y == y2) {//出口
System.out.println(path);
return;
}
for(int i = 0; i < 4; i++) {
int x3 = x + r[i];
int y3 = y + c[i];
if(x3 >=0 && x3 <= n-1 && y3 >=0 && y3 <= m-1 && graph[x3][y3] == 1&& visited[x3][y3] != 1) {
//每层扩展就加1
queue.add(new Node(x3, y3, path + 1));
visited[x3][y3] = 1;
// System.out.println(path);
}
}
}
System.out.println(-1);
}
}
5 小明的背包1（dp，01背包）
输入输出样例
示例 1
输入
5 20
1 6
2 5
3 8
5 15
3 3
输出
37
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
难度: 简单 标签: dp, 背包, 01背包
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int N = scan.nextInt();
int V = scan.nextInt();
int[] vn = new int[N+1];
int[] val = new int[N+1];
int[] dp = new int[V+1];
for(int i=1;i<=N;i++){
vn[i] = scan.nextInt();
val[i] = scan.nextInt();
}
scan.close();
for(int i = 1;i<=N;i++){
//01背包
for(int j=V;j>=vn[i];j--){
//dp算法核心
dp[j] = Math.max(dp[j],(dp[j-vn[i]]+val[i]));
}
}
System.out.println(dp[V]);
}
}
6 小明背包2（dp，完全背包）
输入输出样例
示例 1
输入
5 20
1 6
2 5
3 8
5 15
3 3
输出
120
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
难度: 简单 标签: DP, 背包, 完全背包
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
String[] str = scan.nextLine().split(" ");
int N = Integer.parseInt(str[0]);
int V = Integer.parseInt(str[1]);
int[] w = new int[N+1];
int[] v = new int[N+1];
int[] dp = new int[V+1];
for(int i=1;i<=N;i++){
str = scan.nextLine().split(" ");
w[i] = Integer.parseInt(str[0]);
v[i] = Integer.parseInt(str[1]);
}
for(int i=1;i<=N;i++ ){
//完全背包
for(int j=w[i];j<=V;j++){
dp[j] = Math.max(dp[j],(dp[j-w[i]]+v[i]));
}
}
System.out.println(dp[V]);
scan.close();
}
}
7 小明的衣服（哈夫曼树）
输入输出样例
示例 1
输入
5
5 1 3 2 1
输出
25
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
难度: 简单 标签: 哈夫曼树, 贪心
import java.util.Scanner;
import java.util.PriorityQueue;
// 1:无需package
// 2: 类名必须Main, 不可修改
/*
贪心的最优策略：
1、每次染一件路费最贵的。
2、最贵的只染一次（只运送一次），其次2次，以此类推，最小的要一直运送即需要加n次。
3、优先队列，每次选最小的两个数的和累加，并把这个和再加入队列中！
*/
public class Main {
static long sum=0;
//最优队列，也称哈夫曼树
static PriorityQueue<Long> a = new PriorityQueue<>();
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int N = scan.nextInt();
for(int i=0;i<N;i++){
a.add(scan.nextLong());
}
while(a.size()!=1){
Long val1 = a.poll();
Long val2 = a.poll();
sum+=val1+val2;
a.add(val1+val2);
}
System.out.println(sum+"");
scan.close();
}
}
8 百亿富翁(单调栈)
输入输出样例
示例 1
输入
5
3 1 2 5 4
输出
-1 1 1 -1 4
4 3 4 -1 -1
运行限制
- 最大运行时间：2s
- 最大运行内存: 256M
难度: 简单 标签: 单调栈
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int N = scan.nextInt();
int[] h = new int[N];
int[] l = new int[N];
int[] r = new int[N];
// String[] str = scan.nextLine().split(" ");
// for(int i=0;i<N;i++){
// h[i] = Integer.parseInt(str[i]);
// }
for(int i=0;i<N;i++){
h[i] = scan.nextInt();
}
//判断左边第一个比自己高的编号
for(int i=0;i<N;i++){
if(i==0) {
l[i] = -1;
}
//从i-1开始，到0结束
for(int j=i-1;j>=0;j--){
if(h[j]>h[i]){
l[i] = j+1;
break;
}else{
l[i] = -1;
}
}
System.out.print(l[i]+" ");
}
System.out.println();
//判断右边第一个比自己高的编号
for(int i=0;i<N;i++){
if(i==N-1){
r[i]=-1;
}
for(int j=i+1;j<N;j++){
if(h[j]>h[i]){
r[i] = j+1;
break;
}else{
r[i]=-1;
}
}
System.out.print(r[i]+" ");
}
scan.close();
}
}
9 排个序（冒泡排序）
输入输出样例
示例 1
输入
3 2
3 2 1
1 2
输出
YES
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
难度: 简单 标签: 冒泡排序
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;
/**
* 思路：两个数组，用第二个数组里面的数能否将第一个数排好序,给的数据是从1开始的
*/
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//输入数据
int n = scan.nextInt();
int p = scan.nextInt();
int[] arr = new int[n+1];
for (int i=1; i<=n; i++) {
arr[i] = scan.nextInt();
}
//存放排序数组的
ArrayList arrayList = new ArrayList();
for (int i=0; i<p; i++) {
arrayList.add(scan.nextInt() );
}
//根据给的数组下标。排序
for (int i=1; i < n; i++) {
int t=0;
for (int j=1; j <= n-i; j++) {
if (arrayList.contains(j) ) {
if (arr[j] > arr[j+1]) {
t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
}
//判断是否排好序了
boolean flag = true;
for (int i=1; i < n; i++) {
if (arr[i] > arr[i+1]) {
flag = false;
break;
}
}
if (flag) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
10 解立方根（Math.cbrt(x)）(BigDecimal)
输入输出样例
示例 1
输入
3
0
1
8
输出
0.000
1.000
2.000
运行限制
- 最大运行时间：5s
- 最大运行内存: 128M
import java.util.*;
import java.math.BigDecimal;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner (System.in);
int n = sc.nextInt();
for(int i = 0; i<n; i++){
int a = sc.nextInt();
System.out.printf("%.3f",Math.cbrt(a));
System.out.println();
}
}
}
11 回文判定（尺取法，双指针）
输入输出样例
示例 1
输入
abcba
输出
Y
示例 2
输入
abcbb
输出
N
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
String str = scan.nextLine();
scan.close();
for(int i = 0;i<str.length()/2;i++){
if(str.charAt(i) != str.charAt(str.length()-1-i)){
System.out.println("N");
return;
}
}
System.out.println("Y");
}
}
12 最长公共子序列（dp，LCS）
输入输出样例
示例 1
输入
5 6
1 2 3 4 5
2 3 2 1 4 5
输出
4
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int N = 1000+5;
static int[][] lcs = new int[N][N];
static int[] a;
static int[] b;
static void LCS(int n,int m){
for(int i = 0;i<n;i++) lcs[i][0] = 0;
for(int i = 0;i<n;i++) lcs[0][i] = 0;
for(int i =1;i<=n;i++){
for(int j= 1;j<=m;j++){
if(a[i]==b[j]) {
lcs[i][j] = lcs[i-1][j-1]+1;
}else if(a[i]!=b[j]){
if(lcs[i-1][j]>lcs[i][j-1]){
lcs[i][j]=lcs[i-1][j];
}else{
lcs[i][j]=lcs[i][j-1];
}
//lcs[i][j] = Math.max(lcs[i-1][j],lcs[i][j-1]);
}
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n = scan.nextInt();
int m = scan.nextInt();
a = new int[n+1];
b = new int[m+1];
for(int i = 1;i<=n;i++){
a[i] = scan.nextInt();
}
for(int i = 1;i<=m;i++){
b[i] = scan.nextInt();
}
LCS(n,m);
System.out.println(lcs[n][m]);
scan.close();
}
}
13 蓝桥骑士（dp，LIS）
输入输出样例
示例 1
输入
6
1 4 2 2 5 6
输出
4
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 3s | 256M |
| Python3 | 3s | 256M |
难度: 中等 标签: dp, LIS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int)in.nval;
int[] nums = new int[n];
for(int i=0; i<n; i++){
in.nextToken();
nums[i] = (int)in.nval;
}
System.out.print(LengthOfLIS2(nums));
}
/*
* 动态规划算法
* 时间复杂度：O(n²)
* 空间复杂度：O(n)
*/
public static int LengthOfLIS(int[] nums) {
if(nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for(int i=1; i<nums.length; ++i) {
dp[i] = 1;
for(int j=0; j<i; ++j) {
if(nums[i]>nums[j]) {
dp[i] = Math.max(dp[j]+1, dp[i]);
}
}
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
/*
* 二分法+贪心法
* 时间复杂度：O(n*log(n) )
* 空间复杂度：O(n)
*/
public static int LengthOfLIS2(int[] nums) {
if(nums.length == 0) {
return 0;
}
//tails数组是以当前长度连续子序列的最小末尾元素
//如tail[0]是求长度为1的连续子序列时的最小末尾元素
//例：在 1 6 4中 tail[0]=1 tail[1]=4 没有tail[2] 因为无法到达长度为3的连续子序列
int tails[] = new int[nums.length];
//注意：tails一定是递增的 因为看题解那个动画 我们最开始的那个元素一定找的是该数组里最小的 不然如果不是最小 由于我们需要连续 后面的数一定会更大（这样不好的原因是 数越小 我们找到一个比该数大的数的几率肯定会更大）
int res=0;
for(int num : nums) {
//每个元素开始遍历 看能否插入到之前的tails数组的位置 如果能 是插到哪里
int i=0, j=res;
while(i<j) {
int m = (i+j)/2;
if(tails[m] < num) {
i = m+1;
}else {
j = m;
}
}
//如果没有到达j==res这个条件 就说明tail数组里只有部分比这个num要小 那么就把num插入到tail数组合适的位置即可 但是由于这样的子序列长度肯定是没有res长的 因此res不需要更新
tails[i] = num;
//j==res 说明目前tail数组的元素都比当前的num要小 因此最长子序列的长度可以增加了
if(j == res) {
res++;
}
}
return res;
}
}
14 小明背包3（dp，多重背包）
输入输出样例
示例 1
输入
3 30
1 2 3
4 5 6
7 8 9
输出
39
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static int N,V;
static int[] wi;
static int[] vi;
static int[] si;
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
String[] first = cin.readLine().split(" ");
N = Integer.parseInt(first[0]);
V = Integer.parseInt(first[1]);
wi = new int[N+1];
vi = new int[N+1];
si = new int[N+1];
int[] dp = new int[V+1];
for(int i = 1; i<= N; i++) {
first = cin.readLine().split(" ");
wi[i] = Integer.parseInt(first[0]);
vi[i] = Integer.parseInt(first[1]);
si[i] = Integer.parseInt(first[2]);
}
for(int i=1;i<=N;i++) {
for(int j=V;j>=0;j--) {
for(int k=0;k<=Math.min(si[i],j/wi[i]);k++) {
dp[j] = Math.max(dp[j], dp[j-k*wi[i]]+k*vi[i]);
}
}
}
System.out.println(dp[V]);
}
}
15 蓝桥幼儿园（并查集）
输入输出样例
示例 1
输入
5 5
2 1 2
1 1 3
2 1 3
1 2 3
2 1 2
输出
NO
YES
YES
运行限制
- 最大运行时间：5s
- 最大运行内存: 256M
import java.util.Scanner;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static BufferedReader buffin = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter buffout = new BufferedWriter(new OutputStreamWriter(System.out));
static int N = (int)(2e5+10);
static int[] p = new int[N];
//初始化
public static void pInit(){
for(int i=0;i<N;i++){
p[i] = i;
}
}
//查询
public static int find(int x){
if (p[x]!=x){
p[x] = find(p[x]);
}
return p[x];
}
public static void main(String[] args) throws IOException{
// pInit();
String[] str = buffin.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
for(int i=1;i<=n;i++){
p[i] = i;
}
while(m-->0){
int op,x,y;
str = buffin.readLine().split(" ");
op = Integer.parseInt(str[0]);
x = Integer.parseInt(str[1]);
y = Integer.parseInt(str[2]);
if(op==1){//合并
p[find(x)] = find(y);
}
else{//查询
if(find(x) == find(y)){
buffout.write("YES"+"\n");
}else{
buffout.write("NO"+"\n");
}
}
}
buffout.flush();
}
}
16 蓝桥侦探（种类并查集）
输入输出样例
示例 1
输入
4 5
1 2
1 3
2 3
3 4
1 4
输出
2
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
import java.util.Scanner;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
static int N = (int)(5*10e5+10);
static int[] p = new int[2*N];
static int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
static void union(int x,int y){
int fx = find(x),fy=find(y);
p[fx] = fy;
}
public static void main(String[] args) throws IOException {
//在此输入您的代码...
String[] str = cin.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
for(int i = 0; i<2*n; i++){
p[i] = i;
}
int x,y;
while(m-->0){
str = cin.readLine().split(" ");
x = Integer.parseInt(str[0]);
y = Integer.parseInt(str[1]);
if(find(x)!=find(y)){
union(x+n,y);
union(x,y+n);
}else{
cout.write(x+"");
break;
}
}
cout.flush();
}
}
17 期望DP
输入输出样例
示例 1
输入
2
1
12
输出
1.00
37.24
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static int N = (int)1e3+10;
static double[] dp = new double[N];
public static void main(String[] args)throws IOException {
//在此输入您的代码...
int t = Integer.parseInt(cin.readLine());
for(int j=t;j>0;j--){
int n = Integer.parseInt(cin.readLine());
dp[n] = 0;
for(int i=n-1; i>=0; i--){
dp[i] = dp[i+1] + 1.0 * n/(n-i);
}
System.out.printf("%.2f\n",dp[0]);
}
}
}
18 最大公约数&最小公倍数（GCD&LCM）
输入输出样例
示例 1
输入
5
2 4
3 7
5 10
6 8
7 9
输出
2
1
5
2
1
运行限制
- 最大运行时间：2s
- 最大运行内存: 128M
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException{
//在此输入您的代码...
int N = Integer.parseInt(cin.readLine());
for(int i = 0; i < N; i++){
String[] str = cin.readLine().split(" ");
int A = Integer.parseInt(str[0]);
int B = Integer.parseInt(str[1]);
System.out.println(getGCD(A,B));
}
}
static int getGCD(int n,int m){
if(n==0) return m;
return getGCD(m%n,n);
}
//两个数的最小公倍数 等于 两数之积除以他们的最大公约数
// lcm(a, b) = (a * b) / lcd(a, b)
static int getLCM(int a, int b) {
return (a*b) / getGCD(a,b);
}
}
19 数的次幂（快速幂）
输入输出样例
示例 1
输入
3
2 3 7
4 5 6
5 2 9
输出
1
4
7
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException{
//在此输入您的代码...
int T = Integer.parseInt(cin.readLine());
for(int i = 0; i< T; i++){
String[] str = cin.readLine().split(" ");
long N = Long.parseLong(str[0]);
long M = Long.parseLong(str[1]);
long P = Long.parseLong(str[2]);
long res=FastPow(N,M,P);
System.out.println(res);
}
cin.close();
}
static long FastPow(long a,long b,long c){
long res=1;
while (b>0){
if (b%2==1) res=res*a%c;
a = a*a%c;
b=b/2;
}
return res;
}
}
20 快速幂
输入输出样例
示例
输入
2 10 9
输出
7
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
import java.util.Scanner;
import java.math.BigInteger;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
long a = scan.nextLong();
long d = scan.nextLong();
long c = scan.nextLong();
BigInteger b = BigInteger.valueOf(a);
BigInteger p = BigInteger.valueOf(d);
BigInteger k = BigInteger.valueOf(c);
// public BigInteger modPow(BigInteger exponent, BigInteger m)
// 返回一个 BigInteger，其值为 (this的exponent次方 mod m)。 与 pow 不同，此方法允许使用负指数。
BigInteger bigInteger = b.modPow(p, k);//mod意为取模
System.out.println(bigInteger);
scan.close();
}
}
21 ST线性表
问题描述
问题描述：小蓝有一个序列 a[1], a[2], …, a[n]。
给定一个正整数 k，请问对于每一个 1 到 n 之间的序号 i，a[i-k], a[i-k+1], …, a[i+k] 这 2k+1 个数中的最小值是多少？
当某个下标超过 1 到 n 的范围时，数不存在，求最小值时只取存在的那些值。
输入格式
输入的第一行包含一整数 n。
第二行包含 n 个整数，分别表示 a[1], a[2], …, a[n]。
第三行包含一个整数 k 。
输出格式
输出一行，包含 n 个整数，分别表示对于每个序号求得的最小值。
样例输入
5
5 2 7 4 3
1
样例输出
2 2 2 3 3
评测用例规模与约定
对于 30% 的评测用例，1 <= n <= 1000，1 <= a[i] <= 1000。
对于 50% 的评测用例，1 <= n <= 10000，1 <= a[i] <= 10000。
对于所有评测用例，1 <= n <= 1000000，1 <= a[i] <= 1000000。
/**
* 问题描述
问题描述：小蓝有一个序列 a[1], a[2], …, a[n]。
给定一个正整数 k，请问对于每一个 1 到 n 之间的序号 i，a[i-k], a[i-k+1], …, a[i+k] 这 2k+1 个数中的最小值是多少？
当某个下标超过 1 到 n 的范围时，数不存在，求最小值时只取存在的那些值。
输入格式
输入的第一行包含一整数 n。
第二行包含 n 个整数，分别表示 a[1], a[2], …, a[n]。
第三行包含一个整数 k 。
输出格式
输出一行，包含 n 个整数，分别表示对于每个序号求得的最小值。
样例输入
5
5 2 7 4 3
1
样例输出
2 2 2 3 3
评测用例规模与约定
对于 30% 的评测用例，1 <= n <= 1000，1 <= a[i] <= 1000。
对于 50% 的评测用例，1 <= n <= 10000，1 <= a[i] <= 10000。
对于所有评测用例，1 <= n <= 1000000，1 <= a[i] <= 1000000。
*
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static int n,k,f;
static int[] arr;
static int[][] ST;
static int N = (int)(1e3+10);
static int[] dp = new int[N];
public static void main(String[] args) throws IOException{
n = Integer.parseInt(cin.readLine());
f = (int) Math.ceil(Math.log(n) / Math.log(2));
arr = new int[n];
ST = new int[n][f];
String[] str = cin.readLine().split(" ");
for(int i=0; i<str.length;i++) {
arr[i] = Integer.parseInt(str[i]);
}
k = Integer.parseInt(cin.readLine());
init();
for(int i=0;i<n;i++) {
int begin = Math.max(i-k, 0);
int end = i+k<n ? i+k : n-1;
System.out.print(query(begin,end)+" ");
}
}
//初始化
static void init() {
for(int i=0;i<n;i++) {
ST[i][0]=arr[i];
}
for(int j=1;j<f;j++) {
for(int i=0;i+(1<<j)<=n;i++) {
ST[i][j] = Math.min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
}
}
}
//查询
static int query(int l,int r) {
int len = r - l + 1;
int k = (int)(Math.log(len) / Math.log(2));
return Math.min(ST[l][k], ST[r - (1 << k) + 1][k]);
}
}
训练：
输入输出样例
示例 1
输入
5 3
5 3 2 4 1
输出
2
2
1
运行限制
- 最大运行时间：2s
- 最大运行内存: 256M
import java.util.Scanner;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
static int[] temp;
public static void main(String[] args) throws IOException{
String[] str = cin.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
temp = new int[n+1];
int[] a = new int[n+1];
str = cin.readLine().split(" ");
for(int i=1;i<=n;i++){
a[i] = Integer.parseInt(str[i-1]);
}
//求最小
//hh为队头索引（最左边），tt为队尾索引（最右边）
int hh=0,tt=-1;
for(int i = 1;i<=n;i++){
if(hh<=tt && temp[hh]<i-m+1){
hh++;
}
while(hh<=tt && a[temp[tt]]>=a[i]){
tt--;
}
tt++;
temp[tt]=i;
if(i>=m){
cout.write(a[temp[hh]]+"\n");
}
}
cout.flush();
}
}
22 区间最大值（ST表）
输入输出样例
示例 1
输入
5 5
1 2 3 4 5
1 1
1 2
1 3
3 4
2 5
输出
1
2
3
4
5
运行限制
- 最大运行时间：3s
- 最大运行内存: 512M
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static int N,Q,f;
static int[] arr;
static int[][] ST;
public static void main(String[] args)throws IOException{
//在此输入您的代码...
String[] first = cin.readLine().split(" ");
N = Integer.parseInt(first[0]);
Q = Integer.parseInt(first[1]);
arr = new int[N];
f = (int) Math.ceil(Math.log(N) / Math.log(2));
ST = new int[N][f];
first = cin.readLine().split(" ");
for(int i = 0; i < N; i++){
arr[i] = Integer.parseInt(first[i]);
}
init();
for(int i = 0; i < Q; i++){
first = cin.readLine().split(" ");
int L = Integer.parseInt(first[0]);
int R = Integer.parseInt(first[1]);
// if(L==R){
// System.out.println(arr[L]);
// }else{
System.out.println(query(L-1,R-1));
// }
}
}
static void init(){
for(int i=0;i<N;i++){
ST[i][0] = arr[i];
}
for(int j=1;j<f;j++){
for(int i=0;i+(1<<j)<=N;i++){
ST[i][j] = Math.max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
}
}
}
static int query(int l, int r){
int len = r - l + 1;
int k = (int)(Math.log(len) / Math.log(2));
return Math.max(ST[l][k],ST[r-(1<<k)+1][k]);
}
}
23 美丽的区间（尺取法）
输入输出样例
示例 1
输入
5 6
1 2 3 4 5
输出
2
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
总通过次数: 1016 | 总提交次数: 1226 | 通过率: 82.9%
难度: 简单 标签: 尺取法
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n = scan.nextInt();
int S = scan.nextInt();
int[] a = new int[n];
for(int i=0;i<n;i++){
a[i] = scan.nextInt();
}
int sum=0;
int k = 10*n;
for(int i=0,j=0;i<n;i++){
sum +=a[i];
while((sum-a[j]>=S)&&j<n){
sum = sum-a[j];
j++;
//k表示区间长度
if(i-j+1<k) k = i-j+1;
//或者 k = Math.min(k,i-j+1);
}
}
if(k==10*n){
//表示不存在美丽区间
System.out.println("0");
}else{
System.out.println(k);
}
scan.close();
}
}
24 三角形的面积
输入输出样例
示例 1
输入
2
0 1
1 0
1 1
0 0
1 1
2 2
输出
0.50
0.00
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
总通过次数: 824 | 总提交次数: 1052 | 通过率: 78.3%
难度: 简单 标签: 计算几何基础
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int N = scan.nextInt();
for(int i=0;i<N;i++){
double x1 = scan.nextDouble();
double y1 = scan.nextDouble();
double x2 = scan.nextDouble();
double y2 = scan.nextDouble();
double x3 = scan.nextDouble();
double y3 = scan.nextDouble();
double S = Math.abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2);
System.out.printf("%.2f",S/2);
System.out.println();
}
scan.close();
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
double x1 = sc.nextDouble();
double y1 = sc.nextDouble();
double x2 = sc.nextDouble();
double y2 = sc.nextDouble();
double x3 = sc.nextDouble();
double y3 = sc.nextDouble();
point temp = new point(x2-x1,y2-y1);
point temp1 = new point(x3-x1,y3-y1);
double s = cross(temp,temp1);
System.out.println(String.format("%.2f",s/2));
}
}
private static double cross(point A,point B){
return Math.abs(A.x*B.y - A.y*B.x);
}
}
class point{
double x;
double y;
public point(double a,double b){
this.x = a;
this.y = b;
}
}
25 蓝桥公园（Floyd）
输入输出样例
示例 1
输入
3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3
输出
1
3
2
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 3s | 256M |
| Python3 | 50s | 256M |
总通过次数: 676 | 总提交次数: 863 | 通过率: 78.3%
难度: 简单 标签: Floyd
import java.util.Scanner;
import java.io.*;
//1:无需package
//2: 类名必须Main, 不可修改
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
static long MaxValue = 0x3f3f3f3f3f3f3f3fL;
static void flody(long[][] matrix){
for(int m = 0;m<matrix.length;m++){
for(int i=0;i<matrix.length;i++){
for(int j = 0;j<matrix.length;j++){
if((matrix[i][m] + matrix[m][j]) < matrix[i][j])
matrix[i][j] = matrix[i][m]+matrix[m][j];
//matrix[i][j] = Math.min(matrix[i][j],matrix[i][m]+matrix[m][j]);
}
}
}
}
public static void main(String[] args) throws IOException{
String[] str1 = cin.readLine().split(" ");
int N = Integer.parseInt(str1[0]);
int M = Integer.parseInt(str1[1]);
int Q = Integer.parseInt(str1[2]);
long[][] matrix = new long[N+1][N+1];
//初始化邻接矩阵
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++){
matrix[i][j] = MaxValue;
}
}
//初始化边权值
for(int i =0;i<M;i++){
String[] str2 = cin.readLine().split(" ");
int u = Integer.parseInt(str2[0]);
int v = Integer.parseInt(str2[1]);
long w = Integer.parseInt(str2[2]);
//注意重复路径，取最小
matrix[u][v] = Math.min(matrix[u][v],w);
matrix[v][u] = Math.min(matrix[v][u],w);
}
//调用Floyd 算法计算最短路径
flody(matrix);
//找出最短路程
for(int i=0;i<Q;i++){
String[] str3 = cin.readLine().split(" ");
int st = Integer.parseInt(str3[0]);
int ed = Integer.parseInt(str3[1]);
if(st!=ed){
if(matrix[st][ed]==MaxValue){
cout.write("-1"+"\n");
}else{
cout.write(matrix[st][ed]+"\n");
}
}else{
cout.write("0"+"\n");
}
}
cout.flush();
cin.close();
cout.close();
}
}
26 递增序列
对于下面的 3030 行 5050 列的矩阵，请问总共有多少个递增序列？
VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
总通过次数: 9357 | 总提交次数: 11225 | 通过率: 83.4%
难度: 简单 标签: 填空题, 2019, 国赛
import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.setIn(Main.class.getResourceAsStream("inc.txt"));
Scanner sc = new Scanner(System.in);
char[][] data = new char[30][50];
for (int i = 0; i < 30; i++) {
data[i] = sc.nextLine().toCharArray();
System.out.print(data[i]);
System.out.println();
}
int ans = 0;
int dir[][] = {{1, 1}, {1, -1}, {-1, 1}, {1, 0}, {0, 1}};// 右下，右上，左下，右，下
for (int i = 0; i < 30; i++) {
for (int j = 0; j < 50; j++) {///举例每个字符
for (int k = 0; k < 5; k++) {///五个方向
int x = i, y = j;
while (true) {
x += dir[k][0];
y += dir[k][1];
if (x < 0 || x >= 30 || y < 0 || y >= 50) break;//越界
if (data[x][y] > data[i][j]) ans++;///符合条件
}
}
}
}
System.out.println(ans);
sc.close();
}
}
//52800
27 点和直线的关系
输入输出样例
示例 1
输入
3
0 1
1 0
1 1
0 0
1 1
2 2
0 0
0 1
1 0
输出
L
IN
R
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
总通过次数: 229 | 总提交次数: 242 | 通过率: 94.6%
难度: 简单 标签: 计算几何基础
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
//在此输入您的代码...
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i=0;i<T;i++) {
double xa = sc.nextDouble();
double ya = sc.nextDouble();
double xb = sc.nextDouble();
double yb = sc.nextDouble();
double xc = sc.nextDouble();
double yc = sc.nextDouble();
Point temp = new Point(xb-xa,yb-ya);
Point temp1 = new Point(xc-xb,yc-yb);
double crossVal = cross(temp,temp1);
System.out.println(crossVal==0?"IN":(crossVal>0 ? "L":"R"));
}
sc.close();
}
//叉积，为正时角度方向是逆时针，为负时角度方向为顺时针
//同时，叉积的模也是两条向量为边组成平行四边形的面积
static double cross(Point p1,Point p2){
return p1.x*p2.y - p2.x*p1.y;
}
}
class Point{
double x;
double y;
Point (double a, double b){
this.x = a;
this.y = b;
}
}
28 LCIS(最大公共递增子序列)
输入输出样例
示例 1
输入
5 6
1 3 2 4 5
2 3 1 4 5 6
输出
3
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
总通过次数: 355 | 总提交次数: 409 | 通过率: 86.8%
难度: 简单 标签: dp, LCIS
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int[] a;
static int[] b;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//在此输入您的代码...
int n = sc.nextInt();
int m = sc.nextInt();
a = new int[n+1];
b = new int[m+1];
for(int i=1;i<=n;i++){
a[i] = sc.nextInt();
}
for(int i=1;i<=m;i++){
b[i] = sc.nextInt();
}
int[][] dp = new int[n + 1][m + 1];// 表示a的前i个数到b以j为结尾的数的最长子序列
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j] = dp[i-1][j];
if(a[i] == b[j]){//有相等的至少为1
dp[i][j] = Math.max(dp[i][j],1);
//判断是否时递增
for(int k=1;k<j;k++){
if(b[k] < b[j]){
dp[i][j] = Math.max(dp[i][j], dp[i-1][k]+1);
}
}
}
}
}
int max = 0;
for(int col=1;col<=m;col++){
max = Math.max(max,dp[n][col]);
}
System.out.println(max);
sc.close();
}
}
29 子串分值
输入输出样例
示例
输入
ababc
输出
21
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
总通过次数: 4110 | 总提交次数: 6938 | 通过率: 59.2%
难度: 中等 标签: 模拟, 规律, 2020, 省赛
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
/*
思路
这道题可以用暴力解法，但是本题的本意并不是在这里。这里其实是求字母的贡献度，只有当字母个数在子串中个数为1才会有贡献度。
对此，我们可以从要分析字母A的左右两边出发，分别计算移动了多远才会出现一个字母与A相同，然后停止遍历，记录下步长left和right。然后是怎么算总的贡献度。
当前**字母的贡献度=(left+1) * (right+1)**。为什么是这个呢？
以**bacbacdb**为例,我们对第四个字母b进行分析:
- 先往左边遍历,可以移动两个单位,则left = 2;
- 再往右边遍历,可以移动3个单位,则right = 3;
则对于b字母,有贡献度的部分为acbacd,满足的字串(**注意要有b**)有：
- 从左边第一个字母a开始,分别是acb,acba,acbac,acbacd,有4个
- 然后左边从第二个字母c开始,为cb,cba,cbac,cbacd,有4个
- 从左边第三个字母b开始,为b,ba,bac,bacd,有4个
我们在分析过程中可以得到规律,就是**(往左移动的步数+1) * (往右移动的步数+1)**,加1是因为**要包含分析的字母**。
*/
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
String str = scan.next();
char chs[] = str.toCharArray();
int len = str.length();
int res = 0;
for(int i = 0;i < len;i++){
int left = 0;
int right = 0;
char c = chs[i];
for(int j = i - 1;j >=0 && chs[j] != c;j --){
left++;
}
for(int j = i + 1;j < len && chs[j] != c;j++){
right++;
}
res += (left+1)*(right+1);
}
System.out.println(res);
scan.close();
}
}
真题训练
1 枚举、模拟
1.1 卡片
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int[] count = new int[10];
int sum = 1;
int temp;
boolean flag = false;
while(true){
temp = sum;
while(temp!=0){
count[temp%10]++;
if(count[temp%10]>2021){
flag = true;
break;
}
temp/=10;
}
if(flag==true){
//当前sum统计的时候数字已经不够了，所以sum要减1
System.out.println(sum-1);
break;
}else{
sum++;
}
}
scan.close();
}
}
1.2 数的分解
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
//数的分解
/*
* 用2个for循环遍历数字，第3个数字为2019减前两个，要保证一个数比一个大，才能保证不会重。
* 用一个方法判断每个数都不等于2和4；
*/
public class Main {
public static void main(String[] args) {
//在此输入您的代码...
int count=0;
//要保证前面比后面一个数小,0不能包括
for(int i = 1;i<2020/2;i++){
for(int j = i+1;j<2020;j++){
int k = 2019-i-j;
//要保证不重复，不交换顺序，那么后面的要大于前面的
if((i<j) && (j<k)){
//判断是否出现2和4
if(isF(i) && isF(j) && isF(k)){
count++;
}
}
}
}
System.out.println(count);
}
//判断是不是2和4的方法
static boolean isF(int n){
int x = n;
while(true){
if(x%10 == 2 || x%10 == 4){
return false;
}
if(x<10){
return true;
}
x = x/10;
}
/*
String str = n+"";
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i)=='2' || str.charAt(i)=='4' ) {
return false;
}
}
return ture;
*/
}
}
2 搜索
2.1 大胖子走迷宫
输出描述
输出一个整数，表示答案。
输入输出样例
示例
输入
9 5
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++
输出
16
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 2s | 256M |
| Python3 | 3s | 256M |
总通过次数: 333 | 总提交次数: 406 | 通过率: 82%
难度: 简单 标签: BFS, 2019, 国赛
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
public class Main {
static class Node{
int x;
int y;
int t;
public Node(int x,int y,int t){
this.x = x;
this.y = y;
this.t = t;
}
}
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static int N = 305,n,k;
static char[][] w = new char[N][N];
static int[] r = new int[] {2,1,0};
static boolean[][] st = new boolean[N][N];
static LinkedList<Node> q = new LinkedList<Node>();
static int[] dx = new int[] {1,0,-1,0};
static int[] dy = new int[] {0,1,0,-1};
public static void main(String[] args) throws IOException{
String[] str = cin.readLine().split(" ");
n = Integer.parseInt(str[0]);
k = Integer.parseInt(str[1]);
for(int i = 0; i<n;i++){
w[i] = cin.readLine().toCharArray();
}
q.add(new Node(2,2,0));
st[2][2] = true;
bfs();
cin.close();
}
private static void bfs(){
while (!q.isEmpty()) {
Node now = q.poll();
int x = now.x;
int y = now.y;
int t = now.t;
if (x == n - 3 && y == n - 3) { // 出口
System.out.println(t);
return;
}
if (t / k < 2) // 待在原地，时刻加 1
q.add(new Node(x, y, t + 1));
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
int nr = (t / k) > 2 ? 0 : r[t / k]; // 防止下标越界
if (nx - nr < 0 || nx + nr >= n || ny - nr < 0 || ny + nr >= n || st[nx][ny])
continue;
boolean ok = true; // 是否能走到
for (int j = nx - nr; j <= nx + nr; j++) {
for (int m = ny - nr; m <= ny + nr; m++) {
if (w[j][m] == '*') {
ok = false;
break;
}
}
}
if (ok) {
st[nx][ny] = true;
q.add(new Node(nx, ny, t + 1));
}
}
}
}
}
2.2 七段码
import java.util.*;
public class Main {
private static int ans;
private static int[][] g = new int[7][7];
private static boolean[] vis = new boolean[7];
private static boolean[] flag = new boolean[7];
private static void bfs(int x) {
LinkedList<Integer> que = new LinkedList<Integer>();
que.offer(x);
vis[x] = true;
while (!que.isEmpty()) {
int u = que.peek();
que.poll();
for (int i = 0; i <= 6; i++) {
if (g[u][i] != 0 && flag[i] && !vis[i]) {
vis[i] = true;
que.offer(i);
}
}
}
}
private static boolean check(int x) {
for (int i = 0; i <= 6; i++) {
flag[i] = vis[i] = false;
}
int cnt = 0;
for (int i = 6; i >= 0; i--) {
if ((x >> i & 1) != 0) {
flag[i] = true;
}
}
for (int i = 0; i <= 6; i++) {
if (flag[i] && !vis[i]) {
bfs(i);
cnt++;
}
}
return cnt == 1;
}
public static void main(String[] args) {
g[0][1] = g[0][5] = 1;
g[1][0] = g[1][2] = g[1][6] = 1;
g[2][1] = g[2][3] = g[2][6] = 1;
g[3][2] = g[3][4] = 1;
g[4][3] = g[4][5] = g[4][6] = 1;
g[5][0] = g[5][4] = g[5][6] = 1;
g[6][1] = g[6][2] = g[6][4] = g[6][5] = 1;
for (int i = 0; i < (1 << 7); i++) {
if (check(i)) {
ans++;
}
}
System.out.print(ans);
System.out.print('\n');
}
}
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
//用 1 ~ 7 来代表 a ~ g；
static int count = 0;//有一种情况就加一
static int [][] e = new int[10][10];//不会对结果有影响
static int[] f = new int[10];//用来存放并查集的父亲
static boolean[] st = new boolean[10];//用来判断该点边是否已经被拿来用了
//用并查集的find找该点的父亲
public static int find(int i){
if(f[i]==i){
return i;
}
return f[i] = find(f[i]);
}
//用dfs搜索
public static void dfs(int d){
//终止条件
if(d > 7 ){
//先初始化各点的父亲(并查集，初始化)
for (int i = 1; i <= 7; i++) {//从下标为1开始到下标为7的数字，初始化他们对应的父亲
f[i] = i;
}
//进行深度优先搜索(需要用到两套嵌套循环)
for (int i = 1; i <= 7; i++) {
for (int j = 1; j <= 7; j++) {
//判断该二极管发光且相邻，则合并
if((e[i][j] == 1) && (st[i] ==true) &&(st[j] ==true)){
//取出他们当前的父亲
int fx = find(i);
int fy = find(j);
//若这两个人的父亲不相等，则合并
if(fx!=fy){
f[fx] = fy;
}
}
}
}
int k = 0;//用来判断该次dfs中有多少个由边组成的集合
for (int i = 1; i <= 7 ; i++) {
//需要满足该点是需要亮的点
if(st[i] && f[i] == i)k++;
}
//则表明该只有一个集合
if(k==1)count++;
return ;
}
//打开第d个二极管
st[d] = true;
dfs(d+1);
//关闭了第d个二极管
st[d] = false;
dfs(d+1);
}
public static void main(String[] args) {
e[1][2]=e[1][6]=1;//表示相邻
e[2][1]=e[2][7]=e[2][3]=1;
e[3][2]=e[3][7]=e[3][4]=1;
e[4][3]=e[4][5]=1;
e[5][7]=e[5][6]=e[5][4]=1;
e[6][5]=e[6][7]=e[6][1]=1;
e[7][2]=e[7][3]=e[7][5]=e[7][6]=1;
dfs(1);
System.out.println(count);
}
}
3 动态规划
3.1 数字三角形
输入输出样例
示例
输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出
27
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
总通过次数: 17164 | 总提交次数: 21254 | 通过率: 80.8%
难度: 简单 标签: 动态规划, 2020, 省赛
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static int[][] a = new int[110][110];
static int[][] dp = new int[110][110];
public static void main(String[] args) throws IOException{
//在此输入您的代码...
int N = Integer.parseInt(cin.readLine());
for(int i=1;i<=N;i++){
String[] str = cin.readLine().split(" ");
for(int j=1;j<=i;j++){
a[i][j] = Integer.parseInt(str[j-1]);
}
}
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++){
dp[i][j] = -100000000;
}
}
dp[1][1] = a[1][1];
for(int i=2;i<=N;i++){
for(int j=1;j<=i;j++){
dp[i][j] = Math.max(dp[i-1][j-1],dp[i-1][j]) + a[i][j];
}
}
if(((N-1) & 1) != 0){
//奇数
System.out.println(Math.max(dp[N][1+(N-1)/2], dp[N][1+(N-1)/2 +1]));
}else{
//偶数
System.out.println(dp[N][1+(N-1)/2]);
}
cin.close();
}
}
3.2 左孩子右兄弟
输入输出样例
示例 1
输入
5
1
1
1
2
输出
4
评测用例规模与约定
对于 30%的评测用例，1≤N≤20；
对于所有评测用例，1≤N≤100000。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
总通过次数: 1669 | 总提交次数: 1981 | 通过率: 84.3%
难度: 简单 标签: 2021, 省赛
输入：7 1 1 1 3 3 6
输出：6
import java.util.*;
import java.io.*;
class InputReader {
private final static int BUF_SZ = 65536;
BufferedReader in;
StringTokenizer tokenizer;
public InputReader(InputStream in) {
super();
this.in = new BufferedReader(new InputStreamReader(in), BUF_SZ);
tokenizer = new StringTokenizer("");
}
private String next() {
while (!tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(in.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
class Edge {
//记录下一条边的位置
public int nex;
//记录节点编号
public int to;
}
public class Main {
public static final int N = 100010;
public static Edge[] edge = new Edge[N << 1];//记录边，(N<<1表示N*2^1)
public static int[] head = new int[N << 1];//记录结点邻接表的起始地位
public static int TOT;//edge的下表
public static void add_edge(int u, int v) {//存储一条边
edge[++TOT].nex = head[u];//头插法
edge[TOT].to = v;
head[u] = TOT;
}
public static int n;
public static int v;
public static int[] dp = new int[N];//记录dp[]
public static ArrayList[] vec = new ArrayList[N];//记录子结点
public static void dfs(int u, int far) {//求解dp[u]
int ma = 0;
for (int i = head[u]; i != 0; i = edge[i].nex) {
int v = edge[i].to;
if (v == far) {
continue;
}
dfs(v, u);
ma = Math.max(dp[v], ma);
}
dp[u] = ma + vec[u].size();//dp[u]=max{dp[vi]}+k;
}
public static void main(String[] args) {
InputReader cin = new InputReader(System.in);
n = cin.nextInt();
for (int i = 1; i <= 2 * n; i++) edge[i] = new Edge();
for (int i = 1; i <= n; i++) vec[i] = new ArrayList();
for (int i = 2; i <= n; i++) {
v = cin.nextInt();
vec[v].add(i);
add_edge(i, v);
add_edge(v, i);
}
dfs(1, 0);
System.out.println(dp[1]);
}
}
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = (int) 1e5;
static ArrayList<Integer> shu[] = new ArrayList[N + 10];
// 存储根节点距离当前节点的最大距离
static int f[] = new int[N + 10];
static void dfs(int u)
{
// 遍历当前所有子节点
for (int i : shu[u])
{
//当前节点距离根节点的距离 = 父节点距离根节点最深的距离 + 当前节点的子节点数(要使该节点最深的话, 也就是这个点在兄弟节点中最下面的一个)
f[i] = f[u] + shu[u].size();
dfs(i);
}
}
public static void main(String[] args)
{
int n = sc.nextInt();
for (int i = 1; i <= n; i++)
shu[i] = new ArrayList<Integer>();
for (int i = 2; i <= n; i++)
{
int x = sc.nextInt();
shu[x].add(i);
}
dfs(1);
int max = 0;
for (int i = 1; i <= n; i++)
max = Math.max(max, f[i]);
out.println(max);
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}
4 数论
4.1 等差数列
输入输出样例
示例
输入
5
2 6 4 10 20
输出
10
样例说明： 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
总通过次数: 7265 | 总提交次数: 9449 | 通过率: 76.9%
难度: 简单 标签: 2019, GCD
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int N = scan.nextInt();
int[] A = new int[N];
for(int i=0;i<N;i++){
A[i] = scan.nextInt();
}
Arrays.sort(A);
int gcd = getGCD(A[N-1],A[0]);
//找出最小的公差
for(int i=0;i<N-1;i++){
if(gcd > getGCD(A[i+1],A[i])){
gcd = getGCD(A[i+1],A[i]);
}
}
//注意公差为0的情况
if(gcd==0){
System.out.println(N);
}else{
System.out.println((A[N-1] - A[0])/gcd + 1);
}
scan.close();
}
//两数之差，找公差
static int getGCD(int a, int b){
return a-b;
}
}
4.2 阶乘约数（约数定理）
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int N = (int)1e2+10;
static int[] cnt = new int[N];
public static void main(String[] args) {
//在此输入您的代码...
for(int i=1;i<=100;i++){
int x = i;// 不能让分解结果影响循环
for(int j=2;j*j<=x;j++){ // i 为被分解数
// 以sqrt(n)为界 如果一个数在左边，必然有一个数在右边，不用求完 只需要求一半(i*i)就行 就可以判断是不是质数
if(x%j == 0){
// 不是质数 开始分解
while(x%j==0){
x /= j;
// 对应位置次数+1
cnt[j]++;
}
}
}
//x为质数且大于1，对应位置次数+1
if(x>1) cnt[x]++;
}
long res = 1;
for(int i=1;i<=100;i++){
if(cnt[i]!=0){
res *= (cnt[i]+1);
}
}
System.out.println(res);
}
}
5 组合数学
5.1 组合数问题(数位dp)
输入输出样例
示例
输入
1 2
3 3
输出
1
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 2s | 512M |
| C | 2s | 512M |
| Java | 5s | 512M |
| Python3 | 15s | 512M |
总通过次数: 119 | 总提交次数: 198 | 通过率: 60.1%
难度: 简单 标签: 数位DP, 数论, 2019压轴题, 省赛
import java.util.*;
import java.io.*;
class InputReader {
public BufferedReader Reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
Reader = new BufferedReader(new InputStreamReader(System.in), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(Reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public float nextFloat() {
return Float.parseFloat(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
public class Main {
private static final long mod = 1000000007;
private static final long inv2 = 500000004;
private static long n;
private static long m;
private static long k;
private static long[][] dp = new long[65][4];
private static long[] b = new long[65];
private static long[] c = new long[65];
private static long calc1(long n, long m) {
if (n < 0 || m < 0) {
return 0;
}
if (n < m) {
return (n % mod + 2) * (n % mod + 1) % mod * inv2 % mod;
}
return ((m % mod + 2) * (m % mod + 1) % mod * inv2 % mod + (n % mod - m % mod + mod) % mod * (m % mod + 1) % mod + mod) % mod;
}
private static long calc2(long n, long m) {
return (Math.min(n, m) + 1 + mod) % mod;
}
private static long calc3(long n, long m) {
if (n < m) {
return 0;
}
return (n - m + 1 + mod) % mod;
}
public static void main(String[] args) {
InputReader cin = new InputReader(System.in);
int T = cin.nextInt();
k = cin.nextLong();
while ((T--) != 0) {
for(int i = 0 ; i < 65 ; i ++) for(int j = 0 ; j < 4 ; j ++) dp[i][j] = 0;
for(int i = 0 ; i < 65 ; i ++) b[i] = c[i] = 0;
n = cin.nextLong();
m = cin.nextLong();
m = Math.min(n, m);
long tot = calc1(n, m);
int len1 = 0, len2 = 0;
while (n != 0) {
b[len1++] = n % k;
n /= k;
}
while (m != 0) {
c[len2++] = m % k;
m /= k;
}
dp[len1][3] = 1;
for (int i = len1 - 1; i >= 0; i--) {
dp[i][0] = dp[i + 1][0] * calc1(k - 1, k - 1) % mod + dp[i + 1][1] * calc1(b[i] - 1, k - 1) % mod + dp[i + 1][2] * calc1(k - 1, c[i] - 1) % mod + dp[i + 1][3] * calc1(b[i] - 1, c[i] - 1) % mod;
dp[i][1] = dp[i + 1][1] * calc2(b[i], k - 1) % mod + dp[i + 1][3] * calc2(b[i], c[i] - 1) % mod;
dp[i][2] = dp[i + 1][2] * calc3(k - 1, c[i]) % mod + dp[i + 1][3] * calc3(b[i] - 1, c[i]) % mod;
if (dp[i + 1][3] == 1 && b[i] >= c[i]) dp[i][3] = 1;
else dp[i][3] = 0;
dp[i][0] %= mod;
dp[i][1] %= mod;
dp[i][2] %= mod;
}
System.out.println((tot - (dp[0][0] + dp[0][1] + dp[0][2] + dp[0][3]) % mod + mod) % mod);
}
}
}
6 图论
6.1 路径
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int[] dp = new int[2022];
dp[1] = 0;
for(int i=2;i<=2021;i++){
dp[i] = Integer.MAX_VALUE;
}
//dp
//当前dp[j] 表示 从 1~j的最短距离
//dp[j] 可以是 当前 1~j的最短距离 或者 前一状态 到 该点的最短距离
for(int i=1;i<=2020;i++){
for(int j=i+1;j<=2021 && (j-i<=21);j++){
dp[j]= Math.min(dp[j],dp[i]+getLCM(i,j));
}
}
System.out.println(dp[2021]);
scan.close();
}
private static int getGCD(int a,int b){
if(a==0) return b;
return getGCD(b%a,a);
}
private static int getLCM(int a,int b){
return (a*b)/getGCD(a,b);
}
}
6.2 出差（dijkstra）
样例输入
4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5
样例输出
13
样例说明
评测用例规模与约定
对于 100% 的数据, 1≤N≤1000,1≤M≤10000,1≤Ci≤200,1≤u,v≤N*,1≤c*≤1000
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
总通过次数: 256 | 总提交次数: 301 | 通过率: 85%
难度: 简单 标签: 2022, 国赛
迪杰斯特拉dijkstra
import java.util.Scanner;
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
//N 表示 A 国的城市数量
int N = scan.nextInt();
//M 表示未关闭的路线数量
int M = scan.nextInt();
//各国等待时间
int[] C = new int[N + 1];
//到达编号为i的城市后需要隔离 的时间
for(int i=1;i <=N;i++){
C[i] = scan.nextInt();
}
// 第 3…M+2 行: 每行 3 个正整数,u,v,c,
// 表示有一条城市u到城市v的【双向路线】仍然开通着, 通过该路线的时间为c
int[][] c = new int[N+1][N+1];
for(int i=0;i<M;i++){
int u = scan.nextInt();
int v = scan.nextInt();
int cc = scan.nextInt();
// 双向，可能往回跑加入计划1->5 可能 1->3->2->5
c[u][v] = cc;
c[v][u] = cc;
}
//求1——N的最短路径
int[] path = new int[N+1];
int[] dist = new int[N+1];
//初始化
for(int i=2;i<=N;i++){
dist[i] = Integer.MAX_VALUE;
}
dist[1] = 0;
boolean[] vis = new boolean[N+1];
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1);
while(!queue.isEmpty()){
int currentIndex = queue.poll();
vis[currentIndex] = true;
for(int j=2;j<=N;j++){
if(currentIndex !=N && c[currentIndex][j]!=0){
path[j] = currentIndex;
dist[j] = Math.min(dist[j],dist[currentIndex]+c[currentIndex][j]+C[j]);
}
}
int minIndex = 0;
int min = Integer.MAX_VALUE;
// 贪心地找可以通向谁最短（不访问已经访问过的）
for(int k = 1;k<dist.length;k++){
if(vis[k] == false){
minIndex = dist[k] < min ? k : minIndex;
min = dist[k] < min ? dist[k] : min;
}
}
queue.add(minIndex);
if(minIndex==0){
break;
}
}
System.out.println(dist[N]-C[N]);
scan.close();
}
}
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static int INF = 0x3f3f3f3f;//最大值设置，专业，用Integer.MAX_VALUE不专业，容易出差错
static int M = 20010;
public static int[] ea = new int[M];
public static int[] eb = new int[M];
public static int[] ec = new int[M];
public static int[] d = new int[M];
public static int[] t = new int[M];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int m=scanner.nextInt();
for (int i = 1; i <=n ; i++) {
t[i]= scanner.nextInt();
}
for (int i = 1; i <=m ; i++) {
int a= scanner.nextInt();
int b= scanner.nextInt();
int c= scanner.nextInt();
ea[i]=a;
eb[i]=b;
ec[i+m]=ec[i]=c;
ea[i+m]=b;
eb[i+m]=a;
}
Arrays.fill(d,INF);
d[1]=0;
for (int k = 1; k <=n ; k++) {
for (int i = 1; i <=2*m ; i++) {
int u=ea[i];
int v=eb[i];
int res=t[v];
if(v==n) res=0;
d[v]=Math.min(d[v],d[u]+ec[i]+res);
}
}
System.out.println(d[n]);
}
}
7 数据结构
7.1 修改数组（并查集）
输入输出样例
示例
输入
5
2 1 1 3 4
输出
2 1 3 4 5
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
总通过次数: 2067 | 总提交次数: 3272 | 通过率: 63.2%
难度: 简单 标签: 并查集, 2019, 省赛
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static int num = (int)1e5+5;
static int[] A;
static int[] f = new int[num];
public static void main(String[] args) throws IOException {
//在此输入您的代码...
int N = Integer.parseInt(cin.readLine());
A = new int[N];
String[] str = cin.readLine().split(" ");
init();
for(int i = 0;i<N;i++){
A[i] = Integer.parseInt(str[i]);
int x = find(A[i]);
A[i] = x;
f[A[i]] = find(x+1);
}
for(int i:A){
System.out.print(i+" ");
}
cin.close();
}
//初始化
static void init(){
for(int i=1;i<num;i++){
f[i] = i;
}
}
//查询
static int find(int x){
if(x==f[x]) return x;
else{
//路径压缩
return f[x] = find(f[x]);
}
}
}
7.2 翻转括号序列
输入输出样例
示例
输入
7 5
((())()
2 3
2 2
1 3 5
2 3
2 1
输出
4
7
0
0
评测用例规模与约定
对于 20% 的评测用例，n,m≤5000；
对于 40% 的评测用例，n,m≤30000；
对于 60% 的评测用例，n,m≤100000；
对于所有评测用例，1≤n≤106,1≤m≤2×105。
运行限制
- 最大运行时间：10s
- 最大运行内存: 512M
总通过次数: 64 | 总提交次数: 116 | 通过率: 55.2%
难度: 中等 标签: 国赛, 线段树, 2021
50%通过：
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException{
//在此输入您的代码...
String[] str = cin.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
char[] arr = new char[n];
String str1 = cin.readLine();
for(int i=0;i<n;i++){
arr[i] = str1.charAt(i);
}
for(int i=0;i<m;i++){
str = cin.readLine().split(" ");
if(Integer.parseInt(str[0]) == 1){
int L = Integer.parseInt(str[1]);
int R = Integer.parseInt(str[2]);
for(int j=L-1;j<=R-1;j++){
if(arr[j]=='(') arr[j] = ')';
else arr[j] = '(';
}
}else{
int L = Integer.parseInt(str[1]);
int R = 0;
int pair = 0;
for(int j = L-1;j<n;j++){
if(arr[j] == '(') pair +=1;
else pair -=1;
if(pair == 0) R = j+1;
else if(pair==-1) break;
}
System.out.println(R);
}
}
cin.close();
}
}
66.7%通过：
import java.util.Arrays;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n= scan.nextInt();
int m= scan.nextInt();
String sequence= scan.next();
int array[]=new int[n+1];
for (int i=1;i<=n;i++)
{
array[i]=sequence.charAt(i-1)=='('?1:-1;
}
for (int i=0;i<m;i++)
{
int operate= scan.nextInt();
if (operate==1)
{
int left= scan.nextInt();
int right= scan.nextInt();
for (int j=left;j<=right;j++)
{
array[j]*=-1;
}
}
else
{
int left= scan.nextInt();
int right=0;
int pair=0;
for (int j=left;j<=n;j++)
{
pair+=array[j];
if (pair==0)
{
right=j;
}
else if (pair==-1)
{
break;
}
}
System.out.println(right);
}
}
scan.close();
}
}
8 计算几何
8.1 荒岛探测
输入输出样例
示例
输入
10 6 4 12 12
0 2 13 2 13 15
输出
39.99
样例说明
荒岛的形状和定位设备工作正常的区域如下图所示，蓝色的三角形表示荒岛，红色的曲线围成的区域为定位设备工作正常的区域。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
总通过次数: 102 | 总提交次数: 241 | 通过率: 42.3%
难度: 中等 标签: 计算几何, 2020, 省赛
import java.util.*;
public class Main {
private static final double eps = 1e-6;
private static double xa;
private static double ya;
private static double xb;
private static double yb;
private static double L;
private static double A;
private static double ans;
private static double[] x = new double[6];
private static double[] y = new double[6];
private static double[] Y = new double[6];
private static double dist(double a, double b, double c, double d) {
return Math.sqrt((c - a) * (c - a) + (d - b) * (d - b));
}
private static double get(double now, int pos1, int pos2) {
if (Math.abs(x[pos1] - x[pos2]) <= eps && Math.abs(x[pos1] - now) <= eps) {
return 1002;
}
if (now <= Math.min(x[pos1], x[pos2]) || now >= Math.max(x[pos1], x[pos2])) {
return 1002;
}
return (y[pos2] - y[pos1]) / (x[pos2] - x[pos1]) * (now - x[pos2]) + y[pos2];
}
private static boolean ok1(double now) {
double xx = (xa + xb) / 2;
double yy = (ya + yb) / 2;
double a = L / 2;
double c = dist(xa, ya, xb, yb) / 2;
double b = Math.sqrt(a * a - c * c);
double mid = 1.0 - (now - xx) * (now - xx) / (a * a);
if (mid <= 0) {
return false;
}
mid = Math.sqrt(mid) * b;
Y[1] = yy - mid;
Y[2] = yy + mid;
return true;
}
private static boolean ok2(double now) {
int cnt = 2;
for (int i = 1; i <= 3; i++) {
int nex = i + 1 == 4 ? 1 : i + 1;
double mid = get(now, i, nex);
if (mid - 1000 > eps) {
continue;
}
if (cnt == 3 && Math.abs(mid - Y[cnt]) <= eps) {
continue;
}
Y[++cnt] = mid;
}
if (cnt != 4) {
return false;
}
return true;
}
private static double get_angle(double a, double b, double c, double d) {
double now = Math.acos((c - a) / dist(a, b, c, d));
if (d - b < 0) {
return 2 * Math.acos(-1) - now;
}
return now;
}
private static void init() {
A = get_angle(xa, ya, xb, yb);
double dis1 = dist(0, 0, xa, ya);
double dis2 = dist(0, 0, xb, yb);
double S1 = get_angle(0, 0, xa, ya) - A;
double S2 = get_angle(0, 0, xb, yb) - A;
xa = dis1 * Math.cos(S1);
ya = dis1 * Math.sin(S1);
xb = dis2 * Math.cos(S2);
yb = dis2 * Math.sin(S2);
}
private static void change(int pos) {
double dis = dist(0, 0, x[pos], y[pos]);
double S = get_angle(0, 0, x[pos], y[pos]) - A;
x[pos] = dis * Math.cos(S);
y[pos] = dis * Math.sin(S);
}
private static double calc(double now) {
if (!ok1(now)) {
return 0;
}
if (!ok2(now)) {
return 0;
}
double ma = Math.max(Math.min(Y[1], Y[2]), Math.min(Y[3], Y[4]));
double mi = Math.min(Math.max(Y[1], Y[2]), Math.max(Y[3], Y[4]));
if (mi - ma <= eps) {
return 0;
}
return mi - ma;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
xa = cin.nextDouble();
ya = cin.nextDouble();
xb = cin.nextDouble();
yb = cin.nextDouble();
L = cin.nextDouble();
init();
for (int i = 1; i <= 3; i++) {
x[i] = cin.nextDouble();
y[i] = cin.nextDouble();
change(i);
}
if (L <= eps || dist(xa, ya, xb, yb) >= L) {
System.out.print("0.00\n");
return;
}
for (double i = -1000; i <= 1000; i += 0.001) {
ans += calc(i) * 0.001;
}
System.out.printf("%.2f\n", ans);
}
}