## 蓝桥基础

### 离散化

```
package LQ_10;
import java.util.*;

public class EXE {
	public static void main(String[] args) {
		Scanner scan=new Scanner (System.in);
		int n=scan.nextInt();
		int[] arr=new int[n];
		int[] a=new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=scan.nextInt();
			a[i]=arr[i];
		}
		Set<Integer>set=new HashSet<>();
		Arrays.sort(a);
		Map<Integer,Integer>map=new HashMap<>();
		for(int i=0;i<n;i++)
		{
			set.add(a[i]);
			map.put(a[i],set.size());
		}
		for(int i=0;i<n;i++)
		{
			System.out.println(map.get(arr[i])+" ");
		}
		
	}
}

```



## 进制转化

### 奇怪的捐赠

地产大亨 Q 先生临终的遗愿是：拿出 100100 万元给 X 社区的居民抽奖，以稍慰藉心中愧疚。

麻烦的是，他有个很奇怪的要求：

1. 100 万元必须被正好分成若干份（不能剩余）。每份必须是 7 的若干次方元。比如：1 元, 7 元， 49 元，343 元，...
2. **相同金额的份数不能超过 5 份。**————》woc 这tm是迷惑你的
3. 在满足上述要求的情况下，分成的份数越多越好！

请你帮忙计算一下，最多可以分为多少份？

```java
思路就是：分成多少分，重点是7的平方
想一下一个数是又一个数的各种平方合成的————》进制***太深了
那么难点就是进制转换的问题了
```

```java
public class Main {
    public static void main(String[] args) {
        int n=1000000;
        int cnt=0;
        while(n>0){
          cnt+=n%7;
          n/=7;
        }
        System.out.println(cnt);
    }
}
```

## 常识题

**本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。**

小蓝的IP地址为 `192.168.*.21`，其中 `*` 是一个数字，请问这个数字最大可能是多少？



## 高精度

### 题目描述

计算 A×B*A*×*B* 。

### 输入描述

每一行将包含两个整数 A*A* 和 B*B*。备注:每个整数的长度不能超过 1000010000。

### 输出描述

输出 A×B*A*×*B* 。

### 输入输出样例

#### 示例 1

### 题目描述

计算 A×B*A*×*B* 。

### 输入描述

每一行将包含两个整数 A*A* 和 B*B*。备注:每个整数的长度不能超过 1000010000。

### 输出描述

输出 A×B



```txt
1000
2
```



```txt
2000
```



```java
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.math.BigInteger;***注意导包
public class Main {
    public static void main(String[] args) {
		  Scanner scan = new Scanner(System.in);
		  while(scan.hasNext()) {
			  BigInteger a=scan.nextBigInteger();
			  BigInteger b=scan.nextBigInteger();
			  System.out.println(a.multiply(b));
    }
}
}
```

============================================================================================================================================================================================================================================================================================================================

## 双指针



1372

```java
package LQ_10;
import java.util.*;

public class LQ1372 {
	public static void main(String [] args)
	{
		
		 Scanner scan = new Scanner(System.in);
	     int n=scan.nextInt();//n个数
	     int s=scan.nextInt();//s 目标常数
	     int ans=Integer.MAX_VALUE;//表示长度
	     int sum=0;//表示和
	     int [] arr=new int[n];
	     for(int i=0;i<n;i++)
	    	 arr[i]=scan.nextInt();
	     for(int i=0,j=0;i<n;) {
	    	 if(sum<s) {
	    		 sum+=arr[i];
	    		 i++;
	    	 }else {
	    		 ans=Math.min(i-j,ans);
	    		 sum-=arr[j];
	    		 j++;
	    	 }
	     }
	     
	     if(ans==Integer.MAX_VALUE)
	    	 System.out.println("0");
	     else
	    	 System.out.println(ans);
	     scan.close();
		
	}
	
 }
题目核心：
你什么时候达到S以及到达S的时候怎么能最小
刚开始 i=j=0
这个题用的是双指针 就是让sum=0 如果sum<=（都对）s那么就让sum+arr[i],i++ 这样就是扩大了i的长度
既然有扩大长度 那么就有缩短长度 那么如何缩短长度 就是需要j 如果sum>=s 那么就是sum=-arr[j] j++这样 i在前面扩大长度 j在后面缩小长度  当i<n的时候就是到头了 不能扩大了 就是程序结束的时候
Q：你怎么确定 排序是从小打大 （题目似乎没有给出） 是否需要用贪心算法 +动归
```

============================================================================================================================================================================================================================================================================================================================

## 常用函数

```java
	public static int gcd (int m,int n) {
		int r=n;
		while(m%n!=0)
		{
			r=m%n;
			m=n;
			n=r;
		}
		return r;
	}
	R为最小公因数
	m*n/r为最小公倍数s
	
	判断是否是素数
public static boolean isPrime (int x) {
        if(x==1)
            return false;
        for(int i=2;i<=Math.sqrt(x);i++)
        {
            if(x%i==0)
                return false;
        }
        return true;
	}
	
```

============================================================================================================================================================================================================================================================================================================================

## 字符串

```java
给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见实例 2）。

package LQ_10;
import java.util.*;

public class LQ396 {
	 public static void main(String args[]) {
         Scanner scan=new Scanner(System.in);
             int n=scan.nextInt();
          int b=Math.abs(n);
           StringBuilder str=new StringBuilder();
           str.append(b);
           StringBuilder str1=str.reverse();
           String str2=str1.toString();
           int a=Integer.valueOf(str2);
     if(n>=0){
       System.out.println(a);
     }
           else{
       System.out.println(-a);
     }
       }
}

```

## 排序

### 冒泡

把最大的冒泡到前面去

```java
int []arr= {5,8,4,4,6,7,4,8};
for (int i = arr.length - 1; i > 0; i--) {
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 与 arr[j + 1]
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
	for(int i:arr) {
		System.out.printf(i+" ");
	}
	时间复杂度O N^2
```

### 选择

选择最小的与前面的交换

```java
	int []arr= {3,8,4,4,6,7,4,8,9,1,1,1,5,2,7,8,15};
	for(int i=0;i<arr.length;i++) {
		int k=i;
		for(int j=i+1;j<arr.length;j++) {
			if(arr[j]<arr[k])
			k=j;
		}
		if(k!=i) {
			int t=arr[i];
			arr[i]=arr[k];
			arr[k]=t;
		}
	}
```

### 插入排序

```java
package LQ_10;

public class EXE {
public static void main (String [] args) {
	int []nums= {3,8,4,4,6,7,4,8,9,1,1,1,5,2,7,8,15};

	for(int i=1;i<nums.length;i++){
		int base=nums[i],j=i;
		while(j>0&&nums[j]>base) {
			nums[j+1]=nums[j];
			j--;
		}
		nums[j+1]=base;
	}
	
	for(int i:nums) {
		System.out.printf(i+" ");
	}
}
}
```

### 快排

```java
package LQ_10;

public class EXE {
	public static void main(String[] args) {
		int[] nums = { 3, 8, 4, 4, 6, 7, 4, 8, 9, 1, 1, 1, 5, 2, 7, 8, 15 };
		quickSort(nums,0,nums.length-1);
		for (int i : nums) {
			System.out.printf(i + " ");
		}
	}

	public static void swap(int[] nums, int i, int j) {
		int t = nums[i];
		nums[i] = nums[j];
		nums[j] = t;
	}
	public static void quickSort(int []nums,int left,int right) {
		if(left>right)return;//左边的数等于右边的数 就是说只有一个数了 那还排什么
		int pivot=partition(nums,left,right);//找中枢点
		quickSort(nums,left,pivot-1);
		quickSort(nums,pivot+1,right);
	}
	public static int partition(int []nums,int left,int right) {
		int i=left,j=right;
		while(i<j) {
			while(i<j&&nums[j]>=nums[left])j--;
			while(i<j&&nums[i]<=nums[left])i++;
			swap(nums,i,j);
			}
		swap(nums,i,left);
	   return i;
	}
}

```

### 归并排序

```java
package LQ_10;

public class EXE {
	public static void main(String[] args) {
		int[] nums = { 3, 8, 4, 4, 6, 7, 4, 8, 9, 1, 1, 1, 5, 2, 7, 8, 15 };
		int[] arr=mergeSort(nums,0,nums.length-1);
		for (int i : arr) {
			System.out.printf(i + " ");
		}
	}

	public static int[] mergeSort(int[] nums, int left, int right) {
		if (left == right)
			return new int[] {nums[left]};
		int mid = (left + right) / 2;
		int[] leftarr = mergeSort(nums, left, mid );
		int[] rightarr = mergeSort(nums, mid+1, right);
		int[] newarr = new int[leftarr.length + rightarr.length];
		int m = 0, l = 0, r = 0;
		while (l < leftarr.length && r < rightarr.length)
			newarr[m++] = leftarr[l] <rightarr[r] ? leftarr[l++] : rightarr[r++];
		while (l < leftarr.length)
			newarr[m++] = leftarr[l++];
		while (r < rightarr.length)
			newarr[m++] = rightarr[r++];
		return newarr;
	}
}

```

## 进制转化

```java
public static String ts(int a,int x) {
		StringBuilder str1=new StringBuilder();
		while(a>0)
		{
			str1.append(a%x);
			a/=x;
		}
		return str1.reverse().toString();
	}
```

## 贪心

```java
package LQ_10;

import java.util.*;

public class Main {
	public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        List<Integer> lt=new ArrayList<Integer>();
        for(int i=0;i<n;i++)
        	lt.add(scan.nextInt());
        long sum=0;
    	Collections.sort(lt);
        while(lt.size()>1) {
        	int a=lt.get(0);
        	int b=lt.get(1);
        	sum+=a+b;
        	lt.remove(0);
        	lt.remove(0);
        	lt.add(a+b);
        	Collections.sort(lt);
        }
        System.out.print(sum);
        scan.close();
	}
}
```

![image-20241030223825354](C:\Users\33882\AppData\Roaming\Typora\typora-user-images\image-20241030223825354.png)



# 系统学习

## 循环

### 进制转换

```java

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a=scan.nextInt();
        int out=0;
        int pow=1;
        while(a>0){
            int c=a%10;
            a/=10;
            out+=c*pow;
            pow*=9;
        }
        System.out.println(out);
        scan.close();
    }
}
```

### 枚举法求最大公约数

```java
设a, b是两个整数，如果d能整除a且d能整除b，那么，d就称为是a和b的公约数。a和b的公约数中最大的整数称为a和b的最大公约数。
输入两个正整数a和b，求它们的最大公约数。
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt(), b = scan.nextInt();
        int min= Math.min(a, b);
        for(int i=min;i>=1;i--){
            if(a%i==0 && b%i==0){
                System.out.println(i);
                break;
            }
        }
        scan.close();
    }
}

  递归大法
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
   public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();
        System.out.println(gcd(a,b));
    }
    public static int gcd(int a,int b) {
        return b == 0 ? a : gcd(b,a%b);
    }
}
```

## 数组与字符串

### 冒泡排序

```java

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int arr[]=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=scan.nextInt();
        }
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-i-1;j++){//n-1-i n-1是因为有j+1的存在 i是因为每次冒出去一个就会占一个
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        for(int i=0;i<n;i++){
            if(i==0){
                System.out.print(arr[i]);
            }
            else{
                System.out.print(" "+arr[i]);
            }

        }
        scan.close();
    }
}
```

### 选择排序

```java
/* 选择排序 */
void selectionSort(int[] nums) {
    int n = nums.length;
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {//因为是找最小的 所以不用从自己开始
            if (nums[j] < nums[k])
                k = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}
```

## JAVA基本API

```
Integer.parseInt(String s ,int radix)  将（radix表示的s是几进制的）转换为10进制

toString(String s ,int radix)  将s转换为radix进制的字符串
```

## JAVA快读

```java
static FastReader in = new FastReader(); // 创建一个静态的 FastReader 对象，用于处理输入
static PrintWriter out = new PrintWriter(System.out); // 创建一个静态的 PrintWriter 对象，用于输出数据

// FastReader 类，用于处理高效的输入
static class FastReader {
    static BufferedReader br; // 静态的 BufferedReader，用于高效读取输入
    static StringTokenizer st; // 静态的 StringTokenizer，用于将输入字符串分割为标记

    // 构造函数，初始化 BufferedReader 以从标准输入读取数据
    FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in)); // 使用 System.in 作为输入流初始化 BufferedReader
    }

    // next() 方法，返回下一个字符串标记
    String next() {
        String str = ""; // 定义一个空字符串，用于存储读取到的行
        // 如果 StringTokenizer 为 null 或没有更多标记可读取，读取新行
        while (st == null || !st.hasMoreElements()) {
            try {
                str = br.readLine(); // 使用 BufferedReader 读取一整行输入
            } catch (IOException e) { // 捕获可能的 I/O 异常
                throw new RuntimeException(e); // 如果发生异常，抛出运行时异常
            }
            st = new StringTokenizer(str); // 将读取到的行传递给 StringTokenizer 进行分割
        }
        return st.nextToken(); // 返回 StringTokenizer 的下一个标记
    }
    String nextLine(){
        String str="";
        try {
            str = br.readLine(); // 使用 BufferedReader 读取一整行输入
        } catch (IOException e) { // 捕获可能的 I/O 异常
            throw new RuntimeException(e); // 如果发生异常，抛出运行时异常
        }
        return str;
    }
    // nextInt() 方法，返回下一个整数输入
    int nextInt() {
        return Integer.parseInt(next()); // 使用 next() 方法读取字符串并转换为整数
    }

    // nextDouble() 方法，返回下一个双精度浮点数输入
    double nextDouble() {
        return Double.parseDouble(next()); // 使用 next() 方法读取字符串并转换为双精度浮点数
    }

    // nextLong() 方法，返回下一个长整数输入
    long nextLong() {
        return Long.parseLong(next()); // 使用 next() 方法读取字符串并转换为长整数
    }
}
```

还有一种

```java

class Read{
	StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	public int nextInt() throws Exception{
		st.nextToken();
		return (int)st.nval;
	}
	public String readLine() throws Exception{	//	不推荐使用
		st.nextToken();
		return st.sval;
	}
}

```

## 一维前缀和

```
本题为一维前缀和模板。
给定一个长度为 n 的序列 a。
再给定 q组查询，对于每次查询:给定一对l r,你需要输出 的结果。
输入格式
第一行输入两个正整数 n, q。(1 ≤ n,q < 10°)
第二行输入 n 个正整数 αi。(1 ≤i≤ n,1 ≤ ai< 104)。
接下来 q 行，每行输入 2 个正整数 l,γ。(1 <l<r< n)。
输出格式
对于每次查询，输出一行一个整数，表示该次查询的结果。

样例输入
5 3
2 1 3 6 4
1 2
1 3
2 4

输出
3
6
10


自制小代码
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(),q=scan.nextInt();
        int arr[]=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=scan.nextInt();
        }
        for(int i=0;i<q;i++){
            int l=scan.nextInt(),r=scan.nextInt();
            int sum=0;
            for(int j=l-1;j<r;j++){
                sum+=arr[j];
            }
            System.out.println(sum);
        }
        scan.close();
    }
}  简单易懂 但是时间很长


标准答案 利用了求和公式的变形
S[n]=s[n-1]+a;

然后要求l到r的和就是  S[r]-s[l-1] 因为是包括L的所以说是从L-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 n=scan.nextInt(),q=scan.nextInt();
        int arr[]=new int[n+2];
        arr[0]=0;
        for(int i=1;i<=n;i++){
            arr[i]=scan.nextInt()+arr[i-1];
        }
        for(int i=0;i<q;i++){
            int l=scan.nextInt(),r=scan.nextInt();
            System.out.println(arr[r]-arr[l-1]);
        }
        scan.close();
    }
}
```

## 差分

```java
问题描述
给定一个长度为 n 的序列 a。
再给定 m 组操作，每次操作给定3个正整数l,",d，表示对 ai~，中的所有数增加 d。
最终输出操作结束后的序列 a。
Update:由于评测机过快，n,m于2024-12-09 从 105加强至 2 x105杜绝暴力通过本题。
输入格式第一行输入两个正整数n,m。(1<n,m<2x105)第二行输入 n 个正整数 ai。(1 ≤i≤ n,1 ≤ ai < 104)。接下来 m 行，每行输入 3 个正整数 l,™,d。(1 ≤l≤r≤ n,-104 ≤d≤ 104)。
输出格式
输出 几 个整数，表示操作结束后的序列 a。
样例输入
6 3
2 2 12 1
3 1
5
6 1
样例输出
3 4 5 3 4 2
    
    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(), m=scan.nextInt();
        int arr[]=new int[n+5];
        int brr[]=new int[n+5];
        int crr[]=new int[n+5];
        arr[0]=0;brr[0]=0;crr[0]=0;
        for(int i=1;i<=n;i++) arr[i]=scan.nextInt();
        for(int i=1;i<=n;i++) brr[i]=arr[i]-arr[i-1];
        for(int i=1;i<=m;i++){
            int l=scan.nextInt(),r=scan.nextInt(),d=scan.nextInt();
            brr[l]+=d; 
            brr[r+1]-=d;
        }
        for(int i=1;i<=n;i++) crr[i]=crr[i-1]+brr[i];

        for(int i=1;i<=n;i++){
            System.out.print(crr[i]+" ");
        }
        scan.close();
    }
}
差分数组求前缀和就是求原数组
```

### 小蓝的操作（2星）

![image-20250120141310885](C:\Users\33882\AppData\Roaming\Typora\typora-user-images\image-20250120141310885.png)

```java
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();//n家店铺
        int t = in.nextInt();//t行点赞情况
        int q = in.nextInt();//q组查询
        int x = in.nextInt();//信赖店铺的点赞数量
        int arr[] = new int[n+20];//开辟一个n个空间的数组  表示店铺
        for (int i = 0; i < t; i++) {
            int l = in.nextInt();
            int r = in.nextInt();
            arr[l] += 1;//我在l的地方+1  在我后面代码arr[i]+=arr[i-1]中 所有的在l后面的代码都会加上1 
            arr[r+1] -= 1;//但是我又为了防止 r后面的不能加上因为我的加的范围是l-r 所以 r+1就需要减去1 与前面的l对冲
        }
        for (int i = 1; i <= n; i++) {
            arr[i] = arr[i] + arr[i - 1];  //将差分数组 转化为原数组  bn=an+an-1 
        }

        int brr[]=new int[n+10];
        for (int i = 1; i <= n; i++) {
            if (arr[i] >= x)//如果被定义为信赖的为1
                arr[i]=1;
            else
                arr[i]=0;
            brr[i]=brr[i-1]+arr[i];//前缀和
        }
        for(int i=1;i<=q;i++){
            int l= in.nextInt(),r= in.nextInt();
            System.out.println(brr[r]-brr[l-1]);
        }
        in.close();
    }

}
```

### 二维差分数

给定一个 大小的矩阵 。
给定 组查询，每次查询为给定 4 个正整数 ，你需要输出 的值。

第一行输入 3 个正整数 。
接下来 行每行输入 个整数，表示 。
接下来 行，每行输入 4 个正整数 

对于每次查询，输出一个整数，表示查询的子矩阵的和。

```plaintext
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
```

#### 样例输出

```plaintext
17
27
21
```

```java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int q = scan.nextInt();
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + scan.nextInt();
            }
        }

        while (q-- > 0) {
            int x1 = scan.nextInt();
            int y1 = scan.nextInt();
            int x2 = scan.nextInt();
            int y2 = scan.nextInt();
            int result = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
            System.out.println(result);
        }

        scan.close();
    }
}
```

## 单调队列

### 滑动窗口问题

```java
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] num = new int[10];
        int n, k;
        n = sc.nextInt();
        k = sc.nextInt();
        int[] ans = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque();
        for (int i = 0; i < n; i++) {  
            while (!q.isEmpty() && num[i] > num[q.peekLast()]) {
                q.pollLast();
            }
            q.addLast(i);
            if (i - q.getFirst() >= k) {//如果队列头部的元素已经不在滑动窗口内，则将其移除
                q.pollFirst();
            }
            if (i >= k - 1) 
                ans[i - k + 1] = num[q.getFirst()];//记录当前滑动窗口的最大值
        }
    }
}
```



## 位运算

### 相或为k（2星）

#### 问题描述

给定你n个非负整数a[i]，你是否可以从中选出一些数进行或运算使得值为k，若可以，则输出Yes，若不可以，则输出No。

或运算：二进制位1|1 = 1, 1|0 = 1, 0|0 = 0。

#### 输入格式

第一行一个t代表数据组数。

每组数组第一行二个整数n, k。

每组数据第二行n个数a[i]。

#### 输出格式

输出t行，为符合题目要求的Yes或No。

#### 样例输入

#### 1
4 6
1 2 3 4

#### 样例输出

Yes

```java
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();
        while(t-->0) {
            int n = sc.nextInt();
            int k= sc.nextInt();
            int ans=0;
            for(int i=0;i<n;i++){
                int r= sc.nextInt();
                if((r&k)==r){
                    ans|=r;
                }
            }
            /**
             * 判断是否为k的子集
             * 如果r&k==r，则说明r是k的子集
             * 就让ans 加上r也就是ans|r  
             * 最后再看是否ans==k  也就是所有的k的子集是否都出现了
             * 这个题  题目不好理解 但是 只要理解了  就很简单了 
             */
            if(ans==k){
                System.out.println("Yes");
            }
            else{
                System.out.println("No");
            }
        }
    }
}
```



## 求阶乘（3星）

**问题描述**：满足 `N!` 的末尾恰好有 `K` 个 `0` 的最小的 `N` 是多少？如果这样的 `N` 不存在输出 `-1` 。 **输入格式**：一个整数 `K` 。 **输出格式**：一个整数代表答案。

 **样例输入**： 2 

**样例输出**： 10 

```java
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {

    static long cale(long x) {
        long num = 0;
        while (x > 0) {
            //求出能有几个会被5整除的 因为在阶乘中5有1个5  25有2个5 所以说通过循环 来判断这个数究竟能被几个5整除
            num += x / 5;
            
            x /=  5;
        }
        return num;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong();
        long left = 0L;
        long right = (long) 1e18 ;

        while (left < right) {
            long mid = (left + right) / 2;

            if(n<=cale(mid)){
                right = mid ;
            }
            else{
                left = mid+1 ;
            }
        }

        if(cale(right)!=n){
            System.out.println(-1);
        }
        else{
            System.out.println(right);
        }
        scan.close();
    }
}
```

## 莫名其妙中间省略了好多

## 背包01dp

```java
        n = in.nextInt();
        m = in.nextInt();
        int []v=new int[n+1];//价值
        int []w=new int[n+1];//体积
        for(int i=0;i<n;i++){
            v[i]=in.nextInt();
            w[i]=in.nextInt();
        }
        int [][]dp=new int[m+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=w[i]){
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
                }
            }
  ////////////////////////////////  ////////////////////////////////////////////////////////////////
            一维优化
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n, m;
        n = in.nextInt();
        m = in.nextInt();
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];
        for (int i = 0; i < n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        int[] dp = new int[m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= w[i]; j--) {//这是从后往前来的 只能这样 因为只有这样 不然从前往后的话就会多加
                                dp[j] = Math.max(dp[j], dp[ j - w[i] ] + v[i]);
                /*
                是这样的 因为啊 这个dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
                需要等价于
                 dp[i][j]=dp[i-1][j];
                if(j>=w[i]){
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
                   dp[j] = Math.max(dp[j]  是没有错的Math.max(dp[j] 是上一个的 其实就是等价于dp[i][j]=Math.max(dp[i][j]
                   可以这么认为 因为此时左边的dp[j]还没有被算出来 而右边的dp[j]是上一个dp[i-1][j]的 已经被算出来的
                */

            }
        }
        in.close();
    }
}
            
```

## 完全背包

```java
        n = in.nextInt();
        m = in.nextInt();
        int []v=new int[n+1];//价值
        int []w=new int[n+1];//体积
        for(int i=0;i<n;i++){
            v[i]=in.nextInt();
            w[i]=in.nextInt();
        }
        int [][]dp=new int[m+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=w[i]){
                    dp[i][j]=Math.max(dp[i][j],dp[i][j-w[i]]+v[i]);
                }
            }
             //注意这个  dp[i][j]=Math.max(dp[i][j],dp[i][j-w[i]]+v[i]);
            
            其实完全背包和01背包差不多 都是依赖上一层的来推出下一层
            只不过完全背包可以对同一个物品多次拿去 所以它的上一层就可能是自己发展过来的 所以就是dp[i][j-w[i]]+v[i]
                
  ////////////////////////////////////////////////////////////////////////////////////////////////              
                
                            一维优化
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n, m;
        n = in.nextInt();
        m = in.nextInt();
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];
        for (int i = 0; i < n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        int[] dp = new int[m + 1];
        for (int i = 0; i < n; i++) {
            for (int j =w[i]; j<=m; j++) {//这是从前往后来的 所以说就是可以直接从w[i]到m 跟上面的反着记就好了
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        in.close();
    }
}
```

## 多重背包

```java
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
     public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        int v[]=new int[n+1];
        int w[]=new int[n+1];
        int c[]=new int[n+1];
        int dp[]=new int[m+1];

        for (int i = 1; i <= n; i++) {
            v[i]=sc.nextInt();
            w[i]=sc.nextInt();
            c[i]= sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >=v[i]; j--) {
                for (int k = 0; k*v[i]<=j&&k<=c[i] ; k++) {//不仅选的次数要关注容量 也要关注本身的限制
                   dp[j]=Math.max(dp[j],dp[j-k*v[i]]+k*w[i]);
                }
            }
        }
        System.out.println(dp[m]);
    }
}
O(N*M*K)比较大 只能支持100的数值
    
```

## 区间DP

```JAVA

题目描述
在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。例如：输入{1，2，3，4，5}，输出33。【3+6+9+15=33】
输入
本题应该处理到文件尾，每组输入包括两行，第一行为石子堆的个数n，第二行则为每堆石子的个数。
输出
输出最小花费。
样例输入
5
1 2 3 4 5
样例输出
33
import java.util.Scanner;

// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
    static int N = 300;
    static int[] s = new int[N];//前缀和
    static int[][] dp = new int[N][N];//i j 这个数组的每一位ij 都代表的是i->j 的最少的花费

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        for(int i=1;i<=n;i++){
            s[i]=in.nextInt()+s[i-1];
        }
        for(int len=2;len<=n;len++){
            for(int l=1;len+l-1<=n;l++){
                int r =len+l-1;
                dp[l][r]=Integer.MAX_VALUE;
                for(int k = l; k< r; k++){
                    dp[l][r]=Math.min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
                }
            }
        }
        System.out.println(dp[1][n]);
    }
}
```