蓝桥杯每日一题(更新中)

前缀和

截断数组

给定一个长度为n的数组。

现在，要将该数组从中间截断，得到三个非空子数组

要求，三个子数组内各元素之和都相等。

请问，共有多少种不同的截断方法？

思路：

1. 三个子数组和相等，说明数组的所有数的和一定是3的倍数
2. 找到数组中的$\frac{1}{3}$与$\frac{2}{3}$

做法：首先求数组的前缀和，然后统计出每一个位置及其前面有多少个$\frac{1}{3}$的倍数，也就是第一段。然后从$2$~$(n-1)$枚举第二段$\frac{2}{3}$，对于每个第二段，都可以和前面的所有的第一段构成截断

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class 截断数组 {
    public static void main(String[] args) {
        solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt();
        int a[]=new int[n+1];
        int b[]=new int[n+1];
        int c[]=new int[n+1];
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
            b[i]=a[i]+b[i-1];
        }
        if(b[n]%3!=0||n<3){
            out.println(0);
            return;
        }
        for(int i=1;i<=n;i++){
            if(b[i]==b[n]/3){
                c[i]++;
            }
            c[i]=c[i-1]+c[i];
        }
        long cnt=0;
        for(int i=2;i<=n-1;i++){
            if(b[i]==b[n]/3*2){
                cnt=cnt+c[i-1];
            }
        }
        out.println(cnt);
    }
    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||!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());
        }
    }
}

二维前缀和

输入一个 $n$ 行 $m$ 列的整数矩阵，再输入 $q$ 个询问，每个询问包含四个整数 $x_1, y_1, x_2, y_2$，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

思路：

这题我们有一个动态规划的思想，$f[i][j]$表示为该位置左上角的前缀和，可以通过递推式$f[i][j]=a[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1]$求出

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class 子矩阵的和 {
    public static void main(String[] args) {
        solve();
        out.flush();
    }
    static void solve(){
        int a[][]=new int[1050][1050];
        int b[][]=new int[1050][1050];
        int 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();
                b[i][j]=a[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
            }
        }
        for(int i=1;i<=q;i++){
            int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();
            int res=b[x2][y2]-b[x2][y1-1]-b[x1-1][y2]+b[x1-1][y1-1];
            out.println(res);
        }
    }

    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||!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());
        }
    }
}

k倍区间

给定一个长度为 $N$ 的数列，$A_1, A_2, ... A_N$，如果其中一段连续的子序列 $A_i, A_{i+1},... A_j$ 之和是 $K$ 的倍数，我们就称这个区间 $[i, j]$ 是 $K$ 倍区间。

你能求出数列中总共有多少个 $K$ 倍区间吗？

$1 \le N, K \le 100000$

$1 \le A_i \le 100000$

思路：

1. 快速求出某一段子序列的和可以使用前缀和相减
2. (a-b)%k==0 推出 a%k-b%k == 0
3. 求出相同的模k数量，然后用$\frac{n*(n-1)}{2}$算出来这部分能构成多少
4. 最后注意原本是k的倍数的前缀和，不需要和别的前缀和进行匹配

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class k倍区间 {
    public static void main(String[] args) {
        solve();
        out.flush();
    }
    static void solve(){
        int a[]=new int[(int) (1e5+10)];
        long b[]=new long[(int)(1e5+10)];
        int vis[]=new int[(int)(1e5+10)];
        int n=in.nextInt(),k=in.nextInt();
        for(int i=1;i<=n;i++) {
            a[i]=in.nextInt();
            b[i]=b[i-1]+a[i];
            vis[(int) (b[i]%k)]++;
        }
        long sum=vis[0];
        for(int i=0;i<n;i++){
            sum=sum+1L*vis[i]*(vis[i]-1)/2;
        }
        out.println(sum);

    }

    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||!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());
        }
    }
}

激光炸弹

地图上有 $N$ 个目标，用整数 $X_{i}, Y_{i}$ 表示目标在地图上的位置，每个目标都有一个价值 $W_i$，不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 $R \times R$ 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 $x，y$ 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

前缀和的应用题：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class 激光炸弹 {
    public static void main(String[] args) {
        solve();
        out.flush();
    }

    static void solve(){
        int a[][]=new int[5050][5050];
        int n=in.nextInt(),r=in.nextInt();
        for(int i=0;i<n;i++){
            int x=in.nextInt()+1,y=in.nextInt()+1,w=in.nextInt();
            a[x][y]+=w;
        }
        for(int i=1;i<=5001;i++){
            for(int j=1;j<=5001;j++){
                a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            }
        }
        if(r>=5001){
            out.println(a[5001][5001]);
            return;
        }
        int sum=0;
        for(int i=1;i+r-1<=5001;i++){
            for(int j=1;j+r-1<=5001;j++){
                int x1=i,y1=j,x2=i+r-1,y2=j+r-1;
                sum=Math.max(sum,a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]);
            }
        }
        out.println(sum);
    }

    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||!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());
        }
    }
}

差分

改变数组元素

给定一个空数组 $V$ 和一个整数数组 $a_1,a_2,...a_n$。
现在要对数组 $V$ 进行 $n$ 次操作。
第 $i$ 次操作的具体流程如下：

1. 从数组 $V$ 尾部插入整数 $0$。
2. 将位于数组 $V$ 末尾的 $a_i$ 个元素都变为 $1$（已经是 $1$ 的不予理会）。

注意：

1. $a_i$ 可能为 $0$，即不做任何改变。
2. $a_i$ 可能大于目前数组 $V$ 所包含的元素个数，此时视为将数组内所有元素变为 $1$。

请你输出所有操作完成后的数组 $V$。

第一行包含整数 $T$，表示共有 $T$ 组测试数据。
每组数据第一行包含整数 $n$。
第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$。

每组数据输出一行结果，表示所有操作完成后的数组 $V$，数组内元素之间用空格隔开。
数据范围
$1 \le T \le 20000$,
$1 \le n \le 2 \times 10^5$,
$0 \le a_i \le n$,
保证一个测试点内所有 $n$ 的和不超过 $2 \times 10^5$。

合并区间写法：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.List;

public class 改变数组元素 {
    public static void main(String[] args) {
        int n=in.nextInt();
        while(n-->0) solve();
        out.flush();
    }
    static List<int[]> points1=new ArrayList<>(),points2=new ArrayList<>();
    static int ans[];
    static void solve(){
        points1=new ArrayList<>();
        points2=new ArrayList<>();
        int n=in.nextInt();
        ans=new int[n+10];
        for(int i=1;i<=n;i++){
            int x=in.nextInt();
            if(x!=0){
                int r=i;
                int l=i-x+1;
                if(l<1) l=1;
                points1.add(new int[]{l,r});
            }
        }
        Collections.sort(points1,(x,y)->x[1]-y[1]);
        int templ=0,tempr=0;
        for(int i=0;i<points1.size();i++){
            int l=points1.get(i)[0];
            int r=points1.get(i)[1];
            if(templ==0&&tempr==0){
                templ=l;tempr=r;
                if(i==points1.size()-1){
                    points2.add(new int[]{templ,tempr});
                }
                continue;
            }
            if(tempr>=l){
               if(templ>=l) templ=l;
               if(tempr<=r) tempr=r;
            }
            else{
                points2.add(new int[]{templ,tempr});
                templ=l;
                tempr=r;
            }
            if(i==points1.size()-1){
                points2.add(new int[]{templ,tempr});
            }
        }
        for(int i=0;i<points2.size();i++){
            int l=points2.get(i)[0],r=points2.get(i)[1];
            for(int j=l;j<=r;j++){
                ans[j]=1;
            }
        }
        for(int j=1;j<=n;j++){
            out.print(ans[j]+" ");
        }
        out.println();
    }

    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||!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());
        }
    }
}

从后往前推写法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.List;

public class 改变数组元素 {
    public static void main(String[] args) {
        int n=in.nextInt();
        while(n-->0) solve();
        out.flush();
    }
    static int a[],b[];
    static void solve(){
        int n=in.nextInt();
        a=new int[n+10];
        b=new int[n+10];
        for(int i=1;i<=n;i++) a[i]=in.nextInt();
        int k=-1;
        for(int i=n;i>=1;i--){
            if(k==-1){
                k=a[i];
            }
            k=Math.max(k-1,a[i]-1);
            if(k>=0) b[i]=1;
        }
        for(int i=1;i<=n;i++) out.print(b[i]+" ");
        out.println();
    }

    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||!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());
        }
    }
}

差分

输入一个长度为 $n$ 的整数序列。
接下来输入 $m$ 个操作，每个操作包含三个整数 $l, r, c$，表示将序列中 $[l, r]$ 之间的每个数加上 $c$。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 $n$ 和 $m$。
第二行包含 $n$ 个整数，表示整数序列。
接下来 $m$ 行，每行包含三个整数 $l，r，c$，表示一个操作。
输出格式
共一行，包含 $n$ 个整数，表示最终序列。
数据范围
$1 \le n,m \le 100000$,
$1 \le l \le r \le n$,
$-1000 \le c \le 1000$,
$-1000 \le 整数序列中元素的值 \le 1000$

import java.io.*;

import java.util.StringTokenizer;

public class 差分 {
    public static void main(String[] args) {
//        int n=in.nextInt();
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt(),m=in.nextInt();
        int a[]=new int[n+10];
        int b[]=new int[n+10];
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
            b[i]=a[i]-a[i-1];
        }
        while(m-->0){
            int l=in.nextInt(),r=in.nextInt(),c=in.nextInt();
            b[l]+=c;
            b[r+1]-=c;
        }
        for(int i=1;i<=n;i++) b[i]+=b[i-1];
        for(int i=1;i<=n;i++) out.print(b[i]+" ");
    }

    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||!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());
        }
    }
}

对差分数组求前缀和是原数组

因为差分数组的每一项是当前项与前一项的差值，第一项是原值，那么就可以通过前一项的原值+差值=我现在这一项

差分和前缀和是逆运算

二维差分

差分，和前缀和是一对逆运算定义

我们可以把原数组当成前缀和数组，这样就可以求出差分数组

$a[i][j]=f[i][j]-f[i-1][j]-f[i][j-1]+f[i-1][j-1]$

差分矩阵的每次操作都是对右下角所有的位置做一次操作

import java.io.*;

import java.util.StringTokenizer;

public class 二维差分 {
    public static void main(String[] args) {
//        int n=in.nextInt();
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt(),m=in.nextInt(),q=in.nextInt();
        int a[][]=new int[n+10][m+10];
        int b[][]=new int[n+10][m+10];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                a[i][j]=in.nextInt();
            }
        }
        //a[i][j]=b[i][j]-a[i-1][j-1]+a[i-1][j]+a[i][j-1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                b[i][j]=a[i][j]+a[i-1][j-1]-a[i-1][j]-a[i][j-1];
            }
        }
        for(int i=1;i<=q;i++){
            int x1= in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();
            int c=in.nextInt();
            b[x1][y1]+=c;
            b[x2+1][y1]-=c;
            b[x1][y2+1]-=c;
            b[x2+1][y2+1]+=c;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                out.print(a[i][j]+" ");
            }
            out.println();
        }
    }

    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||!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());
        }
    }
}

增减序列

​ 给定一个长度为 $n$ 的数列 ${a_1,a_2,…,a_n}$，每次可以选择一个区间 $[l,r]$，使下标在这个区间内的数都加一或者都减一。
​ 求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
输入格式
第一行输入正整数 $n$。
接下来 $n$ 行，每行输入一个整数，第 $i+1$ 行的整数代表 $a_i$。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
$0 < n \le 10^5$,
$0 \le a_i <2147483648$

思路：

1. 选择连续区间的数增加或减少可以使用差分数组
2. 差分数组，除了第一位以外，剩下每一位是0，数组元素便全部相等
3. 我们可以对差分数组进行以下操作
   1. 对一个数+1
   2. 对一个数-1
   3. 让前面一个数+1，后面一个数-1
   4. 让前面一个数-1，后面一个数+1
4. 最少操作是除了首位正负最大值，不同值是数量是abs(大)-abs(小)

import java.io.*;

import java.util.StringTokenizer;

public class 增减序列 {
    public static void main(String[] args) {
//        int n=in.nextInt();
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt();
        int a[]=new int[n+1],b[]=new int[n+1];
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
            b[i]=a[i]-a[i-1];
        }
        long f=0,z=0;
        for(int i=2;i<=n;i++){
            if(b[i]<=0) f-=b[i];
            else z+=b[i];
        }
        long ans1=Math.max(f,z);
        long ans2=ans1-Math.min(f,z)+1;
        out.println(ans1);
        out.println(ans2);
    }

    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||!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());
        }
    }
}

二分

二分四模板

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class 二分四模板 {
    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;
        return l;
    }

    static int getR(int a[], int l, int r, int x) {
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (x < a[mid]) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        if (a[l] != x) return -1;
        return l;
    }

    static int lower_bound(int a[], int l, int r, int x) {
        if (x > a[r]) return r + 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (x <= a[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    static int upper_bound(int a[], int l, int r, int x) {
        if (x >= a[r]) return r + 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (x < a[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

1. getL() 是有序序列中 $=x$ 的最左边的数的位置，若 $x$ 不存在则输出-1。
2. getR() 是有序序列中 $=x$ 的最右边的数的位置，若 $x$ 不存在则输出-1。
3. lower_bound() 是有序序列中 $\ge x$ 的第一个数的位置，如果 $x>$ 序列最后一个数，则返回 $n$。
4. upper_bound() 是有序序列中 $>x$ 的第一个数的位置，如果 $x\ge$ 序列最后一个数，则返回 $n$。

我在哪

农夫约翰出门沿着马路散步，但是他现在发现自己可能迷路了！
沿路有一排共 $N$ 个农场。
不幸的是农场并没有编号，这使得约翰难以分辨他在这条路上所处的位置。
然而，每个农场都沿路设有一个彩色的邮箱，所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用 $A..Z$ 之间的一个字母来指定，所以沿着道路的 $N$ 个邮箱的序列可以用一个长为 $N$ 的由字母 $A..Z$ 组成的字符串来表示。
某些邮箱可能会有相同的颜色。
约翰想要知道最小的 $K$ 的值，使得他查看任意连续 $K$ 个邮箱序列，他都可以唯一确定这一序列在道路上的位置。
例如，假设沿路的邮箱序列为 ABCDABC 。
约翰不能令 $K=3$，因为如果他看到了 ABC，则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 $K$ 的值为 $K=4$，因为如果他查看任意连续 $4$ 个邮箱，那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
输入格式
输入的第一行包含 $N$，第二行包含一个由 $N$ 个字符组成的字符串，每个字符均在 $A..Z$ 之内。
输出格式
输出一行，包含一个整数，为可以解决农夫约翰的问题的最小 $K$ 值。
数据范围
$1 \le N \le 100$
输入样例：
7
ABCDABC
输出样例：
4

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class 我在哪 {

    public static void main(String[] args) {
        solve();
        out.flush();
    }
    static boolean check(int k,String s){

        for(int i=0;i+k<=s.length();i++){
            String p=s.substring(i,i+k);
            for(int j=i+1;j+k<=s.length();j++){
                if(p.equals(s.substring(j,j+k))){
                    return false;
                }
            }
        }
        return true;
    }
    static void solve(){
        int n=in.nextInt();
        String line=in.next();
        int l=1,r=n;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid,line)){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        out.println(l);
    }
    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||!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());
        }
    }
}

四平方和

四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 $4$ 个正整数的平方和。
如果把 $0$ 包括进去，就正好可以表示为 $4$ 个数的平方和。
比如：
$5 = 0^2 + 0^2 + 1^2 + 2^2$
$7 = 1^2 + 1^2 + 1^2 + 2^2$
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 $4$ 个数排序：
$0 \le a \le b \le c \le d$
并对所有的可能表示法按 $a,b,c,d$ 为联合主键升序排列，最后输出第一个表示法。
输入格式
输入一个正整数 $N$。
输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围
$0 < N < 5 * 10^6$
输入样例：
5

输出样例：
0 0 1 2

思路：

1. 枚举$i^2+j^2$的和存入表中。
2. 再次枚举$i^2+j^2$，然后利用二分或者Map查找表中最小符合该条件的值。

二分写法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class 四平方和 {

    public static void main(String[] args) {
        solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt();
        List<int[]> list=new ArrayList<>();
        for(int i=0;i*i<=n;i++){
            for(int j=i;i*i+j*j<=n;j++){
                list.add(new int[]{i,j,i*i+j*j});
            }
        }
        Collections.sort(list,(x,y)->{
            if(x[2]!=y[2]){
                return Integer.compare(x[2],y[2]);
            }else if(x[0]!=y[0]){
                return Integer.compare(x[0],y[0]);
            }
            return Integer.compare(x[1],y[1]);
        });
        int ans[]=new int[4];
        for(int i=0;i*i<=n;i++){
            for(int j=i;i*i+j*j<=n;j++){
                int x=n-i*i-j*j;
                int l=0,r=list.size()-1;
                while (l<r){
                    int mid=l+r>>1;
                    if(x<=list.get(mid)[2]) r=mid;
                    else l=mid+1;
                }
                if(list.get(l)[2]==x){
                    ans[0]=i;
                    ans[1]=j;
                    ans[2]=list.get(l)[0];
                    ans[3]=list.get(l)[1];
                    Arrays.sort(ans);
                    for(int v:ans) out.print(v+" ");
                    return;
                }
            }
        }
    }
    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||!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());
        }
    }
}

hash写法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class 四平方和哈希写法 {
    public static void main(String[] args) {
        solve();
        out.flush();
    }
    static int h[]=new int[(int) (5e6+10)];
    static void solve(){
        int n=in.nextInt();
        Arrays.fill(h,-1);
        for(int i=0;i*i<=n;i++){
            for(int j=i;i*i+j*j<=n;j++){
                int k=i*i+j*j;
                if(h[k]==-1){
                    h[k]=i;
                }
            }
        }
        List<Integer> list=new ArrayList<>(4);
        for(int i=0;i*i<=n;i++){
            for(int j=0;i*i+j*j<=n;j++){
                int x=n-(i*i+j*j);
                if(h[x]!=-1){
                    list.add(i);
                    list.add(j);
                    int i1=h[x];
                    int j1=(int)(Math.sqrt(x-h[x]*h[x]));
                    list.add(i1);
                    list.add(j1);
                    Collections.sort(list);
                    for(int v:list) out.print(v+" ");
                    return;
                }
            }
        }
    }
    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||!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());
        }
    }
}

分巧克力

儿童节那天有 $K$ 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 $N$ 块巧克力，其中第 $i$ 块是 $H_i \times W_i$ 的方格组成的长方形。
为了公平起见，小明需要从这 $N$ 块巧克力中切出 $K$ 块巧克力分给小朋友们。
切出的巧克力需要满足：

形状是正方形，边长是整数
大小相同

例如一块 $6 \times 5$ 的巧克力可以切出 $6$ 块 $2 \times 2$ 的巧克力或者 $2$ 块 $3 \times 3$ 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数 $N$ 和 $K$。
以下 $N$ 行每行包含两个整数 $H_i$ 和 $W_i$。
输入保证每位小朋友至少能获得一块 $1 \times 1$ 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
$1 \le N,K \le 10^5$,
$1 \le H_i,W_i \le 10^5$
输入样例：
2 10
6 5
5 6

输出样例：
2

思路：

1. 很明显的思路，二分答案，二分巧克力的边长
2. 然后考虑一块大巧克力能分多少长度为$x$的小巧克力

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class 分巧克力 {
      public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static int w[]=new int[(int)(1e5+10)];
    static int h[]=new int[(int) (1e5+10)];
    static int n,k;
    static void solve(){
        n=in.nextInt();k=in.nextInt();
        for(int i=0;i<n;i++){
            h[i]=in.nextInt();w[i]=in.nextInt();
        }
        int l=1,r=(int) (1e5+10);
        while(l<r){
            int mid=l+r+1>>1;
            if(check(mid)){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        out.println(l);
    }
    static boolean check(int x){
        int res=0;
        for(int i=0;i<n;i++){
            int l1=w[i],l2=h[i];
            res=res+(l1/x)*(l2/x);
        }
        return res>=k;
    }
    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||!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());
        }
    }
}

特殊排序

有 $N$ 个元素，编号 $1,2..N$，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。
注意：不存在两个元素大小相等的情况。
也就是说，元素的大小关系是 $N$ 个点与 $\frac{N \times (N-1)}{2}$ 条有向边构成的任意有向图。
然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过 $10000$ 次提问来获取信息，每次提问只能了解某两个元素之间的关系。
现在请你把这 $N$ 个元素排成一行，使得每个元素都小于右边与它相邻的元素。
你可以通过我们预设的 bool 函数 compare 来获得两个元素之间的大小关系。
例如，编号为 $a$ 和 $b$ 的两个元素，如果元素 $a$ 小于元素 $b$，则 compare(a,b) 返回 true，否则返回 false。
将 $N$ 个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。
数据范围
$1 \le N \le 1000$
输入样例
[[0, 1, 0], [0, 0, 0], [1, 1, 0]]

输出样例
[3, 1, 2]

思路：

1. 使用二分插入排序的思想来做
2. 数组中的元素保持有序，对于新插入的元素，二分找到其最合适的位置
3. 用upper_bound()找出$>i$的第一个位置，然后把i插入到这个位置

class Solution extends Relation {

    public int[] specialSort(int N) {
        int a[] = new int[N];
        int len_a = 0;
        a[len_a++] = 1;
        for (int i = 2; i <= N; i++) {
            int l = 0, r = len_a - 1;
            int k=upper_bound(a,i,len_a);
            a[len_a++]=i;
            for(int j=len_a-1;j>k;j--){
                int t=a[j];
                a[j]=a[j-1];
                a[j-1]=t;
            }
        }
        return a;
    }

    int upper_bound(int a[], int i, int len) {
        int l = 0, r = len - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (compare(i, a[mid])) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if(l==len-1&&compare(a[l],i)) return len;
        return l;
    }  
    
}

双指针

字符串删减

给定一个由 $n$ 个小写字母构成的字符串。
现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的 x。
请问，最少需要删掉多少个字母？
如果字符串本来就不存在连续的三个或三个以上 x，则无需删掉任何字母。
输入格式
第一行包含整数 $n$。
第二行包含一个长度为 $n$ 的由小写字母构成的字符串。
输出格式
输出最少需要删掉的字母个数。
数据范围
$3 \le n \le 100$
输入样例1：
6
xxxiii

输出样例1：
1

输入样例2：
5
xxoxx

输出样例2：
0

输入样例3：
10
xxxxxxxxxx

输出样例3：
8

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
      public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt();
        String s=in.next();
        int cnt=0;
        List<Character> list=new ArrayList<>();
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(c=='x'){
                cnt++;
            }else{
                cnt=0;
            }
            if(cnt<3) list.add(c);
        }
        out.println(n-list.size());
    }

    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||!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());
        }
    }
}

最长连续不重复子序列

给定一个长度为 $n$ 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 $n$。
第二行包含 $n$ 个整数（均在 $0 \sim 10^5$ 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
$1 \le n \le 10^5$
输入样例：
5
1 2 2 3 5

输出样例：
3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
      public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt();
        int a[]=new int[n+1];
        int h[]=new int[(int) (1e5+10)];
        int l=1,r=1;
        int ans=1;
        for(int i=1;i<=n;i++,r++){
            a[i]=in.nextInt();
            h[a[i]]++;
            while(h[a[i]]>1){
                h[a[l]]--;
                l++;
            }
            ans=Math.max(r-l+1,ans);
        }
        out.println(ans);
    }

    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||!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());
        }
    }
}

数组元素目标和

给定两个升序排序的有序数组 $A$ 和 $B$，以及一个目标值 $x$。
数组下标从 $0$ 开始。
请你求出满足 $A[i] + B[j] = x$ 的数对 $(i, j)$。
数据保证有唯一解。
输入格式
第一行包含三个整数 $n,m,x$，分别表示 $A$ 的长度，$B$ 的长度以及目标值 $x$。
第二行包含 $n$ 个整数，表示数组 $A$。
第三行包含 $m$ 个整数，表示数组 $B$。
输出格式
共一行，包含两个整数 $i$ 和 $j$。
数据范围
数组长度不超过 $10^5$。
同一数组内元素各不相同。
$1 \le 数组元素 \le 10^9$
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9

输出样例：
1 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt(),m=in.nextInt(),x=in.nextInt();
        int a[]=new int[n];
        int b[]=new int[m];
        for(int i=0;i<n;i++) a[i]=in.nextInt();
        for(int j=0;j<m;j++) b[j]=in.nextInt();
        int i=0,j=m-1;
        while(a[i]+b[j]!=x){
            if(a[i]+b[j]>x) j--;
            else if(a[i]+b[j]<x)i++;
        }
        out.print(i+" "+j);
    }

    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||!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());
        }
    }
}

判断子序列

给定一个长度为 $n$ 的整数序列 $a_1,a_2,…,a_n$ 以及一个长度为 $m$ 的整数序列 $b_1,b_2,…,b_m$。
请你判断 $a$ 序列是否为 $b$ 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 $\{a_1,a_3,a_5\}$ 是序列 $\{a_1,a_2,a_3,a_4,a_5\}$ 的一个子序列。
输入格式
第一行包含两个整数 $n,m$。
第二行包含 $n$ 个整数，表示 $a_1,a_2,…,a_n$。
第三行包含 $m$ 个整数，表示 $b_1,b_2,…,b_m$。
输出格式
如果 $a$ 序列是 $b$ 序列的子序列，输出一行 Yes。
否则，输出 No。
数据范围
$1 \le n \le m \le 10^5$,
$-10^9 \le a_i,b_i \le 10^9$
输入样例：
3 5
1 3 5
1 2 3 4 5

输出样例：
Yes

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt(),m=in.nextInt();
        int a[]=new int[n];
        int b[]=new int[m];
        for(int i=0;i<n;i++) a[i]=in.nextInt();
        for(int j=0;j<m;j++) b[j]=in.nextInt();
        int i=0;
        for(int j=0;j<m&&i<n;j++){
            if(b[j]==a[i]) i++;
        }
        if(i==n) out.print("Yes");
        else out.print("No");
    }

    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||!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());
        }
    }
}

日志统计

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 $N$ 行。
其中每一行的格式是：
$ts $ $id$

表示在 $ts$ 时刻编号 $id$ 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 $D$ 的时间段内收到不少于 $K$ 个赞，小明就认为这个帖子曾是”热帖”。
具体来说，如果存在某个时刻 $T$ 满足该帖在 $[T, T+D)$ 这段时间内(注意是左闭右开区间)收到不少于 $K$ 个赞，该帖就曾是”热帖”。
给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 $N,D,K$。
以下 $N$ 行每行一条日志，包含两个整数 $ts$ 和 $id$。
输出格式
按从小到大的顺序输出热帖 $id$。
每个 $id$ 占一行。
数据范围
$1 \le K \le N \le 10^5$,
$0 \le ts,id \le 10^5$,
$1 \le D \le 10000$
输入样例：
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出样例：
1
3

思路：

1. 枚举时刻，开一个链式数组去存每一时刻的点赞
2. 用hash表统符合的点赞数
3. 用TreeSet输出答案
4. l维护d分钟前的点赞，i维护当前

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt(),d=in.nextInt(),k=in.nextInt();
        List<Integer>[]lists=new ArrayList[(int) (1e5+10)];
        for(int i=0;i<n;i++){
            int ts=in.nextInt(),id=in.nextInt();
            if(lists[ts]==null) lists[ts]=new ArrayList<>();
            lists[ts].add(id);
        }
        Set<Integer> set=new TreeSet<>();
        int h[]=new int[(int) (1e5+10)];
        int l=0;
        for(int i=0;i<d;i++){
            if(lists[i]!=null){
                for(int v:lists[i]){
                    h[v]++;
                    if(h[v]>=k)set.add(v);
                }
            }
        }
        for(int i=d;i<=1e5;i++,l++){
            if(lists[l]!=null){
                for(int v:lists[l]){
                    h[v]--;
                }
            }
            if(lists[i]!=null){
                for(int v:lists[i]){
                    h[v]++;
                    if(h[v]>=k)set.add(v);
                }
            }
        }
        for(int v:set) out.println(v);
    }

    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||!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());
        }
    }
}

完全二叉树权值

给定一棵包含 $N$ 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 $A_1, A_2, · · · A_N$，如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？
如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 $1$。
输入格式
第一行包含一个整数 $N$。
第二行包含 $N$ 个整数 $A_1, A_2, · · · A_N$。
输出格式
输出一个整数代表答案。
数据范围
$1 \le N \le 10^5$,
$-10^5 \le A_i \le 10^5$
输入样例：
7
1 6 5 4 3 2 1

输出样例：
2

思路：

1. 求二叉树每一层的和中最大值，层序存储二叉树
2. 省空间可以直接数组模拟完全二叉树，左子结点为$i*2$,右子结点为$i*2+1$。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
     public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt();
        List<Integer>[]lists=new ArrayList[20];
        int cnt=0;
        boolean flag=true;
        for(int i=0;flag;i++){
            lists[i]=new ArrayList<>();
            for(int j=1;j<=1<<i;j++){
                lists[i].add(in.nextInt());
                cnt++;
                if(cnt==n){
                    flag=false;
                    break;
                }
            }
        }
        long maxi=1,maxAns=1<<63;
        for(int i=0;lists[i]!=null;i++){
            long sum=0;
            for(int j=0;j<lists[i].size();j++){
                sum=sum+lists[i].get(j);
            }
            if(sum>maxAns){
                maxAns=sum;
                maxi=i+1;
            }
        }
        out.print(maxi);
    }

    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||!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());
        }
    }
}

递推

砖块

$n$ 个砖块排成一排，从左到右编号依次为 $1 \sim n$。
每个砖块要么是黑色的，要么是白色的。
现在你可以进行以下操作若干次（可以是 $0$ 次）：
选择两个相邻的砖块，反转它们的颜色。（黑变白，白变黑）
你的目标是通过不超过 $3n$ 次操作，将所有砖块的颜色变得一致。
输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。
每组数据第一行包含一个整数 $n$。
第二行包含一个长度为 $n$ 的字符串 $s$。其中的每个字符都是 W 或 B，如果第 $i$ 个字符是 W，则表示第 $i$ 号砖块是白色的，如果第 $i$ 个字符是 B，则表示第 $i$ 个砖块是黑色的。
输出格式
每组数据，如果无解则输出一行 $-1$。
否则，首先输出一行 $k$，表示需要的操作次数。
如果 $k>0$，则还需再输出一行 $k$ 个整数，$p_1,p_2,…,p_k$。其中 $p_i$ 表示第 $i$ 次操作，选中的砖块为 $p_i$ 和 $p_i+1$ 号砖块。
如果方案不唯一，则输出任意合理方案即可。
数据范围
$1 \le T \le 10$，
$2 \le n \le 200$。
输入样例：
4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB

输出样例：
3
6 2 4
-1
0
2
2 1

思路：

1. 如果w的数量和b的数量都是奇数一定不成立
2. 只有偶数才能被翻完
3. 从前往后，把偶数的字符依次翻成另一个字符

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
     public static void main(String[] args) {
        int n=in.nextInt();
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt();
        int b=0,w=0;
        String s=in.next();
        char c[]=s.toCharArray();
        for(int i=0;i<n;i++){
            if(s.charAt(i)=='B') b++;
            else w++;
        }
        if(b%2==w%2&&b%2==1){
            out.println(-1);
            return;
        }
        if(b==0||w==0){
            out.println(0);
            return;
        }
        List<Integer> ans=new ArrayList<>();
        for(int i=0;i<n-1;i++){
            if(b%2==0){
                if(c[i]=='B'){
                    c[i]='W';
                    if(c[i+1]=='W') c[i+1]='B';
                    else c[i+1]='W';
                    ans.add(i+1);
                }
            }else if(w%2==0){
                if(c[i]=='W'){
                    c[i]='B';
                    if(c[i+1]=='W') c[i+1]='B';
                    else c[i+1]='W';
                    ans.add(i+1);
                }
            }
        }
        out.println(ans.size());
        for(int v:ans) out.print(v+" ");
        out.println();
    }

    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||!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());
        }
    }
}

翻硬币

小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：$**oo***oooo$
如果同时翻转左边的两个硬币，则变为：$oooo***oooo$
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。
输入样例1：

$**********$

$o****o****$

输出样例1：
5

输入样例2：
$*o**o***o***$
$*o***o**o***$

输出样例2：

1

思路：1.如果一定有解,按照顺序翻一定能翻完

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
     public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        char a[]=in.next().toCharArray();
        char b[]=in.next().toCharArray();
        int ans=0;
        for(int i=0;i<a.length-1;i++){
            if(a[i]!=b[i]){
                if(a[i]=='*'){
                    a[i]='o';
                }else{
                    a[i]='*';
                }
                if(a[i+1]=='*'){
                    a[i+1]='o';
                }else{
                    a[i+1]='*';
                }
                ans++;
            }
        }
        out.println(ans);
    }

    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||!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());
        }
    }
}

递归

树的遍历

一个二叉树，树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。
输入格式
第一行包含整数 $N$，表示二叉树的节点数。
第二行包含 $N$ 个整数，表示二叉树的后序遍历。
第三行包含 $N$ 个整数，表示二叉树的中序遍历。
输出格式
输出一行 $N$ 个整数，表示二叉树的层序遍历。
数据范围
$1 \le N \le 30$,
官方并未给出各节点权值的取值范围，为方便起见，在本网站范围取为 $1 \sim N$。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

思路:

1. 后续遍历的最后一个数是根结点
2. 通过根结点去中序遍历里面求出该节点的左子树有多少个结点，右子树有多少个结点
3. 通过以上求出的结点，再去后序遍历中，分别递归后序的左右子树

输出样例：
4 1 6 3 5 7 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
     public static void main(String[] args) {
        int zu=1;
        while(zu-->0) solve();
        out.flush();
    }
    static int nxt[]=new int[31];
    static int mid[]=new int[31];
    static List<Integer> tree[]=new ArrayList[31];
    static int n;
    static void solve(){
        n=in.nextInt();
        for(int i=0;i<n;i++) nxt[i]=in.nextInt();
        for(int i=0;i<n;i++) mid[i]=in.nextInt();
        dfs(0,0,n-1,0,n-1);
        for(int i=0;tree[i]!=null;i++){
            for(int j=0;j<tree[i].size();j++)
            out.print(tree[i].get(j)+" ");
        }
    }
    static void dfs(int c,int l_n,int r_n,int l_m,int r_m){//存后序遍历的左右端点 子树中序遍历的左右端点
        if(l_n>r_n||l_m>r_m) return;
        int root=nxt[r_n];
        if(tree[c]==null) tree[c]=new ArrayList<>();
        tree[c].add(root);
        int k=find(root,mid);//找到中序遍历根结点位置
        int left_cnt=k-l_m;//根左边子树的结点数
        int right_cnt=r_m-k;//根右边子树节点数
        dfs(c+1,r_n-left_cnt-right_cnt,r_n-right_cnt-1,l_m,k-1);//存后序遍历的左右端点 子树中序遍历的左右端点
        dfs(c+1,r_n-right_cnt,r_n-1,k+1,r_m);//存后序遍历的左右端点 子树中序遍历的左右端点
    }
    static int find(int x,int a[]){
        int i=0;
        for(i=0;i<n;i++){
            if(a[i]==x) break;
        }
        return i;
    }
    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||!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());
        }
    }
}

数据结构

并查集

合并集合

一共有 $n$ 个数，编号是 $1 \sim n$，最开始每个数各自在一个集合中。
现在要进行 $m$ 个操作，操作共有两种：

M a b，将编号为 $a$ 和 $b$ 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 $a$ 和 $b$ 的两个数是否在同一个集合中；

输入格式
第一行输入整数 $n$ 和 $m$。
接下来 $m$ 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 $a$ 和 $b$ 在同一集合内，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
$1 \le n,m \le 10^5$
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：
Yes
No
Yes

思路:DSU的最基本板子，合并集合

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static int p[]=new int[(int) (1e5+10)];
    static int a[]=new int[(int)(1e5+10)];
    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]]=a[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.println("No");
                }
            }
        }
    }

    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||!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());
        }
    }
}

连通块中点的数量

给定一个包含 $n$ 个点（编号为 $1 \sim n$）的无向图，初始时图中没有边。
现在要进行 $m$ 个操作，操作共有三种：

C a b，在点 $a$ 和点 $b$ 之间连一条边，$a$ 和 $b$ 可能相等；
Q1 a b，询问点 $a$ 和点 $b$ 是否在同一个连通块中，$a$ 和 $b$ 可能相等；
Q2 a，询问点 $a$ 所在连通块中点的数量；

输入格式
第一行输入整数 $n$ 和 $m$。
接下来 $m$ 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b，如果 $a$ 和 $b$ 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 $a$ 所在连通块中点的数量
每个结果占一行。
数据范围
$1 \le n,m \le 10^5$
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：
Yes
2
3

思路:

1. 用一个size数组来维护当前点所在集合的点的数量
2. 如果二个点不在一个集合，用并查集合并后，把size数组+到合并入的点的地方去，在的话不管

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static int p[]=new int[(int) (1e5+10)];
    static int size[]=new int[(int) (1e5+10)];
    static void solve(){
        int n=in.nextInt();
        int m=in.nextInt();
        for(int i=1;i<=n;i++){
            p[i]=i;
            size[i]=1;
        }
        for(int i=1;i<=m;i++){
            String op=in.next();
            if(op.equals("C")){
                int a=in.nextInt();
                int b=in.nextInt();
                if(find(a)!=find(b)) {
                    size[find(b)]+=size[find(a)];
                }
                p[find(a)]=find(b);
            }else if(op.equals("Q1")){
                int a=in.nextInt();
                int b=in.nextInt();
                if(find(a)==find(b)){
                    out.println("Yes");
                }else{
                    out.println("No");
                }
            }else{
                int a=in.nextInt();
                out.println(size[find(a)]);
            }
        }
    }
    static int find(int x){
        return p[x]==x?x:(p[x]=find(p[x]));
    }

    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||!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());
        }
    }
}

银河英雄传说

有一个划分为 $N$ 列的星际战场，各列依次编号为 $1,2,…,N$。

有 $N$ 艘战舰，也依次编号为 $1,2,…,N$，其中第 $i$ 号战舰处于第 $i$ 列。
有 $T$ 条指令，每条指令格式为以下两种之一：

M i j，表示让第 $i$ 号战舰所在列的全部战舰保持原有顺序，接在第 $j$ 号战舰所在列的尾部。
C i j，表示询问第 $i$ 号战舰与第 $j$ 号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。

现在需要你编写一个程序，处理一系列的指令。
输入格式
第一行包含整数 $T$，表示共有 $T$ 条指令。
接下来 $T$ 行，每行一个指令，指令有两种形式：M i j 或 C i j。
其中 $M$ 和 $C$ 为大写字母表示指令类型，$i$ 和 $j$ 为整数，表示指令涉及的战舰编号。
输出格式
你的程序应当依次对输入的每一条指令进行分析和处理：
如果是 M i j 形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是 C i j 形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 $i$ 号战舰与第 $j$ 号战舰之间布置的战舰数目，如果第 $i$ 号战舰与第 $j$ 号战舰当前不在同一列上，则输出 $-1$。
数据范围
$N \le 30000 , T \le 500000$
输入样例：
4
M 2 3
C 1 2
M 2 4
C 4 2

输出样例：
-1
1

思路：

1. 并查集的一道应用题，首先定义三个数组$p,size,dis$
2. p[x]表示x的父结点是谁，size[x]数组表示x所在的集合有多少结点，dis[x]表示x到其父结点的距离是多少
3. 当我把a集合合并到b集合，那么b集合的结点数量就要加上a结点的元素数量，size[b]+=size[a]
4. 把a集合合并到b集合，a集合的根是直接连接到b集合的根，所以a集合到其父结点的距离就是b集合元素数量，便是dis[a]=size[b]
5. a结点内其他结点的根结点此时依然是a结点，他们的dis[x]是到a的距离，当我查询a结点内的一个x节点到b结点内的距离，我在路径优化的时候，会把内部结点x直接连到b结点上，那么x到b结点的距离便是x到a结点的距离+a到b结点的距离，便是dis[x]+=dis[p[x]]
6. 最后查询集合内二个结点中间其他结点的数量，便是二个结点到根结点的距离-1
7. 最后注意，如果两个节点已经在一个集合，那么便没有必要再次合并，否则原本他们的父结点都相等，到父结点的距离都为0，就会变成到父结点的距离是集合的元素数量

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt();
        for(int i=1;i<=3e4;i++){
            p[i]=i;
            size[i]=1;
        }
        for(int i=1;i<=n;i++){
            String op=in.next();
            int a=in.nextInt(),b=in.nextInt();
            int fa=find(a),fb=find(b);
            if(op.equals("M")){
                if(fa==fb) continue;
                p[fa]=fb;
                dis[fa]=size[fb];
                size[fb]+=size[fa];
            }else{
                if(fa==fb){
                    out.println(Math.max(0,Math.abs(dis[a]-dis[b])-1));
                }else{
                    out.println(-1);
                }
            }
        }
    }
    static int find(int x){
        if(p[x]==x) return x;
        int v=find(p[x]);
        dis[x]=dis[x]+dis[p[x]];
        return p[x]=v;
    }
    static int size[]=new int[(int) (3e4+10)];
    static int dis[]=new int[(int)(3e4+10)];
    static int p[]=new int[(int) (3e4+10)];
    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||!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());
        }
    }
}

食物链

动物王国中有三类动物 $A,B,C$，这三类动物的食物链构成了有趣的环形。
$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。
现有 $N$ 个动物，以 $1 \sim N$ 编号。
每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：
第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。
第二种说法是 2 X Y，表示 $X$ 吃 $Y$。
此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

当前的话与前面的某些真的话冲突，就是假话；
当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
当前的话表示 $X$ 吃 $X$，就是假话。

你的任务是根据给定的 $N$ 和 $K$ 句话，输出假话的总数。
输入格式
第一行是两个整数 $N$ 和 $K$，以一个空格分隔。
以下 $K$ 行每行是三个正整数 $D，X，Y$，两数之间用一个空格隔开，其中 $D$ 表示说法的种类。
若 $D=1$，则表示 $X$ 和 $Y$ 是同类。
若 $D=2$，则表示 $X$ 吃 $Y$。
输出格式
只有一个整数，表示假话的数目。
数据范围
$1 \le N \le 50000$,
$0 \le K \le 100000$
输入样例：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

输出样例：
3

思路：

1. 使用带边权并查集来做这道题
2. 并查集p用来维护两个点是否在一个集合内（是否有联系），d维护两个点之间具体的关系
3. d本质上是该点到父结点的距离，我们用距离决定其与父结点的关系，模3为0是同类，定义为A，模3为1是吃，定义为B，模3为2是被吃，定义为C，A->B->C->A
4. 我们对点进行操作，如果这两个点在一个集合内，我们就根据d判断它们关系
5. 如果这两个点不在一个集合内，我们就要将他们合并，比如把a所在集合合并到b所在集合，便是把p[fa]=fb
6. 这里就是把a的根接了一条线到b的根，如果我们希望db到da距离模3为0，此时b是直接连接到fb，而a和b隔了二层结点，也就是d[a]+d[fa],我们构造d[fa]=d[b]-d[a]，那么在路径压缩的时候d[a]就会变成d[a]+d[b]-d[a]，这样其就等于d[b]了，如果我们构造吃的关系就是d[fa]=d[b]-d[a]+1,压缩后-d[b]刚好为1。这样我们就构造好了

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static int p[]=new int[(int) (5e4+10)];
    static int d[]=new int[(int) (5e4+10)];//每个结点到其父结点的距离，距离模3为0是同类,1是吃，2是被吃
    static void solve(){
        int n=in.nextInt(),k=in.nextInt();
        for(int i=1;i<=n;i++) p[i]=i;
        int res=0;
        for(int i=1;i<=k;i++){
            int op=in.nextInt(),a=in.nextInt(),b=in.nextInt();
            if(a>n||b>n){
                res++;
                continue;
            }
            int fa=find(a),fb=find(b);
            if(op==1){
                if(fa==fb&&(d[a]-d[b])%3!=0) res++;
                else if(fa!=fb){
                    p[fa]=fb;
                    d[fa]=d[b]-d[a];
                }
            }else{
                if(a==b) res++;
                else if(fa==fb&&(d[a]-d[b]-1)%3!=0) res++;
                else if(fa!=fb){
                    p[fa]=fb;
                    d[fa]=d[b]+1-d[a];
                }
            }
        }
        out.println(res);
    }
    static int find(int x){
        if(p[x]==x) return x;
        int r=find(p[x]);
        d[x]+=d[p[x]];
        return p[x]=r;
    }
    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||!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());
        }
    }
}

动态规划

线性DP

Two Arrays

你需要使用1~m以内的数，构造出2个序列

第一个序列是一个不下降子序列，长度为$n$

第二个序列是一个不上升子序列，长度为$n$

要求第一个序列最后一个数<=第二个序列第一个数

请问同时构造出符合条件的长度为m的两个序列的方案数

思路，该问题我们可以转换为用1~m以内的数，构造出长度为2n的不下降子序列的方案数，因为我们可以把第一个序列翻转，拼到第一个。

$状态：//长度为i，第一位为j的非下降子序列(不严格升序)方案数$

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int n,m;
ll f[2010][20];
int main(){//长度为i，第一位为j的非下降子序列(不严格升序)方案数
//包括长度为i-1，第一位为j ，还有个是长度为i，第一位是j+1 
	cin>>n>>m;
	m*=2;
	for(int i=1;i<=n;i++){
		f[1][i]=1;
	}
	for(int i=2;i<=m;i++){
		for(int j=n;j>=1;j--){
			f[i][j]=(f[i][j+1]+f[i-1][j])%mod;
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++) ans=(ans+f[m][i])%mod;
	cout<<ans;
}

Add One

给定你一个数，每次操作，你要把每一位的数变成原本的数+1

状态机

大盗阿福

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 $N$ 家店铺，每家店中都有一些现金。
阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
输入格式
输入的第一行是一个整数 $T$，表示一共有 $T$ 组数据。
接下来的每组数据，第一行是一个整数 $N$ ，表示一共有 $N$ 家店铺。
第二行是 $N$ 个被空格分开的正整数，表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过1000。
输出格式
对于每组数据，输出一行。
该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。
数据范围
$1 \le T \le 50$,
$1 \le N \le 10^5$
输入样例：
2
3
1 8 2
4
10 7 6 14

输出样例：
8
24

样例解释
对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。
对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。

思路：

1. $dp[i][0]$表示已经打劫了前$i$家店铺，且不打劫当前店铺的最大机制， $dp[i][1]$表示已经打劫了前$i$家店铺，且已经连续打劫1家店铺的最大价值。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int n,m;
ll dp[100010][2];
int main(){
	int zu;
	cin>>zu;
	for(int _=0;_<zu;_++){
		cin>>n;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			int x;
			cin>>x;
			dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
			dp[i][1]=dp[i-1][0]+x;
		}
		cout<<max(dp[n][0],dp[n][1])<<"\n";
	} 
}

股票买卖 II

给定一个长度为 $N$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入格式
第一行包含整数 $N$，表示数组长度。
第二行包含 $N$ 个不大于 $10000$ 的正整数，表示完整的数组。
输出格式
输出一个整数，表示最大利润。
数据范围
$1 \le N \le 10^5$
输入样例1：
6
7 1 5 3 6 4

输出样例1：
7

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

输出样例2：
4

输入样例3：
5
7 6 4 3 1

输出样例3：
0

样例解释
样例1：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。共得利润 4+3 = 7。
样例2：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
样例3：在这种情况下, 不进行任何交易, 所以最大利润为 0。

思路：

1. 我们设置状态$f[i][0]$为当前未持有股票的最大价值，$f[i][1]$为当前未持有股票的最大价值
2. $f[i][0]$ 可以从上一次不买转移过来，也可以从上一次已经买过了，这次卖出转移过来，$f[i][1]$可以从上一次买过了转移而来，也可以从上一次没买，这次买转移过来

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class 股票买卖2 {
    static int zu;
    static int N = (int) (1e5 + 10);
    static int a[]=new int[N];
    static int n, m, k;
    static int f[][]=new int[N][2];
    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();
        for(int i=1;i<=n;i++) a[i]=in.nextInt();
        f[0][1]= -0x3f3f3f3f;
        for(int i=1;i<=n;i++){
            f[i][0]=Math.max(f[i-1][0],f[i-1][1]+a[i]);
            f[i][1]=Math.max(f[i-1][1],f[i-1][0]-a[i]);
        }
        out.println(Math.max(f[n][0],f[n][1]));
    }

    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 || !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());
        }
    }

}

股票买卖 IV

给定一个长度为 $N$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。
设计一个算法来计算你所能获取的最大利润，你最多可以完成 $k$ 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。
输入格式
第一行包含整数 $N$ 和 $k$，表示数组的长度以及你可以完成的最大交易笔数。
第二行包含 $N$ 个不超过 $10000$ 的正整数，表示完整的数组。
输出格式
输出一个整数，表示最大利润。
数据范围
$1 \le N \le 10^5$,
$1 \le k \le 100$
输入样例1：
3 2
2 4 1

输出样例1：
2

输入样例2：
6 2
3 2 6 5 0 3

输出样例2：
7

样例解释
样例1：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
样例2：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.

思路：

1. 我们设计 $f[i][j][k]$ 状态为进行到第$i$天，当前是否持股，已经完成了$k$次购买 购买的状态。
2. 转移方程为：$f[i][0][k]=max(f[i-1][0][k],f[i-1][1][k-1]+w[i]),f[i][1][k]=max(f[i-1][1][k],f[i-1][0][k]-w[i])$

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    static int zu;
    static int N = (int) (1e5 + 10);
    static int a[] = new int[N];
    static int f[][][]=new int[N][2][105];
    static int n, m, k;

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

    static void solve() {
        n=in.nextInt();k=in.nextInt();
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<2;j++){
                for(int k1=0;k1<=k;k1++){
                    f[i][j][k1]=-0x3f3f3f3f;
                }
            }
        }
        f[0][0][0]=0;
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=k;j>=1;j--){
                f[i][0][j]=Math.max(f[i-1][0][j],f[i-1][1][j-1]+a[i]);
                f[i][1][j-1]=Math.max(f[i-1][1][j-1],f[i-1][0][j-1]-a[i]);
                ans=Math.max(ans,f[i][0][j]);
                ans=Math.max(ans,f[i][1][j-1]);
            }
            f[i][0][0]=f[i-1][0][0];
        }
        out.println(ans);
    }

    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 || !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());
        }
    }

}

股票买卖V

给定一个长度为 $N$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 $1$ 天)。

输入格式
第一行包含整数 $N$，表示数组长度。
第二行包含 $N$ 个不超过 $10000$ 的正整数，表示完整的数组。
输出格式
输出一个整数，表示最大利润。
数据范围
$1 \le N \le 10^5$
输入样例：
5
1 2 3 0 2

输出样例：
3

样例解释
对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]，第一笔交易可得利润 2-1 = 1，第二笔交易可得利润 2-0 = 2，共得利润 1+2 = 3。

思路:

1. $f[i][0] 表示第i天空仓状态，f[i][1]表示第i天持股状态，f[i][2] 表示第i天不可购买状态$

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class 股票买卖5 {
    static int zu;
    static int N = (int) (1e5 + 10);
    static int f[][] = new int[N][3];
    static int n, m, k;

    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();
        for(int i=0;i<N;i++){
            for(int j=0;j<3;j++){
                f[i][j]=-0x3f3f3f3f;
            }
        }
        f[0][0]=0;
        for(int i=1;i<=n;i++){
            int x=in.nextInt();
            f[i][0]=Math.max(f[i-1][0],f[i-1][2]);
            f[i][1]=Math.max(f[i-1][1],f[i-1][0]-x);
            f[i][2]=f[i-1][1]+x;
        }
        int ans=0;
        ans=Math.max(Math.max(f[n][0],Math.max(f[n][1],f[n][2])),ans);
        out.println(ans);
    }

    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 || !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());
        }
    }

}
	

树形DP

树的重心

给定一棵树，树中包含 $n$ 个结点（编号$1$~$n$）和 $n-1$ 条无向边，每条边都有一个权值。

请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。
输入格式
第一行包含整数 $n$。
接下来 $n-1$ 行，每行包含三个整数 $a_i,b_i,c_i$，表示点 $a_i$ 和 $b_i$ 之间存在一条权值为 $c_i$ 的边。
输出格式
输出一个整数，表示所求点到树中其他结点的最远距离。
数据范围
$1 \le n \le 10000$,
$1 \le a_i,b_i \le n$,
$1 \le c_i \le 10^5$
输入样例：
5
2 1 1
3 2 1
4 3 1
5 1 1

输出样例：
2

思路：

1. 我们定义如下数组，含义分别为：

   d1[i]:以i为根节点向下走的最长路径。
   d2[i]:以i为根节点向下走的次长路径，且不与最长路径走相同的最近子节点。
   p1[i]:记录以i为根节点最长路径走的最近子节点
   p2[i]:记录以i为根节点次长路径走的最近子节点
   up[i]:记录以i为根节点的最近父结点不走自身走的最长路径。

2. 接下来我们做二次DFS，分别更新向下走和向上走