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×10^5，−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

输入

输出

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

输出

运行限制

最大运行时间：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

输入

输出

运行限制

最大运行时间：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) {//每层扩展就加1queue.add(new Node(x3, y3, path + 1));visited[x3][y3] = 1; 
//                    System.out.println(path);}}}System.out.println(-1);}
}

5 小明的背包1（dp，01背包）

在这里插入图片描述

输入输出样例

示例 1

输入

输出

运行限制

最大运行时间：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

输入

输出

运行限制

最大运行时间：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

输出

运行限制

最大运行时间：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

输入

输出

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

输出

示例 2

输入

abcbb

输出

运行限制

最大运行时间：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

输出

运行限制

最大运行时间：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

输出

运行限制

语言	最大运行时间	最大运行内存
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

输入

输出

运行限制

最大运行时间：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 stubString[] 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

输入

输出

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

输入

输出

运行限制

最大运行时间：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

输入

输出

运行限制

最大运行时间：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

输入

输出

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

输出

运行限制

最大运行时间：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 个整数，分别表示对于每个序号求得的最小值。样例输入55 2 7 4 31样例输出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

输入

输出

运行限制

最大运行时间：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

输出

运行限制

最大运行时间：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

输入

输出

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

输入

输出

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 stubSystem.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

输入

输出

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

输出

运行限制

最大运行时间：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]){//有相等的至少为1dp[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

输出

运行限制

最大运行时间：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要减1System.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和4if(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
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++

输出

运行限制

语言	最大运行时间	最大运行内存
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) // 待在原地，时刻加 1q.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 数字三角形

在这里插入图片描述

输入输出样例

示例

输入

输出

运行限制

最大运行时间：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

输入

输出

评测用例规模与约定

对于 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

输出

样例说明：包含 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;// 对应位置次数+1cnt[j]++;}}}//x为质数且大于1，对应位置次数+1if(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

输出

运行限制

语言	最大运行时间	最大运行内存
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）

在这里插入图片描述

样例输入

样例输出

样例说明

在这里插入图片描述

评测用例规模与约定

对于 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的【双向路线】仍然开通着, 通过该路线的时间为cint[][] 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->5c[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

输出

评测用例规模与约定

对于 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);}
}