# JavaLanqiao

**Repository Path**: wyfcn/java-lanqiao

## Basic Information

- **Project Name**: JavaLanqiao
- **Description**: 存放蓝桥杯Java的学习笔记
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-02-19
- **Last Updated**: 2025-04-10

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# JAVA蓝桥杯知识点
## 考前须知
1. 有结果填空，代码填空，程序设计三个部分；注意：代码填空所填写的语句<mark>不超过一条语句（中间不能出现分号）<mark>，把答案直接通过网页提交，不要写注释等多余内容
2. 所有源码在同一文件中，调试通过后，拷贝提交
3. 主类名必须为Main,不要使用package语句


## 注意事项
1. 交换逻辑错误：

change方法中的交换逻辑没有实际效果，因为Java是按值传递的，方法内部的交换不会影响到方法外部的变量。
应该把数组包含在里面，例如：
~~~
    public static void change(int[] array, int index1, int index2) {
        int t = array[index1];
        array[index1] = array[index2];
        array[index2] = t;
    }
~~~

2. 数组索引错误： 

在Java中，数组索引是从0开始的。你在循环中从1开始赋值和访问数组元素，这会导致数组索引越界错误。

## 必须掌握的知识点
### 1.基础的数论（快速幂，求质数，gcd，lcm等等）
1. 快速幂
问题描述
给定t组数据，每组数据给三个正整数a,b,p，需要输出a^b mod p
例如计算a^69,由于69的二进制数是1000101，因此可以拆分成a^64*a^4*a^1

~~~
快速幂中，每次循环都会将底数 (a) 平方（即倍增），同时将指数 (b) 右移一位（相当于除以 2）。这样做的目的是为了逐步处理 (b) 的每一位二进制位。
static long qpow(long a,long b,long p)
{
    long res=1;
    while(b!=0)
    {
        if((b&1)==1)//检查b的这一个二进制位是否为1
        {
            res=res*a%p;//是的话累乘当前结果并取模
        }
        a=a*a%p;//每次循环都要将a倍增
        b>>=1;//继续右移一位
    
    }
    return res;
}
~~~
2. 求质数
如果两个数的gcd结果为1，则称两个数互质
3. gcd
是两个或多个整数的最大公约数
辗转相除法，a mod b通过不断用较小的数和余数递归计算，最终直到余数为0，这时b就是两个数的最大公约数
~~~
static int gcd(int a,int b)
{
    while(b!=0){
    int temp=a;
    a=b;
    b=temp%b;
    }
    return a;
}
~~~
注意：如果两个数的gcd结果为1，则称两个数互质
4. lcm
是两个或多个整数的最小公倍数
gcd(a*b)*lcm(a,b)=a*b
由此得lcm(a,b)=a*b/gcd(a,b)
~~~
static long lcm(long a,long b)
{
    return a*b/gcd(a,b);
}

~~~
5. 1~n的最小公倍数
求1~n的最小公倍数m
输入n
输出m，结果对10^9+7取模

算法思想：
1. 对1~n的所有数进行质因数分解
2. 对每个质数p，取1~n范围内的最高幂次p^k
3. 最终LCM是所有p^k的乘积
~~~

import java.util.Scanner;
public class Main{
    static int N=100010;//数组大小
    static int cnt=0;//当前筛选出的质数的个数
    static int prime[]=new int[N];//存储所有质数
    static boolean st[]=new boolean[N];//标记是否为合数
    static int mod=(int)(1e9+7);

//筛选1~n的所有质数
    static void sieve(int n){    
        for(int i=2;i<=n;i++){
            if(!st[i]){//如果i是质数
                prime[++cnt]=i;//将质数存入prime数组
            }
            //筛去i的倍数
            for(int j=1;j<=cnt;j++){
                if((long)prime[j]*i>n)break;//超过n时候跳出循环
                st[prime[j]*i]=true;//标记为合数
                if(i%prime[j]==0)break;//保证每个合数只被最小质因子筛去
        }
    }
}

    public static void main(String[] args){
        Scanner in =new Scanner(System.in);
        //在此输入您的代码.
        int n=in.nextInt();
        sieve(n);//筛选质数
        long res=1;//初始化结果为1
        for(int i=1;i<=cnt;i++)
        {
            //对每个质数计算1~n的范围内的最高幂次
            res=res*calc(prime[i],n)%mod;
        }
        System.out.println(res);
    }
    //计算1~n范围内x的最高幂次x^k
    static long calc(int x,int y)
    {
        long t=x;//t初始时为x
        while(t<=y)//找到最大的t=x^k<=y
        {
            t*=x;
        }
        return t/x;//回退一步得到x^k;
    }
}

~~~

对于筛选1~n的所有质数的解析
~~~
    static void sieve(int n){    
        for(int i=2;i<=n;i++){
            if(!st[i]){//如果i是质数
                prime[++cnt]=i;//将质数存入prime数组
            }
            //筛去i的倍数
            for(int j=1;j<=cnt;j++){//用当前已经筛选出的质数，与i相乘标记合数
                if((long)prime[j]*i>n)break;//超过n时候跳出循环
                st[prime[j]*i]=true;//标记为合数，因为质数*i一定是合数
                if(i%prime[j]==0)break;//保证每个合数只被最小质因子筛去
            }
    }
}
1.合数：大于1的非质数，即除了1和它本身还有别的数
2.代码中st[i]=false:i是质数；st[i]=true:i是合数
3. if(i%prime[j]==0)break;
任何合数=最小质因子*最大因子
eg:12=2*6
i%prime[j]==0：说明prime[j]是i的最小质因子，也是prime[j] * i 的最小质因子。
如果不break,后续更大的质数 prime[j+1] 会尝试标记 prime[j+1] * i，但这个数应该由 prime[j] 筛去（因为 prime[j] 是更小的质因子）。
这个break跳出内层j循环
~~~

### 2.dfs(搜索)，就是递归，建议先学这个
利用递归函数实现暴力枚举
1. 回溯法
实现斐波那契数列
int func(int i)
{
    if(i==1||i==2)return 1;
    return func(i-1)+func(i-2);//注意这里先计算func(i-1)再计算func(i-2)
}
2. dfs实现指数型枚举
从1~n中任选若干个整数（可以选0个数），输出所有可能的方案
示例：
输入：3
输出：
3 
2 
2 3
1 
3
1 3
1 2
1 2 3 
~~~
//思路：对于每个整数，有两种选择：选或者不选；递归地对每个节点进行这两种选择，可以遍历出所有可能的组合
//用st[i]这个布尔型数组，标记整数i是否位选中
static void dfs(int u)
{
    if(u>n){//表示处理完1~n所有元素，此时得到了一种选择方案
        for(int i=1;i<=n;i++)//遍历st[i]将所有被选中的整数输出
        {
            if(st[i])System.out.print(i+" ");//选，就输出
        }
        System.out.println();
        return;//如果没有这个return，就会一直递归下去,所以需要return
    }
    dfs(u+1);//不选u,继续处理u+1的情况
    st[u]=true;//选u
    dfs(u+1);//选u，处理u+1的情况
    st[u]=false;//恢复到未选择u的状态，以便后续递归调用
}
~~~
全排列
~~~
package demo2;
import java.util.*;

public class Main {
	static List<List<Integer>>list=new ArrayList<>();//二维列表存储排列
	
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int []v=new int[n+1];//是否被选过
        List<Integer>t=new ArrayList<>();
        dfs(n,v,t);
        scan.close();
        for(int i=0;i<list.size();i++)
        {
        	for(int j=0;j<list.get(i).size();j++) {
        		System.out.print("     "+list.get(i).get(j));
        	}
        }
    }
    public static void dfs(int n,int []v,List<Integer>t)
    {
    	if(t.size()==n)//所有的数值都已经选了
    	{
    		list.add(new ArrayList<>(t));//t作为参数加入全排列list中
    		return;//递归出口,return会返回到上一层递归调用即i=3时候的dfs,此时dfs执行完毕，执行v[i]=0操作
    	}
    	for(int i=1;i<=n;i++)
    	{
    		if(v[i]==1)continue;//被选过
    		v[i]=1;//否则没被选过，就选他
    		t.add(i);
    		dfs(n,v,t);//进行下一层for循环
    		v[i]=0;//回撤操作
    		t.remove(t.size()-1);//把加进去的删掉
    	}
    }
}
//由于第三层递归调用是第二层递归调用的dfs触发的，当第三层递归调用的for结束后，就会返回到第二层递归调用中dfs

~~~

3. dfs与记忆化搜索
增加了一个记录中间结果的缓存（一般是数组），避免重复计算 
斐波那契数列记忆化搜索
~~~
int f(int i)
{
    if(i==1||i==2)return 1;
    if(f[n]!=-1)return f[n];
    return f[n]=f(n-1)+f(n-2);
}
通过数组f[]缓存结果，避免重复运算 
~~~
例题：采药
~~~

int dfs(int u,int s){
    if(u>n)return 0;
    int ans1=0,ans2=0;
    if(s+v[u]<=m)
        ans1=dfs(u+1,s+v[u])+w[u];
    ans2=dfs(u+1,s);
    return Math.max(ans1,ans2);

}

int dfs(int u,int s){
    if(u>n)
        retarn dp[u][s]=0;
    if(dp[u][s]!=-1)//检查dp是否已经被计算过，如果值不为-1，说明已经被计算过，直接返回存储的结果
        return dp[u][s];
    int ans1=0,ans2=0,ans=0;
    if(s+v[u]<=m)
        ans1=dfs(u+1,s+v[u])+w[u];
    ans2=dfs(u+1,s);
    ans=Math.max(ans1,ans2);
    return dp[u][s]=ans;//存储当前状态(u,s)的最优解结果到dp[u][s]中，下次遇到相同状态时候无需重新计算
}
第一段代码没有使用记忆化搜索，即没有dp数组，欸此递归都要重新计算子问题的结果
第二段代码使用二维数组dp[u][s]来存储以及计算过的状态（u,s）的结果。如果某个状态（u,s）已经被计算过，则直接返回存储的结果，避免重复计算

~~~

### 3.常见的数组操作（前缀和，差分）
前缀和：用于快速计算数组中某个区间的元素和。二维的可以快速计算矩阵的元素和
差分：用于快速对数组的某个区间进行批量修改，二维的可以快速对矩阵进行批量修改
1. 一维前缀和
~~~
import java.util.*;
import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main{
    static int zu;
    static int a[]=new int[100010] ;
    static int s[]=new int[100010] ;

    public static void main(String[] args){
        int t=1;
        for(zu=1;zu<=t;zu++)solve();
        out.flush();
    }

    static void solve(){
        int n=in.nextInt(),q=in.nextInt();
        for(int i=1;i<=n;i++)   a[i]=in.nextInt();
        for(int i=1;i<=n;i++){
            s[i]=s[i-1]+a[i];
        }
    }
}

~~~
2. 一维差分
1.区间修改问题
    给定一个长度为n的序列a，有m次修改，每次选择一个连续区间l,r,修改区间内所有元素加d
    暴力做法：每次修改区间内所有元素，时间复杂度为O（mn）
2.一维差分实现原理
    定义差分数组b,bi=a[i]-a[i-1]
    b1=a1
    b2=a2-a1
    b3=a3-a2
    对数组b求前缀和得到新数组c
    c1=b1
    c2=b1+b2=a1+a2-a1=a2
    c3=b1+b2+b3=a1+a2+a3-a1-a2=a3
    c4=b1+b2+b3+b4=a1+a2+a3+a4-a1-a2-a3=a4
    得到结论：差分数组求前缀和得到的就是原数组 
3. 二维前缀和
 二维前缀和原理 公式：S[i,j]=a[i,j]+a[i-1,j]+a[i,j-1]+a[i-1,j-1]
4. 二维差分  
### 4.二分（真的很常考二分，二分查找，二分答案）
### 5.dp(动态规划)，有点难，但是爱考，至少要掌握一些最基本的模型，01背包，完全背包，子序列等问题
#### 线性dp
最优子结构
通过子问题的最优解来构建整体最优解
设dp[i][j]为顶点到位置（i,j）的最大路径和
对于（i,j）可以从上一层的（i-1,j）和（i-1,j-1）得到，因此dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])+a[i][j]

无后效性
状态只与上一个状态有关，而不受之前状态的计算过程影响

1. 数字三角形问题
~~~
public static int maximumPathSum(int[][] a) {
    //使用状态方程填充dp数组
    for(int i = 1; i < n; i++){
        //可以从上方或者左上方到达，取两者的最大值
        for(int j = 1; j <=i; j++){
            dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];

        }
    }
    //找到最后一行中的最大值，即最大路径
    int maxSum=0;
    for(int j = 1; j <= n; j++){
        maxSum = Math.max(maxSum, dp[n][j]);
    }
    return maxSum;
}
~~~
2. 最长上升子序列问题
dp[i]=max(dp[i],dp[j]+1)
dp[i]：以第i个元素结尾的最长上升子序列的长度
~~~
int ans=1;
for(int i=1;i<n;i++)
{
    for(int j=0;j<i;j++)
    {
        if(a[i]>a[j]){
            dp[i]=Math.max(dp[i],dp[j]+1);
        }
    }
}
~~~
Arrays.fill(dp,1):将数组dp中所有元素设置为1
3. 翻转后1的数量
dp[i][0]:对于第i个字符，还未经过翻转操作，最多可以得到1的数量
dp[i][1]：对于第i个字符，正在进行翻转操作，最多可以得到1的数量
dp[i][2]：对于第i个字符，已经进行过一次翻转操作，最多可以得到1的数量

~~~
static void solve() {
    int n = in.nextInt();          // 字符串长度
    String s = " "+in.next();          // 二进制字符串,加了一个空格，这样下标就从1开始
    for (int i = 1; i <= n; i++) {
        char x = s.charAt(i-1);    // 第i个字符
        // 状态转移
        dp[i][0] = dp[i-1][0] + (x - '0');  // 未翻转：直接累加当前字符值
        dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]) + ((x ^ 1) - '0'); // 正在翻转：取前驱最大值 + 翻转后的值
        dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]) + (x - '0');       // 翻转结束：取前驱最大值 + 原始值
    }
    // 最终结果是三种状态的最大值
    System.out.println(Math.max(dp[n][0], Math.max(dp[n][1], dp[n][2])));
}
~~~
#### 01背包
不选
dp[i][j]=dp[i-1][j]
选
dp[i][j]=dp[i][j-v[i]]+w[i]
因此有转移方程
dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])
一维优化：
for(int i=1;i<=n;i++)
{
    for(int j=v[i];j<=m;j++){
        dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
    }
}
#### 完全背包
区别于01背包，01背包是每个物品只能选一次，完全背包是每个物品可以选多次
dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])
一维优化：
for(int i=1;i<=n;i++)
{
    for(int j=v[i];j<=m;j++){
        dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
    }
}
只需记住“完全背包正序，01背包逆序”，其他代码完全一致。
01背包：逆序遍历容量（保证物品只选一次）。
完全背包：正序遍历容量（允许重复选择）。

### 6.List和Map
1. List
    1. ArrayList是一个可以动态修改的数组，和普通数组的区别是，没有固定大小的限制，可以添加或者删除元素
    List<Integer>list=new ArrayList<>();
       1. add();
       2. size();
       3. get(int index):返回列表中指定位置的元素,index从0开始
       后面三个方法不太常用
       4. isEmpty();
       5. contains(Object o):判断集合中是否包含某个元素
       6. remove(int index):删除指定位置的元素,并返回删除的元素
    ~~~
    List<Integer> list new ArrayList<>();
    list.add(1);
    list.add(2);
    int x=list.size();//输出2
    int y=list.get(0);//输出1

    ~~~
2. Map
   1. HashMap存储的内容是对键值对key-value的映射
   2. 无序的
   3. 常用方法
      1. put(key,value):添加键值对
      2. get(key):根据key获取value,没有返回null
      3. size():获取键值对的个数
      4. getOrdefault(key,value):根据key获取value 
3. List 和 Map 的联合使用
~~~
 //创建一个哈希map，用于储存日志的ID和对应的时间戳列表
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        //创建一个优先队列 用于存储日志的id 按照默认的自然顺序进行排序（输出格式为从小到大）
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        
 if(map.get(id)==null) {        //如果map中不存在该id对应的时间列表，就创建一个新的列表，并将该id添加到queue中
                map.put(id, new ArrayList<>());
                queue.add(id);
            }
            map.get(id).add(t);            //将时间t添加到该id对应的时间列表中
~~~
### 7. 常用API
   1. 字符串类
        1. charAt(int index):返回char指定索引处的值
~~~
x.charAt(i) 返回的是 char 类型的值，要把字符转换为对应的数字
// 通过减去字符 '0' 将字符转换为对应的数字
            sum += x.charAt(i) - '0';
~~~
        2. append(String str):在字符串末尾追加字符串str
        3. delete(int start,int end):删除指定区间的字符串
        4. reverse():反转字符串
        5. String.valueOf() :将传入的参数转换为字符串类型
        6. boolean isEmpty():判断是否为空字符串
        7. boolean equals(Object obj):比较字符串的内容是否相等
        8. String substring(int beginIndex,int endIndex):返回指定子串,从beginIndex到endIndex-1
        9.  int compareTo(String anotherString):按字典顺序比较两个字符串的大小
        10. Sring[] split(String regex):按照给定规则分割字符串
        11. char[] toCharArray():将字符串转换为字符数组
        12. 将别的类型转化成字符串类，加上一个空的字符串就会自动变成字符串的类型
   ~~~
    String str=new String("abcdef");
    int n=str.length();//0. 字符串长度
    char x=charAt(5);//x=f
    String s=("abcd");
    boolean b=str.equals(s);//3.b=false
    String s1=str.substring(0,2);//4.s1=ab,不包含2处的字符
    int c=str.compareTo(s);//5.c=1,大于输出1，小于输出-1，等于输出0
    //如果字符串按照空格来分割
    String str1="a b c d e f";
    String[] s2=str.split(" ");
    for(int i=0;i<s2.length;i++)
    {
        System.out.println(s2[i]);//6.
    }
    char []c=str.toCharArray();//7.
>   char a='a';
>   String c=a+"";//8.
>    ~~~
1. 大数类
当遇到超过长整型的数据时候
~~~
import java.math.BigInteger;
public classMain{
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        BigInteger a=new BigInteger("123");
        BigInteger b=new BigInteger("456");
        BigInteger c=a.add(b);//加法
        BigInteger d=a.multiply(b);//乘法
        BigInteger e=a.divide(b);//除法
        BigInteger f=a.subtract(b);//减法

    }
}

~~~
### 8. 优先队列
1. 创建优先队列
PriorityQueue<Integer> queue = new PriorityQueue<>();//默认从小到大
PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());//从大到小
2. 常用方法
1. add(E e):添加元素
2. poll():取出并移除队列中的最小元素，如果队列为空，返回null
3. peek():取出队列中的最小元素，如果队列为空，返回null
~~~
import java.util.PriorityQueue;
public class Main {
    public static voi dmain(Strinf ars[])
    {
        PriorityQueue<Integer>priorityQueue=new PriorityQueue<>();

    }
}
~~~
## 遇到的问题
### Map
1. Map实现类
    1. HashMap:不保证元素的顺序
    2. LinkedHashMap:保证元素的顺序
    3. TreeMap:保证元素的顺序,按键的自然顺序或者指定的Comparator排序
2. 其他常见用法
map.getOrDefault(key, defaultValue);//根据键查找对应的值，如果键不存在则返回默认值
### 日期问题
日期字符串输入，
DateTimeFormatter dtf = DateTimeFormatter.ofPattern("yyyyMMdd");
DateTimeFormatter 是 Java 8 引入的一个类，用于格式化和解析日期时间。ofPattern 方法允许您定义一个自定义的日期时间格式模式
LocalDate start = LocalDate.parse(scan.next(), dtf);
LocalDate end = LocalDate.parse(scan.next(), dtf);

天数增加1填：start = start.plusDays(1);

1. 选择合适的日期时间类型
使用 LocalDate 处理日期，不涉及时间部分。
使用 LocalDateTime 处理日期和时间。
使用 ZonedDateTime 处理带有时区的日期和时间。
2. 定义日期格式
使用 DateTimeFormatter 定义日期的格式。
常见的格式模式包括 yyyy-MM-dd（标准格式）、yyyyMMdd（紧凑格式）等。
4. 解析和格式化日期
使用 LocalDate.parse 方法将字符串解析为 LocalDate 对象。
使用 LocalDate.format 方法将 LocalDate 对象格式化为字符串。
~~~
// 定义日期格式
        DateTimeFormatter dtf = DateTimeFormatter.ofPattern("yyyyMMdd");
        
        // 解析字符串为 LocalDate 对象
        String dateStr = "20230101";
        LocalDate date = LocalDate.parse(dateStr, dtf);
        System.out.println("Parsed Date: " + date); // 输出: Parsed Date: 2023-01-01
        
        // 将 LocalDate 对象格式化为字符串
        String formattedDate = date.format(dtf);
        System.out.println("Formatted Date: " + formattedDate); // 输出: Formatted Date: 20230101
~~~
5. 操作日期
使用 plusDays、minusDays、plusMonths、minusMonths、plusYears、minusYears 等方法来增加或减少日期。
使用 isBefore、isAfter、isEqual 等方法来比较日期。
~~~
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;

public class Main {
    public static void main(String[] args) {
        // 定义日期格式
        DateTimeFormatter dtf = DateTimeFormatter.ofPattern("yyyyMMdd");
        
        // 解析字符串为 LocalDate 对象
        String dateStr = "20230101";
        LocalDate date = LocalDate.parse(dateStr, dtf);
        System.out.println("Original Date: " + date.format(dtf)); // 输出: Original Date: 20230101
        
        // 增加一天
        LocalDate nextDay = date.plusDays(1);
        System.out.println("Next Day: " + nextDay.format(dtf)); // 输出: Next Day: 20230102
        
        // 减少一天
        LocalDate previousDay = date.minusDays(1);
        System.out.println("Previous Day: " + previousDay.format(dtf)); // 输出: Previous Day: 20221231
        
        // 增加一个月
        LocalDate nextMonth = date.plusMonths(1);
        System.out.println("Next Month: " + nextMonth.format(dtf)); // 输出: Next Month: 20230201
        
        // 减少一个月
        LocalDate previousMonth = date.minusMonths(1);
        System.out.println("Previous Month: " + previousMonth.format(dtf)); // 输出: Previous Month: 20221201
        
        // 增加一年
        LocalDate nextYear = date.plusYears(1);
        System.out.println("Next Year: " + nextYear.format(dtf)); // 输出: Next Year: 20240101
        
        // 减少一年
        LocalDate previousYear = date.minusYears(1);
        System.out.println("Previous Year: " + previousYear.format(dtf)); // 输出: Previous Year: 20220101
    }
}
~~~
~~~
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;

public class Main {
    public static void main(String[] args) {
        // 定义日期格式
        DateTimeFormatter dtf = DateTimeFormatter.ofPattern("yyyyMMdd");
        
        // 解析字符串为 LocalDate 对象
        String dateStr1 = "20230101";
        String dateStr2 = "20230102";
        LocalDate date1 = LocalDate.parse(dateStr1, dtf);
        LocalDate date2 = LocalDate.parse(dateStr2, dtf);
        
        // 比较日期
        if (date1.isBefore(date2)) {
            System.out.println(date1.format(dtf) + " is before " + date2.format(dtf)); // 输出: 20230101 is before 20230102
        }
        
        if (date1.isAfter(date2)) {
            System.out.println(date1.format(dtf) + " is after " + date2.format(dtf));
        } else {
            System.out.println(date1.format(dtf) + " is not after " + date2.format(dtf)); // 输出: 20230101 is not after 20230102
        }
        
        if (date1.isEqual(date2)) {
            System.out.println(date1.format(dtf) + " is equal to " + date2.format(dtf));
        } else {
            System.out.println(date1.format(dtf) + " is not equal to " + date2.format(dtf)); // 输出: 20230101 is not equal to 20230102
        }
    }
}
~~~
6. 特殊情况
~~~
LocalDate 类会自动处理闰年，确保日期的有效性。
例如，2024-02-29 是有效的日期，而 2023-02-29 是无效的日期。
LocalDate 类会自动处理不同月份的天数。
例如，2023-01-31 加一个月会自动调整为 2023-02-28，而不是 2023-02-31。
~~~
### String类
1. charAt(int index)
这是 String 类的一个方法，用于获取字符串中指定索引位置的字符。
~~~
String str = "Hello, World!";
char ch = str.charAt(7); // ch = 'W'
~~~
2. substring(int beginIndex, int endIndex)
返回从 beginIndex 到 endIndex-1 的子字符串。
3. substring(int beginIndex)
返回从 beginIndex 到字符串末尾的子字符串。
4. concat(String str)
将指定字符串连接到当前字符串的末尾。
~~~
String str1 = "Hello";
String str2 = "World";
String result = str1.concat(", ").concat(str2); // result = "Hello, World"
~~~
5. equals(Object obj)
比较两个字符串是否相同
~~~
String str1 = "Hello";
String str2 = "Hello";
boolean isEqual = str1.equals(str2); // isEqual = true
~~~
6. equalsIgnoreCase(String str)
比较两个字符串是否相同，忽略大小写。
~~~
String str1 = "Hello";
String str2 = "hello";
boolean isEqualIgnoreCase = str1.equalsIgnoreCase(str2); // isEqualIgnoreCase = true
~~~
7. indexOf(String str)
返回指定字符第一次出现的索引，如果未找到返回-1
~~~
String str1 = "Hello World";
int index=str1.indexOf("W");//index=7
//返回子字符串第一次出现的索引，未找到返回-1
int index=str1.indexOf("World");//index=7
~~~
8. lastIndexOf(String str)
返回指定字符最后一次出现的索引，如果未找到返回-1
9. endsWith(String suffix)
检查字符串是否以指定后缀结尾。
~~~
String str = "Hello, World!";
boolean endsWithWorld = str.endsWith("World!"); // endsWithWorld = true
~~~
10. contains(CharSequence s)
判断字符串是否包含指定的字符序列
11. replace(CharSequence target, CharSequence replacement)
将指定字符序列替换为另一个字符序列。

### 取模
为了防止取模过程中出现负数，需要+mod
比如
（a-2*b+c）%mod
应该是（a%mod-2*b%mod+c%mod+mod）%mod
其实取模运算对加法和乘法没有影响，主要是出现减法和除法的时候，可能会出现负数
原理就是-a和-a+mod对mod取模是同余数，所以可以加mod
如果是除法
/a可以用*a^(mod-2)来表示即pow(a,-2,mod)
### 输入
scan.nextLine():

用途: 读取整行输入，包括空格。
scan.nextInt():

用途: 读取下一个整数。
### 输入字符串
 String input = scan.nextLine();
### 回文
~~~
// 检查一个字符串是否是回文
    public static boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
~~~
### 降序升序问题
//a1~aq降序
Arrays.sort(a,1,q+1, Collections.reverseOrder());//排序的结束索引（不包含），因此实际排序范围是 [1, q]。
//aq~an升序
Arrays.sort(a,q,a.length);//[q, n-1]
### 增强for循环
~~~
for (int num : numbers) {
    System.out.println(num);
}
~~~
适用于只需要遍历元素，不需要使用索引的情况
int num是一个临时变量，存储每次从numbers中取出的元素。
### 哈希表
假设输入为：
10
0 5
1 3
1 7
2 2
2 8
2 6
3 1
3 4
3 9
3 10
1. 初始化哈希表
~~~
HashMap<Integer, ArrayList<Integer>> hm = new HashMap<>();
// 初始化后：
// hm: {0=[], 1=[], 2=[], 3=[], 4=[], 5=[], 6=[], 7=[], 8=[], 9=[]}
~~~
1. 读取并填充哈希表
~~~
for (int i = 0; i < n; i++) {
    hm.get(sc.nextInt()).add(sc.nextInt());
}
// 填充后：
// hm: {0=[5], 1=[3, 7], 2=[2, 8, 6], 3=[1, 4, 9, 10]}
~~~
1. 处理每种数字的代价
~~~
for (int i = 0; i < 10; i++) {
    if (hm.containsKey(i)) {// 如果哈希表中存在该数字
        Collections.sort(hm.get(i));// 对数字列表进行排序
        int m = hm.get(i).size() - k;
        for (int j = 0; j < m; j++) {
            ans += hm.get(i).get(j);// 代价累加
        }
    }
}
// 处理过程：
// 数字0:
// 已排序: [5]
// m = 1 - 1 = 0, 不需要移除任何数字
// 数字1:
// 已排序: [3, 7]
// m = 2 - 1 = 1, 移除最小代价3
// 数字2:
// 已排序: [2, 6, 8]
// m = 3 - 1 = 2, 移除最小代价2和6
// 数字3:
// 已排序: [1, 4, 9, 10]
// m = 4 - 1 = 3, 移除最小代价1、4和9
// 其他数字没有出现，跳过
~~~
### 算阶乘
// 迭代法计算阶乘
    static BigInteger solve(int n) {
        BigInteger res = BigInteger.ONE;//这行代码初始化了一个 BigInteger 类型的变量 res，并将其值设置为 1。BigInteger.ONE 是 BigInteger 类中表示数字 1 的常量。res 将用于存储阶乘的计算结果。
        for (int i = 2; i <= n; i++) {
            res = res.multiply(BigInteger.valueOf(i));//将 res 与 i 相乘，并将结果重新赋值给 res。BigInteger.valueOf(i) 将整数 i 转换为 BigInteger 类型，以便能够与 res 进行乘法运算。这个操作在循环中用于计算阶乘
        }
        return res;
    }

### 两个数是否互质
// 使用欧几里得算法计算最大公约数
    static int gcd(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }
    if(gcd(i,c)==1)//x和y的最大公约数是1，两个数互质
### 将一个数组转换成二进制
int[] dp = new int[10];
int l=dp.length;
int mask=0;
for(int i = 1; i <=l; i++){
    mask|=dp[i];
}
### 循环读取操作
        while(sc.hasNext()){}
### 数组求和
使用 Java 8 的 Stream API 对数组 dp 进行求和操作，并将结果赋值给 sum。
        sum = Arrays.stream(dp).sum();// 数组求和
### 将整数转换为字符串:
通过将整数 x 与空字符串进行拼接，将整数 x 转换为字符串形式，存储在变量 s 中
      String s = x + "";
### 将字符串中的字符转换成对应的整数值
将字符串 s 中的每个字符转换为对应的整数值，并存放在数组dp中
~~~
// 数x的每一位都拆出来存入数组
      for(int i = 0 ; i < l ; i++){
        dp[i] = s.charAt(i) - '0';
      }
~~~

### 绝对值
 Math.abs(left - right)
### 整行输入
在IDEL里面测试不出来因为不知道什么时候输入结束，但是程序可识别：
~~~
// 读取输入的导弹高度
        while (scanner.hasNextInt()) {   //使用 scanner.hasNextInt() 判断输入流中是否还有整数。
            heights.add(scanner.nextInt());   //scanner.nextInt() 读取该整数并将其添加到 heights 列表中。
        }
~~~
### 字符串的定义
String[] s = new String[n + 1];//创建一个长度为n+1的数组，用于存储输入的整数。s 是一个字符串数组，长度为 n + 1，索引从0到 n。


### 导入必要的类
import java.util.Scanner;//用于从标准输入读取数据。
import java.util.Arrays;//提供静态方法来操作数组，例如排序。
import java.util.Comparator;//用于自定义对象的排序顺序。

###  使用自定义比较器进行排序
~~~
//Arrays.sort 方法对数组 s 的子数组（从索引1到 n）进行排序。
//使用自定义的 Comparator 来定义排序规则。
//对于字符串 a 和 b，如果 b + a 大于 a + b，则 b 应排在 a 前面
Arrays.sort(s, 1, n + 1, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                return (b + a).compareTo(a + b);
            }
        });
~~~
return (b + a).compareTo(a + b);：
将两个字符串 a 和 b 拼接成两种形式 b + a 和 a + b，然后比较这两种拼接结果的字典顺序，返回比较结果。具体来说：

如果 b + a 大于 a + b，返回正数；
如果 b + a 小于 a + b，返回负数；
如果两者相等，返回0
### 最大值最小值
x=Math.min(a,b);
y=Math.max(a,b);
### 将数组中的整数合并成一个整数
1. 数组中的元素是整数
   将每个整数转换为字符串，然后合并成一个字符串，再转换成整数
   注意合并后的数较大，因此要用long

~~~
public class Main {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        long mergedNumber = mergeArrayToInteger(array);
        System.out.println("Merged Number: " + mergedNumber);
    }

    public static long mergeArrayToInteger(int[] array) {
        //将每个整数转换为字符串并追加到 StringBuilder 中。
        StringBuilder sb = new StringBuilder();

        //使用增强的 for 循环遍历数组 array 中的每个元素 num。
        for (int num : array) {
            //将每个整数 num 转换为字符串并追加到 StringBuilder 对象 sb 中。
            sb.append(num);
        }
        return Long.parseLong(sb.toString());
    }
}
~~~
append 方法用于将指定的内容添加到该对象的末尾。
sb.toString() 方法将 StringBuilder 或 StringBuffer 对象转换为字符串。该方法返回一个表示当前对象内容的字符串，并且不会修改原对象。
Long.parseLong将字符串参数解析为长整型数值

2. 数组中的元素是字符串，将这些字符串连接起来，然后转换为整数。
~~~
public class Main {
    public static void main(String[] args) {
        String[] array = {"1", "2", "3", "4", "5"};
        long mergedNumber = mergeArrayToInteger(array);
        System.out.println("Merged Number: " + mergedNumber);
    }

    public static long mergeArrayToInteger(String[] array) {
        StringBuilder sb = new StringBuilder();
        for (String str : array) {
            sb.append(str);
        }
        return Long.parseLong(sb.toString());
    }
}
~~~


3. 数组元素是字符
将这些字符连接起来，然后转换为整数。
~~~
public class Main {
    public static void main(String[] args) {
        char[] array = {'1', '2', '3', '4', '5'};
        long mergedNumber = mergeArrayToInteger(array);
        System.out.println("Merged Number: " + mergedNumber);
    }

    public static long mergeArrayToInteger(char[] array) {
        StringBuilder sb = new StringBuilder();
        for (char ch : array) {
            sb.append(ch);
        }
        return Long.parseLong(sb.toString());
    }
}

~~~

### JAVA如何输出long,float double类型
int 类型使用 %d
float 类型使用 %f
double 类型使用 %f（与 float 相同，但通常用于更精确的浮点数）
long 类型使用 %d
### 创建列表用于动态删除和添加元素
创建一个名为 heights 的空列表，该列表用于存储整数类型的元素。ArrayList 是 Java 中的一个动态数组实现，可以灵活地添加和删除元素
        List<Integer> heights = new ArrayList<>();

 //将输入的导弹高度添加到 H 数组中
int n = heights.size();
        int[] H = new int[n];
        for (int i = 0; i < n; i++) {
            H[i] = heights.get(i);
        }

### Hash MAP
1. HashSet<Map<Double, Double>> lines
用途：存储所有不同的直线（通过斜率和截距表示）。
每条直线用 Map<Double, Double> 表示，其中键为斜率 k，值为截距 b（对应直线方程 y = kx + b）。
HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。
2. List<Map<Integer, Integer>> list
用途：存储所有网格点的坐标（横纵坐标均为整数）。
每个点用 Map<Integer, Integer> 表示，键为横坐标 x，值为纵坐标 y。
List 保存所有点的列表，方便后续遍历所有两点组合

## 蓝桥杯题单
### JAVA 2025 A组
#### 拼正方形
题目如下：小蓝正在玩拼图游戏，他有 
7385137888721 个 2×2 的方块和 
10470245 个 1×1 的方块，他需要从中挑出一些来拼出一个正方形，比如用 
3 个 2×2 和 4 个 1×1 的方块可以拼出一个 4×4 的正方形，用 9 个 2×2 的方块可以拼出一个 6×6 的正方形，请问小蓝能拼成的最大的正方形的边长为多少。
题解如下：
~~~
/*边长为L个单位长度,在其下方与右边扩展各扩展L个单位面积，右下角再扩展一个单位面积，边长就变成L+1个单位，这里将单位面积看成2*2的方块*/
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        long a2 = 7385137888721L;
        long a1 = 10470245;
        long a = a2 + a1/4;
        long L = 1;
        while(a >= 2*L+1){
            a-= 2*L+1;
            L+=1;
        }
        System.out.println(2*L);
    }
}

~~~
为什么最终输出结果是2*L，因为最开始初始化的时候，L=1是为边长的一半，所以最终边长为2*L
#### 召唤数学精灵
问题描述
数学家们发现了两种用于召唤强大的数学精灵的仪式，这两种仪式分别被称为累加法仪式 A(n) 和累乘法仪式 B(n)据说，当某个数字 i 满足 A(i)−B(i) 能被100 整除时，数学精灵就会被召唤出来。
现在，请你寻找在 1 到 2024041331404202 之间有多少个数字 i，能够成功召唤出强大的数学精灵。
~~~
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        long a = 2024041331404202L;
        long ans = 0;
        int res = 1,cur = 0;
        for(int i = 1; i <= 9; i++){//阶乘从第10项开始都是100的倍数，所以后面只需要判读累加是不是100的倍数就可以，
            res *= i;
            cur += i;
            if ((res-cur) %100 == 0)ans+=1;
        }
        ans += (a/1000)*20;//打表可发现累加中每1000，有20个是100的倍数；
        for(long i = 2024041331404001L; i<= a;i++) {//判断余下不到1000的部分
            long q = i % 100;
            if((q*(q+1)/2) % 100 == 0)ans++;
        }
        System.out.println(ans);
    }
}
~~~
#### 数字诗意
如果一个数能够以若干个（至少两个）连续的正整数相加表示，那么它就蕴含诗意。例如，数字 6 就蕴含诗意，因为它可以表示为 1+2+3。而 8 则缺乏诗意，因为它无法用连续的正整数相加表示。小蓝希望他面前的所有数字都蕴含诗意，为此，他决定从这 n 个数字中删除一部分。请问，小蓝需要删除多少个数字，才能使剩下的数字全部蕴含诗意？
输入格式
第一行包含一个整数 n，表示展示的数字个数。
第二行包含 n 个整数 a1,..an，表示展示的数字。

输出格式
输出一个整数，表示小蓝需要删除的数字个数，以使剩下的数字全部蕴含诗意。
~~~
import java.util.Scanner;
/*找规律
1.除了1以外的奇数都符合
2.对于一个偶数除以2以后是奇数的也可以成立
*/

public class Main {
 public static void main(String[] args) {

        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int ans=0;
        for(int i=1;i<=n;i++) {
            Long j=scan.nextLong();
            while(j%2==0&&j>1) {//注意这里是while循环，是偶数的话就循环直到循环到奇数，否则不用管
                j/=2;
            }
            if(j==1) {
                ans++;
            }
        }
        System.out.println(ans);
    
    }

}

~~~
#### 回文数组
问题描述:
小蓝在无聊时随机生成了一个长度为 n 的整数数组，数组中的第之个数为 ai，他觉得随机
生成的数组不太美观，想把它变成回文数组，也是就对于任意i€[1,n]满足 ai=
a(n-i+1)。小蓝一次操作可以指定相邻的两个数，将它们一起加 1 或减 1;也可以只指定-
个数加 1 或减 1，请问他最少需要操作多少次能把这个数组变成回文数组?
输入格式:
输入的第一行包含一个正整数 n。
第二行包含 几 个整数 a1,a2,···,an，
相邻整数之间使用一个空格分隔。
输出格式:
输出一行包含一个整数表示答案。
~~~
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[ ] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int []num=new int[n+1];
        for(int i=1;i<=n;i++)
            num[i]=scan.nextInt();
        //通过调整相邻的两个元素，减少操作次数
        long res=0;
        for(int i=1;i<n/2;i++){
            int x=num[i]-num[n-i+1];//当前元素与对称元素的差值
            int y=num[i+1]-num[n-i];//下一个元素与对称元素的差值
            if(x<0&&y<0){//两个元素都比对称元素小，注意这里x,y都是负数
                int nums=Math.max(x,y);//计算增加的最大值
                num[i]=num[i]-nums;//因此这里是减负数即加上绝对值
                num[i+1]=num[i+1]-nums;//同理
                res=res-nums;//同理
            }
            else if(x>0&&y>0){
                int nums=Math.min(x,y);
                num[i]=num[i]-nums;
                num[i+1]=num[i+1]-nums;
                res=res+nums;
            }
        }
        //无法通过相邻元素调整的满足的元素，单独调整
        for(int i=1;i<=n/2;i++)
            res+=Math.abs(num[i]-num[n-i+1]);
        System.out.println(res);
        scan.close();
    }
}
~~~

#### 吊坠
问题描述
小蓝想制作一个吊坠，他手上有n个长度为 m 的首尾相连
的环形字符串{s1,s2，…,sn}，他想用n-1条边将这
n-1个字符串连接起来做成吊坠，要求所有的字符串连完后形
成一个整体。
连接两个字符串 si,sj的边的边权为这两个字
符串的最长公共子串的长度(可以按环形旋转改变起始位
置，但不能翻转)
小蓝希望连完后的这n-1条边的边权和最大，这样的吊坠他觉得最好看，请计算最大的边权和是多少。
输入格式:
输入的第一行包含两个正整数 n,m，用一个空格分隔。
接下来n行，每行包含一个长度为 m 的字符串，分别表示
S1,s2,..,Sn。
输出格式:
输出一行包含一个整数表示答案。
样例输入
4 4
aabb
abba
acca
abcd
样例输出
8
样例说明
连接< 1,2 >,< 2,3 >,<2,4>，边权和为4+2+2 =8。
~~~
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    // 存储所有字符串
    static String[] strings;
    // 存储最大边权和
    static int maxWeightSum = 0;
    // 字符串长度
    static int m;
    // 顶点数量
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        strings = new String[n];

        // 读取每个字符串
        for (int i = 0; i < n; i++) {
            strings[i] = scanner.next();
        }

        // 存储当前生成树的边
        List<int[]> currentTree = new ArrayList<>();

        // 调用 buildSpanningTree 方法，从顶点 0 开始构建生成树，初始边权和为 0。
        buildSpanningTree(0, currentTree, 0);

        System.out.println(maxWeightSum);
        scanner.close();
    }

    // 递归构建生成树
    public static void buildSpanningTree(int currentVertex, List<int[]> currentTree, int currentWeightSum) {
        // 如果生成树的边数达到 n - 1，说明已经构建好一棵生成树
        if (currentTree.size() == n - 1) {
            // 检查是否是有效的生成树（所有顶点都连通）
            if (isValidSpanningTree(currentTree)) {
                // 更新最大边权和
                maxWeightSum = Math.max(maxWeightSum, currentWeightSum);
            }
            return;
        }

        // 尝试连接当前顶点到其他未连接的顶点
        for (int nextVertex = currentVertex + 1; nextVertex < n; nextVertex++) {
            // 计算当前边的权重
            int edgeWeight = calcValue(strings[currentVertex], strings[nextVertex], m);
            // 记录当前边
            int[] edge = {currentVertex, nextVertex, edgeWeight};
            // 将边加入当前生成树
            currentTree.add(edge);
            // 递归构建下一个顶点的生成树
            buildSpanningTree(nextVertex, currentTree, currentWeightSum + edgeWeight);
            // 回溯，移除当前边
            currentTree.remove(currentTree.size() - 1);
        }
    }

    // 检查当前边的组合是否构成一棵有效的生成树
    public static boolean isValidSpanningTree(List<int[]> tree) {
        boolean[] visited = new boolean[n];
        dfs(0, visited, tree);
        for (boolean v : visited) {
            if (!v) {
                return false;
            }
        }
        return true;
    }

    // 深度优先搜索遍历图
    public static void dfs(int node, boolean[] visited, List<int[]> tree) {
        visited[node] = true;
        for (int[] edge : tree) {
            if (edge[0] == node && !visited[edge[1]]) {
                dfs(edge[1], visited, tree);
            } else if (edge[1] == node && !visited[edge[0]]) {
                dfs(edge[0], visited, tree);
            }
        }
    }

    // 计算两个字符串的最大连续匹配长度
    public static int calcValue(String a, String b, int length) {
        int maxCnt = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                int cnt = 0;
                for (int pos = 0; pos < length; pos++) {
                    if (a.charAt((i + pos) % length) == b.charAt((j + pos) % length)) {
                        cnt++;
                    } else {
                        break;
                    }
                }
                maxCnt = Math.max(maxCnt, cnt);
            }
        }
        return maxCnt;
    }
}

~~~
#### 砍柴
问题：t个长度为x的木头，两个人交替砍柴，每次砍下长度为p的木头，2<=p<=x,且p为质数，当x=1或x=0时候不能继续砍柴，就输了。对每根木头判断是哪一方赢
A赢输出1，B赢输出0,A先出手
输入：
第一行输入t
接下来t行，每行一个正整数，其中第i的整数位ni
输出：
t行，每行一个整数，表示第i根木头，A赢还是B赢
例子
输入：
3
1
2
6
输出
0
1
1
解释：n1=1,相当于当前长度x=1,B赢
n2=2,A选择p=2时，轮到B，x=2-2=0,A赢
n3=6，A选择p=5,轮到B时，x=6-5=1,A赢
思路：每次都是A先出手，她选择的p既是质数，又是大于2小于给的数字x的，
①如果当前数字<=1，则A输
②如果A出的数剩下的数字<=1，则A赢，否则A输
所以：（1）先写一个判断是否为质数的函数
（2）A每次出范围内最大的质数，然后判断剩下的数字是否<=1，是则A赢，否则A输
~~~
/*
用我自己的方法竟然通过率百分之0，这也太挫败了我勒个天

import java.util.Scanner;

public class Main {

    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        for (int i = 0; i < t; i++) {
            int n = scan.nextInt();
            if (n <= 1) {
                System.out.println("0");
            } else {
                int a = 2; // 初始化 a 为最小的质数
                for (int j = 2; j <= n; j++) {
                    if (isPrime(j)) {
                        a = j; // 更新 a 为当前找到的最大质数
                    }
                }
                // 检查 n 和 a 的差值
                if ((n - a) <= 1) {
                    System.out.println("1");
                } else {
                    System.out.println("0");
                }
            }
        }
        scan.close();
    }
}
这种方法的思路过于简单，只考虑了 A 每次选择范围内最大的质数进行砍伐，而没有考虑到整个游戏过程中的策略。在实际的游戏中，玩家会根据当前的局面做出最优选择，而不是固定选择最大的质数。例如，对于某些数字，选择较小的质数可能会让自己处于更有利的位置，而该方法没有考虑这种情况，所以导致通过率为 0。
*/
/*第二种方法使用了动态规划（DP）的思想，考虑了所有可能的砍伐情况。通过构建一个 dp 数组，记录每个长度的木头在最优策略下的胜负情况，从而可以准确地判断出对于任意长度的木头，先手玩家是否能赢。*/

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    // 判断质数
    public static boolean isZhiShu(Integer num) {
        if (num == 0 || num == 1) {
            return false;
        }
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int[] arr = new int[t];
        for (int i = 0; i < t; i++) {
            arr[i] = sc.nextInt();
        }
        // 初始化质数表
        int[] zhiShu = new int[100000];//长度位100000的数组存储质数
        int zhiShuIndex = 0;//用于记录质数的数量
        for (int i = 0; i < 1000001; i++) {//将1000001以内的质数存储在数组中
            if (isZhiShu(i)) {
                zhiShu[zhiShuIndex] = i;
                zhiShuIndex++;
            }
        }
        // dp表记录胜负情况，判断是否我放赢，1代表我方赢，0代表我方输
        int[] dp = new int[100001];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 1;
        // 初始化dp
        for (int i = 4; i < 100001; i++) {
            int flag = 0;
            // 遍历质数表，取出数字小于当前的i的所有质数，判断如果我砍掉这个数字之后，对方拿到的剩下的数字是不是必输
            // 即dp[i-zhiShu[j]]==0
            //差别就在这！遍历了所有在范围内的质数的情况
            for (int j = 0; zhiShu[j] <= i; j++) {
                if (dp[i - zhiShu[j]] == 0) {
                    dp[i] = 1; // 对方必输，我方赢
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) {
                dp[i] = 0;
            }
        }
        // 每个dp就是对应的结果
        for (int j : arr) {
            System.out.println(dp[j]);
        }
    }
}
~~~
#### 回文字符串
题目：
只包含小写字母的字符串S，可以往字符串开头加入任意数目的指定字符，l,q,b(ASCII码分别是108，113，98)，判断是否能通过这种方式将S转化成回文字符串。
输入：
第一行整数t
t组数据
每组数据一行包含一个字符串S
输出：
t行，每行一个Yes或No
示例：
输入：
3
gmgqlq
pdlbll
aaa
输出：
Yes
No
Yes
思路：
（1）本来就是回文字符串，直接输出Yes（写一个判断回文字符串的函数）
（2）如果不是，看l==r,如果是，再看l++,r--,是否相等；如果不是，看r是不是l,q，b其中一个，加到开头，不是直接return,再r--判断
~~~
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.nextLine();
        for (int i = 0; i < n; i++) {
            String s = scan.nextLine();
            if(check(s)){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
    }

    public static boolean check(String s) {
        int l = 0, r = s.length() - 1;
        while(l <= r){
            char left = s.charAt(l),right = s.charAt(r);
            if(left == right){
                l++;
                r--;
            }else{
                if(right == 'l' || right == 'q' || right == 'b'){
                    r--;//妙啊！我想的是加，应该直接减，省事！
                }else{
                    return false;
                }
            }
        }
        return true;
    }
}
~~~
charAt(int index) 是 String 类的一个方法，它接受一个整数参数 index，并返回该索引位置处的字符
因此，s.charAt(left) 的意思是获取字符串 s 在索引 left 处的字符。

#### 智力测试
问题描述：
n*m的棋盘，对每行设置权重{R1,R2,R3...Rn},对每列设置权重{C1,C2,C3...Cm}，因此对于r行r列的格子，其点权为（Rr,Cc）,可以一步走到任意格子（r',c）或（r,c'），其中Rr'>Rr,Cc'>Cc
有t个问题，第i个问题是：假设从（sir,sic）出发，移动到（tir,tic）有多少种走法，答案对1000000007取模
输入格式：
第一行三个正整数n,m,t
第二行n个正整数，表示每行的权重
第三行m个正整数，表示每列的权重
t行，每行四个正整数sir,sic,tir,tic
输出格式：
t行，每行一个正整数，表示第i个问题的答案
示例：
输入：
4 4 2
4 2 3 1
2 1 2 1
4 4 1 1 
2 2 2 4
输出：
4
0
思路：
（1）只能往右，往下，不能往左，往上

~~~

~~~
### JAVA 2025 B组
#### 报数游戏
问题：轮流报出20或24背书的正整数
前10 个被报出的数是：
20,24,40,48,60,72,80,96,100,120。
请问第 202420242024 个被报出的数是多少?
思路：发现第10个数，第20个数，第30个数，第40个数......（每十个数为一轮）等等都是120的倍数，

既然题目要求第202420242024个数，那我们不妨先求第202420242020个数，然后再往后再多求4个数就行。
也就是202420242020/10*120=202429042904240，找它之后的四个能被20或24整除的数，也就是
2429042904288
~~~
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        long a=2429042904288L;
        System.out.println(a);
  
        scan.close();
    }
}
~~~
#### 类斐波那契循环数
问题：n位十进制数N=d1d2d3..dn可以生成一个斐波那契数列，数列S的前n个数{S1=d1,S2=d2..Sn=dn}数列S的第k个数是Sk-n+...+Sk-1。
如果这个数N会出现哎对应的类斐波那契数列S中，那么N就是一个类斐波那契循环数。
对于197，对应数列S为{1，9，7，17，33，57，107，197...},其中
17=1+9+7
33=9+7+17
57=7+17+33
107=17+33+57
197=33+57+107
197出现在数列S中，所以197是一个类斐波那契循环数。
问：0至10^7中，最大的类斐波那契循环数是多少？

解题思路：
反向遍历，找到的第一个类斐波那契数就是最大的（要写一个判断的函数）
~~~
import java.util.Scanner;
import java.util.Arrays;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //反向遍历
        for(int i = 10000000 ; i > 0 ; i--){
          if(check(i)){// i为目标则打印结果，并结束循环
            System.out.println(i);
            break;
          }
        }
        scan.close();
    }

    /*
      检查该数是否为类斐波那契循环数
    */
    public static boolean check(int x){
//将整数转换为字符串:通过将整数 x 与空字符串进行拼接，将整数 x 转换为字符串形式，存储在变量 s 中
      String s = x + "";
      // 获取位数
      int l = s.length();
      int[] dp = new int[l];

      // 数x的每一位都拆出来存入数组
      for(int i = 0 ; i < l ; i++){
        dp[i] = s.charAt(i) - '0';
      }
      int sum = 0 ;
      // 迭代数组检查该数是否为类斐波那契循环数
      for(int i = l ; sum < x ; i++){
        //使用 Java 8 的 Stream API 对数组 dp 进行求和操作，并将结果赋值给 sum。
        sum = Arrays.stream(dp).sum();// 数组求和
        dp[i%l] = sum;
      }
      // 跳出循环后sum >= x
      return sum == x;
    }
}
~~~
#### 分布式队列
题目：N个结点的队列，0号为主节点，其余1~N-1都是副节点，每个节点各自维护一个队列，每次添加元素都是讲元素添加到主节点对应队列的尾部，副节点只负责同步主节点中的队列。元素只有同步到副节点后才具有可见性
给出一个分布式队列的状态，所有操作按顺序执行，回答在某个时刻，队列中有多少个元素具有可见性
输入：
第一行一个正整数N，表示队列中结点的个数
多行输入，每行一个操作，操作类型有：add（添加到队列）,sync（同步操作，副节点会从主节点中同步下一个自己缺失的元素）,query（查询，当前分布式队列中有多少个元素具有可见性）
输出：对于每个query操作，输出一行，包含一个整数表示答案
示例：
输入：
3
add 1
add 2
query
add 1
sync 1
sync 1
sync 2
query
sync 1
query
sync 2
sync 2
sync 1
query
输出：
0
1
1
3
思路：
（1）使用一个数组来记录每个副节点的同步状态，初始时所有副节点的同步状态为 - 1，表示未同步任何元素
（2）对于每个add操作，将元素添加到主节点对应的队列的尾部,还得记录一下a数组的个数，因为b数组每个元素的最大值不超过a数组的个数
（3）对于每个sync操作，将副节点对应下标元素加一
（4）对于每个query操作，统计副节点队列中每个下标，元素最小的那个就是可见的元素个数
~~~
import java.util.Scanner;
    public class Main{
      public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//节点数
        int count[] = new int[n];//count用于记录每个节点队列的元素数,下标为0的是主节点
        //!!!循环读取操作
        while(sc.hasNext()){
          String op = sc.next();
          if(op.equals("add")){
            int x = sc.nextInt();
            count[0]++;   //如果添加，主节点队列元素数加1
          }else if(op.equals("sync")){
            int x = sc.nextInt();
            //副队列同步主队列，如果在执行这次操作时副队列已经是跟主队列相同了，此时再加1并不合理，最高就是跟主队列相同
            count[x] = Math.min(count[x] + 1,count[0]);
          }else{
            int mi = count[0];//先假定主队列的所有数都可见，然后不断对比副队列去缩小个数
            for(int i = 1;i < n; i++){//从1开始，因为下标0是主队列的元素个数
              mi = Math.min(count[i],mi);//所有队列都有的才可见
            }
            System.out.println(mi);
          }
        }        
      }
    }
~~~
#### 食堂
问题：
a2个两人寝，a3个三人寝，a4个四人寝
食堂有b4个四人桌，b6个六人桌
每个寝室的同学在一个桌吃饭，食堂最多可以同时满足多少同学用餐
输入：
输入整数q表示测试用例的组数
输入q行，每行a2,a3,a4,b4,b6
输出：
q行，每行一个整数，表示最多可以同时满足多少人用餐
示例：
输入
2
3 0 1 0 1
0 2 2 1 1
输出：
6
10
思路：
数组a[]={a2,a3,a4}={2*i,3*i,4*i},b4[],b6[]
（1）先看有几人桌，
①有一个六人桌,最多可以容纳6个人，看人数：3*2，1*4，看他们之间的组合值，取最大，注意不能大过6
②有一个四人桌，一个六人桌，最大值是10
人数：有2*3，2*4，10
（2）问题在于，如何进行组合(分类讨论呀！！！情况又不多，直接列举！！！)
~~~
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int q=sc.nextInt();
        while(q-->0) {
            int a2=sc.nextInt();
            int a3=sc.nextInt();
            int a4=sc.nextInt();
            int b4=sc.nextInt();
            int b6=sc.nextInt();
            int sum=0;
            //满座匹配4人寝坐4人桌
            while(b4>0&&a4>=1) {
                b4--;a4--;sum+=4;
            }
            //满座匹配2x2人寝坐4人桌
            while(b4>0&&a2>=2) {
                b4--;a2-=2;sum+=4;
            }
            //满座匹配2+4人寝坐6人桌
            while(b6>0&&a4>=1&&a2>=1) {
                b6--;a4--;a2--;sum+=6;
            }
            //满座匹配2x3人寝坐6人桌
            while(b6>0&&a3>=2) {
                b6--;a3-=2;sum+=6;
            }
            //满座匹配3x2人寝坐6人桌
            while(b6>0&&a2>=3) {
                b6--;a2-=3;sum+=6;
            }
            //空1座匹配2+3人寝坐6人桌
            while(b6>0&&a2>=1&&a3>=1) {
                b6--;a2--;a3--;sum+=5;
            }
            //空1座匹配3人寝坐4人桌
            while(b4>0&&a3>0) {
                b4--;a3--;sum+=3;
            }
            //空2座匹配2x2人寝坐6人桌
            while(b6>0&&a2>=2) {
                b6--;a2-=2;sum+=4;
            }
            //空2座匹配4人寝坐6人桌
            while(b6>0&&a4>0) {
                b6--;a4--;sum+=4;
            }
            //空2座匹配2人寝坐4人桌
            while(b4>0&&a2>0) {
                b4--;a2--;sum+=2;
            }
            //空3座匹配3人寝坐6人桌
            while(b6>0&&a3>0) {
                b6--;a3--;sum+=3;
            }
            //空4座匹配2人寝坐6人桌
            while(b6>0&&a2>0) {
                b6--;a2--;sum+=2;
            }
            System.out.println(sum);
        }
    }
}
~~~
#### 最优队列
（感觉像是二分法的演变）
问题：
将n个宠物分成若干组，每组k只，如果测试为阴性则该组宠物没有感染；若为阳性，则对k只宠物单独测试，消耗k只试剂
已知每只宠物被感染的可能性为p，k应该取值为多少才使得测试剂消耗数目最少
输入：
第一行整数n
第二行浮点数p
输出：
k
~~~
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n = scan.nextInt();
        double p = scan.nextDouble();
        // 初始化最小测试次数为double类型的最大值
        double miny = Double.MAX_VALUE;
        // 初始化最小组数为int类型的最大值
        int mink = Integer.MAX_VALUE;

        for(int k=n;k>=1;k--) {//分成k组
            if(n%k==0) {//每组n/k只
            //每组k只宠物都不感染的概率
                double P=Math.pow(1-p,k);
                //测试次数：不感染的概率*n/k+感染概率*(k+1)*n/k
                double E=(P+(1-P)*(K+1))*N/K;//测试次数
                if(K==1)E=N;
                //如果当前测试次数小于最小测试次数，更新最小测试次数和最小组数
                if(E<miny) {
                    miny=E;
                    mink=k;
                }
            }
        }
        System.out.println(mink);
        scan.close();
    }
}
~~~
#### 星际旅行
题目：
有n个星球，m到双向传送门，第i道传送门可以连接ai,bi两颗星球
有Q个盲盒，第i个盲盒里规定起始星球xi最多可以使用传送门的次数yi。只要从起始星球出发，使用传送门不超过规定次数，能到达的所有星球都可以去旅行
输入：一共m+Q+1行
第一行：n m Q
m行：每行ai bi
Q行：每行xi yi
输出：
一个浮点数（保留两位小数）
样例：
3 2 3
1 2
2 3
2 1
2 0
1 1
输出：
2.00
思路：
1. 创建一个n*n的二维数组，用来记录每个星球的传送门次数，初始化为0
2. 遍历m行，将ai和bi的值赋给对应的位置
3. 
~~~
import java.util.*;
 
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[][] distance = new int[n+1][n+1];//从[ ]到[ ]的最短距离 
        for(int i=0;i<=n;i++) {
            Arrays.fill(distance[i], Integer.MAX_VALUE/2);//先存入一个较大的数
            distance[i][i] = 0;//自己到自己的距离为0
        }
        for(int i=0;i<m;i++) {//如果ab间有传送点
            int a = scan.nextInt();
            int b = scan.nextInt();
            distance[a][b] = 1;//ab ba间距离为1
            distance[b][a] = 1;
        }
        for(int k=1;k<=n;k++) {//中间点
            for(int i=1;i<=n;i++) {//起始点
                for(int j=1;j<=n;j++) {//中止点
              //如果i与j之间存在一个k使ik+kj的距离比ij更小,ij的最短距离就是他
                    distance[i][j] = Math.min(distance[i][k]+distance[k][j], distance[i][j]);
                }
            }
        }
        double count = 0;
        for(int i=0;i<q;i++) {
            int start = scan.nextInt();
            int usecount = scan.nextInt();
            int ans = 0;
            for(int j=1;j<=n;j++) {
                if (distance[start][j] <= usecount) {//如果从起始到j的距离小于可使用次数
                    ans++;//该盲盒可旅行到的星球++
                    }
            }
            count += ans;//累加进总次数
        }
        System.out.println(String.format("%.2f", count/q));
    }
}
~~~
1. Arrays.fill(distance[i], Integer.MAX_VALUE/2);：
   使用 Arrays.fill 方法将 distance[i] 数组（即二维数组的每一行）的所有元素填充为 Integer.MAX_VALUE/2，这是一个较大的数，表示初始时任意两个星球之间的距离是未知的（无穷大）。

#### LITS游戏

#### 拼十字


### JAVA 2024 A组
#### 特殊日期
问题：1900年1月1日至9999年12月31日总共有多少天：年份的数位数字之和=月的数位数字之和+日的数位数字之和
例如：2022年11月13日满足要求，2+0+2+2=1+1+1+3
提交满足条件的日期总数量
思路：输入一个日期，日期从1900年1月1日到9999年12月31日，判断年份前四位数之和与后四位数之后是否相等
我的答案：错误
错误原因：没有考虑到每个月的差异，只是按照31天来算，也没有考虑闰年的问题
计算年份的数位和：year/1000+year/100%100+yuear/10%10+year%10
计算月份和日期的数位和：mon%10+mon/10+day%10+day/10
每次循环结束后增加天数，天数超出实际天数，重置天数并增加月份，月份超出实际月份，重置月份并增加年份
~~~
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int ans=0;
        for(int i = 1900; i <= 9999; i++)
        {
            //获取年份前四位数之和
            int sum = i/10000+(i/1000)%10+(i/100)%10+(i/10)%10+i%10;
            for(int j = 1; j <= 12; j++)
            {
                for(int k = 1; k <= 31; k++)
                {
                    if(j+k == sum)ans++;
                }
            }
        }
        System.out.println(ans);
        scan.close();
    }
}
~~~
我的答案：94155
正确答案：70910
~~~
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
    int year = 1900; //年
        int mon = 1; //月
        int day = 1; //日
        int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
        int count = 0;
        while (true) {
            if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) { //先判断是否为闰年
                month[2] = 29; //是的话2月有29天
            } else {
        month[2] = 28; //不是的话2月有28天，一定要加这个else，否则闰年过后2月还是29天，没改回来
      }
            if (year / 1000 + year / 100 % 10 + year / 10 % 10 + year % 10 == mon % 10 + mon / 10 + day % 10
                    + day / 10) { //把年份的每一位拆解，月份和天也拆解，判断是否数位相加之后相等
                count++;
            }
            day++;
            if (day > month[mon]) { //如果天数大于这个月的具体天数，则天数归1，月份+1
                day = 1;
                mon++;
                if (mon > 12) { //月份如果大于了12，就表示该进入下一年，月份归1，年份+1
                    mon = 1;
                    year++;
                }
            }
            if (year == 9999 && mon == 12 && day == 31) { //到这个日期停止，手动算一下这天不符合题目要求，就直接跳出while循环
                break;
            }
        }
        System.out.println(count); //输出结果
    }
}
~~~
#### 与或异或
题目：
arr[i][j]表示第i行第j列的元素值，其中arr[0][0]=(In[0],In[1],In[2],In[3],In[4])表示的是输入数据，对于某一个arr[i][j]，计算方式是arr[i][j]=arr[i-1][j] op arr[i-1][j+1],其中op表示的是将arr[i-1][j],arr[i-1][j+1]作为输入，arr[i][j]作为输出，op的取值有三种：&,|,^（异或）
已知：
In[0]=1,In[1]=0,In[2]=1,In[3]=0,In[4]=1
想要最终输出的结果为1，请问又多少种不同的门电路组合方式
~~~
public class Trial {
    static int [][]op=new int[5][5];
    static int [][]In=new int[10][10];
    static long ans;
    public static void main(String[] args) {
        In[0][1]=1;In[0][2]=0;  In[0][3]=1;In[0][4]=0;  In[0][5]=1;
        dfs(1,1);
        System.out.println(ans);
    }
    static void dfs(int x,int y){
        if(x==5){//递归终止条件（已经完成了5层的操作符填充）
            for(int i=1;i<=4;i++){
                for(int j=1;j<=5-i;j++){//遍历操作符
                    if(op[i][j]==1)
                        In[i][j]=In[i-1][j]&In[i-1][j+1];//&操作
                    if(op[i][j]==2)
                        In[i][j]=In[i-1][j]|In[i-1][j+1];//|操作
                    if(op[i][j]==3)
                        In[i][j]=In[i-1][j]^In[i-1][j+1];//^操作
                }
            }
            if(In[4][1]==1)
                ans++;
            return;
        }
        for(int i=1;i<=3;i++){
            op[x][y]=i;//对于每一层的每一个位置尝试填充三种操作符
            if(x+y==5)//如果所有操作符已经填充完毕，进入下一行递归
                dfs(x+1,1);
            else
                dfs(x,y+1);//否则进入当前行的下一列递归
        }
    }
}
~~~
#### 平均
长度为n的数组（n是10的倍数），每个数ai都是区间[0,9]中的整数，每种数出现的次数不太平均，更改第i个数的代价是bi,想更改若干个数的值使得这10种数出现的次数相等（都等于n/10），代价和最小为多少
输入：
n
n行：每行两个数ai,bi
输出：
代价和
思路：
对于相同的ai,保留代价最大的n个，其他都更改
我的答案0/20
错误原因：
1. 忽略题目核心：将数组中的每种数字调整为出现次数相等（n/10）且代价最小
2. 题目要求的是全局最优解，而我的代码是局部最优解，只处理了相邻相同的数字
3. 没有统计每种数字ai出现的次数
4. 没有根据每种数字的出现次数决定需要更改哪些数字以及如何更改才能使代价最小

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

public class Main {
	static void solve(int x)
	{
		//将b[i]排序，输出
	}
 public static void main(String[] args) {
     Scanner scan = new Scanner(System.in);
     //在此输入您的代码...
     int N = scan.nextInt();
     int n=N/10;
     int a[]=new int[10001];
     int b[]=new int[10001];
     int ans=0;
     for(int i=0;i<N;i++)
     {
    	 a[i]=scan.nextInt();
    	 b[i]=scan.nextInt();
     }
     for(int i=0;i<N;i++)
     {
    	 if(a[i]==a[i+1])
    	 {
    			 if(b[i+1]>b[i])
    			 {
    				 ans+=b[i];
    			 }
    		 
    	 }
     }
     System.out.println(ans);
     scan.close();
 }
}
~~~
正确代码：
1. 使用小根堆来存储每个数字的ai和所有代价bi（主要核心在这！）
2. 对于每种数字ai,如果出现次数超过n/10,将对于的数字对应的最小代价累加到ans中
3. 遍历结束后，输出ans
~~~
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n,ans=0;
        n = sc.nextInt();
        int k = n / 10;

        HashMap<Integer, ArrayList<Integer>> hm = new HashMap<>();
        for (int i = 0; i < 10; i++) {
            hm.put(i,new ArrayList<Integer>());
        }
        for (int i = 0; i < n; i++) {
            //读取ai,bi,并将bi添加到对应数字ai的ArrayList中
            hm.get(sc.nextInt()).add(sc.nextInt());
        }
        for (int i = 0; i < 10; i++) {
            if(hm.containsKey(i)){//如果哈希表中存在该数字，则对该数字的所有代价进行升序排序
                Collections.sort(hm.get(i));
                int m = hm.get(i).size()-k;//计算需要移除的数字个数
                for (int j = 0; j < m; j++) {
                    ans += hm.get(i).get(j);//累加前m个最小代价到ans中
                }
            }
        }
        System.out.println(ans);
    }
}
~~~
#### 棋盘
问题：
n*n的棋盘，一开始棋盘上全是白子，m次操作，每次操作将棋盘上某个范围内的棋子颜色取反。输出所有操作做完后棋盘上每个棋子的颜色
输入：
n m
m行，每行四个数，x1,y1,x2,y2
输出：
n行，每行n个0或1，表示棋盘上每个棋子的颜色
我的答案：10/10正确！
~~~
package project1;
import java.util.Scanner;
//1:无需package
//2: 类名必须Main, 不可修改

public class Main {
 public static void main(String[] args) {
     Scanner scan = new Scanner(System.in);
     //在此输入您的代码...
     int n=scan.nextInt();
     int m=scan.nextInt();
     int a[][]=new int[n+1][n+1];
     //初始化
     for(int i=1;i<=n;i++)
     {
    	 for(int j=1;j<=n;j++)
    	 {
    		 a[i][j]=0;
    	 }
     }
     for(int k=0;k<m;k++)
     {
    	 int x1=scan.nextInt();
    	 int y1=scan.nextInt();
    	 int x2=scan.nextInt();
    	 int y2=scan.nextInt();
    	 for(int i=x1;i<=x2;i++)
         {
        	 for(int j=y1;j<=y2;j++)
        	 {
        		 a[i][j]++;
        	 }
         }
     }
     for(int i=1;i<=n;i++)
     {
    	 for(int j=1;j<=n;j++)
    	 {
    		 if(a[i][j]%2==0)System.out.printf("0");
    		 else
    			 System.out.printf("1");
    	 }
    	 System.out.printf("\n");
     }
     
     scan.close();
 }
}

~~~
#### 互质数的个数
我的答案：4分（运行超时）
分析：
1. 使用简单循环来计算c，当b非常大时，这种方法会超时
2. 在计算有多少个数和c互质的时候使用双重循环，可能会超时
3. 题目要求计算小于a^b且与a^b互质的数，这是一个典型的欧拉函数，但是没有利用欧拉函数的性质，而是直接暴力检查每个数是否互质，效率低下
~~~
/*a,b,求1<=x<a^b,中有多少个x和a^b互质，答案对998244353 取模*/
package project1;
import java.util.Scanner;
//1:无需package
//2: 类名必须Main, 不可修改

public class Main {
	static long gcd(long x,long y)
	{
		while(y!=0)
		{
			long temp=y;
			y=x%y;
			x=temp;
		}
		return x;
	}
	// 判断两个数是否互为质数
    static boolean areCoprime(long x, long y) {
        return gcd(x, y) == 1;
    }
 public static void main(String[] args) {
     Scanner scan = new Scanner(System.in);
     //在此输入您的代码...
     long a=scan.nextInt();
     long b=scan.nextInt();
     long c=1;
     long N=998244353L;
     scan.close();
     for(int i=0;i<b;i++)
     {
    	 c=(c*a)%N;
     }
     //在1~c中有哪些数和c互质
     long count=0;
     for(int i=1;i<c;i++)
     {
    	 if(areCoprime(i,c))//x和y的最大公约数是1，两个数互质
    	 {
    		 //System.out.println(i);
    		 count++;
    	 }
     }
     long ans=0;
     ans=count % N;
     
     System.out.println(ans);
    
 }
}
~~~
正确答案：
要计算1~a^b范围内与a^b互质的数的个数：（即质因素，因素中互质的那些数）
解题步骤：
1. 欧拉函数：计算与a互质的数的个数f(a)
2. 快速幂：计算a^(b-1)
3. 利用欧拉函数的性质，f(a^b)=f(a)*a^(b-1)
其中，f(a)=a*(1-1/p1)*(1-1/p2)*...*(1-1/pk)
其中p1,p2..pk是a的所有不同的质因素
~~~
import java.util.*;
import java.io.*;

public class test {
    static int mod = 998244353;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        if(a == 1) System.out.println(0);//1的倍数是1，任何数不和1互质
        //欧拉函数计算
        //res存储最终的f(a)的值，x用于分解质因素
        long res = a,x = a;
        //i从2遍历到根号x（i*i<=x）
        for(int i = 2; i <= x / i; i ++) {
            //i是a的一个质因数
            if(x % i == 0) {
                while(x % i == 0) x/= i;//通过循环将x中所有i因子去除
                res = res / i * (i - 1);//这一步即:res *= (1 - 1/i),但因为整数除法问题，转化为该形式
            }
        }
        if(x > 1) res = res / x * (x - 1);
        System.out.println(res * qmi(a,b - 1) % mod);
    }
    
    //快速幂的计算
    private static long qmi(long a,long b) {
        long res = 1 % mod;
        for(;b > 0; b >>= 1) {
            if((b & 1) == 1) res = res * a % mod;
            a = a * a % mod;
        }
        return res % mod;
    }
}

~~~
~~~
欧拉函数计算部分：
1.初始化res=a，x=a
2.遍历2到根号x（i*i<=x）
3.如果是质因素，去除x中所有i因子，并更新res

while(x % i == 0) x/= i;//通过循环将x中所有i因子去除：
欧拉函数只需要每个质因素出现一次，不需要幂次信息，f(12)中，12=2^2*3^1,但只需要2和3计算，不需要关心幂次
初始时，x=12
i=2时，12%2==0进入while循环
                    x=12/2=6(去除一个2)
        6%2==0，进入while循环
                    x=6\2=3(去除一个2)
        3%2！=0，退出循环
此时x=3
12中的所有2因子去除
i=3时，3%3==0进入while循环
                    x=3/3=1(去除一个3)
                    x=1，退出循环
质因素：3，1

if(x > 1) res = res / x * (x - 1);
这是欧拉函数计算的最后一步，用于处理剩余的最后一个质因素
在之前的循环中，我们尝试用 i 从2遍历到 sqrt(x) 来分解质因数。
如果循环结束后 x > 1，说明剩下的 x 本身就是一个质数（没有被之前的 i 整除）。
例如：
计算 φ(14)
初始：res = 14, x = 14
i = 2:
14 % 2 == 0 → x = 7 (去除所有2的因子)
res = 14 / 2 * (2 - 1) = 7
循环结束（i 最大到 sqrt(7) ≈ 2）
此时 x = 7 > 1 → 处理最后一个质因数7：
res = 7 / 7 * (7 - 1) = 6
结果：φ(14) = 6（正确：1,3,5,9,11,13）有6个质因素

欧拉函数公式要求覆盖所有质因数。循环只能处理到 sqrt(x) 的因数，所以需要额外处理可能剩余的大质数。
~~~

#### 阶乘的和
题目：给定n个数ai,问能满足m!为(a1+a2+..ai)的因素的最大m是多少
我的答案：0
~~~
package project1;
import java.util.*;
import java.math.BigInteger;

//1:无需package
//2: 类名必须Main, 不可修改

public class Main {
    // 迭代法计算阶乘
    static BigInteger solve(int n) {
        BigInteger res = BigInteger.ONE;//这行代码初始化了一个 BigInteger 类型的变量 res，并将其值设置为 1。BigInteger.ONE 是 BigInteger 类中表示数字 1 的常量。res 将用于存储阶乘的计算结果。
        for (int i = 2; i <= n; i++) {
            res = res.multiply(BigInteger.valueOf(i));//将 res 与 i 相乘，并将结果重新赋值给 res。BigInteger.valueOf(i) 将整数 i 转换为 BigInteger 类型，以便能够与 res 进行乘法运算。这个操作在循环中用于计算阶乘
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int a[] = new int[n];
        BigInteger sum = BigInteger.ZERO;//sum=0

        // 计算所有 a[i]! 的和
        for (int i = 0; i < n; i++) {
            a[i] = scan.nextInt();
            BigInteger factorial = solve(a[i]);
            sum = sum.add(factorial);
        }
        scan.close();

        // 找到最大的 m，使得 m! 是 sum 的因数
        int m = n;
        BigInteger res = BigInteger.ZERO;
        while (m > 0) {
            BigInteger factorial = solve(m);
            if (sum.mod(factorial).equals(BigInteger.ZERO)) {//
                res = BigInteger.valueOf(m);//
                break;
            }
            m--;
        }

        System.out.println(res);
    }
}
~~~
正确代码：
~~~
// 下面举例说明为什么要将nums[]中最小的元素作为因子初始值
        // 3！ 6
        // 4！ 24
        // 5！ 120
        // 和为150 必是 3！的倍数！ 因为 4！5！都是3！的倍数，所以加起来肯定也是 (min) 3！的倍数
        // 所以应该找出数组最小值作为初始的sum，再一个一个往上找
        // 比如上面这个例子，需要有 4个3！才能进化为 4！，由于只有一个 3！所以不能往上找了，break退出，答案就是3
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        //读取输入，并找到最小值min
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] nums = new long[n];
        long min = Long.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextLong();
            min = Math.min(min, nums[i]);
        }
        long sum = min;  // sum为nums[]中的最小值

        //计算sum的阶乘倍数
        long num = 0;    // num当前sum的倍数个数
        while (true) {
            //将当前sum倍数合并为sum+1的倍数
            num = num / sum;
            //遍历nums数组，统计nums中有多少个等于sum的元素个数，并累加到num中
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == sum) {
                    num++;
                }
            }
            //如果num是sum+1的倍数，则sum+1，否则退出循环，当前的sum就是最大阶乘因子
            if (num % (sum + 1) == 0 && num != 0) {
                sum++;
            } else break;
        }
        System.out.println(sum);
    }
}
~~~
#### 小蓝的旅行计划
我的答案：2分（估计是得的-1的条件下的分）
DAMN!不太会！感觉是dfs但是脑子转不过来，涉及的条件有点多了
#### 太阳
我的答案：0
~~~
/*
(x,y)处有一个光源，有n条线平行x轴放置，第i条线段的左端点在(xi,yi),长度为li
线段之间不会重合，但端点可能相交
有多少条线段能被太阳照亮
一条线段有大于0的长度被照亮都算*/
//思路：x所在区域被
package project1;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Scanner;

//1:无需package
//2: 类名必须Main, 不可修改

public class Main {
	static int X;
	static long Y;
	
 public static void main(String[] args) {
     Scanner scan = new Scanner(System.in);
     //在此输入您的代码...
     int n=scan.nextInt();//有n条线
     //光源所在位置(x,y)
     X=scan.nextInt();
     Y=scan.nextInt();
     
     int x[]=new int[n+1];
     int y[]=new int[n+1];
     int l[]=new int[n+1];
     int count=1;//记录能被照亮的条数
     for(int i=0;i<n;i++)
     {
    	 //第i条线段的左端点位置（xi,yi)
    	 x[i]=scan.nextInt();
    	 y[i]=scan.nextInt();
    	 //第i条线段的长度li
    	 l[i]=scan.nextInt();
    	 
    	
     }
     scan.close();
     
     //创建一个索引数组用于排序
     Integer[] indices=new Integer[n];
     for(int i=0;i<n;i++)indices[i]=i;
     
     //根据y的大小排序
     Arrays.sort(indices,new Comparator<Integer>() {
    	 @Override
    	 public int compare(Integer i,Integer j)
    	 {
    		 return Integer.compare(y[j], y[i]);//从大到小排
    	 }
     });
     
  // 根据排序后的顺序判断线段是否能被照亮
     int lastRightEnd = Integer.MIN_VALUE; // 记录上一个线段的最右端点
     
     for (int i : indices) {
         // 如果当前线段的最左端点大于上一个线段的最右端点，则当前线段能被照亮
         if (x[i] > lastRightEnd) {
             count++;
             lastRightEnd = x[i] + l[i];
         }
         // 如果当前线段的最右端点大于上一个线段的最右端点，则更新最右端点
         else if (x[i] + l[i] > lastRightEnd) {
             lastRightEnd = x[i] + l[i];
             count++;
         }
     }
     System.out.println(count);
 }
}

~~~
#### 高塔
游戏n个回合，一开始拥有m点能量，每一个回合都有Ai表示角色状态，每回合可以选择消费任意点能量Ci
（最低消费1点，没有上限），在本回合最多可以向上攀爬Ai*Ci层。实际攀爬层数取决于小蓝在这回合的表现，最差能爬1层
某回合能量消耗完，这个游戏就结束，n个回合后，无论游戏有没有消耗完，游戏都会结束
问：有多少种玩法
//思路：感觉也是动态规划
####

### JAVA十三届
### 3.寻找整数
~~~
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        int[] mod = {0, 0, 1, 2, 1, 4, 5, 4, 1, 2, 9, 0, 5, 10, 11, 14,
            9, 0, 11, 18, 9, 11, 11, 15, 17, 9, 23, 20, 25, 16, 29, 27, 25, 
            11, 17, 4, 29, 22, 37, 23, 9, 1, 11, 11, 33, 29, 15, 5, 41, 46};
        long ans = 1L;
        long k = 2;//k是当前已经处理的数的最小公倍数
        for (int i = 3; i < mod.length; i++) {
            while (true)
                if(ans%i == mod[(int)i]) {//逐行检查每个模数i是否满足ans%i==mod[i]
                    k = lcm(k, i);//每次变更的值
                    break;
                }else ans+=k;//如果不满足，则增加ans为k的倍数
                /*这里k=lcm(2,3)=6，因为6是2，3的倍数所以 对2，3分别取余结果还是一样的*/
        }
        System.out.println(ans);//处理完后ans就是满足所有同余条件的最小正整数
    }
    //如果 b 为 0，返回 a。否则，递归调用 gcd(b, a % b)，直到 b 为 0。
      static long gcd(long a,long b) {
        return b==0? a : gcd(b, a%b); 
    }
    static long lcm(long a,long b) {
        return a*b/gcd(a,b);//最小公倍数公式=a*b/gcd(a,b)
    }
}
~~~
#### 4.GCD
~~~
/*
两个正整数a,b,求正整数k使得gcd(a+k,b+k)尽可能的大，其中gcd(a,b)表示a,b的最大公约数，如果存在多个k
请输出所有满足条件的k中最小的那个
*/
/*
解题思路：找到一个k使得gcd(a+k,b+k)最大
设d=gcd(a+k,b+k)
d可以整除a+k,d可以整除b+k,根据整除定义，两个能被d整除的数，相减后仍然能被d整除
所以d是|a-b|的约数，为了使gcd(a+k,b+k)最大，d=|a-b|,
*/
import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    long a = scan.nextLong();
    long b = scan.nextLong();
    scan.close();
    long mod = Math.abs(a-b);
    System.out.println(mod-a%mod);

  }
  
}
//k = mod - a % mod 是为了让 a + k 成为 mod 的倍数。减去余数不就整除了嘛
~~~
#### 5.蜂巢
考点：坐标转换，距离计算
我不会的点：坐标转换，以及斜着的距离不知道怎么计算
思路：
1. 先转换成直角坐标系
2. 计算方法：坐标之差的绝对值dx=|x1-x2|，dy=|y1-y2|
   如果dx>=dy,那么最小步数是(dx+dy)/2,即先横着走再斜着走
   如果dx<dy,一直斜着走就行，最小步数是dy
~~~
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        new Main().solution();
    }

    int[] x = new int[] { -2, -1, 1, 2, 1, -1 };
    int[] y = new int[] { 0, 1, 1, 0, -1, -1 };

    private void solution() {
        Scanner sc = new Scanner(System.in);
        long[][] a = new long[2][3];
        int d1 = sc.nextInt();
        long p1 = sc.nextLong();
        long q1 = sc.nextLong();
        int d2 = sc.nextInt();
        long p2 = sc.nextLong();
        long q2 = sc.nextLong();
        long[] pos1 = new long[2];
        long[] pos2 = new long[2];
        getPos(d1, p1, q1, pos1);
        getPos(d2, p2, q2, pos2);
        System.out.println(getDis(pos1, pos2));
    }

    private long getDis(long[] p1, long[] p2) {
        long dx = Math.abs(p1[0] - p2[0]);
        long dy = Math.abs(p1[1] - p2[1]);
        if (dx < dy)
            return dy;
        else
            return (dx + dy) / 2;
    }

    private void getPos(int i, long j, long k, long[] p) {
        p[0] += j * x[i] + k * x[(i + 2) % 6];
        p[1] += j * y[i] + k * y[(i + 2) % 6];
    }
}
//其实还是简单，主要是就这个转换要考虑到，直接画图就可以看出来，建立数组，往哪个方向走，x变化了多少，y变化了多少
//难点其实在于距离的计算，不知道这个规律是怎么的来的，估计是找规律出来的？

~~~
#### 青蛙过河
利用二分查找，要求所有长度为k的区间内，能被踩2x次
~~~
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    //判断再给定的整数数组high和前缀和数组sum中，是否存在长度为k的连续子数组，使得该子数组的和至少为2*x。
    public static boolean judge(int k, int[] high, int[] sum, int x) {
        for (int i = 0; i <= high.length - k; i++) {//遍历所有长度为k的区间，有high.length-k个区间
            if (i == 0) {//第一个区间，直接判断前缀和
                if (sum[i + k - 1] < 2 * x)
                    return false;
            }
            else if (sum[i + k - 1] - sum[i - 1] < 2 * x)
                return false;
        }
        return true;
    }
     public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = 0, x = 0, sum_i = 0;
        n = scan.nextInt();
        x = scan.nextInt();
        int[] high = new int[n - 1];
        int[] sum = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            high[i] = scan.nextInt();
            sum_i += high[i];
            sum[i] = sum_i;
        }
        scan.close();
        
        int l = 1, r = n;//1到n里面二分查找k
        while(l < r) {
            int mid = (l + r) / 2;
            if (judge(mid, high, sum, x)) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        System.out.println(l);
    }
}
~~~
二分法，在有序，随机，单调（比如找到第一个大于x的值）的情况下可以使用
#### 因数平方和
数论
关键思路是：要找出每个数的因子会耗费比较多的时间，因为g(n)是求和结果，可以反过来求每个因子作为加数的次数。
比如说n=10
1是所有数的因子，加了10次，2是偶数因子用了5次，3用来3次等
因此g(n)=因数^2*
~~~
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    static final int MOD = 1000000007;
    static final long INV6 = 166666668;
    public static long squareSum(long factor){
        return ((factor * (factor + 1) % MOD) * ((2 * factor + 1) % MOD) % MOD * INV6 % MOD);
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n = scan.nextInt();
        long anwser = 0L;
        //
        long right;
        for(long left = 1L; left <= n; left = right + 1){
            right = n / (n / left);
            anwser += (squareSum(right) - squareSum(left - 1)) * (n / left) % MOD;
            anwser = (anwser + MOD) % MOD;
        }
        scan.close();
        System.out.println(anwser);
    }
}
~~~
#### 最优清零方案
~~~
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(), k = scan.nextInt();
        int[] nums = new int[n + 1];
        long cnt = 0;
        for(int i = 1; i <= n; i++)nums[i] = scan.nextInt();

        for(int i = 1; i + k - 1 <= n;){
          int min = Integer.MAX_VALUE;
          int d = 0;
        
          for(int j = i; j <= i + k - 1; j++){//找到最小数和它的下标
            if(nums[j] <= min){
              min = nums[j];
              d = j;
            }
          }
          cnt += min;
          for(int j = i; j <= i + k - 1; j++){//当前数组全部减去min
            nums[j] -= min;
          }
          i = d + 1;//将下标移动到最小数的下一个位置
        }
        for(int i = 1; i <= n; i++)cnt += nums[i];//将剩余元素累加到cnt中
        System.out.println(cnt);
        scan.close();
    }
}
~~~
#### 0推导
~~~
import java.util.*;

public class Main {
    static final int N = (int) 2e5 + 10;
    
    static int[] p = new int[N];//父节点
    static long[] d = new long[N];//前缀和
    
    static Scanner sc = new Scanner(System.in);
    static int n, m, q;
    
    static int find(int x) {
        if (p[x] != x) {//如果x不是自己的父节点，则递归求出父节点
            int t = p[x];
            p[x] = find(p[x]);
            d[x] += d[t];
        }   
        return p[x];
    }
    
    public static void main(String[] args) {
        n = sc.nextInt();//数组长度
        m = sc.nextInt();//已知的部分和数量
        q = sc.nextInt();//询问的部分和数量
        
        //初始化每个数组的父节点都是自己
        for (int i = 1; i <= n; i++) p[i] = i;
        
        while (m-- > 0) {//已知的部分
            int l = sc.nextInt();
            int r = sc.nextInt();
            long s = sc.nextLong();
            //找到l-1,r的父节点，并把l-1的集合合并到r的集合中
            int pt = find(l - 1), pr = find(r);
            p[pt] = pr;
            //更新d[pt]
            d[pt] = d[r] - s - d[l - 1];
        }
        
        while (q-- > 0) {//要求的部分
            int l = sc.nextInt();
            int r = sc.nextInt();
            
            int pt = find(l - 1), pr = find(r);
            if (pt != pr) System.out.println("UNKNOWN");
            else System.out.println(d[r] - d[l - 1]);
        }
    }
}
~~~
合并前的关系：
已知 d[r] - d[l-1] = S
合并后的关系：
将 pt 的父节点设为 pr，需满足：
d[pt] + d[r] - d[l-1] = S
代入 d[r] 和 d[l-1] 的表达式，解得：
d[pt] = d[r] - S - d[l-1]

~~~
static int find(int x) {
    if (p[x] != x) {          // 如果x不是根节点
        int t = p[x];         // 保存x的原始父节点
        p[x] = find(p[x]);    // 递归找到根节点，并路径压缩
        d[x] += d[t];        // 更新x到新父节点的权值
    }
    return p[x];              // 返回根节点
}
路径压缩（Path Compression）
1. 将节点 x 到根节点的路径上的所有节点直接挂到根节点下，降低后续查询时间复杂度。
2. 权值累加（Weight Maintenance）
    在路径压缩时，同步更新 d[x] 为 x 到根节点的累计权值（而不仅仅是到父节点的权值）。

d[i] 表示 前缀和 S[i] 与 S[root] 的差值（即 S[i] - S[root]）。

通过路径压缩，d[i] 被更新为 i 到当前根节点的累计差值，使得后续查询可以直接计算。
~~~

### 3.8双周赛
#### 祝福语
问题：
两个字符串S，T都是由小写字母组成的，其中T不能是S的子串，T的字典序是最小的
输入：
字符串S
输出：
字符串T

~~~
FALL!!!!!!
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        String s=scan.nextLine();
        char[] ch=s.toCharArray();
        Arrays.sort(ch);
        int len=ch.length;
        //取第一个即可
        for(int i=0;i<len;i++)
        System.out.print(ch[0]);
       
        scan.close();
    }
}
~~~
错误原因：
我的代码是把字符串排序，输出第一个字符，重复n次，但如果输入aaaa,输出还是aaaa,所以出错；且没有保证字典序最小

正确代码：
思路：统计字符串s中连续字符a的最大长度。注意是连续的a的最大长度max，然后输出长度为max+1的全为a的字符串
因为要找字典序最小的非子串，字典序最小的字符串往往是由多个'a'组成的，如果输入字符串种连续a的最大长度是m，那么由n+1个'a'组成的字符串，字典序最小。
当输入为aaa,输出为aaaa
~~~
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int count = 0, max = 0; 
        for(int i=0;i<s.length();i++) {
            if(s.charAt(i)=='a') {
                count++;
                max = Math.max(max, count);
            }else {
                count=0;
            }
        }
        for(int i=0;i<=max;i++) System.out.print('a');
    }
}
~~~
#### 社区服务
题目：
有n个服务点，每个服务点可能有志愿者（1）也可能暂时无人（0），每个服务点都有居民需要帮助，需要从左往右为每个无志愿者服务点计算距离最近的有志愿服务点的距离，若不存在则输出-1
输入：
整数n，表示服务点个数
长度为n的二进制字符串表示每个服务点志愿者情况
输出：
若干整数，表示每个无志愿者服务点到有志愿者服务点的最近距离，若不存在输出-1
~~~
这题还是FALL!!!!不知道哪里出了问题，我自己测试的结果的都是对的
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String s = scan.next();
        // 将字符串转换为字符数组，放在循环外部，避免重复转换
        char[] ch = s.toCharArray();

        // 判断字符串是否全为 0
        boolean allZero = true;
        for (char c : ch) {
            if (c != '0') {
                allZero = false;
                break;
            }
        }

        if (allZero) {
            System.out.println(-1);
        } else {
            for (int i = 0; i < n; i++) {
                if (ch[i] == '0') {
                    int left = i - 1;
                    int right = i + 1;
                    int leftDistance = Integer.MAX_VALUE;
                    int rightDistance = Integer.MAX_VALUE;

                    // 向左查找最近的 '1'
                    while (left >= 0) {
                        if (ch[left] == '1') {
                            leftDistance = i - left;
                            break;
                        }
                        left--;
                    }

                    // 向右查找最近的 '1'
                    while (right < n) {
                        if (ch[right] == '1') {
                            rightDistance = right - i;
                            break;
                        }
                        right++;
                    }

                    // 取左右距离的最小值
                    int minDistance = Math.min(leftDistance, rightDistance);
                    System.out.print(minDistance + " ");
                }
            }
        }

        scan.close();
    }
}
~~~
错误原因：
应该是不存在1的情况下输出n个-1，我只输出了一个
正确代码：
~~~
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取服务点的数量
        int n = scanner.nextInt();
        // 读取表示服务点状态的二进制字符串
        String s = scanner.next();
        scanner.close();

        // 存储有志愿者的服务点的索引
        List<Integer> volunteerIndices = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                volunteerIndices.add(i);
            }
        }

        // 存储每个无志愿者服务点到最近有志愿者服务点的距离
        List<Integer> distances = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                int minDistance = Integer.MAX_VALUE;
                // 遍历所有有志愿者的服务点，计算最小距离
                for (int index : volunteerIndices) {
                    minDistance = Math.min(minDistance, Math.abs(i - index));
                }
                // 如果最小距离仍为最大值，说明不存在有志愿者的服务点
                if (minDistance == Integer.MAX_VALUE) {
                    minDistance = -1;
                }
                distances.add(minDistance);
            }
        }

        // 输出结果
        for (int i = 0; i < distances.size(); i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(distances.get(i));
        }
    }
}
~~~
#### 表演队
题目：
n个同学，每个同学的能力值分别为a1,a2..an,从n个同学中挑选k个，要求这k个人的差异值最小，求最小值
差异值是1<=i<=j,|ai-aj|之和最小
输入：
n,k
a1,a2..an
输出：
k个同学的最小差异值
示例：
5 3
1 5 10 7 8
输出：
6
~~~
FALL!!!!到底哪有毛病啊！
import java.util.*;

public class Main {
    // 存储所有可能的 k 人组合
    private static List<int[]> combinations = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取 n 和 k
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];
        // 读取每个同学的能力值
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        scanner.close();

        // 生成所有可能的 k 人组合
        generateCombinations(a, new int[k], 0, 0);

        int minDiff = Integer.MAX_VALUE;
        // 遍历所有组合，计算每个组合的差异值
        for (int[] combination : combinations) {
            int diff = calculateDifference(combination);
            minDiff = Math.min(minDiff, diff);
        }

        System.out.println(minDiff);
    }

    // 生成所有可能的 k 人组合
    private static void generateCombinations(int[] arr, int[] combination, int start, int index) {
        if (index == combination.length) {
            combinations.add(Arrays.copyOf(combination, combination.length));
            return;
        }

        for (int i = start; i < arr.length; i++) {
            combination[index] = arr[i];
            generateCombinations(arr, combination, i + 1, index + 1);
        }
    }

    // 计算一个组合的差异值
    private static int calculateDifference(int[] combination) {
        int diff = 0;
        int length = combination.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                diff += Math.abs(combination[i] - combination[j]);
            }
        }
        return diff;
    }
}
错误原因：
时间复杂度太高

正确代码：
~~~
import java.util.Arrays;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(),k = scan.nextInt();
        long[] num = new long[n];
        for (int i = 0; i < n; i++) {
            num[i] = scan.nextLong();
        }
        Arrays.sort(num);
        long min = Long.MAX_VALUE;
        for (int i = 0; i <= n-k; i++) {
            long temp = 0;
            //计算当前前组合的差异值
            //t:给该组的元素赋权值，目的是一次性计算出一个组合内部之间差异值的总和
            /*
            以k = 3为例，权值分别为-2、0、2。假设选取的三个数为a、b、c，那么计算-2*a + 0*b + 2*c，实际上等价于计算2*(c - a)，这个结果与|a - b| + |a - c| + |b - c|的最小情况是等价的。因为在a <= b <= c的情况下，|a - b| + |a - c| + |b - c|展开化简后就是2c - 2a
            因为a ≤ b,所以|a -Ы ≡b- a。
            因为a ≤ c，所以|a-c|=c- a。
            因为b ≤ c，所以|b-c|=c-b。
            将上述绝对值展开后的式子代入原式可得:2c-2a
            */
            for (int t = -(k-1),j = 0; j < k;t+=2,j++) {
                temp += t*num[i+j];
            }
            min = Math.min(min,temp);
        }
        System.out.println(min);
    }
}

~~~
~~~
#### 花束搭配
问题：
n种鲜花，每种花有两种属性，放在外部：Ai,放在内部Bi
一束花需要由两种不同的花组成，一种放在外部，一种放在内部，如果Ai+Aj>Bi+Bj，则这束花是完美搭配
计算有多少种完美搭配
输入：
整数n
n个整数Ai
n个整数Bi
输出：
一个整数，表示有多少种完美搭配
~~~
还是FALL!!!!
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取鲜花的种类数 n
        int n = scanner.nextInt();

        // 初始化数组 A 和 B，分别存储每种鲜花放在外部和内部的艳丽度
        int[] A = new int[n];
        int[] B = new int[n];

        // 读取数组 A 的元素
        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextInt();
        }

        // 读取数组 B 的元素
        for (int i = 0; i < n; i++) {
            B[i] = scanner.nextInt();
        }

        // 用于记录完美搭配方案的数量
        int count = 0;

        // 遍历所有可能的鲜花两两组合
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 确保是不同的鲜花组合
                if (i != j) {
                    // 判断是否满足完美搭配方案的条件
                    if (A[i] + A[j] > B[i] + B[j]) {
                        count++;
                    }
                }
            }
        }

        // 输出完美搭配方案的数量
        System.out.println(count);
        scanner.close();
    }
}

~~~
错误原因：
都能正确解决问题，但代码下面的代码在效率上更具优势。
正确代码：
解题思路：通过对数组D进行排序，然后针对每个c[i]进行二分查找，通过一傲剑来统计判断
~~~
import java.util.Arrays;
import java.util.Scanner;

public class text5 {
    public static int erfen(int x,int[] D) {
        int l=0;
        int r=D.length-1;
        int res=-1;
        while(l<=r) {
            int mid=(l+r)/2;
            if(D[mid]<x) {
                l=mid+1;
                res=mid;
            }
            else{
                r=mid-1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int[] A=new int[n];
        int[] B=new int[n];
        int[] C=new int[n];
        int[] D=new int[n];
        for(int i=0;i<n;i++)A[i]=scan.nextInt();
        for(int i=0;i<n;i++)B[i]=scan.nextInt();
        for(int i=0;i<n;i++) {
            C[i]=A[i]-B[i];
            D[i]=B[i]-A[i];
        }
        Arrays.sort(D);
        long res=0;
        for (int i = 0; i < n; i++) {
        // 调用二分查找函数，找到 D 数组中小于 C[i] 的最大索引
        int index = erfen(C[i], D);
        // 如果找到了小于 C[i] 的元素
        if (index != -1) {
        // 获取 D 数组中小于 C[i] 的最大元素
        int element = D[index];
        // 判断该元素是否大于等于 -C[i]
        if (element >= -C[i]) {
            // 如果满足条件，说明有 index 个元素满足搭配条件，累加到结果中
            res += index;
        } else {
            // 如果不满足条件，说明除了前面的 index 个元素，当前元素也满足搭配条件
            // 所以满足条件的元素个数是 index + 1，累加到结果中
            res = res + index + 1;
        }
    }
}
        System.out.println(res);
        
                

    }

}
~~~
#### 妇女唇膏
题目：
n只口红，每只色号a1,a2..an，需要将所有口红调制出统一的颜色B，
已知只有当A+B=A异或B，二者色彩最佳。因此要实现活动目标，需要对每支口红Ai，B都要满足Ai+B=Ai异或B
找到一个最小正整数B使得每一只口红Ai都能达到最佳效果

原理如下：加法运算，如果都是1会发生进位，而异或运算如果都是1结果为0；因此A,B的二进制表示中，相同位置上不能同时为1
其他情况0+0=0^0=0,0+1=0^1=1,1+0=1^0=1
~~~
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }

        int mask = 0;
        // 合并所有 A[i] 的二进制表示
        for (int i = 0; i < N; i++) {
            mask |= A[i];// 将 A[i]中的每一个元素与mask进行按位或操作，如果对应位置上有1则结果为1，这样就记录了所有A[i]的二进制位
        }

        int B = 1;
        // 找到最小的 B，使得 B 的二进制位与 mask 不冲突
        while ((B & mask) != 0) {//不等于0，表面B和mask冲突，B+1
            B++;
        }

        System.out.println(B);
        scanner.close();
    }
}
~~~
## 洛谷题单
### 导弹拦截
题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式
一行，若干个整数，中间由空格隔开。

输出格式
两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
~~~
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/*
解决两个问题：
计算这套系统最多能拦截多少导弹（即最长非递增子序列的长度）：使用动态规划和二分查找来计算最长非递增子序列的长度。
计算拦截所有导弹最少需要多少套系统（即最少的非递增子序列数量）：使用贪心算法来计算最少的非递增子序列数量。
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        //创建一个名为 heights 的空列表，该列表用于存储整数类型的元素。ArrayList 是 Java 中的一个动态数组实现，可以灵活地添加和删除元素
        List<Integer> heights = new ArrayList<>();

        // 读取输入的导弹高度
        while (scanner.hasNextInt()) {   //使用 scanner.hasNextInt() 判断输入流中是否还有整数。
            heights.add(scanner.nextInt());   //scanner.nextInt() 读取该整数并将其添加到 heights 列表中。
        }

        int n = heights.size();
        int[] H = new int[n];
        for (int i = 0; i < n; i++) {
            H[i] = heights.get(i);//将输入的导弹高度添加到 H 数组中
        }

        // 计算最长非递增子序列的长度
        int longestNonIncreasing = longestNonIncreasingSubsequence(H);

        // 计算最少的非递增子序列数量
        int minSystems = minSystemsToInterceptAllMissiles(H);

        // 输出结果
        System.out.println(longestNonIncreasing);
        System.out.println(minSystems);
    }

    // 计算最长非递增子序列的长度，光看代码有点难理解，直接让AI写一个简单例子来解释
    static int longestNonIncreasingSubsequence(int[] H) {
        int n = H.length;
        int[] F = new int[n + 1];//辅助数组，用来存储当前找到的非递增子序列的末尾元素
        int t = 0;//记录当前找到的最长非递增子序列的长度
        F[0] = Integer.MAX_VALUE;//设置为最大整数

        // 使用二分找到第一个大于等于当前元素H[i]的位置
        for (int i = 0; i < n; i++) {
            int l = 0, r = t + 1;
            while (r - l > 1) {
                int m = l + (r - l) / 2;
                if (F[m] >= H[i]) {
                    l = m;
                } else {
                    r = m;
                }
            }
            int x = l + 1;
            if (x > t) {
                t = x;
            }
            F[x] = H[i];
        }
        return t;
    }

    // 计算最少的非递增子序列数量
    static int minSystemsToInterceptAllMissiles(int[] H) {
        int n = H.length;
        List<Integer> tails = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int height = H[i];
            int index = binarySearch(tails, height);
            //如果位置等于 tails 的长度，则将高度值添加到 tails；否则替换 tails 中对应位置的值
            if (index == tails.size()) {
                tails.add(height);
            } else {
                tails.set(index, height);
            }
        }

        return tails.size();
    }

    // 二分查找，找到第一个大于等于 target 的位置
    static int binarySearch(List<Integer> tails, int target) {
        int left = 0, right = tails.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails.get(mid) >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
~~~
二分查找：
条件：有序，查找数量只能是1个而不是多个
注意，不能直接比较，比如数组 [3, 5, 2, 7, 4, 6, 1]，[7,4,6,1]也是一组

### 大数累加累乘
累加：
~~~
static long sum(long n) {
    return n * (n + 1) / 2;
}
~~~
根据等差数列求和公式

累乘：
~~~
static long factorial(long n) {
    long b = 1;
    for (long i = 1; i <= n; i++) {
        b *= i;
        b %= 100; // 取模 100 避免溢出
    }
    return b;
}

~~~
取模 100，这是因为我们只关心最终结果对 100 取模的情况
如果结果是对1000取模，这里也同样适用，即 b %= 1000

在main函数里面：
~~~
public static void main(String[] args) {
    long count = 0;

    // 只需要检查 n 从 1 到 9
    for (long i = 1; i <= 9; i++) {
        long a = sum(i) % 100;
        long b = factorial(i);
        if ((a - b + 100) % 100 == 0) { // (a - b) % 100 == 0
            count++;
        }
    }

    System.out.println(count);
}
~~~

只对  从 1 到 9 进行检查。这是因为当 n>=10 时，B(n)=n! 中一定包含因数 2 和 5，所以 B(n) 能被 10 整除，进而 B(n) 对 100 取模的结果一定为 0。此时，判断  A(n)-B(n)能否被 100 整除就相当于判断 A(n) 能否被 100 整除。

if ((a - b + 100) % 100 == 0) :这里加上 100 是为了避免 a-b 为负数的情况，因为在 Java 中，负数对正数取模的结果可能是负数，加上 100 后再取模可以确保结果在 0 到 99 之间，方便判断是否为 0

## 第一章：初时算法竞赛

1. 温度单位的转换（模板题）
题目：给定一个整数C,表示摄氏度，需要将C转换为华氏度F，并输出。F=C*9./5+32。结果只保留整数部分
输入：整数C（-89<=C<=54）
输出：华氏度F

~~~
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        //我的代码
        int c=sc.nextInt();
        System.out.println((int)(c*9.0/5+32));//注意转换成整数,以及9/5=1,因此要转换为9.0/5
        sc.close();
    }
}
~~~

2. A+B（模板题）
题目：输入两个整数A,B，输出A+B的结果。
~~~
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int a=input.nextInt();
        int b=input.nextInt();
        System.out.println(a+b);
        input.close();
    }
}
~~~

3. 输出格式练习（模板题）
题目：第一行输入一个正整数a（1<=a<=1440），你需要计算从0时0分后经过a分钟得到的时间是多少。输出以xx:xx的形式表示，如果不足两位则左侧补0
例如：a=36输出00:36;a=61输出01:01
第二行输入两个整数c,d，输出c/d的结果，保留三位小数。

输入：第一行输入a,第二行输入c,d
~~~
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a=sc.nextInt();
        int c=sc.nextInt();
        int d=sc.nextInt();
        System.out.println("%02d:%02d\n",a/60,a%60);
        System.out.printf("%.3f",(double)c/d);
        sc.close();
        
    }
}

~~~


4. 报数游戏（1星）
题目：从小到大报出20或24倍数的正整数，前10个报出的数是：20，24，40，48，60，72，80，96，100，120.请问第202420242024个被报出的数是多少？
填空题
可以再写10个数出来，找找规律
140，144，160，168，180，192，200，240，256，280
发现差140-20=120，所以可以得出规律，即第202420242024个被报出的数是202420242024/10*120+第4个数（48）=20242024202*120+48


### 循环
1. 九进制转十进制（1星）
题目：九进制正整数（2022）9转十进制是多少？
填空
~~~

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println(2+18+2*729)；
        sc.close();
    }
}
~~~

2. 枚举法求最大公约数（1星）
~~~
题目：a,b是两个整数，如果d能整除a且d能整除b，则d是a和b的公约数。求最大公约数
输入：两个正整数a,b
输出：最大公约数d
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        for(int i=Math.min(a,b);i>=1;i--){
            if(a%i==0&&b%i==0){
                System.out.println(i);
                break;
            }
        }
        sc.close();
    }
}
~~~

### 数组与字符串
1. 冒泡排序（1星）
题目：给定一个长度为n的序列a，输出升序排序后的结果
输入：整数n，下一行输入n个正整数ai
输出：升序排序后的结果
~~~
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            System.out.print(a[i]+" ");
            for(int j=0;j<n-1;j++){
                if(a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
            for(int i=0;i<n;i++){
                System.out.print(a[i]+" ");
            }
            sc.close();
        }
        
    }
}
~~~

2. 选择排序(1星)
~~~
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=0;i<n-1;i++){
            //保存最小值的下标
            int t=-1;
            //保存最小值的值
            int mn=a[i];
            //寻找最小值对应的下标
            for(int j=i;j<n;j++){
                if(a[j]<mn){
                    mn=a[j];
                    t=j;
                }
            }
            //如果找到了更小的值（即 t != -1），则交换当前元素和最小值的位置。
            if(t!=-1){
                int temp=a[i];
                a[i]=a[t];
                a[t]=temp;

            }
        }
        for(int i=0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        sc.close();
    }
}
~~~

### 函数
### 算法竞赛中常用的面向对象
### Java的基本API（一）


## 二．算法基础
### 时间复杂度与空间复杂度
   
### 一维前缀和
1. 区间求和问题
例题：给定一个长度位n的序列a，有m次查询，每次选择一个连续区间a1_ar,输出所有元素之和
暴力做法：每次遍历该区间求和，时间复杂度最坏为O（nm）
优化：用一维前缀和，时间复杂度为O（n+m）
①构建前缀和数组
    S[i]=a1+a2+...+ar
    S[i]=S[i-1]+a[i]
时间复杂度为O（n）
②快速查询任意区间和
sunm(l,r)=S[r]-S[l-1]
时间复杂度为O（1）

例题：一维前缀和（模板题）
给定一个长度为n的序列a，有q次查询，每次选择一个连续区间l,r,输出所有元素之和
输入：
    第一行：两个正整数n,q;
    第二行：n个正整数ai;
    接下来q行，每行输入两个正整数l,r
输出：
    对于每次查询，输出一行一个整数，表示该次查询的结果
~~~
import java.util.*;
import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main{
    static int zu;
    static int a[]=new int[100010] ;
    static int s[]=new int[100010] ;

    public static void main(String[] args){
        int t=1;
        for(zu=1;zu<=t;zu++)solve();
        out.flush();
    }

    static void solve(){
        int n=in.nextInt(),q=in.nextInt();
        for(int i=1;i<=n;i++)   a[i]=in.nextInt();
        for(int i=1;i<=n;i++){
            s[i]=s[i-1]+a[i];
        }
    }
}

~~~

### 一维差分

    1.区间修改问题
        给定一个长度为n的序列a，有m次修改，每次选择一个连续区间l,r,修改区间内所有元素加d
        暴力做法：每次修改区间内所有元素，时间复杂度为O（mn）
    2.一维差分实现原理
        定义差分数组b,bi=a[i]-a[i-1]
        b1=a1
        b2=a2-a1
        b3=a3-a2
        对数组b求前缀和得到新数组c
        c1=b1
        c2=b1+b2=a1+a2-a1=a2
        c3=b1+b2+b3=a1+a2+a3-a1-a2=a3
        c4=b1+b2+b3+b4=a1+a2+a3+a4-a1-a2-a3=a4
        得到结论：差分数组求前缀和得到的就是原数组


（4）例题：一维前缀和模板
1. 一维差分
    题目：第一行输入n，m表示n个数据，有m次修改
        第二行输入n个正整数a1,a2,a3,...,an
        接下来有m行，每行输入三个正整数l,r,d，表示修改区间[l,r]内所有元素加d
        输出：修改完成后的数组
~~~
    static void solve(){
        int n=in.nextInt(),m=in.nextInt();
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
        }
        //计算差分数组 b,用于后续的操作处理
        for(int i=1;i<=n;i++){
            b[i]=a[i]-a[i-1];
        }
        //将区间 [l, r] 内的每个元素增加 d
        for(int i=1;i<=m;i++){
            int l=in.nextInt(),r=in.nextInt(),d=in.nextInt();
            b[l]=b[l]+d;
            b[r+1]=b[r+1]-d;
        }
        //恢复了原始数组 a
        for(int i=1;i<=n;i++){
            c[i]=c[i-1]+b[i];
        }
        for(int i=1;i<=n;i++){
            System.out.print(c[i]+" ");
        }
    }
~~~


2. 小蓝的操作
    一个数组a中包含n个数，问最少多少次操作，可让a数组所有数都变成1
    操作的内容是：每次操作可以任选一个区间，让区间内的所有数字减1，数据保证一定有解
    输入：
    第一行：输入整数n；第二行：n个正整数a1,a2,a3,...,an
    输出：最少操作次数


~~~
    static int N=100010;
    static int a[]=new int[N],b[]=new int[N];
    static void solve(){
        int n=in.nextInt();
        long res=0;
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
            b[i]=a[i]-a[i-1];
            //计算所有相邻元素之间的正差值之和。
            if(b[i]>0)res=res+b[i];
        }
        out.println(res);

    }

~~~

### 二维前缀和
(1)子矩阵求和问题

(2)二维前缀和原理
公式：S[i,j]=a[i,j]+a[i-1,j]+a[i,j-1]+a[i-1,j-1]
![二维前缀和公式图解](二维前缀和公式图解.png)
~~~

static void solve(){
    int n=in.nextInt(),m=in.nextInt();
    int q=in.nextInt();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=in.nextInt();
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
            //![构造前缀和数组公式图解](构造前缀和数组公式图解.png)
        }
    }
    while(q-->0)
    {
        int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();
        int res=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
        out.println(res);
    }
}
~~~
算法复杂度是O（nm+q）


### 二维差分
（1）子矩阵修改问题

（2）二维差分实现原理
~~~
static void solve(){
    //分别表示二维数组的行列和操作次数
    n=in.nextInt();
    m=in.nextInt();
    q=in.nextInt();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=in.nextInt();//构造二维数组a
            b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];//构造二维差分数组b
        }
    }
    //将矩形区域 [x1, y1] 到 [x2, y2] 内的所有元素增加 c
    for(int i=1;i<=q;i++){
        int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt(),c=in.nextInt();
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=c;
    }
    //恢复原始数组 a
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            b[i][j]=b[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
            out.print(b[i][j]+" ");
            }out.println();
    }
}
~~~

### 位运算
(1)原码反码补码
(2)常见位运算
(3)二进制中1的数量
例：要求计算一个整数的二进制表示中有多少个1，例如9的二进制为1001，包含两个1
解法：可以使用位运算，每次将当前数与1进行按位与运算，判断最低位是否为1，然后右移一位，直到数字变为0
~~~
public int countOne(int n){
    int count=0;
    while(n!=0){
        if((n&1)==1)count++;
        n=n>>1;
    }
    return count;
}
~~~

### 整数二分
(1)猜数字游戏
(2)二分原理
步骤：
①确定初始查找区间[l,r]
②计算区间的中点mid
③如果mid满足要求，则更新r=mid，否则更新l=mid+1
//找到区间中=x最左边的数字的位置
~~~
static int getL(int a[],int l,int r,int x){
    while(l<r){
        int mid=l+r>>1;//注意：没有括号
        if(x<=a[mid]){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    if(a[l]!=x)return -1;
}

//找到区间中=x最右边的数字的位置
static int getR(int a[],int l,int r,int x){
    while(l<r){
        int mid=l+r+1>>1;
        if(x>=a[mid]){
            l=mid;
        }
        else{
            r=mid-1;
        }
    }
    if(a[r]!=x)return -1;
}
//找到有序区间中>=x第一个数字的位置
static int lower_bound(int a[],int l,int r,int x)
{
    if(x>a[r])return -1;
    while(l<r){
        int mid=l+r>>1;//位运算 l + r >> 1 等价于 (l + r) / 2，但更高效。
        if(a[mid]>=x){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return l;
}
//找到有序区间中>x第一个数字的位置
static int upper_bound(int a[],int l,int r,int x)
{
    if(x>=a[r])return -1;
    while(l<r){
        int mid=l+r>>1;//位运算 l + r >> 1 等价于 (l + r) / 2，但更高效。
        if(a[mid]>x){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return l;
}
~~~
(3)例题：整数二分模板讲解
(4)分巧克力
当题目符合单调的时候，就可以使用二分求解。
随着巧克力的边长变小，巧克力分出来的数量越多，因此是递减函数，可以二分
~~~
int 1=1,r=100000;
while(l<r){
    int mid=(l+r+1)/2;
    if(check(mid)){
        l=mid;
    }
    else{
        r=mid-1;
    }
}
out.println(l);

static boolean check(int x){
    long ans=0;
    for(int i=1;i<=n;i++){
        ans=ans+(h[i]/x)*(w[i]/x);
        if(ans>=k)return true;
    }
    return false;
}
~~~

### 浮点数二分
数的M次方根
暴力做法是从0开始枚举，每次加10^(-7)，时间复杂度太高了
我们可以二分 M 次方根，二分左端点为 0，右端点为 N。二分的终止条件我们要从l<r变成l+eps<r。
eps 是一个误差小数，一般小数位数是7，我们就写10^(-9)次方，如果是6，就写 10^(-8)。
~~~
double eps=1e-9;
double 1=0,r=N;
while(l+eps<r){
    double mid=(l+r)/2;
    if(check(mid))r=mid;//check(mid):mid^M>N 
    else l=mid;
}

public class Main {
    public static void main(string[] args){
    solve();
    out.flush();
    }
    static double N,M;
    static double eps=1e-9;
    static boolean check(double x){了
        double res=1;
        for(int i=1;i<=M;i++){
            res=res*x;
        }
        return res>=N;
    }
    static void solve(){
        N=in.nextDouble();
        M=in.nextDouble();
        double 1=1,r=N;
        while(l+eps<r){
            double mid=(1+r)/2;
            if(check(mid)){
                r=mid;
            }else{
                l=mid;
            }
        }
        out.println("%.7f",l);
    }
}
~~~
蓝桥杯中基本没有该题，因为eps不好确定，了解算法思想即可


### 双指针
（1）基本概念
用于解决数组或链表中的问题

（2）左右指针
两个指针方向相反
主要用于处理排序数组中的问题，尤其是在查找特定和，差值等场景中适用

（3）快慢指针
两个指针方向相同
使用 slow 和 fast 指针分别初始化为 0。
创建一个 set(哈希集合)来存储当前窗口内的字符。这个集合能够帮助快速判断当前窗口中是否已经包含了某个字符。
我们从字符串的左侧开始，用 fast 指针向右遍历字符串，用于向窗口中添加字符。
    每次 fast 指针右移，将对应的字符 s[fast]加入哈希集合中。如果该字符不在集合中，说明没有重复，可以继续扩展窗口。
    当发现当前字符 s[fast]已经存在于哈希集合中，说明窗口中出现了重复字符。这时我们需要通过移动slow 指针来缩小窗口。
具体做法是:不断移动 slow 指针，并从集合中移除 s[slow]，直到窗口中不再有重复字符。·每次成功扩展窗口时(即 s[fast] 不在集合中)，我们都需要更新当前最长无重复子串的长度maxLen，计算方式为 fast- slow+1。


### Java的基础常见API
1. BigInteger的常见使用
其有以下几种基本处理函数和应用于数论中的函数在算
BigInteger 是 Java 语言中自带的高精度处理类
~~~
static BigInteger a,b;
//加法
static void add(){
    out.println("add:");
    a= new BigInteger("123");
    b= new BigInteger("123");
    out.println(a.add(b));//输出 246
}
//减法
static void subtract(){
    out.println("subtract:");
    a = new BigInteger("123");
    b= new BigInteger("123");
    out.println(a.subtract(b));//输出 0
}
//乘法
static void multiply(){
    out.println("multiply:");
    a = new BigInteger("12");
    b = new BigInteger("12");
    out.println(a.multiply(b));//输出144
}
//除法
static void divide(){
    out.println("divide:");
    a= new BigInteger("12”);
    b= new BigInteger("11");
    out.println(a.divide(b));// 输出 1
}
//取余
static void remainder(){
    out.println("remainder:");
    a = new BigInteger(“12");
    b= new BigInteger("10");
    out.println(a.remainder(b));//输出2
}
static void gcd(){ // 最大公约数
    a= new BigInteger("120032414321432144212100");
    b= new BigInteger("240231431243123412432140");
    out.printIn(string.format("gcd(%s,%s)=%s",a.tostring(),b.tostring(),a.gcd(b).tostring()));
}
static void isprime(){
     //基干米勒罗宾判定该数是否是素数，参数越大准确性越高，复杂度越高。准确性为(1-1/(va1*2))
     a = new BigInteger("1200324143214321442127");
     out.println("a:"+ a.toString());
     out.printin(a.isProbablePrime(10)?"a is prime" : "a is not prime"): // a is not prime
}
static void nextPrime(){ // 找出该数的下一个素数
    a= new BigInteger("1200324143214321442127");
    out.println("a:" + a.tostring());
    out.printIn(String.format("a nextprime is %s", a.nextprobablePrilye().tostring()));// a nextprime is 1288324143214321442199
}

static void modPow(){ // 快速幂，比正常版本要快，内部有数学优化
    a=new BigInteger(“2);
    b =new BigInteger("10");
    p= new BigInteger("1000");
    out.println(String.format("a:%s b:%s p:%s",a,b, p));
    out.printIn(String.format("a^b mod p:%s",a.modPow(b, p).tostring()));// 24
}

static void modInverse(){
    a = new BigInteger(“10");
    b= new BigInteger("3");
    out.println(a.modInverse(b));//a^(p-2)mod p=1
}
~~~

2. Arrays 的常见使用
Arrays.fill(a,-1):将数组a中全部元素赋值为 -1。
Arrays.sort()是对数组进行的排序的方法，主要重载方法如下:
~~~
Arrays.sort(a);//1

Arrays.sort(a,firstIdx，lastIdx);//2

Arrays.sort(b,new Comparator<Integer>(){//3
    @Overridepublic intcompare(Integer o1,Integer o2){
        return 02 -01;
    }
});

Arrays.sort(b,firstIdx, lastIdx, new comparator<Integer>(){ //4
    @Overridepublic int compare(Integer ol,Integer o2){
        return o2 - 01;
    }
});

~~~
由于 Java 8 后有 Lambda 表达式，第三个重载及第四个重载亦可写为
~~~
Arrays.sort(b,(x，y)->{//5
    return y-x;
});
Arrays.sort(a,fromIndex,toIndex,(x,y)->{ // 6
    return y-x;
});
~~~
1. 对数组a进行排序，默认升序。
2. 对数组a的指定位置进行排序，默认升序，排序区间为左闭右开[firstIdx,lastIdx)。
3. 对数组a以自定义的形式排序，第二个参数-第一个参数为降序,第一个参数-第二个参数为升序,当自定义排序比较器时，数组元素类型必须为对象类型。
4. 对数组a的指定位置进行自定义排序，排序区间为左闭右开 [firstIdx,lastIdx)，当自定义排序比较器时，数组元素类型必须为对象类型
5. 和3同理，用Lambda 表达式优化了代码长度。
6. 和4同理，用 Lambda 表达式优化了代码长度。


### 基础算法综合
1. 前缀和与前缀异或和
题目：长度为n的非负整数a，需要处理q组询问，每组询问有两个参数l,r，需要判断a[l]+a[l+1]+...+a[r]是否等于a[l]a[l+1]^...^a[r]。a[l]异或a[l+1]异或...异或a[r]
输入：
   1. 第一行包含两个整数n和q，n表示数组a的长度，q表示询问的个数。
   2. 第二行包含n个整数，表示数组a。
   3. q行，每行包含两个整数l和r，表示询问的区间。
输出：
    输出q行，每行包含一个整数，表示询问的结果。
    1. 如果a[l]+a[l+1]+...+a[r]等于a[l]a[l+1]^...^a[r]，输出YES，否则输出NO。
~~~
static int N=100010;
static int n,q;
static int[] a=new int[N];
static long[] s=new int[N],s2[]=new int[N];

static void solve(){
    n=in.nextInt();
    q=in.nextInt();
    for(int i=1;i<=n;i++){
        a[i]=in.nextInt();
    }
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];
        s2[i]=s2[i-1]^a[i];
    }
    for(int i=1;i<=q;i++){
        l=in.nextInt();r=in.nextInt();
        out.println(s[r]-s[l-1]==s2[r]^s2[l-1]?"YES":"NO");
    }
}
~~~

题目： 长度为N的数列，A1,A2,...,AN，如果其中一段连续的子序列Ai,Ai+1,...,Aj之和是K的倍数，称区间[i,j]为K倍数区间。求出所有K倍数区间的个数。
输入：
    第一行包含两个整数N和K，以下输入N个整数，表示数列。
输出：一个整数，代表K倍区间的数目
~~~
static int N=100010;
static int n,k;
static int[] a=new int[N],int[] cnt=new int[N];
static long[] s=new int[N];

static void solve(){
    n=in.nextInt();
    k=in.nextInt();
    for(int i=1;i<=n;i++){
        a[i]=in.nextInt();
        s[i]=s[i-1]+a[i];
    }
    long res=0;//用于存储最终的结果
    for(int i=1;i<=n;i++){
       if(s[i]%k==0){
        res++;
       }
       res=res+cnt[(int)s[i]%k];//将 cnt 数组中对应位置的值加到 res 上。
       cnt[(int)s[i]%k]++;//然后将 cnt 数组中对应位置的值增加 1。
    }
    out.println(res);
}
~~~

### 例题：一维前缀与一维差分
1. 店铺编号由1~n，一开始时每家店铺的点赞值都是 0，会有用户给店铺点赞，如果一家店铺的点赞值大于等于x，会被认定为信赖店铺。
点赞情况由t行数据构成，每行数据由一个区间[l,r]构成，表示l编号到r编号的店铺都被点了 1个赞。
现在给你q组查询，每组查询一个区间[l,r]，你可以计算出该区间有多少家店铺是信赖店铺吗?

输入格式:
    第一行输入四个整数 n,t,q,x
    接下来t行输入，每行两个整数l,r表示被点赞的店铺编号区间。
    接下来q行输入，每行二个整数l,r表示需要查询的店铺编号区间。

输出格式:
q行输出，对于每一个查询，输出该区间值得信赖的店铺数量。
~~~
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),t=sc.nextInt(),q=sc.nextInt(),x=sc.nextInt();

        int[] b=new int[n+2];//差分数组，用于记录区间增量变化
        for(int i=0;i<t;i++)//进行差分操作
        {
            int l=sc.nextInt(),r=sc.nextInt();
            b[l]+=1;
            b[r+1]-=1;
        }
        //构建原数组，并求出前缀和
        int[] a=new int[n+1];//用于存储每个店铺实际点赞值
        for(int i=0;i<=n;i++)
        {
            a[i]=a[i-1]+b[i];//通过累加来恢复每个店铺的实际点赞值
        }

        int[] cnt=new int[n+1];//用于记录满足条件的前缀和
        for(int i=1;i<=n;i++)
        {
            if(a[i]>=x){
                cnt[i]=cnt[i-1]+1;
            }
            else{
                cnt[i]=cnt[i-1];
            }
        }

        for(int i=0;i<q;i++)//用计数数组快速计算区间内有多少家信赖店铺
        {
            int l=sc.nextInt(),r=sc.nextInt();
            int ans=cnt[r]-cnt[l-1];
            System.out.println(ans);
        }
    }
}
~~~
核心思想：使用差分数组来高效地处理区间更新，并通过前缀和数组快速回答区间查询。

2. 字符迁移
   长度为 N 的字符串 S,进行 Q 次操作:每次操作给定三个整数l,r,k，将S 的第l个字符到第r个字符都循环右移k次在操作完成后S是多少?
   字符右移表示为按字母表进行移动，例如a右移1次变为 b,b右移 2 次变为 d。特别地,z 右移 1 次变回为 a。
   
输入格式:
第一行输入两个整数 N,Q(1<=N,Q <=2 x 10^5)表示字符串 S 的长度和操作次数。
第二行输入一个字符串 S，保证 S 只包含小写字符。
接下来 Q 行每行输入三个整数 l,r,k(1 ≤l≤r≤ N,1≤k≤ 10^9)表示一次操作。
输出格式:
输出一个字符串表示答案。 
解题思路：将循环右移转化为加法操作，然后对26取余。加法操作可以用差分实现
~~~
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),q=sc.nextInt();
        sc.nextLine();//注意要写这里不然会报错！！！
        String s=sc.nextLine();
//注意b的范围一定要写成n+2 ,r=n,b[r+1]=b[n+1],n+1代表的是第n+2的位置，数组下标是0，1，2，3
        int[] b=new int[n+2];//差分数组
        for(int i=0;i<q;i++)//进行差分操作
        {
            int l=sc.nextInt(),r=sc.nextInt(),k=sc.nextInt();
            int t=k%26;
            b[l]+=t;
            b[r+1]-=t;
        }

        int[] a=new int[n+1];//对差分数组做前缀和恢复原数组a
        for(int i=0;i<=n;i++)
        {
            a[i]=a[i-1]+b[i];
        }

        StringBuilder ans=new StringBuilder();//?
        for(int i=1;i<=n;i++)
        {
            //获取字符串 s 中的第 i 个字符（注意索引从 0 开始）
            char ch=s.charAt(i-1);
            //计算偏移量 a[i] 对 26 取模的结果，确保偏移量在 0 到 25 之间
            int chh=a[i]%26;
            /*
            ch - 'a'：将字符 ch 转换为相对于 'a' 的偏移量（例如 'a' -> 0, 'b' -> 1, ...）。
            + chh：加上偏移量 chh。
            + 26：确保结果为正数。
            % 26：对 26 取模，确保结果在 0 到 25 之间。
            + 'a'：将结果转换回字符。
            */
            char c=(char)((ch-'a'+chh+26)%26+'a');
            //将加密后的字符添加到 StringBuilder 对象 ans 中
            ans.append(c);
        }
        System.out.println(ans.toString());
    }
}
~~~
补充：StringBuilder: 这是一个可变的字符序列，用于高效地构建和修改字符串。与 String 不同，StringBuilder 是可变的，避免频繁创建新的 String 对象，提高性能。
假设你需要构建一个字符串 "Hello, World!"，使用 StringBuilder 的过程如下：
~~~
java
StringBuilder ans = new StringBuilder();
ans.append("Hello");
ans.append(", ");
ans.append("World");
ans.append("!");
String result = ans.toString();
System.out.println(result); // 输出: Hello, World
~~~

3. 区间次方和
给定一个长度为 n 的整数数组 a以及 m 个查询。
每个查询包含三个整数 l,r,k 表示询问l~r之间所有元素的 k 次方和。
请对每个查询输出一个答案，答案对 10^9+7取模。
输入格式:
第一行输入两个整数 n,m 其含义如上所述。
第二行输入 n 个整数 a[1], a[2],…, a[n]。
接下来 m 行，每行输入三个整数l,r,k 表示一个查询。
输出格式
输出 m 行，每行一个整数，表示查询的答案对 109 +7取模的结果。
~~~
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        
        for(int i=1;i<=n;i++)
        {
            a[i]=in.nextLong();
        }
        for(int j=1;j<=5;j++)
        {
            for(int i=1;i<=n;i++)
            {
                s[j][i]=(long)((s[j][i-1]+Math.pow(a[i],j))%mod);

            }
        }
        for(int i=0;i<m;i++)
        {
            int l=sc.nextInt(),r=sc.nextInt(),k=sc.nextInt();
            long res=(s[k][r]-s[k][l-1]+mod)%mod;
           System.out.println(res);
        }
    }
}
~~~
注意：取模部分：
例子：a=10,b=7,mod=9
原本a-b=3
a%mod=10%9=1
b%mod=7%9=7
a-b=-6
错误，因此变成((a+mod)-b)%mod=((10+9)-7)%mod=3

4. 类斐波那契循环数
填空题
题目：对于一个有n位的十进制数N=d1d2d3...dn,可以生成一个类斐波那契数列S,数列S的前n个数为{S1=d1,S2=d2,S3=d3...Sn=dn},数列S的第k(k>n)个数为：Si=Si-1+...+Si-n
如果这个数N会出现在对应的类斐波那契数列S中，那么N就是一个类斐波那契循环数
例如：对于197，对应的数列S为：{1，9，7，17，33，57，107，197...}
(17=1+9+7;
33=9+7+17;
57=7+17+33;
...)
197出现在S中，所以197是一个类斐波那契循环数。
请问在0至10^7中，最大的类循环数是多少？
如果N=193，d1=1,d2=9,d3=3,
~~~
import java.util.ArrayList;
import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long an = 0;
        for (int i = 197; i < 1e7; i++) {
            if (pd(i)) {
                an = i;
            }
        }
        System.out.println(an);
    }

    private static boolean pd(int i) {
        ArrayList<Integer> ans = new ArrayList<>();
        String s = "" + i;
        int anss=0;

        // 将数字的每一位添加到列表中，并计算前 n 位的和
        for (int j = 0; j < n; j++) {
            ans.add( s.charAt(j) - '0');
            anss=anss+s.charAt(j) - '0';
        }

        // 初始化数列的前 n 位
        ans.add(anss);

        // 生成类斐波那契数列并检查是否包含原数字
        while (true) {
            anss=(anss*2)-ans.get(0);//计算公式，其中ans.get(0)表示ans的第一个元素
            ans.remove(0);
            ans.add(anss);

            if (anss == i) {
                return true;
            } else if (anss > i) {
                return false;
            }
        }
    }
}
~~~
解题思路：
1. 首先，定义一个函数 pd(int i)，用于判断一个数是否是一个类斐波那契循环数。
2. 在函数中，首先将数字 i 转换为字符串，并获取字符串的长度 n。
3. 然后，创建一个 ArrayList ans，用于存储数列的前 n 位。用一个数列ans存储所有的数字，并计算前 n 位的和anss。
4. 使用while 循环，生成类斐波那契数列，每次将 ans 的第一个元素删除，并将 ans 的和 ans 乘以 2 再减去 ans 的第一个元素，然后将结果添加到 ans 的末尾。

### 例题：二维前缀与二维差分
1. 二位前缀和
问题描述
给定一个 nx m 大小的矩阵 A。
给定q组查询，每次查询为给定4个正整数 1,y1,2,y2，你需要输出 ∑r1∑u Aj 的值。
输入格式
第一行输入 3 个正整数 n,m,q。(1 ≤ n,m ≤ 103,1≤q≤105)
接下来 n 行每行输入 m 个整数，表示 Aij。(-10°< Ai,j <103,l≤i≤ n,l≤j<m)
接下来q行，每行输入4个正整数 1,y1,℃2,y2。(l ≤ 1≤æ2 ≤ n,l ≤ yi ≤ y2 < m)
输出格式
对于每次查询，输出一个整数，表示查询的子矩阵的和。
~~~
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(),g= sc.nextInt();
    int[][] a = new int[n+1][m+1];
    int[][] b= new int[n+1][m+1];
    for(int i = 1; i <= n; i++){
        for(int j=1; j<= m; j++){
            a[i][j]= sc.nextInt();
            b[i][j] = a[i][j] + b[i-1][j] + b[i][j-1]- b[i-1][j-1];
        }
    }
    for(int i = 0; i< q; i++){
        int x1 =sc.nextInt(),y1=sc,nextInt(),x2=sc.nextInt(),y2 = sc.nextInt();
        System.out.println(b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+ b[x1-1][y1-1]);
    }
    sc.close();
    }
}
~~~


1. 闪耀的灯光
问题描述
公园可以被视为由nxm个矩形区域构成。每个区域都有一盖灯，初始亮度为 a[i][j]。
小蓝可以选择一个大的矩形区域，并按下开关一次，这将使得该区域内每盏灯的亮度减少1，但每个区域内的灯的亮度最多只能减少至a[i][j]-c。如果此时亮度为 a[i][j]-c，再次按下开关将使得灯的亮度恢复为 a[i][j]。
现在小蓝将进行t次操作。每次操作他会选择一个矩形区域，该区域的左上角端点为(x1,y1)，右下角端点为(x2,y2)，然后将该区域内所有灯按下k次开关。他想知道，在每次操作结束后，该区域内所有灯的总亮度是多少?然后在下一次操作前，他会将公园内所有灯光恢复初始值。
数据保证每盖灯的亮度不会减少至负数。

~~~
import java.util.scanner;

public class Main {
    public static void main(string[] args){
    Scanner sc =new scanner(system.in);
    //在此输入您的代码..
    int n=sc.nextInt(),m=sc.nextInt(),c= sc.nextInt();
    int[][] a = new int[n+1][m+1];
    int[][] b= new int[n+1][m+1];
    for(int i = 1; i <= n; i++){
        for(int j=1; j<= m; j++){
            a[i][j]= sc.nextInt();//灯的初始亮度
            b[i][j] = a[i][j] + b[i-1][j] + b[i][j-1]- b[i-1][j-1];
        }
    }
    int t=sc.nextInt();
    for(int i = 0; i< t; i++){
        int x1 =sc.nextInt(),y1=sc,nextInt(),x2=sc.nextInt(),y2 = sc.nextInt(),k = sc.nextInt();
        k%=c+1；
        System.out.println(b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+ b[x1-1][y1-1]-(long)(x2-x1+1)*(y2-y1+1)*k);
        //(x2 - x1 + 1) * (y2 - y1 + 1)：计算矩形区域内的点的数量，即矩形的面积;* k：将矩形区域内的点的数量乘以系数 k
    }
    sc.close();
    }
}
~~~
2. ROG
   问题描述
给定一个大小为 n xm 的字符矩阵(仅包含大写英文字母)
我们定义“幸运字符串”为一种包含三个不同字符的字符串。在该矩阵中，如果三个字符为 R、O 和 G，且其位置分别为(x1,y1)、(x2, y2)、(x3, y3),并满足 x1 ≤ x2 ≤ xз目 y1≤ y2≤ y3，则称该字符串为一个“幸运字符串”。
请找出矩阵中所有满足条件的"ROG"幸运字符串的个数。由于结果可能很大，最终答案需对 998244353 取模。
以下方字符矩阵为例:
RAG
OGR
ROG
(1,1)→(2,1)→(3,3)，字符分别是R、0、G。
(1,1)→(3,2)→(3,3)，字符分别是 R、0、G
(1,1)→(2,1)→(2,2)，字符分别是 R、O、G。
(3,1)→(3,2)→(3,3)，字符分别是 R、0、G。
总计 4种。
~~~
import java.util.scanner;

public class Main {
    public static void main(string[] args){
    Scanner sc =new scanner(system.in);
    //在此输入您的代码..
    int mod = 998244353;
    int n=sc.nextInt(),m= sc.nextInt();
    //输入字符矩阵
    char[][]c= new char[n + 1][m + 1];
    for(int i=1; i <= n; i++){
        string s= sc.next();
        for(int j=1; j<= m; j++){
            c[i][j]=s.charAt(j- 1);
        }
    }
    //求前缀和，后缀和
    int[][] q = new int[n + 2][m + 2];
    int[][]h= new int[n + 2][m + 2];

    for(int i = 1; i<= n; i++){
        for(intj=1;j<= m; j++){
            h[i][j]=h[i-1][j]+ h[i][j-1]- h[i - 1][j - 1];
            if(c[i][j]=='R')h[i][j]++;
        }
    }

    for(int i =n; i >= 1; i--){
        for(intj=m;j>=1; j--){
            q[i][j]= q[i + 1][j]+ q[i][j + 1]- q[i + 1][j + 1];
            if(c[i][j]=='G')q[i][j]++;
        }
    }

    long ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(c[i][j]=='O')
            {
                ans+=((long)h[i][j]*q[i][j])%mod;//左上乘右下
                ans%=mod;
            }
        }
    }
    System.out.println(ans);
    sc.close();

    }
}
~~~
解题思路：
例如：abbccefacbbda,求aeb子序列的个数，从e分开abbcc e facbbda，（前面有几个a）*（后面有几个b）就有几个序列，所以就是a*b的个数。
本题类似,如图：
![ROG解题图示](ROG解题图示.png)
注意：两次取余操作，
第一次取余操作：((long)h[i][j] * q[i][j]) % mod
这里的目的是确保每次乘法结果不会超出模数 mod 的范围。
第二次取余操作：ans %= mod
这里的目的是确保累加后的 ans 始终在 [0, mod-1] 范围内

3. 棋盘
问题描述
小蓝拥有 n xn 大小的棋盘，一开始棋盘上全都是白子。进行了m 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色，黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。
输入格式:
输入的第一行包含两个整数 n，m，用一个空格分隔，表示棋盘大小与操作数。
接下来 m 行每行包含四个整数 x1，y1，x2，y2，相邻整数之间使用一个空格分隔，表示将在 x1至x2行和 y1至 y2 列中的棋子颜色取反。
输出格式:
输出几行，每行几个0或1表示该位置棋子的颜色。如果是白色则输出 0，否则输出 1。
~~~
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] b = new int[n + 2][n + 2];

        for (int i = 0; i < m; i++) {
            int x1 = sc.nextInt(), y1 = sc.nextInt(), x2 = sc.nextInt(), y2 = sc.nextInt();
            b[x1][y1] += 1;
            b[x2 + 1][y1] -= 1;
            b[x1][y2 + 1] -= 1;
            b[x2 + 1][y2 + 1] += 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print((b[i][j] % 2));
            }
            System.out.println();
        }

        sc.close();
    }
}
~~~
解题思路：
差分
每次操作会将矩形区域 (x1, y1) 到 (x2, y2) 内的棋子颜色取反。
使用差分数组的思想，在矩形的四个角上进行标记：
左上角 (x1, y1) 加1。
右下角下方 (x2+1, y1) 减1。（不再受当前矩形的影响）
左下角右侧 (x1, y2+1) 减1。（不再受当前矩形的影响）
右下角右下方 (x2+1, y2+1) 加1（被多减了一次，所以+1）

前缀和：通过累加差分数组，恢复实际的颜色变化情况。
，如果是偶数：白色，奇数：黑色

## 三.数据结构基础

### 1.链表
   1. 单链表
   2. 双链表
   3. 例题：左移右移
    长度为 N 的数组,初始时从左到右依次是 1,2,3,...N。对这个数组进行了 M 次操作,每次操作可能是以下 2 种之一,
    1.左移 x,即把 x 移动到最左边。
    2.右移 x,即把 x 移动到最右边。
    请你回答经过 M 次操作之后,数组从左到右每个数是多少?
    模拟双链表就可以，注意移动操作是<mark>先删除后插入<mark>
~~~
    //初始化双链表
    int l[]=new int[n+10],r[]=new int[n+10];
    for(int i=l;i<=n;i++){
        l[i]=i-1;//上一个结点是i-1
        r[i]=i+1;//下一个结点是i+1
    }
    l[n+1]=n;//n+1的上一个结点是n,将n+1看成尾结点tail
    r[0]=1;//0的下一个结点是1,0看成头节点head
    Scanner in=new Scanner(System.in);
    //具体操作
    while(m-->0){
        for(int i=1;i<=m;i++){
        String op=in.next();
        int x=in.nextInt();

        //如果要删除的结点是首结点
        if(x==r[0])r[0]=r[x];
        //如果x是节点，则
        else if(x==l[n+1])1[n+1]=1[x];
        //删除操作
        r[l[x]]=r[x];//当前结点x的上一个结点l[x]的下一个结点r[l[x]]是当前结点的下一个结点r[x]
        1[r[x]]=1[x];//当前结点x的下一个结点r[x]的上一个结点l[r[x]]是当前结点的上一个结点l[x]

        //插入操作
        if(op.equals("L")){
            l[r[0]]=x;//首结点r[0]的上一个结点=x
            l[x]=0;//首结点l[x]的上一个结点=0
            r[x]=r[0];
            r[0]=x;
        }
        else{
            r[l[n+1]]=x;
            l[x]=l[n+1];
            r[x]=n+1;
            l[n+1]=x;
        }
    }
    for(int i=r[0];i!=n+1;i=r[i]){
        out.print(i+"");
    }
    }
    
~~~
![链表插入删除代码演示](链表插入删除代码演示.png)
### 2.栈
   1. 栈的原理
   后进先出
   基本操作：
    2. 压入（Push）
    3. 弹出（Pop）
    4. 查看顶部元素（Peek）
    5. 检查栈是否为空（isEmpty）
    6. 获取栈的大小（size）
   
   2. 例题：模拟栈
    用数组stk模拟栈，top变量来维护栈顶指针
    入栈
    stk[++top]=x
    出栈
    top--
    判空
    top==0
    获取栈的大小
    return top
题目：你需要实现一个栈，初始时栈为空。有 m 组查询，每次查询为以下四种操作之一
push x:向栈顶插入一个正整数 
pop:删除栈顶元素，若此时栈为空，则不做任何操作。
empty:判断栈是否为空，若为空输出 YES，否则输出 NO。
query:输出栈顶元素，若栈为空则输出 empty。
输入格式：
第一行输入一个正整数 m。(1 ≤ m ≤ 10^5)
接下来 m 行，每行输入一种操作，对于empty与 query，需要有对应的输出。
push x的范围(1 ≤x< 10^5)。
输出格式:
对于 empty 与 query 操作，按照题目要求输出。

~~~
import java.util.Scanner;

public class Main {
    Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int n=1;
        while(n-->0)solve();
        out.flush();
    }

    static int stk[]=new int[100010];
    static int top=0;

    static void push()
    {
        stk[++top]=x;
    }

    static void pop(){
        if(isEmpty())return;
        top--;
    }
    static boolean isEmpty(){
        return top==0;
    }
    static void query(){
        if(isEmpty())System.out.println("empty");
        System.out.println(stk[top]);
    }
    static void solve() {
        int m = sc.nextInt();
        while (m-- > 0) {
            String op = sc.next();
            if(op.equals("push"))
            {
                int x = sc.nextInt();
                push();
            }
            else if(op.equals("pop")){
                pop();
            }
            else if(op.equals("empty")){
                System.out.println(isEmpty()?"YES":"NO");
            }
            else if(op.equals("query")){
                query();
            }
        }
    
    }
        
}
~~~
   3. 例题：判定括号序列
问题描述
长度为n的括号串，仅由字符(、)构成，请你帮他判断一下该括号串是否合法，合法请输出 yes ，反之输出 No。
合法括号序列:
1.空串是合法括号序列。
2.若s是合法括号序列，则(s)也是合法括号序列。
3.若 s,t都是合法括号序列，则 st 也是合法括号序列。
例如()()，(())，(())()均为合法括号序列。

输入格式:
第一行包含一个正整数 n，表示括号串的长度。
第二行包含一个长度为 n的括号串。

输出格式:
输出共1行，若括号串合法请输出 Yes ，反之输出 NO。
~~~
import java.util.Scanner;

public class Main {
    static int zu;
    public static void main(String[] args) {
        int t=1;
        for(zu=1;zu<=t;zu++>)solve();
        out.flush();
    }
    static char stk[]=new char[110];
    static int top=0;
    static solve() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        for (int i = 0; i < n; i++) {
            char c=s.charAt(i);//读取字符串的第二个字符
            if (c == '(') {//如果是左括号就入栈
                stk[++top] = '(';
            }
            else{//如果是右括号就出栈
                if (top == 0) {//如果栈为空，则输出NO
                    System.out.println("NO");
                    retunrn 1;
                }
                else {
                    top--;
                }
            } 
        }
        if (top == 0) {//如果栈为空，则输出YES
            System.out.println("YES");
        }
        else {//如果栈不为空，则输出NO
            System.out.println("NO");
        }
    }

}
~~~

### 3.队列
   1. 什么是队列
   
   2. 例题：模拟队列
问题描述：
你需要实现一个队列，初始时队列为空。有 m 组查询，每次查询为以下四种操作之一
push x:向队尾插入一个正整数
pop:删除队首元素，若此时队列为空，则不做任何操作。
empty:判断队列是否为空，若为空输出 YES，否则输出 NO。
query:输出队首元素，若队列为空则输出 empty。

输入格式：
第一行输入一个正整数 m。(1 ≤ m ≤ 10^5)
接下来 m 行，每行输入一种操作，对于 empty 与 query，需要有对应的输出。
push x的范围(1 ≤ m ≤ 10^5)。

输出格式：
对于 empty 与 query 操作，按照题目要求输出,

可以用数组模拟队列，head表示头指针，tail表示尾指针
初始：head=tail=0;
我们插入元素时，可以写h[tail++]=x;
我们删除元素时，可以写head++ 
判空则判断head==tail

while(m-->0)
[
    String op=in.next();
    if("push".equals(op)){
        int x=sc.nextInt();
        q[tail++]=x;
    }
    else if("pop".equals(op)){
        if(head==tail)continue;
        head++;//头指针移到下一个位置，删除操作
    }
    else if("empty".equals(op)){
        if(head==tail)System.out.println("YES");
        else System.out.println("NO");
    }
    else {
        if(head==tail)System.out.println("empty");
        else System.out.println(q[head]);
    }
]

### 4.递归在程序中运行的原理
   1. 什么是递归
   2. 递归式如何回溯的
      1. 借助栈回溯，当递归函数调用自身时，系统将当前的函数调用状态压入栈中，当递归达到基准状态时，函数开始从栈中弹出，逐个返回调用状态，完成整个递归过程


### 5.集合和哈希
   1. 什么是集合

   2. 例题：哈希表的实现
问题描述：
给定一个集合与q次操作，每次操作具体如下:
I x:在集合中插入一个值为x的数。
Q x:查询x是否在集合中出现过。

输入格式:
第一行输入一个正整数 q，表示查询次数。(1 ≤q≤ 10^5)
接下来q行，每行输入代表依次进行一个操作。(1 ≤ x≤ 10^9)

输出格式:
对于每组查询，如果 灭出现过，则输出 ves，否则输出 NO。
~~~
//取余后，按照余数放入对应的哈希表中，如果重复，则往后顺延；查找的时候，查找对应的余数的位置，没找到就往后寻找
import java.util.Scanner;

public class Main {
    static int zu;
    public static void main(String[] args) {
        int t=1;
        for(zu=1;zu<=t;zu++>)solve();
        out.flush();
    }
    static int N=200010;
    static int mp[]=new int[N];
    static int mod=100003;
    static int hash(int x){
        return x%mod;
    }
    //①每一次数字是否在HASH中存在过，②每次查找哪个坑位适合
    static int find(int x){
        int h=hash(x);
        while(mp[h]!=-1&&mp[h]!=x)h++;//
        return h;
    }
    static class solve(){
        Arrays.fill(mp,-1);
        int q=in.nextInt();
        while(q-->0){
            String op=in.next();
            if(op.equals("I")){
                int x=in.nextInt();
                mp[find(x)]=x;
                
            }
            else{
                int x=in.nextInt();
                if(mp[find(x)]==x)out.println("Yes");
                else out.println("No");
            }
        }
}
    
    
}

~~~
   3. Java提供的Set集合
      1. 不允许由重复的元素
      2. 元素的存储位置和插入顺序无关
      3. 插入，删除和查找操作的时间复杂度平均为O(1)
      4. 常用函数:
        add(E e):向集合中添加元素，如果元素已存在，返回 false。
        remove(0bject o):从集合中移除元素，成功返回 true。
        contains(0bject o):判断集合中是否包含指定元素。
        size():返回集合中元素的数量。
        clear():清空集合中的所有元素。
        isEmpty():判断集合是否为空
        示例代码：
        ~~~
        import java.util.HashSet;

        public class HashSetExample{
            public static void main(Stringl args){
                HashSet<String>set = new HashSet<>();
                // 添加元素
                set.add("apple");
                set.add("banana");
                set.add("cherry");
                //检查是否包含元素
                System.out.println(set.contains("banaa")); // 输出 true
                // 移除元素
                set.remove("banana");
                // 集合大小
                System.out.println(set.size());//输出 2
            }
        } 
        ~~~


        LinkedHashset 是 Hashset 的子类，它基于哈希表实现，同时使用链表来维护元素的插入顺序。因此，它既具备 Hashset 的哈希表特性，又能保证元素按照插入顺序排列。
        ·不允许有重复的元素。
        ·保证元素的插入顺序。
        .插入、删除和查找操作的时间复杂度平均为(0(1))。

~~~
        import java.util.HashSet;

        public class LinkedHashSetExample{
            public static void main(String[] args){
                LinkedHashSet<String> set = new LinkedHashSet<>();
                // 添加元素
                set.add("apple");
                set.add("banana");
                set.add("cherry");
                //输出集合，按插入顺序
                for(String s :set){
                    System.out.println(s);//输出顺序为：apple,banana,cherry
                }
                //检查是否包含元素
                System.out.println(set.contains("banaa")); // 输出 true
             
            }
        } 
~~~


Treeset 是基于红黑树(Red-Black Tree)实现的集合。与 Hashset 和 LinkedHashset 不同，Treeset 会自动对元素进行排序。它实现了 Sortedset 接口，因此可以保证集合中的元素处于自然顺序(或者是用户自定义的排序规则)。
·不允许有重复的元素。
·元素按照自然顺序(或自定义顺序)排序。
·插入、删除和查找操作的时间复杂度为 O(logn)W。
。适用于需要保持元素有序的场景。
~~~
import java.util.TreeSet;
public class TreeSetExample{
    public static void main(String[] args){
        TreeSet<Integer>set =new TreeSet<>();
        // 添加元素
        set.add(30);
        set.add(10);
        set.add(20);
        set.add(40);
        // 自动排序
        System.out.println(set);//输出[10，20，30，40]
        //获取第一个和最后一个元素
        System.out.println("最小值::"+set.first());//输出 10
        System.out.println("最大值:"+ set.last());// 输出 48
        // 获取子集
        System.out.println("小于 38 的元素:"+ set.headset(30)); // 输出[10，20]
        System.out.println("大于等于 20 的元素:"+ set.tailSet(20));// 输出[20，30，40]
    }
}
~~~


   4. Java提供的Map哈希表
HashMap 是基于哈希表实现的 Map，键值对存储无序。
基于哈希表实现，键通过哈希函数映射到哈希表中的位置。
查找、插入、删除操作的平均时间复杂度为 0(1)。
无序存储，元素的顺序不保证与插入顺序一致。常用函数:
put(K key,V value):向 Map 中添加键值对，如果键已存在，更新对应的值。
get(0bject key):根据键查找对应的值。
remove(0bject key):移除指定键对应的键值对
getOrDefault(0bject key,8):根据键查找对应的值，不存在返回 0。5containsKey(0bject key):判断是否包含指定的键。
size():返回 Map 中的键值对数量。
clear():清空所有键值对。
keySet():返回所有键的集合。
~~~
import java.util.HashMap;
public class HashMapExample {
    public static void main(String[] args){
        //创建一个 HashMap
        HashMap<String, Integer>map = new HashMap<>();
        // 添加键值对
        map.put("apple", 1);
        map.put("banana”,2);
        map.put("cherry",3);
        //获取值
        System.out.println("apple 的值:"+ map.get("apple"));// 输出 1
        //判断是否包含键
        System.out.println("是否包含 cherry:"+ map.containsKey("cherry")); // 输出 true
        // 移除键值对
        map.remove("banana");
        //获取键的集合
        System.out.println("键的集合:"+ map.keySet()); // 输出[apple，cherry]
        //获取值的集合
        System.out.println("值的集合:"+ map.values()); // 输出[1，3]
        // 获取 Map 大小
        System.out.println("Map 大小:"+ map.size());// 输出 2
    }
}
~~~

遍历哈希表
~~~
HashMap<String, Integer> map = new HashMap<>();
for(int key:map.keySet()){
//key和yap.get(key);
}
~~~


### 6. 离散化
1. 步骤
对序列a进行去重后排序，得到每个数字的大小关系
将a的值一一映射到b
问题描述:
给定一个长度为n的序列 A，你需要输出序列中每一个元素在原序列 A中的大小排名。最小的数输出1，最大的数输出 cnt。cnt 为序列中不同元素的数量。
输入格式
第一行输入一个正整数 n。(1<n<10^5)
第二行输入几个整数 A。
输出格式
输出一行，按照题目要求输出几个正整数。
Map<Integer,Integer> mp=new TreeMap<>();
int n= in.extInt();
for(int i=1;i<=n;i++){
    a[i]=in.nextInt();
    mp.put(a[i],0);
}
int cnt=1;
for(int key: mp.keySet()){
    mp.put(key,cnt);
    cnt++;
}
for(int i=1;i<=n;i++){
    a[i]=mp.get(a[i]);
}
for(int i=1;i<=n;i++){
    out.print(a[i]+"");
}
### 7. 优先队列
1. 优先队列的使用
   优先队列，堆，分为大根堆和小根堆

优先队列定义方式如下:
Queue<Integer> q=new PriorityQueue<>(),Queue<Integer> q=new PriorityQueue<>((x,y)->y-x);
常见操作:
q.poll()返回并删除队首元素，为优先队列中的最值。复杂度为(log(n))。
q.peek()返回队首元素，为优先队列中的最值。复杂度为O(1)。
q.offer(x)将x插入队列中。复杂度为 O(log(n))。
g.isEmpty()判断队列是否为空。复杂度为 O(1)。
q.size()返回队列中元素个数。复杂度为 O(1)。
q.remove(x)删除指定元素。复杂度为 O(n)。

遍历优先队列
Queue<Integer> q=new PriorityQueue<>();
while(!q.isEmpty())
{
    out.println(q.po11());
}
时间复杂度为 O(nlogn)

2. 例题：堆排序
问题描述：
本题是一道堆排序模板题。
你需要构建一个堆，可以实现如下操作:
1.push:将一个正整数 z 插入堆中。
2.remove:删除堆顶元素。若此时堆为空，则输出 empty。
3.min:输出堆中最小的元素。若此时堆为空，则输出 empty。
4.print:给定一个小于等于出前堆中元素的数字k，你需要在一行内输出当前堆中最小的k个元素，并将其全部删除，数据保证该操作不会在堆为空时出现。

输入格式：
第一行输入一个整数 n，表示操作的数量。
接下来几 行，每行一个字符串，表示具体的操作。

输出格式：
对于 remove，min，print 操作，按照题目要求进行输出。

~~~
static int zu;
public static void main(String[] args){
    int t=1;
    for(zu=1;zu<=t;zu++)solve();
    out.flush();
}
static  Queue<Integer>  q=new PriorityQueue<>();
static void solve(){
    int n=in.nextInt();
    while(n-->0)
    {
        String op=in.next();
        //push：使用q.offer(x),将x插入
        if(op.equals("push")){
            int x=in.nextInt();
            q.offer(x);
        }
        //min：使用q.peek(),获取最小值
        else if(op.equals("min")){
            out.println(q.peek());
        }
        //remove：使用q.poll(),删除最小值
        else if(op.equals("remove")){
            if(!q.isEmpty()){
                q.poll();
            }
            else{
            out.println("empty");
            }
        }else{
                int k=in.nextInt();
                for(int i=0;i<k;i++)
                {
                    out.println(q.poll+" ");//每次迭代从队列q中取出一个元素并打印。
                }
                out.println();
            }
        
    }
}
~~~
### 8. Multiset实现优先队列
1. 支持重复元素何有序性的一种数据结构 
在Java语言中没有系统自带的multiset实现的数据结构的，因此需要利用TreeMap来实现。
需要实现的函数:
add(x):插入一个元素 x。
count(x):返回x的数量。
size():返回元素个数。
peek():返回堆顶元素。
poll():返回并删除堆顶元素。
remove(x):删除指定元素。
removeAll(x):删除全部的指定元素。
isEmpty:判断队列是否为空。
clear:清空队列。

2. 实现逻辑分析
TreeMap<T,Integer> multiset;//T:泛型，根据传入的参数确定类型
int len=0;//统计元素个数
Multiset(){
    multiset=new TreeMap<>();
}
Multiset(Comparator cmp){
    multiset=new TreeMap<>(cmp);
}

add
很简单，对于每一个<key,value>结构，value 存放 key 出现的次数就好了。
void add(T x){
    myltiset.put(x,multiset.getOrDefault(x,0)+1);//如果x在map中存在，则value+1，否则value=1
    len++;//统计元素总个数
}

count与size
int count(T x){
    return multiset.getOrDefault(x,0);//如果x在map中存在，则返回value，否则返回0
}
int size(){
    return len;
}


removeAll与remove
void remove(x){
    int res=multiset.getOrDefault(x,0)-1;
    if(res==-1){//=-1:0-1,直接return
        return;
    }
    if(res==0){
        removeAll(x);//=0,原来有一个，直接删除
        return;
    }
    len--;//否则，原来有多个，减一
    multiset.put(x,res);//减一
}
void removeAll(T x){
    len=len-multiset.getOrDefault(x,0);//减去原来有几个
    multiset.remove(x);//删除x
}


peek,poll
T peek(){//返回堆顶元素（并不删除）
    if(len==0)return null;
    return multiset.firstkey();
}
T pull(){//返回堆顶元素（删除）
    if(len==0)return null;
    T res = multiset.firstKey();
    remove(res);
    return res;
}

isEmpty,clear
boolean isEmpty(){
    return len==0;
}
void clear(){
    len=0;multiset.clear();
}

 
### 9.  单调栈
1. 数的左右最值问题
   
长度为N的序列a,输出每个数字其左边第一个比其大的数字，不存在则输出-1

~~~
public class Main(){
    final static int N=100005;
    static int n;
    static int[] a= new int[N];

    static int top =0;5个用法
    static int[]stack= new int[N]; 4个用法
    static int[]res= new int[N];0个用法
    static int top(){ return stack[top];} 0个用法
    static void push(int x){ stack[+top]=x;}0个用法
    static int pop(){return stack[top--];} 0个用法
    static void init(){top=0;stack[0]=-1;} 0个用法
    static boolean empty(){return top=0;} 0个用法

    static void solve(boolean greater,boolean left){
//第一行输出每个数字其左边第一个比其大的数字，不存在则输出 -1。
//第二行输出每个数字其右边第一个比其大的数字，不存在则输出 -1。
//第三行输出每个数字其左边第一个比其小的数字，不存在则输出 -1。
//第四行输出每个数字其右边第一个比其小的数字，不存在则输出 -1。
        init();
        for(int i=(left?1:n);i<=(left?n:i>=1);i+=(left?1:-1)){
            while(empty()&&greater?a[top]<=a[i]:a[top]>=a[i])
            {
                pop();
            }
            res[i]=top;
            push(i);
        }
        for(int i=1;i<=n;i++)out.print(res[i]==-1?"-1":a[res[i]]+" ");
        out.println();
    }

    public static void main(string[] args){
    n= in.nextInt();
    for(int i=1;i<=n;i+)a[i]= in.nextInt();
    solve(great:true,left:true);//左边比其大
    solve(great:true,left:false);//右边比其大
    solve(great:false,left:true);//左边比其小
    solve(great:false,left:false);//右边比其小

    out.flush();  
    }
}

~~~

2. 单调栈模板


### 10.   单调队列
1. 滑动窗口最值问题  
给定一个长度为N的序列和长度为K的窗口（1<=K<=N）
该窗口从左边滑动到右边，输出一行，每行N-K+1个数字。是每个窗口的最小值

队列始终保持单调，求最小值报吃单调递增（队头最小），求最大值保持单调递增（队头最大）

如何做到？
每次加入新元素，通过比较维护队列的单调性
如果队尾元素比新加入的元素大，说明不可能成为后续窗口的最小值，因此可以移除


问题描述
给定一个长度为 N 的序列 a 与一个长度为 K 的窗口。(1 ≤ K ≤N)
该窗口会从序列的最左端滑动到最右端，
你需要输出2行，每行N -K +1个数字。
第 1 行为每个窗口的最小值。
第 2 行为每个窗口的最大值。
输入格式
第一行输入两个正整数 N,K。(1≤K≤N< 10')
第二行输入 N 个正整数，表示序列 a。(1 ≤ a¡ < 10')
输出格式
输出2行，每行 N -K+1个数字。
第 1 行为每个窗口的最小值。
第 2 行为每个窗口的最大值。
样例输入
8 3
13135367
样例输出
111333
~~~
import java.io.*;
import java.util.stringTokenizer;
public class Main {
    final static int N=100005;
    static int[]a=new int[N];
    static int n,k;
    static int[]q= new int[N];//双端队列，存储当前窗口中的元素索引
    static int head, tail;

    static void solve(boolean greater){
        head=tail=q[0]=0;
        for(int i=1;i<=n;i++){
            if(i!=1&&i-q[head]>=k)head++;//如果当前索引i超过窗口大小k，移除队列头部超出窗口范围的元素
            while(head!=tail &&(greater ? a[q[tail-1]]<=a[i]: a[q[tail-1]]>=a[i]))//根据 greater 的值，调整队列中的元素顺序，确保队列头部始终是当前窗口的最值
            {q[tail++]= i;}
            if(i >= k)out.print(a[q[head]]+" ");//输出当前窗口的最值
        }
    }

    public static void main(string[] args){
        n = in.nextInt();
        k= in.nextInt();
        for(int i=1;i<=n;i++)a[i]= in.nextInt();
        solve(false);//输出当前窗口的最小值
        out.println();
        solve(true);//输出当前窗口的最大值
        out.flush();
    }
}
~~~
### 11.   并查集
 解决不相交集合的并集，并查询并集的个数
 实现上为一个森林，其中每棵树表示一个集合，树种的节点表示对应集合种的元素，树根的编号就是集合的编号
 初始时，将自己连向自己表示节点i属于集合i
 static int[]tree=new int[1005];
 static void init(int n){
    for(int i=1;i<=n;i++)tree[i]=i;
}  

查询
假如要查询a和b是否在一个集合当中，只需要查询a的根节点是否等于b的根节点
static int find(int x){
    return f[x]==x?x:find(f[x]);
}
static boolean query(int x,int y){
    return find(x)==find(y); 
}

合并
合并时将a的根节点的父节点指向b的根节点，这样下次查询a的时候就可以直接查找到b的根节点，即属于同一个集合
static void merge(int x,int y){
    f[find(x)]=find(y);
}

~~~
static int find(int x){//路径优化
    return p[x]==x?x:(p[x]=find(p[x]));
}

static void solve(){
    int n=in.nextInt(),q=in.nextInt();
    for(int i=1;i<=n;i++){
        a[i]=i;
        p[a[i]]=i;
    }
    for(int i=1;i<=q;i++){
        String op=in.next();
        int a=in.nextInt(),b=in.nextInt();
        if(op.equals("M")){
            p[find(b)]=find(a);
        }else{
            if(find(a)==find(b)){
                out.println("Yes");
            }else{
            out.printIn("No");
            }
        }
    }
}
~~~

~~~
import java.io.*;
import java.util.StringTokenizer;

public class Main {
    final static intN=100005;
f   inal static int M= 100005;
}
public static void main(String[] args){
    int n = in.nextInt();
    int m in.nextInt();
    out.flush();
}




//高效读取输入
static FastReader in= new FastReader();
static PrintWriter out = new PrintWriter(System.out); 
static class FastReader{ 
    static BufferedReader br;
    static StringTokenizer st; 
    FastReader(){
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    String next(){ 
        String str ="";
        while(st=null l !st.hasMoreElements()){
            try {
                str = br.readLine();
            }catch(IOException e){
                throw new RuntimeException(e);
            }
                st = new StringTokenizer(str);
        }
        return st.nextToken();
    }
    int nextInt(){return Integer.parseInt(next());}
    double nextDouble(){ return Double.parseDouble(next());}
    long nextLong(){return Long.parseLong(next());}
}
~~~
### 12.  树状数组
原理
规定一个数组ci，包含其向前长度的lowbit(i)的aj[i-lowbit(i)+1,i]

题目描述:
一行 N 个方格，开始每个格子里都有一个整数。
你需要动态地进行一些操作，操作有以下两种类型:
提问:求某一个特定的子区间[a,b]中所有元素的和;
修改:指定某一个格子 x，令加上或者减去一个特定的值 A。
现在要求你能对每个提问作出正确的回答。

输入描述
输入文件第一行为一个整数 N，接下来一行包含 几 个整数，表示格子中原来的整数。
接下一个正整数 m，再接下来有 m 行，表示 m 个询问。每个询问的第一个整数表示询问代号，询问代号1表示增加，后面的两个数x和A表示给位置 X 上的数值增加 A，询问代号 2 表示区间求和，后面两个整数表示a和b，表示要求a,b之间的区间和。

输出描述
共 m 行，每行一个整数，表示每个提问的答案。
~~~

public class Main {
/*lowbit 函数的主要功能是返回一个整数 x 的二进制表示中最低位的 1 所对应的值。
例如，对于十进制数 6，它的二进制表示是 110，最低位的 1 对应的是二进制的 10，也就是十进制的 2，所以 lowbit(6) 的返回值就是 2。*/
    static int lowbit(int x){
        return x & (-x);
    }

    static void add(int x,int y){
        for (;x <= n;x+=lowbit(x)) {
            c[x] += y;
        }
    }

    static int sum(int x){
        int res = 0;
        for (;x > 0;x-=lowbit(x)) {
            res += c[x];
        }
        return res;
    }
    public static void main(String[] args) {
        int n = in.nextInt();
        int[] c = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            add(i,x);
        }
        int m = in.nextInt();

        for (int i = 1; i <= m; i++) {
            int op = in.nextInt();
            if (op == 1) {
                int x = in.nextInt(), A = in.nextInt();
                add(x,A);
            }
            else{
                int a= in.nextInt(), b = in.nextInt();
                out.println(sum(b) - sum(a - 1));
            }
            
        }
        out.flush();
    }
}
~~~

## 四.搜索基础
### dfs
1. 回溯法
实现斐波那契数列
int func(int i)
{
    if(i==1||i==2)return 1;
    return func(i-1)+func(i-2);//注意这里先计算func(i-1)再计算func(i-2)
}
2. dfs实现指数型枚举
从1~n中任选若干个整数（可以选0个数），输出所有可能的方案
示例：
输入：3
输出：
3 
2 
2 3
1 
3
1 3
1 2
1 2 3 
~~~
//思路：将每个整数i看作是一个节点，对于每个节点，有两种选择：选或者不选；通过递归地对每个节点进行这两种选择，可以遍历出所有可能的组合
//用st[i]这个布尔型数组，标记整数i是否位选中
static void dfs(int u)
{
    if(u>n){//表示处理完1~n所有元素，此时得到了一种选择方案
        for(int i=1;i<=n;i++)//遍历st[i]将所有被选中的整数输出
        {
            if(st[i])System.out.print(i+" ");
        }
        System.out.println();
        return;
    }
    dfs(u+1);//不选当前节点，直接处理下一个整数u+1
    st[u]=true;//选当前节点
    dfs(u+1);//选择当前元素的情况下处理下一个整数u+1
    st[u]=false;//恢复到未选择u的状态，以便后续递归调用
}
~~~
### 二进制搜索
利用二进制对集合的自己进行标记，从而生成所有可能的组合
例如数字000，表示所有物品都不选，数字5是101，表示选第1和第3个物品，不选第2个

例题：蛋糕的美味值
问题描述
小蓝去蛋糕店买了n个蛋糕，每个蛋糕有一个美味值 taste[i]。
现在小蓝想吃其中若干个蛋糕，请问在选出的蛋糕的美味值小于k的情况下
小蓝能选出的蛋糕美味值总和最大可以为多少。
输入格式:
第一行输入包含 2 个正整数 n,k。
第二行输入包含 n个正整数，表示蛋糕的美味值序列。
输出格式:
输出一个整数，表示美味值总和最大值。
样例输入:
5 13
1 2 7 8 6
样例输出
11
说明
你可以选择 1,2,8
思路：
有5种情况，转化成5位2进制，即2^5-1,00000就表示一个都不选，00011表示选了1,2;1011表示选了第1，2，4个蛋糕...以此类推
~~~
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] taste = new int[n + 1];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            taste[i] = sc.nextInt();
        }
        for (int i = 0; i <=(1<<n)-1; i++) {//(1<<n)-1:2^n-1
            int sum = 0;
            for (int j = 0; j <n; j++) {
                if (((i >> j) & 1) == 1) {//检查 i 的第 j 位是否为 1
                    sum += taste[j + 1];
                }
            }
            if (sum < k) {
                ans = Math.max(ans, sum);
            }
        }
        System.out.println(ans);
    }

}
~~~
1. 为什么 (1 << n) 表示 2^n
在二进制中，左移运算符 << 是将一个数的二进制表示向左移动指定的位数。每向左移动一位，相当于将该数乘以 2。
2. 为什么判断第 j 位是否为 1。如果为 1，则表示选中第 j + 1 个蛋糕
   将一个 n 位的二进制数与 n 个蛋糕的选择情况一一对应。二进制数的第 0 位对应第 1 个蛋糕，第 1 位对应第 2 个蛋糕，以此类推，第 j 位对应第 j + 1 个蛋糕。
### bfs
探索一个节点的相邻节点，逐层进行
1. 走迷宫
题目描述
给定一个 N x M 的网格迷宫 G。G 的每个格子要么是道路，要么是障碍物
(道路用 1 表示，障碍物用0 表示)
已知迷宫的入口位置为(x1,y1)，出口位置为(x2,y2)。问从入口走到出口，最
少要走多少个格子。
输入描述
输入第 1行包含两个正整数 N,M，分别表示迷宫的大小。
接下来输入一个 N x M 的矩阵。若 Gi.j=1表示其为道路，否则表示其为障
碍物。
最后一行输入四个整数 x1,y1,x2,y2，表示入口的位置和出口的位置。
1 ≤ N, M ≤ 10°, 0 ≤ Gij≤ 1, 1 ≤ rí,™ ≤ N, 1 ≤ y,y ≤ M.
输出描述
输出仅一行，包含一个整数表示答案。
若无法从入口到出口，则输出 一1。
需要注意：
是否是0
是否走出范围外
是否访问状态
~~~
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[][] map = new int[n+2][m+2];//1.为什么加2？
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                map[i][j] = scan.nextInt();
            }
        }
        int sx = scan.nextInt();
        int sy = scan.nextInt();
        int ex = scan.nextInt();
        int ey = scan.nextInt();

        //bfs
        boolean[][] v= new boolean[n+2][m+2];//用来标记是否访问过
        int d[][]=new int[n+2][m+2];//记录起点到每个格子的最短距离
        for(int i = 1; i <= n; i++){
            Arrays.fill(d[i],(int)1e9);//初始化不可达,2.Array.fill是什么意思
        }
        d[sc][sy]=0;//将起点的距离初始化为0
        Queue<int[]> q = new LinkedList<Integer>();//q：存储待扩展的节点
        q.add(new int[]{sc,sy});//将起点加入队列
        int []dx = {0,0,-1,1};
        int []dy = {1,-1,0,0};
        while(!q.isEmpty()){
            int[] o = q.poll();//3.将q的头节点取出，并在q中删除
            int x= o[0],y=o[1];//将取出的节点的坐标赋值给x和y
            if(v[x][y])continue;//如果当前节点已经被访问过，跳过该节点
            v[x][y]=true;//标记当前节点为已访问
            for(int i=0;i<4;i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(nx>n||nx<1||ny>m||ny<1||v[nx][ny]||map[nx][ny]==0)continue;//如果当前节点的坐标超出边界，为0以及被访问过跳过该节点
                d[nx][ny]=d[x][y]+1;//如果当前节点可以访问，则更新该节点的最短距离为当前节点的最短距离+1
                q.add(new int[]{nx,ny});//将当前节点加入队列q，等待后续扩展
            }

        }
        if(!v[ex][ey])System.out.println(-1);//如果终点节点未被访问，则输出-1
        else System.out.println(d[ex][ey]);//如果终点节点已被访问，则输出终点节点的最短距离
        scan.close();
    }
}

~~~
问题：
1.之所以加 2，是为了在迷宫周围创建一个 “围墙”，这样在判断是否越界时会更加方便，避免了复杂的边界条件判断。
2.Arrays.fill 是 Java 中的一个方法，用于将数组的所有元素填充为指定的值。这里将 d 数组的每一行初始化为 1e9（即 1000000000），表示初始时所有格子都是不可达的。
3.q.poll() 方法用于从队列的头部取出一个元素，并将其从队列中移除。这里取出的元素是一个长度为 2 的整数数组，存储了当前节点的坐标。

2. 最少操作数
题目描述
给定两个整数 n 和 た。
现你有以下操作可以执行:
。令n=n+1
。令n=n-1
。令n=nx2
问要使得 n =k，至少要执行多少次操作。
输入描述
输入进一行，包含两个整数 n,た。
1 ≤ n,k ≤ 10'5
输出描述
输出一个整数表示答案。
输入输出样例
示例 
输入
3 19
输出
5
~~~
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int maxn = 200805;
        int[] d = new int[maxn];
        boolean[] v = new boolean[maxn];
        Queue<Integer> q = new LinkedList<>();
        Arrays.fill(d, (int) 1e9); // 不可达
        d[n] = 0;
        q.add(n);
        v[n] = true;
        while (!q.isEmpty()) {
            int x = q.poll();
            int[] a = {1, -1, x};
            for (int i = 0; i < 3; i++) {
                int y;
                if (i == 2) {
                    y = x * a[i];
                } else {
                    y = x + a[i];
                }
                if (y < 1 || y >= maxn) continue;
                if (v[y]) continue;
                v[y] = true;
                d[y] = d[x] + 1;
                q.add(y);
            }
        }
        System.out.println(d[k]);
    }
}    

~~~
## 五.动态规划
### dfs与记忆化搜索
1. 重复搜索
2. 例题：采药
int dfs(int u,int s){
    if(u>n)retarn dp[u][s]=0;
    if(dp[u][s]!=-1) return dp[u][s];
    int ans1=0,ans2=0,ans=0;
    if(s+v[u]<=m)ans1=dfs(u+1,s+v[u])+w[u];
    ans2=dfs(u+1,s);
    ans=Math.max(ans1,ans2);
    return dp[u][s]=ans;
}

输入描述
第一行有两个整数T(1<T<1000)和M(1<M<100)，用一个空格隔开
T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。
接下来的 M 行每行包括两个在1到100之间(包括1和 100)的整数，分别表示采摘某
株草药的时间和这株草药的价值。
输出描述:
输出一个整数，表示在规定的时间内，可以采到的草药的最大总价值，
输入输出样例:
示例 1
76 3
71 100
69
输出：
3
~~~
package project1;
import java.util.*;

public class Main {
    static int m,n;//m表示时间，n表示草药
    static int a[]=new int[110];//每株草药的采集时间
    static int w[]=new int[110];//每株草药的价值
    static int dp[][]=new int[110][1010];//dp[i][j]表示第i个草药采集到第j秒时的最大价值

    static int dfs(int u,int s){
        if(u>n)return dp[u][s]=0;//超出时间限制
        if(dp[u][s]!=-1)return dp[u][s];//如果已经计算过，直接返回
        int ans1=0,ans2=0;//表示选和不选
        if(s+a[u]<=m)ans1=w[u]+dfs(u+1,s+a[u]);
        ans2=dfs(u+1,s);
        return dp[u][s]=Math.max(ans1,ans2);
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        m= scan.nextInt();//总共能够用来采药的时间
        n= scan.nextInt();//草药的数量
        for(int i = 0; i <110; i++)//初始化
        {
            for(int j=0;j<110;j++)
            {
                dp[i][j]=-1;
            }

        }
        for(int i = 1; i <=n; i++){
            a[i] = scan.nextInt();//草药的时间
            w[i] = scan.nextInt();//草药的价值
        }
        System.out.println(dfs(1,0));//从第1珠草药开始：1表示第一个草药，0表示第一个草药的时间

    }
}

~~~

### 动态规划概念
做题来总结经验，下面是动态规划的各种模型
### 组合数的原理（选与不选）
输入两个非负整数n,m,求解组合数C(n,m)
第一行输入t,表示数据总数
t行输入n,m
输出t行C(n,m)
~~~
package project1;
import java.util.*;

public class Main {
    static int f(int n,int m)
    {
        if(n==m||m==0)return 1;
        return f(n-1,m-1)+f(n-1,m);//选+不选
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0)
        {
            int n = sc.nextInt();
            int m = sc.nextInt();
            System.out.println(f(n,m));
        }
    }
}

~~~
### 线性dp
### 01背包
### 完全背包
### 多重背包
### 计数问题
### 区间dp
### 数位dp
### 树形dp
### 前缀与优化dp