1.动态规划

1.1包子凑数

image.png
样例1：
输入：

2 4 5

输出：

6

样例2：
输入：

2 4 6

输出：

INF

1.1.2思路分析

首先我们必须知道一个结论：
对于不定方程模拟赛 - 图2：
若a,b互质，那么就有无限多个c使方程有解，即有有限个c使方程无解
若a,b不互质，那么就有无限多个c使方程无解
对于我们每一种：从不同的蒸笼中取几笼的包子来凑成题目中的X的方案，我们可以视为形如模拟赛 - 图3的不定方程，那么我们只要判断a,b….c这些数是否互质，如果不互质，那么就输出INF
互质：最大公约数为1！！
这个题目从题型上来看是一个完全背包问题（反正我没做出来），正解是，设模拟赛 - 图4是能不能凑出i的集合，如果能凑出则模拟赛 - 图5，如果不能凑出则模拟赛 - 图6。根据题意易知：如果第i个包子能凑出来，那么模拟赛 - 图7个包子也必然能够能凑出来，例如：
有4，5两笼包子，如果能凑出5个包子，对于i=1那么一定能凑出5+4，5+8，5+12个包子
对于i=2，那么一定能凑出5+5，5+10，5+15个包子

1.1.3代码

  1. import java.util.Scanner;
  2. /*
  3. 小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N 种蒸笼，其中第 i 种蒸笼恰好能放 Ai
  4. 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
  5. 每当有顾客想买 X 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 XX 个包子。
  6. 比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时，
  7. 大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。
  8. 当然有时包子大叔无论如何也凑不出顾客想买的数量。
  9. 比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。
  11. 小明想知道一共有多少种数目是包子大叔凑不出来的。
  12.  */
  13. public class Main {
  14.     public static void main(String[] args) {
  15.         Scanner sc=new Scanner(System.in);
  16.         int[] arr=new int[101];
  17.         int[] dp=new int[10000];
  18.         int res=0;
  19.         int count=0;
  20.         //dp[i]表示能不能凑出i个包子
  21.         /*
  22.         对于不定方程ax+by=C，
  23.         若a,b互质（即最大公约数为1），那么有无限多个C能使方程有解（也即有有限个C使方程无解）
  24.         若a，b不互质，那么有无限多个C使方程无解
  25.          */
  26.         int N=sc.nextInt();
  27.         dp[0]=1;
  28.         for(int i=1;i<=N;i++){
  29.             arr[i]=sc.nextInt();
  30.             if(i==1)res=arr[i];
  31.             else res=gcd(res,arr[i]);
  32.             for(int j=0;j<10000;j++){
  33.                 if(dp[j]==1&&j+arr[i]<10000)dp[j+arr[i]]=1;
  34.             }
  35.         }
  36.         if(res!=1){
  37.             System.out.println("INF");
  38.         }else{
  39.             for(int i=0;i<dp.length;i++){
  40.                 if(dp[i]==0){
  41.                     count++;
  42.                 }
  43.             }
  44.             System.out.println(count);
  45.         }
  47.     }
  49.     public static int quickPower(int A, int n) {
  50.         if (n == 0)
  51.             return 1;
  52.         else if (n % 2 == 1)
  53.             return quickPower(A, n - 1) * A;
  54.         else {
  55.             int temp = quickPower(A, n / 2);
  56.             return temp * temp;
  57.         }
  58.     }
  59.     public static int gcd(int m,int n){
  60.         if(m%n==0)return n;
  61.         return gcd(n,m%n);
  62.     }
  63. }

2.dfs搜索

2.1排列小球

image.png

  • 输入：

    3 6 0

  • 输出：

    3

2.1.1思路分析

题目要求我们求出有多少种严格单调递增序列，我们可以以这样一个枚举思想求解：
先枚举要用小球种类，再枚举该种类使用多少个小球。dfs需要记录的数据有：

  • 上一次使用的小球类型
  • 上一次使用的小球类型的数量
  • 还有多少个小球没有使用

递归退出条件为：剩余没用的小球数量为0，即模拟赛 - 图9

2.1.2代码

  1. import java.util.Scanner;
  3. public class Main {
  5.     static int arr[] = new int[3];
  6.     static int count = 0;
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         int sum = 0;
  11.         for (int i = 0; i < arr.length; i++) {
  12.             arr[i] = sc.nextInt();
  13.             sum += arr[i];
  14.         }
  15.         sc.close();
  16.         f(sum, 0, -1);
  17.         System.out.println(count);
  19.     }
  21.     private static void f(int sum, int x, int last) {
  22.         if(sum==0) {
  23.             count++;
  24.             return;
  25.         }
  26.         for (int i = 0; i < arr.length; i++) {
  27.             if(i==last)continue;
  28.             for (int j = x + 1; j <= arr[i] && j <= sum; j++) {
  29.                 arr[i] = arr[i] - j;
  30.                 f(sum - j, j, i);
  31.                 arr[i] = arr[i] + j;
  32.             }
  33.         }
  35.     }
  36. }

2.2正则问题

image.png

2.2.1思路分析

遇到括号匹配的问题我们首先要想到栈的思想（是思想，而不是栈的具体实现），对于这题，给定一个正则表达式（表达式一定是合法的），我们可以建立这样一个递归的思路：
模拟赛 - 图11
遇到‘（’我们就将index（index表示游走在正则表达式字符串上的指针，最初指向0）加1，并进入下一层的递归，遇到‘|’就将当前的最大长度和index+1后dfs（）求出的最大长度相比较，从而更新最大的长度，遇到‘）’就退出该层栈中的递归，此时的‘）’正匹配开头的‘（’。

2.2.2代码

  1. import java.util.Scanner;
  3. public class Main {
  4.     // 正则问题
  5.     static String s;
  6.     static int index = 0;
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         s = sc.nextLine();
  11.         System.out.println(dfs());
  12.     }
  14.     public static int dfs() {
  15.         int res = 0;
  16.         while (index < s.length()) {
  17.             if (s.charAt(index) == '(') {
  18.                 index++;
  19.                 res += dfs();
  20.                 index++;
  21.       //为什么dfs()完成以后还要index++呢？
  22.       /*
  23.         这是因为，我们遇到了‘（’，那么在res+=dfs()的时候我们就
  24.         进入了下一层（假设第二层）的递归，在第二层的递归栈中，我们
  25.         遇到了‘）’，此时我们要退出该层的递归栈并且返回第二层中记录的
  26.         res，第一层的res得到了更新，但是我们的index此时刚好定位在‘）’
  27.         所在的位置下标，我们必须将index++才能使递归一直进行到最后的节点
  28.       */
  29.             } else if (s.charAt(index) == '|') {
  30.                 index++;
  31.                 res = Math.max(res, dfs());
  32.             } else if (s.charAt(index) == ')') {
  33.                 break;
  34.             } else {
  35.                 res++;
  36.                 index++;
  37.             }
  38.         }
  39.         return res;
  40.     }
  42. }

3.BFS搜索

3.1完全二叉树的权值

image.png

  • 输入：

    7 1 6 5 4 3 2 1

  • 输出：

    2

3.1.1思路分析

求二叉树的每一个层数的权值是多少，说白了就是二叉树的层序遍历，这里因为是一个完全二叉树，我们需要知道完全二叉树的性质：

  1. 二叉树的深度=模拟赛 - 图13
  2. 当前节点(n)的左右子节点为2n+1,2n+2;

知道这些知识，我们就可以利用bfs逐步搜索二叉树的每一层

3.1.2代码

  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3. import java.util.Scanner;
  5. public class Main {
  6.     static int index = 0;
  7.     static int i = 1;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         int n = sc.nextInt();
  12.         Node[] arr = new Node[n];
  13.         int[] num = new int[(int) Math.sqrt(n) + 1];
  14.         for (int i = 0; i < n; i++) {
  15.             arr[i] = new Node(i, sc.nextInt());
  16.         }
  18.         Queue<Node> q = new LinkedList<Node>();
  19.         q.offer(arr[0]);
  20.         while (!q.isEmpty()) {
  21.             int size = q.size();
  22.             int sum = 0;
  23.             for (int i = 0; i < size; i++) {
  24.                 Node cur = q.poll();
  25.                 int curpos = cur.pos;
  26.                 int curcount = cur.count;
  27.                 sum += curcount;
  28.                 if (curpos * 2 + 1 < n) {
  29.                     q.offer(arr[curpos * 2 + 1]);
  30.                 }
  31.                 if (curpos * 2 + 2 < n) {
  32.                     q.offer(arr[curpos * 2 + 2]);
  33.                 }
  34.             }
  35.             num[index++] = sum;
  36.         }
  37.         int max = num[0];
  38.         for (int i = 0; i < num.length; i++) {
  39.             max = Math.max(num[i], max);
  40.         }
  42.         for (int i = 0; i < num.length; i++) {
  43.             if (num[i] == max) {
  44.                 System.out.println(i + 1);
  45.                 break;
  46.             }
  47.         }
  49.     }
  51.     static class Node {
  52.         int pos;
  53.         int count;
  55.         public Node(int pos, int count) {
  56.             this.pos = pos;
  57.             this.count = count;
  58.         }
  60.     }
  62. }

4.跑步锻炼

第十一届蓝桥杯 ——跑步锻炼java代码
问题描述
小蓝每天都锻炼身体。
正常情况下，小蓝每天跑 1 千米。
如果某天是周一或者月初（1 日），为了激励自己，小蓝要跑 2 千米。如果同时是周一或月初，小蓝也是跑 2 千米。
小蓝跑步已经坚持了很长时间，从 2000 年 1 月 1 日周六（含）到 2020 年10 月 1 日周四（含）。

请问这段时间小蓝总共跑步多少千米？

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
————————————————
版权声明：本文为CSDN博主「A.�」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Mumu_777/article/details/115578428

  1. import java.text.SimpleDateFormat;
  2. import java.util.Calendar;
  4. public class _03跑步锻炼 {
  5. public static void main(String[] args) {
  6.     int sum=2;
  7.     Calendar c1=Calendar.getInstance();
  8.     SimpleDateFormat a=new SimpleDateFormat("yyyyMMdd");
  9.     //设置开始日期
  10.     c1.set(Calendar.YEAR, 2000);
  11.     c1.set(Calendar.MONTH, 0);
  12.     c1.set(Calendar.DAY_OF_MONTH, 1);
  14.     for (int i = 1; i <=10000; i++) {
  15.         c1.add(Calendar.DAY_OF_YEAR,1);
  16.         sum++;//每天都要跑1千米
  17.         String date=a.format(c1.getTime());//将日期转换成数字数字格式如20000102
  18.         char b[]=date.toCharArray();
  19.         if (c1.get(Calendar.DAY_OF_WEEK)==Calendar.MONDAY || (b[6]=='0' && b[7]=='1'))//判断是不是星期一或者是每个月的1号
  20.          {
  21.             sum=sum+1;//是的话，额外多跑1千米
  22.         }    
  23.         //设置结束日期
  24.         if (date.equals("20201001")) {
  25.             break;
  26.         }
  27.     }
  28.     System.out.println(sum);//sum=8879
  29. }
  30. }