devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java蓝桥杯_蓝桥杯java

作者：小小林熬夜学编程 | 2024-02-10 00:59:58

赞

踩

蓝桥杯java

目录

往年真题

题目分类

搜索

动态规划

并查集

贪心算法

二分查找

输入输出

图论

其他

往年真题

2023年第十四届蓝桥杯大赛软件类省赛Java研究生组真题 - 题库 - C语言网

2022年第十三届蓝桥杯大赛软件类决赛Java研究生组真题 - 题库 - C语言网

2021年蓝桥杯第十二届省赛及国赛真题 - 题库 - C语言网

2020年蓝桥杯第十一届省赛及国赛真题 - 题库 - C语言网

2019年蓝桥杯第十届省赛及国赛真题 - 题库 - C语言网

2018年蓝桥杯第九届省赛及国赛真题 - 题库 - C语言网

2017年蓝桥杯第八届省赛及国赛真题 - 题库 - C语言网

2016年蓝桥杯第七届省赛及国赛真题 - 题库 - C语言网

2015年蓝桥杯第六届省赛及国赛真题 - 题库 - C语言网

2014年蓝桥杯第五届省赛及国赛真题 - 题库 - C语言网

2013年蓝桥杯第四届省赛及国赛真题 - 题库 - C语言网

2012年及以前蓝桥杯大赛历届真题 - 题库 - C语言网

题目分类

搜索

1. 全排列

输出自然数1到n所有不重复的排列，即n的全排列。

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static int n;
  5.     static boolean[] visit;
  6.     static int[] arr;
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         n = sc.nextInt();
  10.         arr = new int[n+1];
  11.         visit = new boolean[n+1];
  12.         dfs(1);
  13.     }
  14.     public static void dfs(int index) {
  15.         if (index == n+1) {
  16.             for (int i = 1; i <= n; i++) {
  17.                System.out.print(" "+arr[i]);
  18.             }
  19.             System.out.println();
  20.             return;
  21.         }
  22.         for (int i = 1; i <= n; i++) {
  23.             if (!visit[i]) {
  24.                 arr[index] = i;
  25.                 visit[i] = true;
  26.                 dfs(index+1);
  27.                 visit[i] = false;
  28.             }
  29.         }
  30.     }
  31. }

2. 跳马

一个8×8的棋盘上有一个马初始位置为(a,b)，他想跳到(c,d)，问是否可以？如果可以，最少要跳几步？

输入格式

一行四个数字a,b,c,d。

输出格式

如果跳不到，输出-1；否则输出最少跳到的步数。

样例输入

1 1 2 3

样例输出

1

数据规模和约定

0<a,b,c,d≤8且都是整数。

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static int n = 8;
  5.     static int a,b,c,d;
  6.     static boolean[][] visit;
  7.     //马走日,一共有8种移动
  8.     static int[][] action = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
  9.     static int min_step = 100;
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         a = sc.nextInt();
  13.         b = sc.nextInt();
  14.         c = sc.nextInt();
  15.         d = sc.nextInt();
  16.         visit = new boolean[n+1][n+1];
  17.         visit[a][b] = true;
  18.         dfs(a, b, 0);
  19.         if (min_step == 100) {
  20.             System.out.print(-1);
  21.         }
  22.         else {
  23.             System.out.print(min_step);
  24.         }
  25.     }
  26.     public static void dfs(int x,int y,int step) {
  27.         //剪枝,如果该点的步数比之前到该点步数大,不必进行后续操作
  28.         if (step > min_step) {
  29.             return;
  30.         }
  31.         if (x == c && y == d) {
  32.             min_step = Math.min(min_step, step);
  33.             return;
  34.         }
  35.         for (int i = 0; i < n; i++) {
  36.             int x_new = x + action[i][0];
  37.             int y_new = y + action[i][1];
  38.             if (x_new >0 && x_new <= n && y_new >0 && y_new <= n) {
  39.                 visit[x_new][y_new] = true;
  40.                 dfs(x_new, y_new,step+1);
  41.                 visit[x_new][y_new] = false;
  42.             }
  43.         }
  44.     }
  45. }

3. 粘木棍

有N根木棍，需要将其粘贴成M个长木棍，使得最长的和最短的的差距最小。

输入格式

第一行两个整数N,M。
一行N个整数，表示木棍的长度。

输出格式

一行一个整数，表示最小的差距

样例输入

3 2
10 20 40

样例输出

10

数据规模和约定

N, M<=7

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static int n,m;
  5.     //记录初始木棍长度
  6.     static int[] arr;
  7.     //记录粘贴后的木棍长度
  8.     static int[] sum;
  9.     //记录某根木棍是否使用
  10.     static boolean[] visit;
  11.     static int res = 0x3f3f3f;
  12.     public static void main(String[] args) {
  13.         Scanner sc = new Scanner(System.in);
  14.         n = sc.nextInt();
  15.         m = sc.nextInt();
  16.         arr = new int[n+1];
  17.         sum = new int[n+1];
  18.         visit = new boolean [n+1];
  19.         for (int i = 1; i <= n; i++) {
  20.             arr[i] = sc.nextInt();
  21.         }
  22.         dfs(1);
  23.         System.out.print(res);
  24.     }
  25.     public static void dfs(int k) {
  26.         //所有木棍均已使用
  27.         if (k > n) {
  28.             int max = sum[1];
  29.             int min = sum[1];
  30.             for (int i = 1; i <= m; i++) {
  31.                 max = Math.max(max, sum[i]);
  32.                 min = Math.min(min, sum[i]);
  33.             }
  34.             res = Math.min(max-min, res);
  35.             return;
  36.         }
  37.         for (int i = k; i <= n; i++) {
  38.             if (!visit[i]) {
  39.                 //使用第i根
  40.                 visit[i] = true;
  41.                 for (int j = 1; j <= m; j++) {
  42.                     sum[j] += arr[i];
  43.                     dfs(k+1);
  44.                     sum[j] -= arr[i];
  45.                 }
  46.                 visit[i] = false;
  47.             }
  48.         }
  49.     }
  50. }

4. 24点

24点游戏是一个非常有意思的游戏，很流行，玩法很简单：给你4张牌，每张牌上有数字（其中A代表1，J代表11，Q代表12，K代表13），你可以利用数学中的加、减、乘、除以及括号想办法得到24，例如：
((A*K)-J)*Q等价于((1*13)-11)*12=24
加减乘不用多说了，但除法必须满足能整除才能除！这样有一些是得不到24点的，所以这里只要求求出不超过24的最大值。

输入格式

输入第一行N(1<=N<=5)表示有N组测试数据。每组测试数据输入4行，每行一个整数(1到13)表示牌值。

输出格式

每组测试数据输出一个整数，表示所能得到的最大的不超过24的值。

样例输入

3
3
3
3
3
1
1
1
1
12
5
13
1

样例输出

24
4
21

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static int res = 0;
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  8.         int[][] arr = new int[n+1][5];
  9.         for (int i = 1; i <= n; i++) {
  10.             for (int j = 1; j <= 4; j++) {
  11.                 arr[i][j] = sc.nextInt();
  12.             }
  13.         }
  14.         for (int i = 1; i <= n; i++) {
  15.             dfs(arr[i],4);
  16.             System.out.println(res);
  17.             res = 0;
  18.         }
  19.     }
  20.     public static void dfs(int[] arr,int n) {
  21.         if (n==1) {
  22.             if (arr[n] <= 24) {
  23.                res = Math.max(res, arr[n]); 
  24.             }
  25.             return;
  26.         }
  27.         //将两个数进行运算
  28.         for (int i = 1; i < n; i++) {
  29.             for (int j = i+1; j <= n; j++) {
  30.                 int a = arr[i];
  31.                 int b = arr[j];
  32.                 //加法
  33.                 arr[j] = a+b;
  34.                 arr[i] = arr[n];
  35.                 dfs(arr, n-1);
  36.                 //乘法
  37.                 arr[j] = a*b;
  38.                 arr[i] = arr[n];
  39.                 dfs(arr, n-1);
  40.                 //减法1
  41.                 arr[j] = a-b;
  42.                 arr[i] = arr[n];
  43.                 dfs(arr, n-1);
  44.                 //减法2
  45.                 arr[j] = b-a;
  46.                 arr[i] = arr[n];
  47.                 dfs(arr, n-1);
  48.                 //除法
  49.                 if (b != 0 && a%b == 0) {
  50.                     arr[j] = a/b;
  51.                     arr[i] = arr[n];
  52.                     dfs(arr, n-1);
  53.                 }
  54.                 if (a != 0 && b%a == 0) {
  55.                     arr[j] = b/a;
  56.                     arr[i] = arr[n];
  57.                     dfs(arr, n-1);
  58.                 }
  59.                 arr[i] = a;
  60.                 arr[j] = b;
  61.             }
  62.         }
  63.     }
  64. }

5. 自然数拆分

HJQ同学发现了一道数学题，要求n拆分成若干自然数和的方案

输入格式

输入n

输出格式

输出n拆分成若干自然数和的方案，每个方案一行

数据规模和约定

n <= 10

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static int n;
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         n = sc.nextInt();
  8.         List<Integer> list = new ArrayList<Integer>();
  9.         dfs(1, list);
  10.     }
  11.     public static void dfs(int start, List<Integer> list) {
  12.         if (sum(list) == n) {
  13.             for (int i = 0; i < list.size(); i++) {
  14.                 if (i != list.size()-1) {
  15.                     System.out.print(list.get(i)+"+");
  16.                 }
  17.                 else {
  18.                     System.out.println(list.get(i));
  19.                 }
  20.             }
  21.             return;
  22.         }
  23.         if (sum(list) > n) {
  24.             return;
  25.         }
  26.         for (int i = start; i < n; i++) {
  27.             //从start开始保证由小到大输出
  28.             list.add(i);
  29.             //防止出现数相同但顺序不同的情况
  30.             dfs(i, list);
  31.             list.remove(list.size()-1);
  32.         }
  33.     }
  34.     public static int sum(List<Integer> list) {
  35.         int sum = 0;
  36.         for (int i = 0; i < list.size(); i++) {
  37.             sum += list.get(i);
  38.         }
  39.         return sum;
  40.     }
  41. }

6. 最大数字

给定一个正整数 N 。你可以对N 的任意一位数字执行任意次以下 2 种操 作：

  1. 将该位数字加 1 。如果该位数字已经是 9 , 加 1 之后变成 0 。
  2. 将该位数字减 1 。如果该位数字已经是 0 , 减 1 之后变成 9 。

你现在总共可以执行 1 号操作不超过 A 次, 2 号操作不超过 B 次。 请问你最大可以将 N 变成多少?

输入格式

第一行包含 3 个整数: N,A,B 。

输出格式

一个整数代表答案。

样例输入

123 1 2

样例输出

933

样例说明

对百位数字执行 2 次 2 号操作, 对十位数字执行 1 次 1 号操作。

评测用例规模与约定

1≤N≤1017;0≤A,B≤100

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static int cnt1,cnt2;
  5.     static String n;
  6.     static long res;
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         n = sc.next();
  10.         cnt1 = sc.nextInt();
  11.         cnt2 = sc.nextInt();
  12.         dfs(0, 0);
  13.         System.out.print(res);
  14.     }
  15.     public static void dfs(int i, long value) {
  16.         if (i < n.length()) {
  17.             int x = n.charAt(i)-'0';
  18.             int t = Math.min(cnt1, 9-x);
  19.             cnt1 -= t;
  20.             dfs(i+1, value*10+x+t);
  21.             cnt1 += t;
  22.             if (cnt2 > x) {
  23.                 cnt2 = cnt2-x-1;
  24.                 dfs(i+1, value*10+9);
  25.                 cnt2 = cnt2+x+1;
  26.             }
  27.         }
  28.         else {
  29.             res = Math.max(res, value);
  30.         }
  31.     }
  32. }

7. 分考场

n个人参加某项特殊考试。为了公平，要求任何两个认识的人不能分在同一个考场。求最少需要分几个考场才能满足条件。

输入格式

第一行，一个整数n(1<n<100)，表示参加考试的人数。
第二行，一个整数m，表示接下来有m行数据
以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。

输出格式

一行一个整数，表示最少分几个考场。

样例输入

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

样例输出

4

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static boolean[][] arr;
  5.     static int[][] place;
  6.     static int n,num;
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         n = sc.nextInt();
  10.         int m = sc.nextInt();
  11.         arr = new boolean[n+1][n+1];
  12.         place = new int[n+1][n+1];
  13.         num = n;
  14.         for (int i = 0; i < m; i++) {
  15.             int a = sc.nextInt();
  16.             int b = sc.nextInt();
  17.             arr[a][b] = true;
  18.             arr[b][a] = true;
  19.         }
  20.         dfs(1,1);
  21.         System.out.print(num);
  22.     }
  23.     public static void dfs(int id, int classes) {
  24.         //剪枝，考场数大于最小考场数
  25.         if (classes >= num) {
  26.             return;
  27.         }
  28.         //安排了n个人
  29.         if (id > n) {
  30.             num = Math.min(num, classes);
  31.             return;
  32.         }
  33.         //初始化考场号和考场位置
  34.         for (int classNumber = 1; classNumber <= classes; classNumber++) {
  35.             //把id号学生放入classNumber号考场
  36.             int classPosition = 1;
  37.             //如果classNumber号考场的classPosition有人，且不认识id号学生
  38.             while(place[classNumber][classPosition]!=0 && !arr[id][place[classNumber][classPosition]]) {
  39.                 classPosition++;
  40.             }
  41.             //如果没人坐则安排入座
  42.             if (place[classNumber][classPosition]==0) {
  43.                 place[classNumber][classPosition] = id;
  44.                 dfs(id+1, classes);
  45.                 //回溯
  46.                 place[classNumber][classPosition] = 0;
  47.             }
  48.         }
  49.         //如果1至classes考场都不能满足，则新开考场
  50.         place[classes+1][1] = id;
  51.         dfs(id+1, classes+1);
  52.         //回溯
  53.         place[classes+1][1] = 0;
  54.     }
  55. }

8. 长草

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。

输入格式

输入的第一行包含两个整数 n, m。接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。接下来包含一个整数 k。

输出格式

输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。

样例输入

4 5

.g...

.....

..g..

.....

2

样例输出

gggg.

gggg.

ggggg

.ggg.

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static class Node {
  5.         int x;
  6.         int y;
  7.         public Node(int x,int y) {
  8.             this.x = x;
  9.             this.y = y;
  10.         }
  11.     }
  12.     static int n,m;
  13.     static char[][] arr;
  14.     static int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
  15.     static Queue<Node> queue = new LinkedList<>();
  16.     public static void main(String[] args) {
  17.         Scanner sc = new Scanner(System.in);
  18.         n = sc.nextInt();
  19.         m = sc.nextInt();
  20.         arr = new char[n][m];
  21.         for (int i = 0; i < n; i++) {
  22.             arr[i] = sc.next().toCharArray();
  23.         }
  24.         int k = sc.nextInt();
  25.         //遍历将有草的位置放入队列
  26.         for (int i = 0; i < n; i++) {
  27.             for (int j = 0; j < m; j++) {
  28.                 if (arr[i][j] == 'g') {
  29.                     queue.offer(new Node(i, j));
  30.                 }
  31.             }
  32.         }
  33.         while(k > 0) {
  34.             k--;
  35.             bfs();
  36.         }
  37.         for (int i = 0; i < n; i++) {
  38.             for (int j = 0; j < m; j++) {
  39.                 System.out.print(arr[i][j]);
  40.             }
  41.             System.out.println();
  42.         }
  43.     }
  44.     public static void bfs() {
  45.         int len = queue.size();
  46.         while (len > 0) {
  47.             len--;
  48.             Node node = queue.poll();
  49.             //向四个方向长草
  50.             for (int i = 0; i < 4; i++) {
  51.                 int nx = node.x + d[i][0];
  52.                 int ny = node.y + d[i][1];
  53.                 if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] == '.') {
  54.                     queue.offer(new Node(nx, ny));
  55.                     arr[nx][ny] = 'g';
  56.                 }
  57.             }
  58.         }
  59.     }  
  60. }

9. 青蛙跳杯子

X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

*WWWBBB

其中，W字母表示白色青蛙，B表示黑色青蛙，表示空杯子。X星的青蛙很有些癖好，它们只做3个动作之一：
1. 跳到相邻的空杯子里。
2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。
对于上图的局面，只要1步，就可跳成下图局面：
WWW*BBB
本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。输入为2行，2个串，表示初始局面和目标局面。输出要求为一个整数，表示至少需要多少步的青蛙跳。

输入描述

输入为 2 行，2 个串，表示初始局面和目标局面。我们约定，输入的串的长度不超过 15。

输出描述

输出要求为一个整数，表示至少需要多少步的青蛙跳。

样例输入

*WWBB

WWBB*

样例输出

2

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static Queue<String> queue = new LinkedList<String>();
  5.     //记录到达当前状态需要几步
  6.     static Map<String, Integer> map = new HashMap<String, Integer>();
  7.     static int[] d = {-3,-2,-1,1,2,3};
  8.     static int step;
  9.     static String start,target;
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         start = sc.next();
  13.         target = sc.next();
  14.         queue.offer(start);
  15.         bfs();
  16.     }
  17.     public static void bfs() {
  18.         while(queue.size() > 0) {
  19.             int len = queue.size();
  20.             step++;
  21.             while(len > 0) {
  22.                 len--;
  23.                 String s = queue.poll();
  24.                 if (s.equals(target)) {
  25.                     System.out.println(map.get(s));
  26.                     return;
  27.                 }
  28.                 //将每一只青蛙在六个方向上
  29.                 for (int i = 0; i < s.length(); i++) {
  30.                     if (s.charAt(i) != '*') {
  31.                         char c = s.charAt(i);
  32.                         for (int j = 0; j < d.length; j++) {
  33.                             int newc = d[j] + i;
  34.                             if (newc >= 0 && newc < s.length() && s.charAt(newc) == '*') {
  35.                                 //跳跃更新位置
  36.                                 StringBuilder sb = new StringBuilder(s);
  37.                                 sb.setCharAt(i, '*');
  38.                                 sb.setCharAt(newc, c);
  39.                                 String newString = sb.toString();
  40.                                 if (!map.containsKey(newString)) {
  41.                                     map.put(newString, step);
  42.                                     queue.offer(newString);
  43.                                 }
  44.                             }
  45.                         }
  46.                     }
  47.                 }
  48.             }
  49.         }
  50.     }  
  51. }

10. 卡片换位

你玩过华容道的游戏吗？这是个类似的，但更简单的游戏。看下面 3 x 2 的格子

+---+---+---+

| A | * | * |

+---+---+---+

| B | | * |

+---+---+---+

在其中放 5 张牌，其中 A 代表关羽，B 代表张飞，* 代表士兵。还有个格子是空着的。你可以把一张牌移动到相邻的空格中去(对角不算相邻)。游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。

输入描述

输入两行 6 个字符表示当前的局面

输出描述

一个整数，表示最少多少步，才能把 A B 换位（其它牌位置随意）

样例输入

* A

**B

样例输出

17

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static String start;
  5.     static int[][] d= {{1,0},{-1,0},{0,1},{0,-1}};
  6.     static Queue<String> queue = new LinkedList<String>();
  7.     //记录到达当前状态的步数
  8.     static HashMap<String, Integer> map = new HashMap<String, Integer>();
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         String string1 = sc.nextLine();
  12.         String string2 = sc.nextLine();
  13.         start = string1+string2;
  14.         bfs();
  15.     }
  16.     public static void bfs() {
  17.         map.put(start, 0);
  18.         queue.offer(start);
  19.         //获取A，B在字符串中的位置
  20.         int a = 0, b = 0;
  21.         for (int i = 0; i < start.length(); i++) {
  22.             if (start.charAt(i) == 'A') {
  23.                 a = i;
  24.             }
  25.             if (start.charAt(i) == 'B') {
  26.                 b = i;
  27.             }
  28.         }
  29.         while(!queue.isEmpty()) {
  30.             String string = queue.poll();
  31.             //判断是否符合
  32.             if (string.charAt(a) == 'B' && string.charAt(b) == 'A') {
  33.                 System.out.print(map.get(string));
  34.                 return;
  35.             }
  36.             //查找空格在字符串的位置
  37.             int index = string.indexOf(' ');
  38.             int x = index/3;
  39.             int y = index%3;
  40.             //四个方向可以向空格移动
  41.             for (int i = 0; i < 4; i++) {
  42.                 int nx = x + d[i][0];
  43.                 int ny = y + d[i][1];
  44.                 if (nx >= 0 && nx < 2 && ny >= 0 && ny < 3) {
  45.                     //交换位置
  46.                     char[] c = string.toCharArray();
  47.                     c[index] = c[nx*3+ny];
  48.                     c[nx*3+ny] = ' ';
  49.                     String newString = new String(c);
  50.                     if (!map.containsKey(newString)) {
  51.                         map.put(newString, map.get(string)+1);
  52.                         queue.offer(newString);
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.     }  
  58. }

11. 移动字母

2x3=6 个方格中放入 ABCDE 五个字母，右下角的那个格空着。如下图所示。

和空格子相邻的格子中的字母可以移动到空格中，比如，图中的 C 和 E 就可以移动，移动后的局面分别是：

A B

D E C

A B C

D E

为了表示方便，我们把 6 个格子中字母配置用一个串表示出来，比如上边的两种局面分别表示为：

AB*DEC

ABCD*E

题目的要求是：请编写程序，由用户输入若干表示局面的串，程序通过计算，输出是否能通过对初始状态经过若干次移动到达该状态。可以实现输出 1,否则输出 0。初始状态为：ABCDE*。

输入描述

先是一个整数 n，表示接下来有 n 行状态。

输出描述

程序输出 n 行 1 或 0。

样例输入

3

ABCDE*

AB*DEC

CAED*B

样例输出

1

1

0

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static int n;
  5.     static String start = "ABCDE*", target;
  6.     static int[][] d= {{1,0},{-1,0},{0,1},{0,-1}};
  7.     static Queue<String> queue;
  8.     static HashSet<String> set;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt();
  12.         for (int i = 0; i < n; i++) {
  13.             target = sc.next();
  14.             bfs();
  15.         }
  16.     }
  17.     public static void bfs() {
  18.         queue = new LinkedList<String>();
  19.         set = new HashSet<String>();
  20.         queue.add(start);
  21.         set.add(start);
  22.         while (!queue.isEmpty()) {
  23.             String string = queue.poll();
  24.             //判断是否符合
  25.             if (string.equals(target)) {
  26.                 System.out.println(1);
  27.                 return;
  28.             }
  29.             //查找空格的位置
  30.             int index = string.indexOf('*');
  31.             int x = index/3;
  32.             int y = index%3;
  33.             //四个方向移动
  34.             for (int i = 0; i < d.length; i++) {
  35.                 int nx = x + d[i][0];
  36.                 int ny = y + d[i][1];
  37.                 if (nx >= 0 && nx < 2 && ny >= 0 && ny < 3) {
  38.                     //交换位置
  39.                     char[] c = string.toCharArray();
  40.                     c[index] = c[nx*3+ny];
  41.                     c[nx*3+ny] = '*';
  42.                     String nstring = new String(c);
  43.                     if (!set.contains(nstring)) {
  44.                         set.add(nstring);
  45.                         queue.add(nstring);
  46.                     }
  47.                 }
  48.             }
  49.         }
  50.         System.out.println(0);
  51.     }
  52. }

动态规划

1. 01背包问题

f[i][j]在i个物品中，选取容量为j的物品的价值。第i个物品只有两种情况，拿或者不拿。如f[4][8]，不拿第4个，当前价值为在其他3个里选取容量为8的物品，即f[3][8]；如果拿第4个，则在其他3个里选取容量为8-value[4] = 3的物品，当前价值为f[3][3]+v[4]。只需要比较两种情况哪个价值更大，选取哪个。

f[4][8] = Max(f[3][8]，f[3][8-5]+v[4]）

状态转移公式：

f[i][j]= Max(f[i-1][j],f[i-1][j-w[i]]+v[i])

2. 质数拆分

将 2019拆分为若干个两两不同的质数之和，一共有多少种不同的方法？ 注意交换顺序视为同一种方法，例如 2+2017=2019 与 2017+2=2019 视为同一种方法。

代码：

  1. import java.util.*;
  2. /*
  3.  * dp[i][j]使用i个素数达到和为j的情况数量
  4.  */
  5. public class Main { 
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int index = 1;
  9.         int[] arr = new int[400];
  10.         long[][] dp = new long[400][2020];
  11.         for(int i=1;i<2019;i++) {
  12.             if(isPrime(i)) {
  13.                 arr[index++] = i;
  14.             }
  15.         }
  16.         dp[0][0] = 1;
  17.         for(int i=1;i<index;i++) {
  18.             for(int j=0;j<=2019;j++) {
  19.                 if(j<arr[i]) {
  20.                     dp[i][j] = dp[i-1][j];
  21.                 }
  22.                 else {
  23.                     dp[i][j] = dp[i-1][j]+dp[i-1][j-arr[i]];
  24.                 }
  25.             }
  26.         }
  27.         System.out.print(dp[index-1][2019]);
  28.     }
  29.     public static boolean isPrime(int n) {
  30.         if(n==1) {
  31.             return false;
  32.         }
  33.         for(int i=2;i<=Math.sqrt(n);i++) {
  34.             if(n%i == 0) {
  35.                 return false;
  36.             }
  37.         }
  38.         return true;
  39.     }
  40. }

3. 秘密行动

小D接到一项任务，要求他爬到一座n层大厦的顶端与神秘人物会面。这座大厦有一个神奇的特点，每层的高度都不一样，同时，小D也拥有一项特殊能力，可以一次向上跳跃一层或两层，但是这项能力无法连续使用。已知向上1高度消耗的时间为1，跳跃不消耗时间。由于事态紧急，小D想知道他最少需要多少时间到达顶层。

输入格式

第一行包含一个整数n，代表楼的高度。接下来n行每行一个整数ai，代表i层的楼层高度（ai <= 100）。

输出格式

输出1行，包含一个整数，表示所需的最短时间。

样例输入

5
3
5
1
8
4

样例输出

1

代码：

  1. import java.util.*;
  2.  
  3. public class Main { 
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         int[] arr = new int[n+1];
  8.         int[][] dp = new int[n+1][2];
  9.         //dp[][0]代表爬，dp[][1]代表跳
  10.         for(int i=1;i<=n;i++) {
  11.             arr[i] = sc.nextInt();
  12.         }
  13.         dp[0][0] = dp[0][1] = 0;
  14.         dp[1][0] = arr[1];
  15.         for(int i=2;i<n+1;i++) {
  16.             //爬，上一次可以是爬或者跳
  17.             dp[i][0] = Math.min(dp[i-1][0]+arr[i], dp[i-1][1]+arr[i]);
  18.             //跳，上一次只能是爬
  19.             dp[i][1] = Math.min(dp[i-2][0], dp[i-1][0]);
  20.         }
  21.         System.out.println(Math.min(dp[n][0], dp[n][1]));
  22.     }
  23. }

4. 第二点五个不高兴的小明

有一条长为n的走廊，小明站在走廊的一端，每次可以跳过不超过p格，每格都有一个权值wi。小明要从一端跳到另一端，不能回跳，正好跳t次，请问他跳过的方格的权值和最大是多少？

输入格式

输入的第一行包含两个整数n, p, t，表示走廊的长度，小明每次跳跃的最长距离和小明跳的次数。
接下来n个整数，表示走廊每个位置的权值。

输出格式

输出一个整数。表示小明跳过的方格的权值和的最大值。

样例输入

8 5 3
3 4 -1 -100 1 8 7 6

样例输出

12

数据规模和约定

1<=n, p, t<=1000, -1000<=wi<=1000。

代码：

  1. import java.util.*;
  2. /* 0 1 2 3    .  . . . n n+1
  3.  * 0 3 4 -1 -100 1 8 7 6 0
  4.  * dp[i][j]跳到第i格跳了j次的价值和
  5.  */
  6. public class Main {
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         int n = sc.nextInt();
  10.         int p = sc.nextInt();
  11.         int t = sc.nextInt();
  12.         int[] w = new int[n+2];
  13.         int[][] dp = new int[n+2][n+2];
  14.         for(int i=1;i<=n;i++) {
  15.             w[i] = sc.nextInt();
  16.         }
  17.         for(int i=0;i<n+2;i++) {
  18.             Arrays.fill(dp[i], -0x3f3f3f);
  19.         }
  20.         for(int i=1;i<=p&&i<=n+1;i++) {
  21.             dp[i][1] = w[i];
  22.         }
  23.         for(int i=1;i<=n+1;i++) {
  24.             for(int j=2;j<=t;j++) {
  25.                 //跳k格
  26.                 for(int k=1;k<=p&&k<=i;k++) {
  27.                     dp[i][j] = Math.max(dp[i][j], dp[i-k][j-1]+w[i]);
  28.                 }
  29.             }
  30.         }
  31.         System.out.println(dp[n+1][t]);
  32.     }
  33. }

5. 和谐宿舍2

我的某室友学过素描，墙上有n张他的作品。这些作品都是宽度为1，高度不定的矩形，从左到右排成一排，且底边在同一水平线上。宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。在能够把所有作品和谐掉的前提下，我们希望这些木板的面积和最小，问最小面积和。

输入格式

第一行两个数n和m，表示作品数和木板数；第二行n个数Hi，表示从左到右第i个作品的高度。

输出格式

一行一个数ans，表示答案。

样例输入

5 2
4 2 3 5 4

样例输出

22

数据规模和约定

对于30%的数据：1<=n，m<=10；对于100%的数据：1<=n，m<=100，1<=Hi<=10000。

代码：

  1. import java.util.*;
  2. /*
  3.  * dp[i][j] 用j块板来挡前i张作品
  4.  * max[i][j] 第i到第j作品的最大高度
  5.  */
  6. public class Main { 
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.         int n = sc.nextInt();
  10.         int m = sc.nextInt();
  11.         int INF = 0x3f3f3f;
  12.         int[] arr = new int[n+1];
  13.         int[][] max = new int[n+1][n+1];
  14.         int[][] dp = new int[n+1][n+1];
  15.         for(int i=1;i<=n;i++) {
  16.             arr[i] = sc.nextInt();
  17.         }
  18.         //求i到j作品的最大高度
  19.         for(int i=1;i<=n;i++) {
  20.             for(int j=i;j<=n;j++) {
  21.                 max[i][j] = Math.max(max[i][j-1], arr[j]);
  22.             }
  23.         }
  24.         for(int i=0;i<=n;i++) {
  25.             Arrays.fill(dp[i], INF);
  26.         }
  27.         //只有一块板的时候
  28.         for(int i=1;i<=n;i++) {
  29.             dp[i][1] = max[1][i]*i;
  30.         }
  31.         for(int i=1;i<=n;i++) {
  32.             for(int j=2;j<=m && j<=i;j++) {
  33.                 //遍历木板的宽度
  34.                 for(int k=1;k<=i-j+1;k++) {//j-1<=i-k
  35.                     dp[i][j] = Math.min(dp[i][j], dp[i-k][j-1]+max[i-k+1][i]*k);
  36.                 }
  37.             }
  38.         }
  39.         System.out.println(dp[n][m]);
  40.     }
  41. }

6. 最大值路径

刷微博，编程序。如下图所示，@北京发布 提出了如下“头脑震荡”问题。对此问题做一般化描述：
有n阶方阵，从矩阵的左下角元素为起点，从行或列（水平或垂直）两个方向上移动，直到右上角。求出有多少条路径可以使得经过的元素累加值最大，最大值是多少。

输入格式

共有n+1行。
第一行整数n，表示矩阵的阶数，2<=n<=10。第二行起，每行n个整数，以空格分隔，共n行。

输出格式

一行，两个空格分隔的数，第一个表示最大值路径的条数，第二个表示最大值。

样例输入

5
4 5 4 5 6
2 6 5 4 6
2 6 6 5 2
4 5 2 2 5
5 2 5 6 4

样例输出

3 47

代码：

  1. import java.util.*;
  2. /*
  3.  * dp[i][j] 到达当前(i,j)点的最大值和
  4.  */
  5. public class Main { 
  6.     static int[][] dp;
  7.     static int cnt=1;
  8.     static int n;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt();
  12.         int[][] arr = new int[n][n];
  13.         dp = new int[n][n];
  14.         for(int i=0;i<n;i++) {
  15.             for(int j=0;j<n;j++) {
  16.                 arr[i][j] = sc.nextInt();
  17.             }
  18.         }
  19.         for(int i=0;i<n;i++) {
  20.             Arrays.fill(dp[i], -0x3f3f3f);
  21.         }
  22.         dp[n-1][0] = arr[n-1][0];
  23.         //将最左侧一列初始化
  24.         for(int i=n-2;i>=0;i--) {
  25.             dp[i][0] = dp[i+1][0]+arr[i][0];
  26.         }
  27.         //将最下面一行初始化
  28.         for(int j=1;j<n;j++) {
  29.             dp[n-1][j] = dp[n-1][j-1]+arr[n-1][j];
  30.         }
  31.         //遍历到达每个点的最大值
  32.         for(int i=n-2;i>=0;i--) {
  33.             for(int j=1;j<n;j++) {
  34.                 //只能从(i+1,j)和(i,j-1)两个点到达(i,j),取大的值加上(i,j)当前的值
  35.                 dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])+arr[i][j];
  36.             }
  37.         }
  38.         System.out.println(dfs(0,n-1)+" "+dp[0][n-1]);
  39.     }
  40.     //回溯遍历寻找最大路径
  41.     public static int dfs(int x,int y) {
  42.         //如果在边缘，则不需再判断，因为后面只有一条直的路径
  43.         if(x!=n-1 && y!=0) {
  44.             //两条路径都为最大的路径
  45.             if(dp[x][y-1] == dp[x+1][y]) {
  46.                 cnt++;
  47.                 dfs(x,y-1);
  48.                 dfs(x+1,y);
  49.             }
  50.             //dp[x][y-1]为最大的路径
  51.             if(dp[x][y-1] > dp[x+1][y]) {
  52.                 dfs(x,y-1);
  53.             }
  54.             //dp[x+1][y]为最大的路径
  55.             if(dp[x][y-1] < dp[x+1][y]) {
  56.                 dfs(x+1,y);
  57.             }
  58.         }
  59.         return cnt;
  60.     }
  61. }

7. 矩阵乘法

有n个矩阵，大小分别为a0*a1, a1*a2, a2*a3, ..., a[n-1]*a[n]，现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。两个大小分别为p*q和q*r的矩阵相乘时的运算次数计为p*q*r。

输入格式

输入的第一行包含一个整数n，表示矩阵的个数。第二行包含n+1个数，表示给定的矩阵。

输出格式

输出一个整数，表示最少的运算次数。

样例输入

3
1 10 5 20

样例输出

150

数据规模和约定

1<=n<=1000, 1<=ai<=10000。

代码：

  1. import java.util.*;
  2. /*
  3.  * dp[i][j] 第i到j个矩阵之间运算次数
  4.  */
  5. public class Main { 
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         long[] arr = new long[n+1];
  10.         long[][] dp = new long[n+1][n+1];
  11.         for(int i=0;i<=n;i++) {
  12.             arr[i] = sc.nextInt();
  13.         }
  14.         for(int i=0;i<=n;i++) {
  15.             Arrays.fill(dp[i], (long) 1e18);
  16.         }
  17.         for(int i=1;i<=n;i++) {
  18.             dp[i][i] = 0;
  19.         }
  20.         for(int l=1;l<=n;l++) {//k表示dp数组中横纵坐标之差
  21.             for(int i=1;i<=n-l;i++) {
  22.                 int j = i+l;
  23.                 for(int k=i;k<j;k++) {
  24.                     dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+arr[i-1]*arr[k]*arr[j]);
  25.                 }
  26.             }
  27.         }
  28.         System.out.println(dp[1][n]);
  29.     }
  30. }

8. 合并石子

在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。

输入格式

输入第一行包含一个整数n，表示石子的堆数。
接下来一行，包含n个整数，按顺序给出每堆石子的大小 。

输出格式

输出一个整数，表示合并的最小花费。

样例输入

5
1 2 3 4 5

样例输出

33

数据规模和约定

1<=n<=1000, 每堆石子至少1颗，最多10000颗。

代码：

  1. import java.util.*;
  2. /*
  3.  * dp[i][j] 第i到j堆石子的最小花费
  4.  */
  5. public class Main { 
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         int[] arr = new int[n+1];
  10.         int[] sum = new int[n+1];
  11.         long[][] dp = new long[n+1][n+1];
  12.         for(int i=1;i<=n;i++) {
  13.             arr[i] = sc.nextInt();
  14.         }
  15.         for(int i=1;i<=n;i++) {
  16.             Arrays.fill(dp[i], (long) 1e18);
  17.         }
  18.         for(int i=1;i<=n;i++) {
  19.             dp[i][i] = 0;
  20.             sum[i] = sum[i-1] + arr[i];
  21.         }
  22.         for(int l=1;l<=n;l++) {
  23.             for(int i=1;i<=n-l;i++) {
  24.                 int j = i+l;
  25.                 for(int k=i;k<j;k++) {
  26.                     dp[i][j] = Math.min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
  27.                 }
  28.             }
  29.         }
  30.         System.out.println(dp[1][n]);
  31.     }
  32. }

9. 拿糖果

妈妈给小B买了N块糖！但是她不允许小B直接吃掉。假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。现在小B希望知道最多可以拿多少糖。

输入格式

一个整数N

输出格式

最多可以拿多少糖

样例输入

15

样例输出

6

数据规模和约定

N <= 100000

代码：

  1. import java.util.*;
  2. /*
  3.  * dp[i] i块糖中可以最多拿的数量
  4.  */
  5. public class Main { 
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         int[] dp = new int[n+1];
  10.         for(int i=2+2;i<=n;i++) {
  11.             for(int p=2;p*p<=i;p++) {
  12.                 //是质因数
  13.                 if(i%p==0 && IsPrime(p)) {
  14.                     dp[i] = Math.max(dp[i], p+dp[i-p-p]);
  15.                 }
  16.             }
  17.         }
  18.         System.out.println(dp[n]);
  19.     }
  20.     public static boolean IsPrime(int n) {
  21.         if(n==1) {
  22.             return false;
  23.         }
  24.         for(int i=2;i<=Math.sqrt(n);i++) {
  25.             if(n%i==0) {
  26.                 return false;
  27.             }
  28.         }
  29.         return true;
  30.     }
  31. }

10. 求最大值

给n个有序整数对ai bi，你需要选择一些整数对 使得所有你选定的数的ai+bi的和最大。并且要求你选定的数对的ai之和非负，bi之和非负。

输入格式

输入的第一行为n，数对的个数。以下n行每行两个整数 ai bi

输出格式

输出你选定的数对的ai+bi之和

样例输入

5
-403 -625
-847 901
-624 -708
-293 413
886 709

样例输出

1715

数据规模和约定

1<=n<=100。-1000<=ai,bi<=1000

代码：

  1. import java.util.*;
  2. /*
  3.  * dp[i][j] 前i个数对中，选的a和为j时，b和最大值
  4.  */
  5. public class Main { 
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int t = 100000;
  9.         int max = 200000;
  10.         int n = sc.nextInt();
  11.         int[] a = new int[n+1];
  12.         int[] b = new int[n+1];
  13.         int[][] dp = new int[n+1][max+1];
  14.         
  15.         for(int i=1;i<=n;i++) {
  16.             a[i] = sc.nextInt();
  17.             b[i] = sc.nextInt();
  18.         }
  19.         for(int i=0;i<=n;i++) {
  20.             Arrays.fill(dp[i], -0x3f3f3f);
  21.         }
  22.         //a有可能是负，下标不能为负，所以加上偏移量t
  23.         for(int i=1;i<=n;i++) {
  24.             dp[i][t+a[i]] = b[i];
  25.         } 
  26.         for(int i=1;i<=n;i++) {
  27.             for(int j=0;j<=max;j++) {
  28.                 //不使用a[i]使a的和为j
  29.                 dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
  30.                 //判断是否越界
  31.                 if(j-a[i]>=0 && j-a[i]<=max) {
  32.                     //使用a[i]使a的和为j
  33.                     dp[i][j] = Math.max(dp[i][j], dp[i-1][j-a[i]]+b[i]);
  34.                 }
  35.             }
  36.         }
  37.         int res = 0;
  38.         //从t开始，保证a的和为正
  39.         for(int i=t;i<=max;i++) {
  40.             //b的和非负
  41.             if(dp[n][i] >=0) {
  42.                 //b的和加上a的和减去偏移量t
  43.                 res = Math.max(res, dp[n][i]+i-t);
  44.             }
  45.         }
  46.         System.out.println(res);
  47.     }
  48. }

11. 概率计算

生成n个∈[a,b]的随机整数，输出它们的和为x的概率。

输入格式

一行输入四个整数依次为n，a，b，x，用空格分隔。

输出格式

输出一行包含一个小数位和为x的概率，小数点后保留四位小数

样例输入

2 1 3 4

样例输出

0.3333

数据规模和约定

对于50%的数据，n≤5。对于100%的数据，n≤100,b≤100。

代码：

  1. import java.util.*;
  2. /*
  3.  * dp[i][j] 前i个整数中和等于j的概率
  4.  * 假设第i个数为k，则i个数和为j的情况等价于前i-1个数和为j-k的概率乘以k的概率，即：
  5.  * dp[i][j] = dp[i-1][j-k]*1.0/(b-a+1)
  6.  */
  7. public class Main { 
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         int n = sc.nextInt();
  11.         int a = sc.nextInt();
  12.         int b = sc.nextInt();
  13.         int x = sc.nextInt();
  14.         double[][] dp = new double[n+1][n*b+1];
  15.         for(int i=a;i<=b;i++) {
  16.             dp[1][i] = 1.0/(b-a+1);
  17.         }
  18.         for(int i=2;i<=n;i++) {
  19.             //k是[a,b]之间的数
  20.             for(int k=a;k<=b;k++) {
  21.                 for(int j=1;j<=x;j++) {
  22.                     if(j>k) {
  23.                         dp[i][j] += dp[i-1][j-k]*1.0/(b-a+1);
  24.                     }             
  25.                 }
  26.             }
  27.         }
  28.         System.out.printf("%.4f", dp[n][x]);
  29.     }
  30. }

12. 印章

共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。

输入格式

一行两个正整数n和m

输出格式

一个实数P表示答案，保留4位小数。

样例输入

2 3

样例输出

0.7500

数据规模和约定

1≤n，m≤20

代码：

  1. import java.util.*;
  2. /*
  3.  * dp[i][j] i张印章j种印章的概率
  4.  * 1.如果i<j,则集齐的概率为0
  5.  * 2.如果i==j&&j==1,即i和j相等且印章重复为同一种，概率为 n*pow(1/n,i) = pow(1/n,i-1);
  6.  * 3.如果i>j&&j!=1,分两种情况:
  7.  *      3.1 第i张的种类之前已经出现过,概率为dp[i-1][j]*j*1.0/n
  8.  *      3.2 第i张的种类是新的,以前没有出现过,概率为dp[i-1][j-1]*(n-(j-1))*1.0/n
  9.  */
  10. public class Main {
  11.     public static void main(String[] args) {
  12.         Scanner sc = new Scanner(System.in);
  13.         int n = sc.nextInt();
  14.         int m = sc.nextInt();
  15.         double[][] dp = new double[m+1][n+1];
  16.         for(int i=1;i<=m;i++) {
  17.             for(int j=1;j<=n;j++) {
  18.                 if(i<j) {
  19.                     dp[i][j] = 0;
  20.                 }
  21.                 if(i==j && j==1) {
  22.                     dp[i][j] = Math.pow(1.0/n,i-1);
  23.                 }
  24.                 else {
  25.                     dp[i][j] = dp[i-1][j]*j*1.0/n + dp[i-1][j-1]*(n-(j-1))*1.0/n;
  26.                 }
  27.             }
  28.         }
  29.         System.out.printf("%.4f",dp[m][n]);
  30.     }
  31. }

13. 最短Hamilton路径（状态压缩）

给定一张n个点的带权无向图，点从 0∼n−1标号，求起点0到终点 n−1的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数n。

接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（记为 a[i,j]）。

对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x]，并且 a[x,y]+a[y,z]≥a[x,z]。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

1≤n≤20
0≤a[i,j]≤107

输入样例：

5

0 2 4 5 1

2 0 6 5 3

4 6 0 8 3

5 5 8 0 5

1 3 3 5 0

输出样例：

18

讲解视频：AcWing 91. 最短Hamilton路径 - AcWing

代码：

  1. import java.util.*;
  2. /*
  3. f[state][j] = f[state_k][k] + w[k][j], state_k代表除去j之后合集，state_k要包含k
  4. */
  5. public class Main {
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         int[][] w = new int[n][n];
  10.         int[][] f = new int[1<<n][n];
  11.         for(int i=0;i<n;i++){
  12.             for(int j=0;j<n;j++){
  13.                 w[i][j] = sc.nextInt();
  14.             }
  15.         }
  16.         for(int i=0;i< 1<<n;i++) {
  17.             Arrays.fill(f[i], Integer.MAX_VALUE>>1);
  18.         }
  19.         f[1][0] = 0;
  20.         for(int i=0;i < 1<<n;i++){
  21.             for(int j=0;j<n;j++){
  22.                 //第i状态下j是不是1，看状态是否合法（是否包含j）
  23.                 if((i>>j & 1)==1){
  24.                     for(int k=0;k<n;k++){
  25.                         if((i >> k & 1)==1){
  26.                             f[i][j] = Math.min(f[i][j], f[i-(1<<j)][k]+w[k][j]);
  27.                         }
  28.                     }
  29.                 }
  30.             }
  31.         }
  32.         System.out.println(f[(1<<n) - 1][n-1]);
  33.     }
  34. }

14. 遍历（状态压缩）

问题描述

给定两张N个点的图，要求找出图中经过指定M个点的一条路径，希望路径最短。

输入格式

第一行两个整数N,M。之后n行每行n个整数，其中第i行的第j个整数x表示i到j的路的长度(i,j从0到n-1)。0表示两点之间没有路。之后一行M个整数，表示指定的点的编号，编号从0开始。

输出格式

一行一个整数表示路径长度。无解输出-1。

样例输入

3 2
0 1 2
3 0 4
5 6 0
0 1

样例输出

1

数据规模和约定

N <= 100 M <= 15

代码：

  1. /*
  2. 采用Floyd求每个点之间最短路径，采用3.最短Hamilton路径中路径压缩的思想。
  3. */
  4. import java.util.*;
  5.  
  6. public class Main {
  7.     static int[][] w;//两点直接的距离
  8.     static int n,m;
  9.     static int[] q;
  10.     static int[][] f;
  11.     public static void main(String[] args) {
  12.         Scanner sc = new Scanner(System.in);
  13.         n = sc.nextInt();
  14.         m = sc.nextInt();
  15.         w = new int[n][n];
  16.         q = new int[m];
  17.         f = new int[1<<m][n];
  18.         for(int i=0;i<n;i++) {
  19.             for(int j=0;j<n;j++) {
  20.                 w[i][j] = sc.nextInt();
  21.                 if(i!=j && w[i][j]==0) {
  22.                     //MAX_VALUE右移1位为了防止后续相加越位
  23.                     w[i][j] = Integer.MAX_VALUE>>1;
  24.                 }
  25.             }
  26.         }
  27.         for(int i=0;i<m;i++) {
  28.             q[i] = sc.nextInt();
  29.         }
  30.         Floyd();
  31.         for(int i=0;i < 1<<m;i++) {
  32.             Arrays.fill(f[i], Integer.MAX_VALUE>>1);
  33.         }
  34.         for(int i=0;i<m;i++) {
  35.             f[1<<i][i] = 0;
  36.         }
  37.         for(int i=0;i<1<<m;i++) {
  38.             for(int j=0;j<m;j++) {
  39.                 if((i>>j & 1)==1) {
  40.                     for(int k=0;k<m;k++) {
  41.                         if((i>>k & 1) ==1) {
  42.                             f[i][j] = Math.min(f[i][j], f[i-(1<<j)][k]+w[q[k]][q[j]]);
  43.                         }
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.         int min = Integer.MAX_VALUE;
  49.         for(int i=0;i<m;i++) {
  50.             min = Math.min(min, f[(1<<m)-1][i]);
  51.         }
  52.         if(min == Integer.MAX_VALUE) {
  53.             System.out.print(-1);
  54.         }
  55.         else {
  56.             System.out.println(min);
  57.         }
  58.     }
  59.     //计算两点之间最短路径
  60.     public static void Floyd() {
  61.         for(int k=0;k<n;k++) {
  62.             for(int i=0;i<n;i++) {
  63.                 for(int j=0;j<n;j++) {
  64.                     w[i][j] = Math.min(w[i][j], w[i][k]+w[k][j]);
  65.                 }
  66.             }
  67.         }
  68.     }
  69. }

数位DP

数位DP学习整理（数位DP看完这篇你就会了）_unique_pursuit的博客-CSDN博客

15. 二进制问题（数位dp）

小蓝最近在学习二进制。他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗？

输入描述

输入一行包含两个整数 N 和 K。

输出描述

输出一个整数表示答案。

输入样例

7 2

输出样例

3

评测用例规模与约定

对于 30% 的评测用例，1≤N≤106,1≤K≤10。

对于 60% 的评测用例，1≤N≤2×109,1≤K≤30。

对于所有评测用例，1≤N≤1018,1≤K≤50。

代码：

  1. import java.util.*;
  2.  
  3. public class Main { 
  4.     static long n;
  5.     static int k;
  6.     static long[][] dp = new long[66][66];
  7.     static String string;
  8.     static int[] num = new int[66];
  9.     public static void main(String[] args){
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextLong();
  12.         k = sc.nextInt();
  13.         for (int i = 0; i < dp.length; i++) {
  14.             Arrays.fill(dp[i], -1);
  15.         }
  16.         System.out.println(solve(n));
  17.     }
  18.     /*
  19.      * 当前取的位长度，已有1的个数，limit判断前面的位是否按照边界n来取的
  20.      * 如：n的二进制是1001.... , 当前是1000....则后边的数位都比n小，0或者1可以随便取，limit一直false
  21.      */
  22.     public static long dfs(int len, int sum, boolean limit) {
  23.         //1的数量等于k，则符合题意返回1，加1
  24.         if (len == 0) {
  25.             return sum == k ? 1 : 0;
  26.         }
  27.         //如果当前状态处理过并且对后边取位没有影响
  28.         if (dp[len][sum] != -1 && !limit) {
  29.             return dp[len][sum];
  30.         }
  31.         //如果前面按照n边界取，最大可取n对应的位的数
  32.         int up;
  33.         if (limit) {
  34.             up = num[len];
  35.         }
  36.         //没有影响，可以随便取，最大取1
  37.         else {
  38.             up = 1;
  39.         }
  40.         long res = 0;
  41.         for (int i = 0; i <= up; i++) {
  42.             if (i == 1) {
  43.                 res += dfs(len-1, sum+1, limit && i == up);
  44.             }
  45.             else {
  46.                 res += dfs(len-1, sum, limit && i == up);
  47.             }
  48.         }
  49.         return dp[len][sum] = res;
  50.     }
  51.     public static long solve(long n) {
  52.         int len = 0;
  53.         //转为倒序二进制
  54.         while (n != 0) {
  55.             num[++len] = (int)(n & 1);
  56.             n >>= 1;
  57.         }
  58.         return dfs(len, 0, true);
  59.     }
  60. }

并查集

图论——并查集(详细版)_哔哩哔哩_bilibili

1.修改数组

给定一个长度为 N 的数组 A = [A1, A2, · · · AN ]，数组中有可能有重复出现 的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A2,A3,··· ,AN。当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则 小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai 没有在 A1 ∼ Ai−1 中出现过。当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。 现在给定初始的 A 数组，请你计算出最终的 A 数组。

输入描述

第一行包含一个整数 N。 第二行包含N个整数A1,A2,··· ,AN

输出描述

输出N个整数，依次是最终的A1,A2,··· ,AN。

样例输入

5

2 1 1 3 4

样例输出

2 1 3 4 5

代码：

  1. import java.util.*;
  2.  
  3. public class Main { 
  4.     static int[] f = new int[2000000];
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         for (int i = 1; i < f.length; i++) {
  8.             f[i] = i;
  9.         }
  10.         int n = sc.nextInt();
  11.         int[] arr = new int[n+1];
  12.         for (int i = 1; i <= n; i++) {
  13.             arr[i] = sc.nextInt();
  14.         }
  15.         for (int i = 1; i <= n; i++) {
  16.             //查找该点的父亲
  17.             int fa = find(arr[i]);
  18.             //该点等于父亲
  19.             arr[i] = fa;
  20.             //父亲变为新节点+1
  21.             f[fa] = find(fa+1);
  22.         }
  23.         for (int i = 1; i <= n ; i++) {
  24.             System.out.print(arr[i]+" ");
  25.         }
  26.     }
  27.     //并查集
  28.     public static int find(int x) {
  29.         if (f[x] != x) {
  30.             f[x] = find(f[x]);
  31.         }
  32.         return f[x];
  33.     }
  34. }

贪心算法

一个视频搞懂贪心算法_哔哩哔哩_bilibili

1.防御力

小明最近在玩一款游戏。对游戏中的防御力很感兴趣。我们认为直接影响防御的参数为“防御性能”，记作d，而面板上有两个防御值A和B，与d成对数关系，A=2^d,B=3^d（注意任何时候上式都成立）。在游戏过程中，可能有一些道具把防御值A增加一个值，有另一些道具把防御值B增加一个值。现在小明身上有n1个道具增加A的值和n2个道具增加B的值，增加量已知。现在已知第i次使用的道具是增加A还是增加B的值，但具体使用那个道具是不确定的，请找到一个字典序最小的使用道具的方式，使得最终的防御性能最大。初始时防御性能为0，即d=0，所以A=B=1。

输入描述
输入的第一行包含两个数n1,n2，空格分隔。第二行n1个数，表示增加A值的那些道具的增加量。
第三行n2个数，表示增加B值的那些道具的增加量。第四行一个长度为n1+n2的字符串，由0和1组成，表示道具的使用顺序。0表示使用增加A值的道具，1表示使用增加B值的道具。输入数据保证恰好有n1个0，n2个1。

输出格式
对于每组数据，输出n1+n2+1行，前n1+n2行按顺序输出道具的使用情况，若使用增加A值的道具，输出Ax，x为道具在该类道具中的编号（从1开始）。若使用增加B值的道具则输出Bx。最后一行输出一个大写字母E。

样例输入

1 2
4
2 8
101

样例输出

B2
A1
B1
E

样例说明
操作 d A B
初始 0 1 1
B2 2 4 9
A1 3 8 27
B1 log3(29) 2^(log3(29)) 29
代码：

  1. import java.util.*;
  2. /*
  3.  * A按照升序，B按照降序时，最后的结果最大
  4.  */
  5. public class Main1 {
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int n1 = sc.nextInt();
  9.         int n2 = sc.nextInt();
  10.         int[] a = new int[n1+1];
  11.         int[] b = new int[n2+1];
  12.         //list存储A和B的下标
  13.         ArrayList<Integer> list1 = new ArrayList<Integer>();
  14.         ArrayList<Integer> list2 = new ArrayList<Integer>();
  15.         for (int i = 1; i <= n1; i++) {
  16.             a[i] = sc.nextInt();
  17.             list1.add(a[i]);
  18.         }
  19.         for (int i = 1; i <= n2; i++) {
  20.             b[i] = sc.nextInt();
  21.             list2.add(b[i]);
  22.         }
  23.         String string = sc.next();
  24.         Arrays.sort(a);
  25.         Arrays.sort(b);
  26.         int index1 = 1, index2 = n2;
  27.         for (int i = 0; i < string.length(); i++) {
  28.             //A升序
  29.             if (string.charAt(i) == '0') {
  30.                 System.out.print("A");
  31.                 System.out.println(list1.indexOf(a[index1++])+1);
  32.             }
  33.             //B降序
  34.             if (string.charAt(i) == '1') {
  35.                 System.out.print("B");
  36.                 System.out.println(list2.indexOf(b[index2--])+1);
  37.             }
  38.         }
  39.         System.out.println("E");
  40.     }
  41. }

2.排座椅

上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。

输入描述

输入第一行，有5各用空格隔开的整数，分别是M，N，K，L，D（2<=N，M<=1000，0<=K<M，0<=L<N，D<=2000）。下来D行，每行有4个用空格隔开的整数，第i行的4个整数Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。输入数据保证最优方案的唯一性。

输出描述

第一行包含K个整数，a[1] a[2] … a[K]，表示第a[1]行和a[1+1]行之间、第a[2]行和第a[2+1]行之间、…、第a[K]行和第a[K+1]行之间要开辟通道，其中a[i]< a[i+1]，每两个整数之间用空格隔开（行尾没有空格）。第二行包含L个整数，b[1] b[2] … b[k]，表示第b[1]列和b[1+1]列之间、第b[2]列和第b[2+1]列之间、…、第b[L]列和第b[L+1]列之间要开辟通道，其中b[i]< b[i+1]，每两个整数之间用空格隔开（行尾没有空格）。

输入样例

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

输出样例

2
2 4

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int m = sc.nextInt();
  7.         int n = sc.nextInt();
  8.         int k = sc.nextInt();
  9.         int l = sc.nextInt();
  10.         int d = sc.nextInt();
  11.         //记录位置和出现的次数
  12.         int[] cnt1 = new int[m];
  13.         int[] cnt2 = new int[n];
  14.         for (int i = 0; i < d; i++) {
  15.             int x = sc.nextInt();
  16.             int y = sc.nextInt();
  17.             int p = sc.nextInt();
  18.             int q = sc.nextInt();
  19.             //在同一行，进行竖向隔离
  20.             if (x == p) {
  21.                 int index = Math.min(y, q);
  22.                 cnt2[index]++;
  23.             }
  24.             //在同一列，进行横向隔离
  25.             else if (y == q) {
  26.                 int index = Math.min(x, p);
  27.                 cnt1[index]++;
  28.             }
  29.         }
  30.         //尽可能多的使用横向通道将学生隔开，将cnt1中前k大的下标输出
  31.         ArrayList<Integer> list1 = new ArrayList<Integer>();
  32.         //查找前k大的数的下标存进list
  33.         for (int i = 0; i < k; i++) {
  34.             int max = -1, index = -1;
  35.             for (int j = 0; j < cnt1.length; j++) {
  36.                 if (max < cnt1[j]) {
  37.                     max = cnt1[j];
  38.                     index = j;
  39.                 }
  40.             }
  41.             //将最大的设为0，方便查找除它外最大的
  42.             cnt1[index] = 0;
  43.             list1.add(index);
  44.         }
  45.         //尽可能多的使用竖向通道将学生隔开，将cnt2中前l大的下标输出
  46.         ArrayList<Integer> list2 = new ArrayList<Integer>(); 
  47.         //查找前l大的数的下标存进list
  48.         for (int i = 0; i < l; i++) {
  49.             int max = -1, index = -1;
  50.             for (int j = 0; j < cnt2.length; j++) {
  51.                 if (max < cnt2[j]) {
  52.                     max = cnt2[j];
  53.                     index = j;
  54.                 }
  55.             }
  56.             //将最大的设为0，方便查找除它外最大的
  57.             cnt2[index] = 0;
  58.             list2.add(index);
  59.         }
  60.         //将list中序号进行排序输出
  61.         list1.sort(null);
  62.         list2.sort(null);
  63.         for (int i = 0; i < list1.size(); i++) {
  64.             System.out.print(list1.get(i)+" ");
  65.         }
  66.         System.out.println();
  67.         for (int i = 0; i < list2.size(); i++) {
  68.             System.out.print(list2.get(i)+" ");
  69.         }
  70.     }
  71. }

3.付账问题

几个人一起出去吃饭是常有的事。但在结帐的时候，常常会出现一些争执。现在有 n 个人出去吃饭，他们总共消费了 S 元。其中第 i 个人带了 ai 元。幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。你需要输出最小的标准差是多少。标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。形式化地说，设第 i 个人付的钱为 bi 元，那么标准差为 :

输入格式

第一行包含两个整数 n、S；第二行包含 n 个非负整数 a1, …, an。

输出格式

输出最小的标准差，四舍五入保留 4 位小数。

数据范围

1≤n≤5×105,

0≤ai,S≤109

输入样例1：

5 2333

666 666 666 666 666

输出样例1：

0.0000

输入样例2：

10 30

2 1 4 7 4 8 3 6 4 7

1

2

输出样例2：

0.7928

 代码：

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.*;
  4.  
  5. public class Main {
  6.     public static void main(String[] args) throws Exception {
  7.         BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  8.         String[] strings = bf.readLine().split(" ");
  9.         int n = Integer.parseInt(strings[0]);
  10.         long s = Long.parseLong(strings[1]);
  11.         long[] arr = new long[n];
  12.         String[] data = bf.readLine().split(" ");
  13.         //每个人带的钱数
  14.         for (int i = 0; i < arr.length; i++) {
  15.             arr[i] = Long.parseLong(data[i]);
  16.         }
  17.         double avg = 1.0*s/n;
  18.         double sum = 0;
  19.         Arrays.sort(arr);
  20.         for (int i = 0; i < n; i++) {
  21.             //钱数少于平均值，将自己的钱全部拿出
  22.             if (arr[i]*(n-i) < s) {
  23.                 sum += Math.pow(arr[i]-avg, 2);
  24.                 //更新剩余的总金额
  25.                 s -= arr[i];
  26.             }
  27.             //多于平均值，后边的都会多于平均值
  28.             else {
  29.                 double cur_avg = 1.0*s/(n-i);
  30.                 sum += Math.pow(cur_avg-avg, 2)*(n-i);
  31.                 break;
  32.             }
  33.         }
  34.         System.out.printf("%.4f", Math.sqrt(sum/n));
  35.     }
  36. }

4.旅行家的预算

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 D1、汽车油箱的容量 C（以升为单位）、每升汽油能行驶的距离 D2、出发点每升汽油价格P 和沿途油站数N（N 可以为零），油站 i 离出发点的距离Di、每升汽油价格 Pi（i=1，2，⋯N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。

输入描述

第一行，D1，C，D2，P，N。接下来有 N 行。第i+1 行，两个数字，油站i 离发点的距离 Di 和每升汽油价格Pi。

输出描述

输出所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。

样例输入

275.6 11.9 27.4 2.8 2

102.0 2.9

220.0 2.2

样例输出

26.95

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) throws Exception {
  5.         Scanner sc = new Scanner(System.in);
  6.         double d1 = sc.nextDouble();
  7.         double c = sc.nextDouble();
  8.         double d2 = sc.nextDouble();
  9.         double p = sc.nextDouble();
  10.         int n = sc.nextInt();
  11.         //起点+n个加油站+终点
  12.         double[] distance = new double[n+2];
  13.         double[] price = new double[n+2];
  14.         for (int i = 1; i <= n; i++) {
  15.             distance[i] = sc.nextDouble();
  16.             price[i] = sc.nextDouble();
  17.         }
  18.         //起点
  19.         distance[0] = 0;
  20.         price[0] = p;
  21.         //终点
  22.         distance[n+1] = d1;
  23.         price[n+1] = 0;
  24.         //如果两加油站需要的油量比油箱总量大，无解
  25.         for (int i = 0; i <= n; i++) {
  26.             if (distance[i+1]-distance[i] > c*d2) {
  27.                 System.out.println("No Solution");
  28.                 return;
  29.             }
  30.         }
  31.         double perMaxDis = c*d2;
  32.         double Allprices = 0;
  33.         double curOil = 0;
  34.         //当前加油站
  35.         int i = 0;
  36.         while (i <= n){
  37.             //可选择的加油站
  38.             int j = 0;
  39.             //查找能到达的价格低的加油站
  40.             for (j = i+1; j <= n+1; j++) {
  41.                 //到达不了j加油站，只能到上一个
  42.                 if (distance[j]-distance[i] > perMaxDis) {
  43.                     j--;
  44.                     break;
  45.                 }
  46.                 //下一个比当前的油价便宜的加油站
  47.                 if (price[j] <= price[i]) {
  48.                     break;
  49.                 }
  50.             }
  51.             //能到比当前便宜的加油站，只需使油量恰好到下一便宜的加油站
  52.             if (price[j] <= price[i]) {
  53.                 Allprices += price[i]*((distance[j]-distance[i])/d2-curOil);
  54.                 curOil = 0;
  55.             }
  56.             //到不了下一个便宜的加油站即当前是最便宜的，加满
  57.             else {
  58.                 Allprices += (c-curOil)*price[i];
  59.                 //开完后剩余的油
  60.                 curOil = c-(distance[j]-distance[i])/d2;
  61.             }
  62.             //从i开到j
  63.             i = j;
  64.         }
  65.         System.out.printf("%.2f", Allprices);
  66.     }
  67. }

5.巧克力

小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 x 天的巧克力。

输入描述

输入的第一行包含两个整数x,n，分别表示需要吃巧克力的天数和巧克力的种类数。接下来 n 行描述货架上的巧克力，其中第 i 行包含三个整数ai,bi,ci，表示第 i 种巧克力的单价为 ai，保质期还剩 bi 天（从现在开始的 bi 天可以吃），数量为 ci。

输出描述

输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 x 天的购买方案，输出 −1。

输入样例

10 3
1 6 5
2 7 3
3 10 10

输出样例

18

样例说明

一种最佳的方案是第 1 种买 5 块，第 2 种买 2 块，第 3 种买 3 块。前 5天吃第 1 种，第 6、7 天吃第 2 种，第 8 至 10 天吃第 3 种。

评测用例规模与约定

对于 30% 的评测用例，n,x≤1000；

对于所有评测用例，1≤n,x≤100000，1≤ai,bi,ci≤1000000000。

代码：

  1. import java.util.*;
  2.  
  3.  
  4. public class Main {
  5.     public static class Chocolate{
  6.         int price,day,num;
  7.         public Chocolate(int price, int day, int num) {
  8.             this.price = price;
  9.             this.day = day;
  10.             this.num = num;
  11.         }
  12.     }
  13.     public static void main(String[] args) {
  14.         Scanner sc = new Scanner(System.in);
  15.         int x = sc.nextInt();
  16.         int n = sc.nextInt();        
  17.         ArrayList<Chocolate> list = new ArrayList<>();
  18.         for (int i = 0; i < n; i++) {
  19.             int a = sc.nextInt();
  20.             int b = sc.nextInt();
  21.             int c = sc.nextInt();
  22.             list.add(new Chocolate(a, b, c));
  23.         }
  24.         list.sort(new Comparator<Chocolate>() {
  25.             public int compare(Chocolate chocolate1, Chocolate chocolate2){   
  26.                 //若价格相等，则按保质期排序，否则按价格排序
  27.                 if (chocolate1.price == chocolate2.price) {
  28.                     if (chocolate1.day == chocolate2.day) {
  29.                         return chocolate1.num - chocolate2.num;
  30.                     }
  31.                     return chocolate1.day - chocolate2.day;
  32.                 }
  33.                 return chocolate1.price - chocolate2.price;
  34.             }
  35.         });
  36.         int needs = x;
  37.         long money = 0;
  38.         //从后往前一块一块的买
  39.         while (needs > 0) {
  40.             int i = 0;
  41.             while (i < n) {
  42.                 int price = list.get(i).price;
  43.                 int day = list.get(i).day;
  44.                 int num = list.get(i).num;
  45.                 //如果保质期可以满足，并且还有剩余
  46.                 if (day >= needs && num > 0) {
  47.                     list.get(i).num--;
  48.                     money += price;
  49.                     break;
  50.                 }
  51.                 i++;
  52.             }
  53.             //所有的巧克力都不满足，无解
  54.             if (i == n) {
  55.                 System.out.println(-1);
  56.                 return;
  57.             }
  58.             needs--;
  59.         }
  60.         System.out.println(money);
  61.     }
  62. }

二分查找

1. 123

小蓝发现了一个有趣的数列，这个数列的前几项如下：1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ...

小蓝发现，这个数列前 1 项是整数 1，接下来 2 项是整数 1 至 2，接下来3 项是整数 1 至 3，接下来 4 项是整数 1 至 4，依次类推。小蓝想知道，这个数列中，连续一段的和是多少？

输入格式

输入的第一行包含一个整数 T，表示询问的个数。

接下来 T 行，每行包含一组询问，其中第 i 行包含两个整数 li 和 ri，表示询问数列中第 li 个数到第 ri 个数的和。

输出格式

输出 T 行，每行包含一个整数表示对应询问的答案。

样例输入

3

1 1

1 3

5 8

样例输出

1

4

8

评测用例规模与约定

对于 10% 的评测用例， 1 ≤ T ≤ 30, 1 ≤ li ≤ ri ≤ 100。

对于 20% 的评测用例， 1 ≤ T ≤ 100, 1 ≤ li ≤ ri ≤ 1000。

对于 40% 的评测用例， 1 ≤ T ≤ 1000, 1 ≤ li ≤ ri ≤ 10 ^ 6。

对于 70% 的评测用例， 1 ≤ T ≤ 10000, 1 ≤ li ≤ ri ≤ 10 ^ 9。

对于 80% 的评测用例， 1 ≤ T ≤ 1000, 1 ≤ li ≤ ri ≤ 10 ^ 12。

对于 90% 的评测用例， 1 ≤ T ≤ 10000, 1 ≤ li ≤ ri ≤ 10 ^ 12。

对于所有评测用例， 1 ≤ T ≤ 100000, 1 ≤ li ≤ ri ≤ 10 ^ 12。

代码：

  1. import java.util.*;
  2. /* index                 sum     num
  3.  * 1         1            1       1
  4.  * 2         1 2          4       3
  5.  * 3         1 2 3        10      6
  6.  * 4         1 2 3 4      20      10
  7.  * 5         1 2 3 4 5    35      15
  8.  * n         1 2 ... n
  9.  *  
  10.  * num[i] = num[i-1] + i;
  11.  * sum[i] = sum[i-1] + num[i]
  12.  * 对于数列中任意位置 i ，一定存在一个最大的 j 满足 num[j]≤i ，这表示第 i 个数落在第 j+1 区间内
  13.  * 对于数列中任意位置i，当它落在第 j+1 个区间，它是该区间第 k 个数，则它在数列中的前缀和为：sum[j]+num[k]，其中 k=i−num[j]。
  14.  */
  15. public class Main {
  16.     static int maxn = 1414215;
  17.     static long[] sum,num;
  18.     public static void main(String[] args) {
  19.         Scanner sc = new Scanner(System.in);
  20.         int n = sc.nextInt();
  21.         sum = new long[maxn];
  22.         num = new long[maxn];
  23.         for (int i = 1; i < maxn; i++) {
  24.             num[i] = num[i-1] + i;
  25.             sum[i] = sum[i-1] + num[i];
  26.         }
  27.         for (int i = 0; i < n; i++) {
  28.             long start = sc.nextLong();
  29.             long end = sc.nextLong();
  30.             System.out.println(preSum(end)-preSum(start-1));
  31.         }
  32.     }
  33.     
  34.     public static long preSum(long i) {
  35.         int l = 0, r = maxn, mid;
  36.         //二分查找
  37.         while(l <= r) {
  38.             mid = (l+r)/2;
  39.             if (num[mid] > i) {
  40.                 r = mid - 1;
  41.             }
  42.             else {
  43.                 l = mid + 1;
  44.             }
  45.         }
  46.         l--;
  47.         return sum[l] + num[(int) (i-num[l])];
  48.     }
  49. }

2.跳石头

一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终 点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达 终点。为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳 跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能 移走起点和终点的岩石)。

输入描述：

输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终 点之间的岩石数,以及组委会至多移走的岩石数。接下来 N 行,每行一个整数,第 i 行的整数 Di(0 < Di < L)表示第 i 块岩石与 起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同 一个位置。

输出格式：
输出只包含一个整数,即最短跳跃距离的最大值。

输入样例：

25 5 2
2
11
14
17
21

输出样例：

4

说明

输入输出样例 1 说明：将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。

另：对于 20%的数据,0 ≤ M ≤ N ≤ 10。 对于50%的数据,0 ≤ M ≤ N ≤ 100。对于 100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static int[] arr;
  5.     static int m;
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int l = sc.nextInt();
  9.         int n = sc.nextInt();
  10.         m = sc.nextInt();
  11.         arr = new int[n];
  12.         for (int i = 0; i < n; i++) {
  13.             arr[i] = sc.nextInt();
  14.         }
  15.         //二分查找最合适的距离
  16.         int left = 0, right = l, mid, res = 0;
  17.         while (left <= right) {
  18.             mid = (left + right)/2;
  19.             //可以满足，继续查找看有没有更大的
  20.             if (check(mid)) {
  21.                 res = mid;
  22.                 left = mid +1;
  23.             }
  24.             //不能满足，说明距离太大了
  25.             else {
  26.                 right = mid - 1;
  27.             }
  28.         }
  29.         System.out.println(res);
  30.     }
  31.     public static boolean check(int d) {
  32.         //cnt记录搬走石头块数，pos为当前的石头到起点的距离
  33.         int cnt = 0, pos = 0;
  34.         for (int i = 0; i < arr.length; i++) {
  35.             //从起跳的石头到第i个石头的距离比d小，则可以搬走
  36.             if (arr[i] - pos < d) {
  37.                 cnt++;
  38.             }
  39.             //从起跳的石头到第i个石头的距离>=d，则不可以搬走，需要跳到该石头
  40.             else {
  41.                 pos = arr[i];
  42.             }
  43.         }
  44.         //搬走的石头数大于m，则距离d不满足
  45.         if (cnt > m) {
  46.             return false;
  47.         }
  48.         else {
  49.             return true;
  50.         }
  51.     }
  52. }

输入输出

几种常用的输入输出方式。

1：Scanner 类最慢，但是最好用，因为这个类没有缓存处理，所以io方面大量输入读取特别慢。

  1. Scanner sc=new Scanner(System.in);
  2. PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

2:bufferedreader类最不方便，但是可以满足大部分输入速度的需求，输入缺点就是只能按行读取数据，必要时需要字符串分割，转成int以及其他类型还需要转换。这种输入方式只能输入字符串然后分割处理等等，效率比Scanner高很多

  1. BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
  2. PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

3：StreamTokenizer类最快，他的底层是用字符分割，但是这样处理有很大局限性。输入string类型除了纯字母。否则混合输入会出错，特殊符号在字符串中输入也不行。

  1. StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  2. PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
  3. in.nextToken();int n=(int)in.nval;
  4. in.nextToken();long p=(long)in.nval;
  5. in.nextToken();double q=in.nval;
  6. out.print(n);
  7. out.flush();

图论

1.发现环（拓扑排序）

小明的实验室有N 台电脑，编号1⋯N。原本这N 台电脑之间有N−1 条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了 BUG。为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？

输入描述

输入范围：第一行包含一个整数N 。以下N 行每行两个整数 a,b，表示a 和 b 之间有一条数据链接相连。其中，1≤N≤105，1≤a,b≤N。输入保证合法。

输出描述

按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。

输入样例

5

1 2

3 1

2 4

2 5

5 3

输出样例

1 2 3 5

代码：

  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.     //存放相连的点都有哪些点
  6.     static ArrayList<Integer>[] edges;
  7.     //存放节点的入度
  8.     static int[] in;
  9.     //存放入度不为1的点
  10.     static ArrayList<Integer> list = new ArrayList<Integer>();
  11.     //队列用于拓扑排序
  12.     static Queue<Integer> queue = new LinkedList<Integer>();
  13.     public static void main(String[] args) throws IOException {
  14.         StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  15.         PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
  16.         st.nextToken();
  17.         int n = (int)st.nval;
  18.         in = new int[n+1];
  19.         edges = new ArrayList[n+1];
  20.         for (int i = 1; i <= n; i++) {
  21.             edges[i] = new ArrayList<Integer>();
  22.         }
  23.         for (int i = 1; i <= n; i++) {
  24.             st.nextToken();
  25.             int a = (int) st.nval;
  26.             st.nextToken();
  27.             int b = (int) st.nval;
  28.             //a,b两点相连
  29.             edges[a].add(b);
  30.             edges[b].add(a);
  31.             //两个点入度分别加一
  32.             in[a]++;
  33.             in[b]++;
  34.         }
  35.         //拓扑排序,将入度为1的点去掉，添加到队列
  36.         for (int i = 1; i <= n; i++) {
  37.             if (in[i] == 1) {
  38.                 queue.add(i);
  39.             }
  40.         }
  41.         while (!queue.isEmpty()) {
  42.             int node = queue.poll();
  43.             //将node点去掉，把与node相连的点入度都减1
  44.             for (int i : edges[node]) {
  45.                 in[i]--;
  46.                 if (in[i] == 1) {
  47.                     queue.add(i);
  48.                 }
  49.             }
  50.         }
  51.         for (int i = 1; i < in.length; i++) {
  52.             //该点入度不为1，则在环中
  53.             if (in[i] > 1) {
  54.                 list.add(i);
  55.             }
  56.         }
  57.         list.sort(null);
  58.         for (int i : list) {
  59.             pw.print(i+" ");
  60.         }
  61.         pw.flush();
  62.     }
  63. }

2. 出差（Dijkstra最短路径）

A 国有 N 个城市，编号为 1 . . . N。小明是编号为 1 的城市中一家公司的员工，今天突然接到了上级通知需要去编号为 N 的城市出差。由于疫情原因，很多直达的交通方式暂时关闭，小明无法乘坐飞机直接从城市 1 到达城市 N，需要通过其他城市进行陆路交通中转。小明通过交通信息网，查询到了 M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。同样由于疫情原因，小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络，小明也查询到了各个城市的隔离信息。（由于小明之前在城市 1，因此可以直接离开城市 1，不需要隔离）。由于上级要求，小明希望能够尽快赶到城市 N，因此他求助于你，希望你能帮他规划一条路线，能够在最短时间内到达城市 N。

输入格式

第 1 行：两个正整数 N, M，N 表示 A 国的城市数量，M 表示未关闭的路线数量

第 2 行：N 个正整数，第 i 个整数 Ci 表示到达编号为 i 的城市后需要隔离的时间

第 3 . . . M + 2 行：每行 3 个正整数，u, v, c，表示有一条城市 u 到城市 v 的双向路线仍然开通着，通过该路线的时间为 c

输出格式

第 1 行：1 个正整数，表示小明从城市 1 出发到达城市 N 的最短时间（到达城市 N，不需要计算城市 N 的隔离时间）

样例输入

4 4

5 7 3 4

1 2 4

1 3 5

2 4 3

3 4 5

样例输出

13

代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     //城市之间的时间
  5.     static int[][] distance;
  6.     //quarantine记录隔离时间
  7.     static int[] quarantine;
  8.     //记录从某城市出发的最早时间
  9.     static int[] dp;
  10.     static boolean[] visit;
  11.     static int n;
  12.     static int MAXN = 0x3f3f3f3f;
  13.     public static void main(String[] args) {
  14.         Scanner sc = new Scanner(System.in);
  15.         n = sc.nextInt();
  16.         int m = sc.nextInt();
  17.         distance = new int[n+1][n+1];
  18.         quarantine = new int[n+1];
  19.         dp = new int[n+1];
  20.         for (int i = 1; i <= n; i++) {
  21.             quarantine[i] = sc.nextInt();
  22.         }
  23.         //初始化邻接矩阵
  24.         for (int i = 1; i <= n; i++) {
  25.             Arrays.fill(distance[i], MAXN);
  26.             distance[i][i] = 0;
  27.         }
  28.         for (int i = 0; i < m; i++) {
  29.             int a = sc.nextInt();
  30.             int b = sc.nextInt();
  31.             int dis = sc.nextInt();
  32.             distance[a][b] = distance[b][a] = dis;
  33.         }
  34.         visit = new boolean[n+1];
  35.         dijkstra();
  36.         System.out.println(dp[n]-quarantine[n]);
  37.     }
  38.      public static void dijkstra() {
  39.         Arrays.fill(dp, MAXN);
  40.         dp[1] = 0;
  41.         for (int iter = 0; iter < n; iter++) {
  42.             //每次找到【最短距离最小】 且【未被更新】的点t
  43.             int t = -1;
  44.             for (int i = 1; i <= n; i++) {
  45.                 if (!visit[i] && (t == -1 || dp[i] < dp[t])) {
  46.                     t = i;
  47.                 }
  48.             }
  49.             visit[t] = true;
  50.             //使用t的最小距离更新其他点
  51.             for (int i = 1; i <= n; i++) {
  52.                 dp[i] = Math.min(dp[i], dp[t]+distance[t][i]+quarantine[i]);
  53.             }
  54.         }
  55.     }   
  56. }

3.治理环境（floyd最短路径+二分查找）

LQ 国拥有 n 个城市，从 0 到 n − 1 编号，这 n 个城市两两之间都有且仅有一条双向道路连接，这意味着任意两个城市之间都是可达的。每条道路都有一个属性 D ，表示这条道路的灰尘度。当从一个城市 A 前往另一个城市 B 时，可能存在多条路线，每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和，LQ 国的人都很讨厌灰尘，所以他们总会优先选择灰尘度最小的路线。

LQ 国很看重居民的出行环境，他们用一个指标 P 来衡量 LQ 国的出行环境，P 定义为：

其中 d(i, j) 表示城市 i 到城市 j 之间灰尘度最小的路线对应的灰尘度的值。为了改善出行环境，每个城市都要有所作为，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路的灰尘度都减少 1，但每条道路都有一个灰尘度的下限值 L，当灰尘度达到道路的下限值时，无论再怎么改善，道路的灰尘度也不会再减小了。具体的计划是这样的：

第 1 天，0 号城市对与其直接相连的道路环境进行改善；

第 2 天，1 号城市对与其直接相连的道路环境进行改善；

…

第 n 天，n − 1 号城市对与其直接相连的道路环境进行改善；

第 n + 1 天，0 号城市对与其直接相连的道路环境进行改善；

第 n + 2 天，1 号城市对与其直接相连的道路环境进行改善；

…

LQ 国想要使得 P 指标满足 P ≤ Q。请问最少要经过多少天之后，P 指标可以满足 P ≤ Q。如果在初始时就已经满足条件，则输出 0 ；如果永远不可能满足，则输出 −1。

输入格式

输入的第一行包含两个整数 n, Q，用一个空格分隔，分别表示城市个数和期望达到的 P 指标。接下来 n 行，每行包含 n 个整数，相邻两个整数之间用一个空格分隔，其中第 i 行第 j 列的值 Dij (Dij = Dji, Dii = 0) 表示城市 i 与城市 j 之间直接相连的那条道路的灰尘度。接下来 n 行，每行包含 n 个整数，相邻两个整数之间用一个空格分隔，其中第 i 行第 j 列的值 Lij (Lij = Lji, Lii = 0) 表示城市 i 与城市 j 之间直接相连的那条道路的灰尘度的下限值。

输出格式

输出一行包含一个整数表示答案。

样例输入

3 10

0 2 4

2 0 1

4 1 0

0 2 2

2 0 0

2 0 0

样例输出

2

代码： 

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static int n;
  5.     static long q;
  6.     //分别记录道路的灰尘度和下限
  7.     static long[][] w,limit;
  8.     //记录两点之间的最小灰尘度
  9.     static long[][] dp;
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         n = sc.nextInt();
  13.         q = sc.nextLong();
  14.         w = new long[n][n];
  15.         limit = new long[n][n];
  16.         dp = new long[n][n];
  17.         for (int i = 0; i < n; i++) {
  18.             for (int j = 0; j < n; j++) {
  19.                 w[i][j] = sc.nextLong();
  20.             }
  21.         }
  22.         for (int i = 0; i < n; i++) {
  23.             for (int j = 0; j < n; j++) {
  24.                 limit[i][j] = sc.nextLong();
  25.                 dp[i][j] =  limit[i][j];
  26.             }
  27.         }
  28.         //此时dp最短路径为下限，如果此时比q大，则永远都不可能满足
  29.         if (floyd() > q) {
  30.             System.out.println(-1);
  31.             return;
  32.         }
  33.         //二分查找符合的天数
  34.         long l = 0, r = 10000010;
  35.         while (l < r) {
  36.             long mid = (l+r)/2;
  37.             //p > q,则需要添加天数，继续改善
  38.             if (check(mid)) {
  39.                 l = mid+1;
  40.             }
  41.             else {
  42.                 r = mid;
  43.             }
  44.         }
  45.         System.out.println(l);
  46.     }
  47.     //判断是否当前天数是否符合题意
  48.     public static boolean check(long x) {
  49.         for (int i = 0; i < n; i++) {
  50.             for (int j = 0; j < n; j++) {
  51.                 dp[i][j] = w[i][j];
  52.             }
  53.         }
  54.         //判断改善了几轮，还余几天
  55.         long h = x/n;
  56.         long s = x%n;
  57.         for (int i = 0; i < n; i++) {
  58.             for (int j = 0; j < n; j++) {
  59.                 if (i == j) {
  60.                     continue;
  61.                 }
  62.                 //因为有下限，所以取较大的值
  63.                 if (s > i) {
  64.                     dp[i][j] = Math.max(limit[i][j], dp[i][j]-h-1);
  65.                 }
  66.                 else {
  67.                     dp[i][j] = Math.max(limit[i][j], dp[i][j]-h);
  68.                 }
  69.                 dp[j][i] = dp[i][j];
  70.             }
  71.         }
  72.         //改善后使用floyd求P,判断是否符合
  73.         return floyd() > q ;
  74.     }
  75.     //floyd求最短路径，最后返回所有节点最短路径和,即题目中的P
  76.     public static long floyd() {
  77.         long p = 0;
  78.         //从i到j的路径，k为中间节点
  79.         for (int k = 0; k < n; k++) {
  80.             for (int i = 0; i < n; i++) {
  81.                 for (int j = 0; j < n; j++) {
  82.                     dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k][j]);
  83.                 }
  84.             }
  85.         }
  86.         for (int i = 0; i < n; i++) {
  87.             for (int j = 0; j < n; j++) {
  88.                 p += dp[i][j];
  89.             }
  90.         }
  91.         return p;
  92.     }
  93. }

4.通电（最小生成树）

2015年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。这一次，小明要帮助 n 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。现在，这 n 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。
小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为 (x_1, y_1) 高度为 h_1 的村庄与坐标为 (x_2, y_2) 高度为 h_2 的村庄之间连接的费用为：

高度的计算方式与横纵坐标的计算方式不同。由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。
输入格式
输入的第一行包含一个整数 n ，表示村庄的数量。接下来 n 行，每个三个整数 x, y, h，分别表示一个村庄的横、纵坐标和高度，其中第一个村庄可以建立发电站。
输出格式
输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。
样例输入

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

样例输出

17.41

评测用例规模与约定
对于 30% 的评测用例，1 <= n <= 10；
对于 60% 的评测用例，1 <= n <= 100；
对于所有评测用例，1 <= n <= 1000，0 <= x, y, h <= 10000。

prim最小生成树代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static class Node{
  5.         double x,y,h;
  6.         public Node(double x,double y,double h) {
  7.             this.x = x;
  8.             this.y = y;
  9.             this.h = h;
  10.         }
  11.     }
  12.     static int n;
  13.     static Node[] nodes;
  14.     static double[][] cost;
  15.     //与结点相连的最小边权，即最小花费
  16.     static double[] dist;
  17.     static boolean[] visit;
  18.     public static void main(String[] args) {
  19.         Scanner sc = new Scanner(System.in);
  20.         n = sc.nextInt();
  21.         nodes = new Node[n+1];
  22.         cost = new double[n+1][n+1];
  23.         dist = new double[n+1];
  24.         visit = new boolean[n+1];
  25.         for (int i = 1; i <= n; i++) {
  26.             double x = sc.nextDouble();
  27.             double y = sc.nextDouble();
  28.             double h = sc.nextDouble();
  29.             nodes[i] = new Node(x, y, h);
  30.         }
  31.         for (int i = 1; i <= n; i++) {
  32.             Arrays.fill(cost[i], Double.MAX_VALUE);
  33.         }
  34.         for (int i = 1; i <= n; i++) {
  35.             for (int j = 1; j <= n; j++) {
  36.                 cost[i][j] = cost[j][i] = get(nodes[i], nodes[j]);
  37.             }
  38.         }
  39.         double res = prim();
  40.         System.out.printf("%.2f", res);
  41.     }
  42.     //计算两村庄之间费用
  43.     public static double get(Node node1,Node node2) {
  44.         double x = node1.x - node2.x;
  45.         double y = node1.y - node2.y;
  46.         double h = node1.h - node2.h;
  47.         return Math.sqrt(x*x+y*y)+h*h;
  48.     }
  49.     //prim算法求最小生成树
  50.     public static double prim() {
  51.         Arrays.fill(dist, Double.MAX_VALUE);
  52.         dist[1] = 0;
  53.         double res = 0;
  54.         for (int i = 1; i <= n; i++) {
  55.             int t = -1;
  56.             //查找未加入最小生成树的结点中距离最小的点
  57.             for (int j = 1; j <= n; j++) {
  58.                 if (!visit[j] && (t == -1 || dist[j] < dist[t])) {
  59.                     t = j;
  60.                 }
  61.             }
  62.             res += dist[t];
  63.             visit[t] = true;
  64.             //更新未加入结点离最小生成树的距离
  65.             for (int j = 1; j <= n; j++) {
  66.                 if (!visit[j]) {
  67.                     dist[j] = Math.min(dist[j], cost[t][j]);
  68.                 }
  69.             }
  70.         }
  71.         return res;
  72.     }
  73. }

kruskal最小生成树代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static class Node{
  5.         double x,y,h;
  6.         public Node(double x,double y,double h) {
  7.             this.x = x;
  8.             this.y = y;
  9.             this.h = h;
  10.         }
  11.     }
  12.     static class Edge{
  13.         int x,y;
  14.         double cost;
  15.         public Edge(int x,int y,double cost) {
  16.             this.x = x;
  17.             this.y = y;
  18.             this.cost = cost;
  19.         }
  20.     }
  21.     static int n;
  22.     static Node[] nodes;
  23.     static ArrayList<Edge> edges = new ArrayList<>();
  24.     static int[] f;
  25.     public static void main(String[] args) {
  26.         Scanner sc = new Scanner(System.in);
  27.         n = sc.nextInt();
  28.         nodes = new Node[n];
  29.         f = new int[n];
  30.         for (int i = 0; i < n; i++) {
  31.             double x = sc.nextDouble();
  32.             double y = sc.nextDouble();
  33.             double h = sc.nextDouble();
  34.             nodes[i] = new Node(x, y, h);
  35.             f[i] = i;
  36.         }
  37.         for (int i = 0; i < n-1; i++) {
  38.             for (int j = i+1; j < n; j++) {
  39.                edges.add(new Edge(i,j,get(nodes[i], nodes[j])));
  40.             }
  41.         }
  42.         kruskal();
  43.     }
  44.     //计算两村庄之间费用
  45.     public static double get(Node node1,Node node2) {
  46.         double x = node1.x - node2.x;
  47.         double y = node1.y - node2.y;
  48.         double h = node1.h - node2.h;
  49.         return Math.sqrt(x*x+y*y)+h*h;
  50.     }
  51.     //kruskal求最小生成树
  52.     public static void kruskal() {
  53.         double res = 0;
  54.         //统计已经连接边的数量，最多有n-1条边相连
  55.         int cnt = 0;
  56.         //在指定范围内按照花费进行升序排序
  57.         edges.sort((o1,o2) -> (int)(o1.cost - o2.cost));
  58.         for (int i = 0; i < edges.size(); i++) {
  59.             //获取一条边的两个点
  60.             Edge edge = edges.get(i);
  61.             int x = edge.x;
  62.             int y = edge.y;
  63.             double cost = edge.cost;
  64.             //如果两点没有相同的祖先结点，则代表不是环
  65.             if (find(x) != find(y)) {
  66.                 merge(x, y);
  67.                 res += cost;
  68.                 cnt++;
  69.                 if (cnt == n-1) {
  70.                     break;
  71.                 }
  72.             }
  73.         }
  74.         System.out.printf("%.2f", res);
  75.     }
  76.     //查找x的祖先结点
  77.     public static int find(int x) {
  78.         if (f[x] != x) {
  79.             f[x] = find(f[x]);
  80.         }
  81.         return f[x];
  82.     }
  83.     //合并两个结点
  84.     public static void merge(int x,int y) {
  85.         int px = find(x);
  86.         int py = find(y);
  87.         f[py] = px;      
  88.     }
  89. }

其他

1.约瑟夫环（链表）

设有 n 个人围坐在圆桌周围，现从某个位置 k 上的人开始报数，报数到 m 的人就站出来。下一个人，即原来的第 m+1 个位置上的人，又从 1 开始报数，再报数到 m 的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这 n 个人的出列顺序。

要求一：采用循环链表解决。

要求二：可以使用模拟法，模拟循环链表。

要求三：可以不使用循环链表类的定义使用方式。

输入描述

输入只有一行且为用空格隔开的三个正整数n,k,m，其含义如上所述。

输出描述

共 n 行，表示这 n 个人的出列顺序。

输入样例

3 5 8

输出样例

3

2

1

 代码：

  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static class Person {
  5.         int id;
  6.         Person next;
  7.         public Person() {}
  8.         public Person(int id) {
  9.             this.id = id;
  10.         }
  11.     }
  12.     public static void main(String[] args) {
  13.         Scanner sc = new Scanner(System.in);
  14.         int n = sc.nextInt();
  15.         int k = sc.nextInt();
  16.         int m = sc.nextInt();
  17.         Person first = new Person();
  18.         Person curPerson = null;
  19.         for (int i = 1; i <= n; i++) {
  20.             Person person = new Person(i);
  21.             //第一个人
  22.             if (i == 1) {
  23.                 first = person;
  24.                 first.next = person;
  25.                 curPerson = first;
  26.             }
  27.             //构成环链
  28.             else {
  29.                 curPerson.next = person;
  30.                 person.next = first;
  31.                 curPerson = person;
  32.             }
  33.         }
  34.         //创建辅助指针，用来判断环是否只剩一个人
  35.         Person last = first;
  36.         while (true) {
  37.             //辅助指针指向最后一个人
  38.             if (last.next == first) {
  39.                 break;
  40.             }
  41.             last = last.next;
  42.         }
  43.         //指向第一个开始报数的人
  44.         for (int i = 1; i < k; i++) {
  45.             first = first.next;
  46.             last = last.next;
  47.         }
  48.         //开始报数
  49.         while (true) {
  50.             //环中只有一个人
  51.             if (last == first) {
  52.                 break;
  53.             }
  54.             for (int i = 1; i < m; i++) {
  55.                 first = first.next;
  56.                 last = last.next;
  57.             }
  58.             //出圈
  59.             System.out.println(first.id);
  60.             first = first.next;
  61.             last.next = first;
  62.         }
  63.         System.out.println(first.id);
  64.     }
  65. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/73606
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号