一、數(shù)論

1）GCD

GCD（求最大公約數(shù)）

public static int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

QGCD（快速GCD）

public static int qGCD(int a, int b) {
    if(a == 0) return b;
    if(b == 0) return a;
    if((a & 1) == 0 && (b & 1) == 0) {
        return qGCD(a >> 1, b >> 1) << 1;
    } else if((b & 1) == 0) {
        return qGCD(a, b >> 1);
    } else if((a & 1) == 0) {
        return qGCD(a >> 1, b);
    } else {
        return qGCD(Math.abs(a - b), Math.min(a, b));
    }
}

extGCD（拓展GCD，解決ax + by = c 問題）

import java.util.Scanner;

public class 數(shù)論_拓展GCD {
    /**
     *  題目描述：
     *  兩只青蛙在網(wǎng)上相識(shí)了，它們聊得很開心，于是覺得很有必要見一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止?？墒撬鼈兂霭l(fā)之前忘記了一件很重要的事情，既沒有問清楚對(duì)方的特征，
     *  也沒有約定見面的具體位置。不過青蛙們都是很樂觀的，它們覺得只要一直朝著某個(gè)方向跳下去，總能碰到對(duì)方的。但是除非這兩只青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個(gè)程序來判斷這兩只青蛙是否能夠碰面，會(huì)在什么時(shí)候碰面。
     *  我們把這兩只青蛙分別叫做青蛙A和青蛙B，并且規(guī)定緯度線上東經(jīng)0度處為原點(diǎn)，由東往西為正方向，單位長(zhǎng)度1米，這樣我們就得到了一條首尾相接的數(shù)軸。設(shè)青蛙A的出發(fā)點(diǎn)坐標(biāo)是x，青蛙B的出發(fā)點(diǎn)坐標(biāo)是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩只青蛙跳一次所花費(fèi)的時(shí)間相同。
     *  緯度線總長(zhǎng)L米。現(xiàn)在要你求出它們跳了幾次以后才會(huì)碰面。
    * 
     *  輸入只包括一行5個(gè)整數(shù)x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
     * 
     *  輸出碰面所需要的跳躍次數(shù)，如果永遠(yuǎn)不可能碰面則輸出一行"Impossible" 
     * Sample Input: 
     * 1 2 3 4 5 
     * Sample Output:
     * 4
     * 
     */
    public static long extGCD(long a, long b, long x, long y) {
        if(b == 0) {
            x = 1;
            y = 0;
            return a;
        }else {
            long d = extGCD(b, a % b, y, x);
            long temp = y;
            y = x - (a / b) * y;
            x = temp;
            return d;
        }
    }

    //分析：
    //設(shè)時(shí)間為t，青蛙A在t時(shí)間后的位置為x + m * t，青蛙B在t時(shí)間后的位置y + n * t
    //因?yàn)榫S度線可視作為一個(gè)圈，則可推出他們相遇時(shí)候的公式：(x + (m * t)) % L = (y + (n * t)) % L
    //上式轉(zhuǎn)換為：(m - n) * t + k * L = y - x;（t、k為未知數(shù)，t為次數(shù)，k為圈數(shù)）
    //滿足ax + by = c
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long x = in.nextLong();
        long y = in.nextLong();
        long m = in.nextLong();
        long n = in.nextLong();
        long L = in.nextLong();
        long a = m - n;
        long b = L;
        long c = y - x;
        long d = extGCD(a, b, x, y);
        if(c % d != 0) {
            System.out.println("Impossible");
        }else {
            x = x * c / d;
            long t = Math.abs(b / d);
            x = (x % t + t) % t;
            System.out.println(x);
        }
    }
}

2）素?cái)?shù)（也稱質(zhì)數(shù)，質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)）

素?cái)?shù)篩選

static boolean[] is_prime = new boolean[100000];

public static void prime(int maxN) {
    Arrays.fill(is_prime, true);
    for(int i = 2; i * i < maxN; i++) {
        if(is_prime[i]) {
            for(int j = i * i; j < maxN; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

3）歐拉函數(shù)（小于n且和n互質(zhì)（兩個(gè)數(shù)的最大公約數(shù)為1）的正整數(shù)（包括1）的個(gè)數(shù)，如12的歐拉函數(shù)是φ(12)=4，有1，5，7，11）

單個(gè)數(shù)的歐拉函數(shù)

public static int euler(int n) {
    int res = n;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            res = res - res / i;
            while(n % i == 0) {
                n /= i;
            }
        }
    }
    if(n > 1) {
        res = res - res / n;
    }
    return res;
}

歐拉函數(shù)篩選

static final int MAX = 100000;
static int[] a = new int[MAX];

public static void euler_meter(){
    for(int i = 1; i < MAX; i++){
        a[i] = i;
    }
    for(int i = 2; i < MAX; i++){
        if(a[i] == i){
            for(int j = i; j < MAX; j += i){
                a[j] = a[j] - a[j] / i;
            }
        }
    }
}

3）博弈論

簡(jiǎn)單博弈

/*
小明經(jīng)常玩 LOL 游戲上癮，一次他想挑戰(zhàn)K大師，不料K大師說：
“我們先來玩?zhèn)€空格填字母的游戲，要是你不能贏我，就再別玩LOL了”。
K大師在紙上畫了一行n個(gè)格子，要小明和他交替往其中填入字母。

并且：
1. 輪到某人填的時(shí)候，只能在某個(gè)空格中填入L或O
2. 誰先讓字母組成了“LOL”的字樣，誰獲勝。
3. 如果所有格子都填滿了，仍無法組成LOL，則平局。

小明試驗(yàn)了幾次都輸了，他很慚愧，希望你能用計(jì)算機(jī)幫他解開這個(gè)謎。
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    
    static Map<String, Integer> map = new HashMap<>();//記憶話搜索，記錄已經(jīng)走過的字符串及勝負(fù)情況
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        for(int i = 0; i < n; i++) {
            String s = in.readLine();
            System.out.println(game(s));
        }
    }

    private static int game(String s) {
        map.clear();
        return f(s.toCharArray());
    }

    private static int f(char[] c) {
        String s = new String(c);
        if(map.get(s) != null) {
            return map.get(s);
        }
        if(s.contains("LOL")) {
            map.put(s, -1);
            return -1;
        }
        if(!s.contains("*")) {
            map.put(s, 0);
            return 0;
        }
        boolean ping = false;
        for(int i = 0; i < c.length; i++) {
            if(c[i] == '*') {
                try {
                    c[i] = 'L';
                    {
                        int k = f(c);
                        if(k == -1) {
                            map.put(s, 1);
                            return 1;
                        }
                        if(k == 0) {
                            ping = true;
                        }
                    }
                    c[i] = 'O';
                    {
                        int k = f(c);
                        if(k == -1) {
                            map.put(s, 1);
                            return 1;
                        }
                        if(k == 0) {
                            ping = true;
                        }
                    }
                }finally {
                    c[i] = '*';
                }
            }
        }
        if(ping) {
            map.put(s, 0);
            return 0;
        }
        map.put(s, -1);
        return -1;
    }
}

NIM堆問題

/*
有3堆硬幣，分別是3,4,5
二人輪流取硬幣。
每人每次只能從某一堆上取任意數(shù)量。
不能棄權(quán)。
取到最后一枚硬幣的為贏家。

求先取硬幣一方有無必勝的招法。
*/
static void f(int[] a){
    int sum = 0;
    for(int i = 0; i < a.length; i++){
        sum ^= a[i];
    }
    if(sum == 0){
        System.out.println("輸了");
            return;
    }
    //打印必勝的方法
    for(int i=0; i<a.length; i++){
        int x = sum ^ a[i];
        if(x<a[i]) System.out.println(a[i] + " --> " + x);
    }
}

4）排列組合

全排列(0 ~ 9)

static int[] a = new int[10];
static boolean[] vis = new boolean[10];

public static void dfs(int step){
    if(step == 10){
        for(int i = 0; i < 10; i++){
            System.out.println(a[i] + " ");
        }
        return;
    }
    for(int i = 0; i < 10; i++){
        if(!vis[i]){
            vis[i] = true;
            a[step] = i;
            dfs(step + 1);
            vis[i] = false;
        }
    }
}

不重復(fù)全排列

static int[] a = {1， 1， 2};

public static void dfs(int k){
    if(k == a.length){
        for(int i = 0; i < a.length; i++){
            System.out.println(a[i] + " ");
        }
        return;
    }
    for(int i = k; i < a.length; i++){
        if(needSwap(k, i)){
            swap(i, k);
            dfs(step + 1);
            swap(i, k);
        }
    }
}

public static boolean needSwap(int from, int to) {
    for(int i = from; i < to; i++) {
        if(a[to] == a[i]) {
            return false;
        }
    }
    return true;
}

public static void swap(int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

不重復(fù)一般組合（例如，從4個(gè)中選3個(gè)所有組合）

static int[] a = {1， 1， 2, 4};

public static void select_combination(int k, int n){
    if(k == n){
        for(int i = 0; i < n; i++){
            System.out.println(a[i] + " ");
        }
        return;
    }
    for(int i = k; i < a.length; i++){
        if(needSwap(k, i)){
            swap(i, k);
            dfs(step + 1);
            swap(i, k);
        }
    }
}

public static boolean needSwap(int from, int to) {
    for(int i = from; i < to; i++) {
        if(a[to] == a[i]) {
            return false;
        }
    }
    return true;
}

public static void swap(int x, int y) {
    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}

全組合（列出數(shù)列的全部子集）:利用了狀態(tài)壓縮

public static void full_combination(int[] a) {
    int len = a.length;
    for(int i = 1; i < (1 << len); i++) {
        for(int j = 0; j < len; j++) {
            if((i & (1 << j)) > 0) {
                System.out.print(a[j] + " ");
            }
        }
        System.out.println();
    }
}

5）快速冪

a ^ b

public static long pow(int a, int b){
    int res = 1;
    while(b > 0){
        if((b & 1) == 1){
            res *= a;
        }
        b >>= 1;
        a *= a;
    }
    return res;
}

矩陣快速冪

static class Matrix{
    int n;
    int a[][] = new int[n][n];
    public Matrix(){}
    public Matrix(int n){
        this.n = n;
    }
}

public static Matrix matrix_pow(A, p, mod){
    Matrix B = unit(A.n);
    while(p > 0){
        if((p & 1) == 1){
            B = matrix_mult(B, A, mod);
        }
        p >>= 1;
        A = matrix_mult(A, A, mod);
    }
    return B;
}

public static Matrix unit(int n){
    Matrix B = new Matrix(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j) {
                B.a[i][j] = 1;
            }else {
                B.a[i][j] = 0;
            }
        }
    }
    return B;
}

public static Matrix matrix_mult(Matrix A, Matrix B, int mod) {
    Matrix C = new Matrix(A.n, B.n);
    for(int i = 0; i < A.n; i++) {
        for(int j = 0; j < B.n; j++) {
            C.a[i][j] = 0;
            for(int k = 0; k < A.n; k++) {
                C.a[i][j] = C.a[i][j] + (A.a[i][k] * B.a[k][j] % mod);
            }
        }
    }
    return C;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int p = in.nextInt();
    int mod = in.nextInt();
    Matrix A = new Matrix(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            A.a[i][j] = in.nextInt();
        }
    }
    Matrix res = matrix_pow(A, p, mod);
    for(int i = 0; i < res.n; i++) {
        for(int j = 0; j < res.n; j++) {
            System.out.print(res.a[i][j] + " ");
        }
        System.out.println();
    }
}

6）循環(huán)節(jié)長(zhǎng)度（a/b）

public static int f(int n, int m) {
    n = n % m;
    Vector<Integer> v = new Vector<>();
    while(true) {
        v.add(n);
        n *= 10;
        n = n % m;
        if (n == 0)
            return 0;
        if (v.indexOf(n) >= 0)
            return v.size() - v.indexOf(n);
    }
}

二、字符串（學(xué)的不多）

編輯距離

/*
編輯距離，?又稱Levenshtein距離（也叫做Edit Distance），是指兩個(gè)字串串之間，由一個(gè)轉(zhuǎn)成 另一個(gè)所需的少編輯操作次數(shù)。許可的編輯操作包括將?一個(gè)字符替換成另一個(gè)字符，插?一個(gè)字 符，刪除?個(gè)字符
*/

public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    String s1 = in.nextLine();
    String s2 = in.nextLine();
    char[] c1 = s1.toCharArray();
    char[] c2 = s2.toCharArray();
    int len1 = c1.length;
    int len2 = c2.length;
    int[][] dp = new int[len1 + 1][len2 + 1];
    for(int i = 1; i <= len1; i++){
        dp[i][0] = i;
    }
    for(int i = 1; i <= len2; i++){
        dp[0][i] = i;
    }
    for(int i = 1; i <= len1; i++){
        for(int j = 1; j <= len2; j++){
            if(c[i - 1] == c[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            }else{
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    System.out.println(dp[len1][len2]);
}

最長(zhǎng)公共子序列

/*
比如字符串1：BDCABA；字符串2：ABCBDAB 最長(zhǎng)公共子序列是：BCBA
*/
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String s = in.nextLine();
    char[] c1 = s.toCharArray();
    s = in.nextLine();
    char[] c2 = s.toCharArray();
    int len1 = c1.length;
    int len2 = c2.length;
    int dp[][] = new int[len1 + 1][len2 + 1];
    for(int i = 1; i <= len1; i++) {
        for(int j = 1; j <= len2; j++) {
            if(c1[i - 1] == c2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    System.out.println(dp[len1][len2]);
}

最長(zhǎng)上升子序列

/*
比如：2 5 3 4 1 7 6  其中最長(zhǎng)上升子序列是 2 3 4 7 
*/
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] a = new int[n];
    for(int i = 0; i < n; i++) {
        a[i] = in.nextInt();
    }
    int dp[] = new int[n];
    int ans = 1;
    for(int i = 0; i < n; i++) {
        dp[i] = 1;
        for(int j = i; j >= 0; j--) {
            if(dp[j] < dp[i]) {
                if(a[j] < a[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        ans = Math.max(dp[i], ans);
    }
    System.out.println(ans);
}

Karp-Rabin算法 （字符串匹配）

/**
比如：字符串1：abcaabcaabcbcabc 字符串2：abc 答案：4
*/
static int send = 31;

public static void karp_rabin(String s1, String s2){
    long hash_s2 = hash(s2);
    int len_s1 = s1.length();
    int len_s2 = s2.length();
    long[] hash_s1 = new long[len_s1 - len_s2 + 1];
    hash_s1[0] = hash(s1.subString(0, len_s2));
    int ans = 0;
    for(int i = len_s2; i < len_s1; i++){
        char newChar = s1.charAt(i);
        char oldChar = s1.charAt(i - len_s2);
        long v = (long) (hash_s1[i - len_s2] * send - oldChar * Math.pow(send, len_s2) + newChar);
        hash_s1[i - len_s2 + 1] = v;
    }
    for(int i = 0; i < hash_s1.length; i++) {
        if (hash_s1[i] == hash_s2) { // 當(dāng)j == len_s2的時(shí)候則說明第二個(gè)循環(huán)從頭掃到尾，即滿足題意。
            ans++;
            // 為了驗(yàn)證是否正確，進(jìn)行了下標(biāo)打?。ㄏ聵?biāo)0代表字符串的第一位）
            System.out.println("match:" + i);
            System.out.println(ans);
        }
    }
}

public static long hash(String s){
    int len = s.length();
    long hash = 0;
    for(int i = 0; i < len; i++){
        hash = send * hash + s.charAt(i);
    }
    return hash;
}

KMP算法（字符串匹配）

public static int[] solve_next(String s){
    int len = s.length();
    int[] next = new int[len];
    next[0] = -1;
    if(len == 1){
        return next;
    }
    next[1] = 0;
    int j = 1;
    int k = next[j];
    while(j < len - 1){
        if(k < 0 || s.charAt(j) == s.charAt(k)){
            next[++j] = ++k;
        }else{
            k = next[k];
        }
    }
    return next;
}

public static int kmp(String s1, String s2){
    int len_s1 = s1.length();
    int len_s2 = s2.length();
    int next[] = solve_next(s2);
    int i = 0;
    int j = 0;
    int count = 0;
    while(i < len_s1){
        if(j == -1 || s1.charAt(i) == s2.charAt(j)){
            i++;
            j++;
        }else{
            j = next[j];
        }
        if(j == len_s2){
            count++;
            i--;
            j = next[j - 1];
        }
    }
    return count;
}

三、背包問題

01背包

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int V = in.nextInt();
    int[] c = new int[N + 1];
    int[] w = new int[N + 1];
    for(int i = 1; i <= N; i++) {
        w[i] = in.nextInt();
        c[i] = in.nextInt();
    }
    int[] dp = new int[V + 1];
    for(int i = 1; i <= N; i++) {
        for(int j = V; j >= c[i]; j--) {
            dp[j] = Math.max(dp[j - c[i]] + w[i], dp[j]);
        }
    }
    System.out.println(dp[V]);
}

多重背包

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int V = in.nextInt();
    int[] c = new int[N + 1];
    int[] w = new int[N + 1];
    int[] n = new int[N + 1];
    for(int i = 1; i <= N; i++) {
        w[i] = in.nextInt();
        c[i] = in.nextInt();
        n[i] = in.nextInt();
    }
    int[] dp = new int[V + 1];
    for(int i = 1; i <= N; i++) {
        for(int j = V; j >= 0; j--) {
            for(int k = 0; k <= n[i]; k++){
                if(j >= k * c[i]){
                    dp[j] = Math.max(dp[j - c[i] * k] + k * w[i], dp[j]);
                }
            }
        }
    }
    System.out.println(dp[V]);
}

多重背包（二進(jìn)制優(yōu)化）

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int V = in.nextInt();
    int[] c = new int[N + 1];
    int[] w = new int[N + 1];
    int[] n = new int[N + 1];
    for(int i = 1; i <= N; i++) {
        w[i] = in.nextInt();
        c[i] = in.nextInt();
        n[i] = in.nextInt();
    }
    int[] dp = new int[V + 1];
    for(int i = 1; i <= N; i++) {
        int t = n[i];
        int k = 1;
        while(k < t){
            for(int j = V; j >= k * c[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - k * c[i]] + k * w[i]);
            }
            k *= 2;
            t -= k;
        }
        for(int j = V; j >= t * c[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - t * c[i]] + t * w[i]);
        }
    }
    System.out.println(dp[V]);
}

完全背包

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int V = in.nextInt();
    int[] c = new int[N + 1];
    int[] w = new int[N + 1];
    for(int i = 1; i <= N; i++) {
        w[i] = in.nextInt();
        c[i] = in.nextInt();
    }
    int[] dp = new int[V + 1];
    for(int i = 1; i <= N; i++) {
        for(int j = c[i]; j <= V; j++) {
            dp[j] = Math.max(dp[j - c[i]] + w[i], dp[j]);
        }
    }
    System.out.println(dp[V]);
}

混合背包

/*
題目鏈接：https://www.acwing.com/problem/content/7/
*/
import java.util.Scanner;

public class 背包問題_混合背包問題 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        int[] s = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
            s[i] = in.nextInt();
        }
        int[] dp = new int[V + 1];
        for(int i = 1; i <= N; i++) {
            if(s[i] == -1) {
                for(int j = V; j >= v[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }else if(s[i] == 0) {
                for(int j = v[i]; j <= V; j++) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }else {
                int k = 1;
                int t = s[i];
                while(k < t) {
                    for(int j = V; j >= k * v[i]; j--) {
                        dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
                    }
                    t -= k;
                    k <<= 1;
                }
                for(int j = V; j >= t * v[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - t * v[i]] + t * w[i]);
                }
            }
        }
        System.out.println(dp[V]);
    }
}

二維費(fèi)用背包問題

/*
題目鏈接：https://www.acwing.com/problem/content/8/
*/
import java.util.Scanner;

public class 背包問題_二維費(fèi)用背包問題 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int M = in.nextInt();
        int[] v = new int[N + 1];
        int[] m = new int[N + 1];
        int[] w = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            v[i] = in.nextInt();
            m[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        int[][] dp = new int[V + 1][M + 1];
        for(int i = 1; i <= N; i++) {
            for(int j = V; j >= v[i]; j--) {
                for(int k = M; k >= m[i]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[V][M]);
    }
}

組合背包問題

/*
題目鏈接：https://www.acwing.com/problem/content/9/
*/
import java.util.Scanner;

public class 背包問題_分組背包問題 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int[] a = new int[N + 1];
        int[][] v = new int[N + 1][];
        int[][] w = new int[N + 1][];
        for(int i = 1; i <= N; i++) {
            a[i] = in.nextInt();
            v[i] = new int[105];
            w[i] = new int[105];
            for(int j = 1; j <= a[i]; j++) {
                v[i][j] = in.nextInt();
                w[i][j] = in.nextInt();
            }
        }
        int[] dp = new int[V + 1];
        for(int i = 1; i <= N; i++) {
            for(int j = V; j >= 0; j--) {
                for(int k = 1; k <= a[i]; k++) {
                    if(j >= v[i][k]){
                        dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);
                    }
                }
            }
        }
        System.out.println(dp[V]);
    }
}

三、圖論

Dijkstra（鄰接矩陣形式）——求單源最短路（無負(fù)權(quán)邊）

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

public class 圖_最短路徑_dijkstra_鄰接矩陣 {
    
    private static int n, m;
    private static int[][] map;
    private static boolean[] vis;
    private static int[] dis;
    private static final int INF = 0x3f3f3f;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        init();//初始化
        for(int i = 0; i < m; i++) {
            int a = in.nextInt();//起點(diǎn)
            int b = in.nextInt();//終點(diǎn)
            int c = in.nextInt();//權(quán)值
            insert(a, b, c);//無向圖
//          insert01(a, b, c);//有向圖
        }
        dijkstra(1);
        System.out.println(dis[n]);
    }

    private static void init() {
        map = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == j) map[i][j] = 0;
                else map[i][j] = INF;
            }
        }
        vis = new boolean[n + 1];
        dis = new int[n + 1];
        Arrays.fill(dis, INF);
    }

    private static void dijkstra(int u) {
        for(int i = 1; i <= n; i++){
            dis[i] = map[u][i];
        }
        vis[i] = true;
        for(int i = 1; i <= n - 1; j++){
            int mind = INF;
            int minj = -1;
            for(int j = 1; j <= n; j++){
                if(!vis[j] && dis[j] < mind){
                    mind = dis[j];
                    minj = j;
                }
            }
            if(minj == -1) return;
            vis[minj] = true;
            for(int j = 1; j <= n; j++){
                if(map[minj][j] < INF){
                    if(dis[j] > dis[minj] + map[minj][j]){
                        dis[j] = dis[minj] + map[minj][j];
                    }
                }
            }
        }
    }

    //無向圖添加邊
    private static void insert(int a, int b, int c) {
        map[a][b] = c;
        map[b][a] = c;
    }
    
    //有向圖添加邊
    private static void insert(int a, int b, int c) {
        map[a][b] = c;
    }

}

Dijkstra（鄰接矩陣鏈表）——求單源最短路（無負(fù)權(quán)邊）

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

public class 圖_最短路徑_dijkstra_鄰接鏈表 {
    
    private static int n, m;
    private static boolean[] vis;
    private static int[] dis;
    private static final int INF = 0x3f3f3f;
    private static Edge[] e;
    private static int[] head;
    private static int size;
    
    static class Edge{
        int v;//終點(diǎn)
        int w;//權(quán)重
        int next;//下一條邊的id
        public Edge(){}
        public Edge(int v, int w, int next){
            this.v = v;
            this.w = w;
            this.next = next;
        }
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        init();//初始化
        for(int i = 0; i < m; i++) {
            int a = in.nextInt();//起點(diǎn)
            int b = in.nextInt();//終點(diǎn)
            int c = in.nextInt();//權(quán)值
            insert(a, b, c);//無向圖
//          insert01(a, b, c);//有向圖
        }
        dijkstra(1);
        System.out.println(dis[n]);
    }

    private static void init() {
        e = new Edge[2 * m + 1];//無向圖
//      e = new Edge[m + 1];//有向圖
        vis = new boolean[n + 1];
        dis = new int[n + 1];
        Arrays.fill(dis, INF);
        head = new int[n + 1];
        Arrays.fill(head, -1);
    }

    private static void dijkstra(int u) {
        dis[u] = 0;
        for(int i = 1; i <= n; i++){
            int mind = INF;
            int minj = -1;
            for(int j = 1; j <= n; j++){
                if(!vis[j] && dis[j] < mind){
                    mind = dis[j];
                    minj = j;
                }
            }
            if(minj == -1){
                return;
            }
            vis[minj] = true;
            for(int j = head[minj]; j != -1; j = e[j].next){
                int v = e[j].v;
                int w = e[j].w;
                if(!vis[v] && dis[v] > dis[minj] + w){
                    dis[v] = dis[minj] + w;
                }
            }
        }
    }

    //無向圖添加邊
    private static void insert(int u, int v, int w) {
        e[size] = new Edge(v, w, head[u]);
        head[u] = size++;
        e[size] = new Edge(u, w, head[v]);
        head[v] = size++;
    }
    
    //有向圖添加邊
    private static void insert(int u, int v, int w) {
        e[size] = new Edge(b, c, head[a]);
        head[u] = size++;
    }

}

SPFA（鄰接鏈表）——單源最短路（有負(fù)權(quán)邊）

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 圖_最短路徑_spfa_鄰接鏈表 {
    
    private static int n, m, size;
    private static Edge[] e;
    private static int[] head;
    private static int[] dis;
    private static boolean[] vis;
    private static final int INF = 0x3f3f3f;
    private static int[] in;
    
    public static class Edge{
        int v;
        int w;
        int next;
        public Edge() {}
        public Edge(int v, int w, int next) {
            this.v = v;
            this.w = w;
            this.next = next;
        }
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        init();
        for(int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            insert02(a, b, c);
        }
        if(spfa(1)) {
            System.out.println("有負(fù)環(huán)");
        }else {
            System.out.println(dis[n]);
        }
    }

    //加入負(fù)環(huán)判斷
    private static boolean spfa(int u) {
        vis[u] = true;
        dis[u] = 0;
        in[u]++;
        Queue<Integer> q = new LinkedList<>();
        q.add(u);
        while(!q.isEmpty()){
            int now = q.poll();
            vis[now] = false;
            for(int i = head[now]; i != -1; i = e[i].next){
                int v = e[i].v;
                int w = e[i].w;
                if(dis[v] > dis[u] + w){
                    dis[v] = dis[u] + w;
                    if(!vis[v]){
                        q.add(v);
                        vis[v] = true;
                        in[v]++;
                        if(in[v] > n) return true;
                    }
                }
            }
        }
        return false;
    }

    private static void init() {
        e = new Edge[2 * m + 1];
        head = new int[n + 1];
        Arrays.fill(head, -1);
        vis = new boolean[n + 1];
        dis = new int[n + 1];
        Arrays.fill(dis, INF);
        in = new int[n + 1];
    }

    private static void insert01(int u, int v, int w) {
        e[size] = new Edge(v, w, head[u]);
        head[u] = size++;
    }
    
    private static void insert02(int u, int v, int w) {
        insert01(u, v, w);
        insert01(v, u, w);
    }
}

floyd——多源最短路

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int[][] map = new int[n + 1][n + 1];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == j) map[i][j] = 0;
            else map[i][j] = 0x3f;
        }
    }
    for(int i = 0; i < m; i++) {
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        map[a][b] = map[b][a] = c;
    }
    //floyd核心
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }
    System.out.println(map[1][n]);
}

圖的拓?fù)渑判?/h4>

public class 圖_拓?fù)渑判?{
    
    private static int n, m;
    private static Edge[] e;
    private static int[] indegree;
    private static int[] head;
    private static int size;
    
    public static class Edge{
        int v;
        int next;
        public Edge() {}
        public Edge(int v, int next) {
            this.v = v;
            this.next = next;
        }
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        init();
        for(int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            insert(a, b);
            indegree[b]++;
        }
        topo();
    }

    private static void topo() {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= n; i++) {
            if(indegree[i] == 0) {
                q.add(i);
            }
        }
        while(!q.isEmpty()) {
            int now = q.peek();
            System.out.println(now);
            q.poll();
            for(int i = head[now]; i != -1; i = e[i].next) {
                int v = e[i].v;
                indegree[v]--;
                if(indegree[v] == 0) {
                    q.add(v);
                }
            }
        }
    }

    private static void insert(int u, int v) {
        e[size] = new Edge(v, head[u]);
        head[u] = size++;
    }

    private static void init() {
        e = new Edge[m + 1];
        indegree = new int[n + 1];
        Arrays.fill(indegree, 0);
        head = new int[2 * m + 1];
        Arrays.fill(head, -1);
    }
}

最小生成樹——Kruskal

public class 最小生成樹 {
    
    static int n, m;
    static Edge[] e;
    static int[] pre;
    
    public static class Edge{
        int u;
        int v;
        int w;
        public Edge() {}
        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
        @Override
        public String toString() {
            return "Edge [u=" + u + ", v=" + v + ", w=" + w + "]";
        }
    }
    
    public static int krusual(){
        init();
        Arrays.sort(e, new Comparator<Edge>() {
            public int compare(Edge o1, Edge o2) {
                return o1.w - o2.w;
            }
        });
        int count = 0;//記錄已生成的邊數(shù)
        int sum = 0;//記錄答案
        for(int i = 0; i < m; i++) {
            if(merge(e[i].u, e[i].v)) {
                count++;
                sum += e[i].w;
            }
            if(count == n - 1) {//滿足最小生成樹條件
                break;
            }
        }
        if(count < n - 1) {
            return -1;
        }else{
            return sum;
        }
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        e = new Edge[m];
        for(int i = 0; i < m; i++) {
            e[i] = new Edge(in.nextInt(), in.nextInt(), in.nextInt());
        }
        int res = krusual();
        if(res == -1){
            System.out.println("不連通);
        }else{
            System.out.println(res);
        }
    }

    private static boolean merge(int u, int v) {
        int uu = find(u);
        int vv = find(v);
        if(uu != vv){
            pre[vv] == uu;
            return true;
        }
        return false;
    }

    private static int find(int u) {
        int r = u;
        while(r != pre[r]){
            r = pre[r];
        }
        return r;
    }

    //并查集初始
    private static void init() {
        pre = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            pre[i] = i;
        }
    }
}

最小生成樹——Prim

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

public class 最小生成樹_Prim {
    
    static int n, m;
    static final int INF = 0x3f3f3f;
    static int[] head;
    static int size;
    static Edge[] e;
    static boolean[] vis;
    static int[] dis;
    
    static class Edge{
        int v;
        int w;
        int next;
        public Edge() {}
        public Edge(int v, int w, int next) {
            this.v = v;
            this.w = w;
            this.next = next;
        }
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        init();
        int st = 0;
        for(int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            int w = in.nextInt();
            insert(u, v, w);
            insert(v, u, w);
            st = u;
        }
        int res = prim(st);
        System.out.println(res);
    }

    private static int prim(int st) {
        int sum = 0;
        int count = 0;
        dis[st] = 0;
        for(int i = head[st]; i != -1; i = e[i].next) {
            int v = e[i].v;
            int w = e[i].w;
            if(dis[v] > w) {
                dis[v] = w;
            }
        }
        vis[st] = true;
        count++;
        while(count < n) {
            int mind = INF;
            int minj = -1;
            for(int i = 1; i <= n; i++) {
                if(!vis[i] && dis[i] < mind) {
                    mind = dis[i];
                    minj = i;
                }
            }
            vis[minj] = true;
            count++;
            sum += mind;
            for(int i = head[minj]; i != -1; i = e[i].next) {
                int v = e[i].v;
                int w = e[i].w;
                if(!vis[v] && dis[v] > w) {
                    dis[v] = w;
                }
            }
        }
        return sum;
    }

    private static void init() {
        head = new int[n + 1];
        Arrays.fill(head, -1);
        e = new Edge[m * 2 + 1];
        vis = new boolean[n + 1];
        dis = new int[n + 1];
        Arrays.fill(dis, INF);
    }

    private static void insert(int u, int v, int w) {
        e[size] = new Edge(v, w, head[u]);
        head[u] = size++;
    }
}

線段樹（多用于解決區(qū)間問題）

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

public class 線段樹_構(gòu)建 {
    
    private static final int MAX = 105;
    private static int[] a = new int[MAX];
    private static int[] minv = new int[MAX * 4];
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }
        build_tree(1, 1, n);
        update_tree(1, 1, n, 5, 7);//更新線段樹中a數(shù)組下標(biāo)為5的值。
        query_tree(1, 1, n, 2, 5);//查詢2~5區(qū)間的最小值
    }


    //區(qū)間查詢
    private static int query_tree(int id, int l, int r, int x, int y) {
        if(x <= l && r <= y) {
            return minv[id];
        }
        int mid = (l + r) >> 1;
        int res = Integer.MAX_VALUE;
        if(x <= mid) {
            res = Math.min(res, query_tree(id << 1, l, mid, x, y));
        }
        if(y > mid) {
            res = Math.min(res, query_tree(id << 1 | 1, mid + 1, r, x, y));
        }
        return res;
    }

    //更新
    private static void update_tree(int id, int l, int r, int x, int v) {
        if(l == r) {
            minv[id] = v;
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) {
            update_tree(id << 1, l, mid, x, v);
        }else {
            update_tree(id << 1 | 1, mid + 1, r, x, v);
        }
        minv[id] = Math.min(minv[id << 1], minv[id << 1 | 1]);
    }

    //構(gòu)建線段樹
    private static void build_tree(int id, int l, int r) {
        if(l == r) {
            minv[id] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build_tree(id << 1, l, mid);
        build_tree(id << 1 | 1, mid + 1, r);
        minv[id] = Math.min(minv[id << 1], minv[id << 1 | 1]);
    }
}

四、二分

二分

private static int binary_search(Integer[] a, int k) {
    int l = 0;
    int r = a.length - 1;
    while(l <= r) {
        int mid = (r + l) >> 1;
        if(a[mid] == k) return mid;
        if(a[mid] < k) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

最大值最小問題

public class 二分_最大值最小 {
    
    static int[] a = {2, 4, 6, 8, 10, 12, 14};
    
    public static void main(String[] args) {
        System.out.println(bsearch_maxMin(11));
    }

    private static int bsearch_maxMin(int x) {
        int l = 0;
        int r = a.length - 1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(x <= a[mid]) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        return l;//返回5
    }
}

最小值最大問題

public class 二分_最小值最大 {
    
    static int[] a = {2, 4, 6, 8, 10, 12, 14};
    
    public static void main(String[] args) {
        System.out.println(bsearch_maxMin(3));
    }

    private static int bsearch_maxMin(int x) {
        int l = 0;
        int r = a.length - 1;
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(x <= a[mid]) {
                r = mid - 1;
            }else {
                l = mid;
            }
        }
        return l;//返回4
    }
}