import java.util.Scanner;

public class Main {
    static int N = 100;
    static int[] st = new int[N];//st[0]代表没用过，st[i]代表这个位置用哪个数
    static int n,m;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        dfs(1,1);
    }

    static void dfs(int u,int start)
    {
        if(u>m)
        {
            for(int i=1;i<=m;i++)
            {
                System.out.print(st[i]+" ");
            }
            System.out.println();
            return;
        }

        for(int i=start;i<=n;i++)
        {
              st[u] = i;
              dfs(u+1,i+1);
              st[u] = 0;
        }
    }
}

package Acwing算法练习.蓝桥第一章递归与递推;

import java.util.Scanner;

public class 递归实现排列型枚举 {
    static int N = 15;
    static int[] st = new int[N];//状态:0代表没用过，1~n代表这个位置用那个数
    static boolean[] used = new boolean[N];
    static int n;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(1);
    }

    static void dfs(int u)
    {
        if(u>n)//遍历结束条件
        {
            for(int i=1;i<=n;i++)
            {
                System.out.print(st[i]+" ");
            }
            System.out.println();
        }

        for(int i=1;i<=n;i++)//依次枚举每个分支，当前位置可以填那些数
        {
            if(used[i]==false)
            {
                st[u] = i;
                used[i] = true;
                dfs(u+1);
                st[u] = 0;
                used[i] = false;
            }
        }

    }

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    static int N = 20;
    static int[] st = new int[N];//状态表示，0表示还没考虑，1表示选，2表示没选
    static int n;
    public static void main(String[] args) throws IOException
    {
        Scanner sc = new Scanner(System.in);
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        String s[] = br.readLine().split("\\s+");
        n = Integer.parseInt(s[0]);
        dfs(0);

    }

    static void dfs(int u)
    {
        if(u==n)//终止条件
        {
            for(int i=0;i<n;i++)
            {
                if(st[i]==1)
                    System.out.print(i+1+" ");
            }
            System.out.println();
            return;
        }

        st[u] = 2;//不选
        dfs(u+1);
        st[u] = 0;

        st[u] = 1;
        dfs(u+1);
        st[u] = 0;


    }


}

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static int N = 110,M = 100010;
    static int[] s = new int[N];// s 表示集合里的数字
    static int[] f = new int[M];// f表示sg的值
    static int n,m;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int res = 0;
        Arrays.fill(f,-1);
        for(int i=0;i<n;i++)
        {
            s[i] = sc.nextInt();
        }
        m = sc.nextInt();
        for(int i=0;i<m;i++)
        {
            int x = sc.nextInt();
            res ^= sg(x);
        }

        if(res!=0) System.out.println("Yes");
        else System.out.println("No");
    }

    static int sg(int x)//求每堆石子的sg值
    {
        if(f[x]!=-1) return f[x];//记忆和搜索，如果搜索过了直接return
        Set<Integer> S = new HashSet<>();
        for(int i=0;i<n;i++)
        {
            int sum = s[i];//每次取sum个石子， 剩余的石子个数为x - sum
            if(x>=sum ) S.add(sg(x-sum));
        }
        for(int i=0;;i++)//mex集合中没出现过的最小的非负整数
        {
            if(!S.contains(i))
                return f[x] = i;
        }
    }


}

import java.util.Scanner;
//根据第奇数阶台阶判断，对所有的奇数阶台阶进行^,如果得0，那么先手必败
//如果奇数阶台阶不得0.那么我们可以通过先手转化成0，让对手面对奇数阶台阶输
//如果只有偶数阶台阶有的话，那么不管怎么先手都可以通过最佳方案赢
public class Main {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        int res = 0;
        for(int i=1;i<=n;i++)
        {
            a[i] = sc.nextInt();
            if(i%2==1)
                res^=a[i];
        }
        if(res!=0) System.out.println("Yes");
        else System.out.println("No");
    }
}

import java.util.Scanner;

public class Main {
    //先手必胜:如果这对数里面全部亦或（^）起来等于x(不等于0)，那么先手一定赢
    //先手必输:如果这对数里面全部亦或（^）起来等于0，那么先手一定输
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int res = 0;
        for(int i=0;i<n;i++)
        {
            a[i] = sc.nextInt();
            res ^= a[i];
        }
        if(res!=0) System.out.println("Yes");
        else System.out.println("No");

    }
}

package Acwing算法练习.第五章dp;

import java.util.Arrays;
import java.util.Scanner;
//f[u][0]表示以u为根节点，并且不包括u的最大快乐指数
//f[u][1]表示以u为根节点，并且包括u的最大快乐指数
public class 没有上司的舞会 {
    static int N = 100010;
    static int[] happy = new int[N];
    static boolean[] has_fa = new boolean[N];
    static int[][] f = new int[N][2];
    static int[] e = new int[N],ne = new int[N],h = new int[N];
    static int idx;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=1;i<=n;i++) happy[i] = sc.nextInt();
        Arrays.fill(h,-1);
        for(int i=0;i<n-1;i++)//n-1条边
        {
            int b = sc.nextInt();
            int a = sc.nextInt();
            has_fa[b] = true;//如果有父节点，就true
            add(a,b);
        }

        int root = 1;
        while(has_fa[root]) root++;
        dfs(root);
        System.out.println(Math.max(f[root][0],f[root][1]));

    }

    static void dfs(int u)
    {
        f[u][1] = happy[u];
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j = e[i];
            dfs(j);//子结点
            f[u][1] += f[j][0];
            f[u][0] += Math.max(f[j][1],f[j][0]);
        }
    }

    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

}

import java.util.Arrays;
import java.util.Scanner;
//f[u][0]表示以u为根节点，并且不包括u的最大快乐指数
//f[u][1]表示以u为根节点，并且包括u的最大快乐指数
public class Main {
    static int N = 100010;
    static int[] happy = new int[N];
    static boolean[] has_fa = new boolean[N];
    static int[][] f = new int[N][2];
    static int[] e = new int[N],ne = new int[N],h = new int[N];
    static int idx;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=1;i<=n;i++) happy[i] = sc.nextInt();
        Arrays.fill(h,-1);
        for(int i=0;i<n-1;i++)//n-1条边
        {
            int b = sc.nextInt();
            int a = sc.nextInt();
            has_fa[b] = true;//如果有父节点，就true
            add(a,b);
        }

        int root = 1;
        while(has_fa[root]) root++;
        dfs(root);
        System.out.println(Math.max(f[root][0],f[root][1]));

    }

    static void dfs(int u)
    {
        f[u][1] = happy[u];
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j = e[i];
            dfs(j);//子结点
            f[u][1] += f[j][0];
            f[u][0] += Math.max(f[j][1],f[j][0]);
        }
    }

    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

}

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
//使用记忆化数组 记录每个点的最大滑动长度
//遍历每个点作为起点
//然后检测该点四周的点 如果可以滑动到其他的点
//那么该点的最大滑动长度 就是其他可以滑到的点的滑动长度+1
//dp[i][j] = max(dp[i][j-1], dp[i][j+1],dp[i-1][j],dp[i+1][j])
public class Main {
    static int N = 410;
    static int n,m;
    static int[][] h = new int[N][N],f = new int[N][N];//h是输入的数组，f是记忆化搜索数组;
    static int[] dx = new int[]{-1,0,1,0};
    static int[] dy = new int[]{0,1,0,-1};
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                h[i][j] = sc.nextInt();
            }
        }
        for(int i=0;i<n;i++) Arrays.fill(f[i],-1);//初始化一个f[][],计算的时候如果f[i][j]是-1，那么代表没计算过，如果计算过直接return
        int res = 0;
        for(int i=0;i<n;i++)//每个都枚举一个，看看在哪里走取最大值//找到从当前位置往下走的最大路径，再取最大值，
        {
            for(int j=0;j<m;j++)
            {
                res = Math.max(res,dp(i,j));
            }
        }
        System.out.println(res);
    }

    static int dp(int x,int y)
    {
        if(f[x][y]!=-1) return f[x][y];
        f[x][y] = 1;
        for(int i=0;i<4;i++)
        {
            int a = x+dx[i];
            int b = y+dy[i];
            if(a>=0 && a<n && b>=0 && b<m && h[a][b]<h[x][y])//检测该点四周的点 如果可以滑动到其他的点
            {
                f[x][y] = Math.max(f[x][y],dp(a,b)+1);//那么该点的最大滑动长度 就是其他可以滑到的点的滑动长度+1
            }
        }
        return f[x][y];
    }

}

package Acwing算法练习.第五章dp;

import java.util.Scanner;
//优化版的完全背包问题
//f[i][j]表示从1-i中选，体积恰好为重量j的数量
public class 整数划分 {
    static int M = 1010,mol = (int) (1e9+7);
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[M];
        dp[0] = 1;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
                dp[j] = (dp[j]+dp[j-i])%mol;
        }
        System.out.println(dp[n]);
    }

}