基础算法

读入

Scanner

import java.util.*;
import java.io.*;
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();

    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = scan.nextInt();
    }
    qsort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        System.out.print(arr[i] + (i == n - 1 ? "\n": " "));
    }
}

BufferedReader

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[] nums = new int[n];
        String[] strs = reader.readLine().split(" ");
        for (int i = 0; i < n; i++)
            nums[i] = Integer.parseInt(strs[i]);
        // ...
        reader.close(); // 记得关闭
    }
}

快速排序

quicksort

随机选择一个数与最左交换依次递归排左边右边

public static void swap(int[] arr, int x, int y) {
    int tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
    return;
}
public static void qsort(int[] arr, int l, int r) {
    if(l >= r) return;
    int index = (int)(Math.random() * (r - l + 1)) + l;
    int v = arr[index];
    int st = l - 1, end = r + 1;
    while(st < end) {
        while(arr[++st] < v);
        while(arr[--end] > v);
        if(st < end)swap(arr, st, end);
    }
    qsort(arr, l, end);
    qsort(arr, end + 1, r);
}

find Kth largest number

O(n)

public static void swap(int[] arr, int i, int j) {
   int tmp = arr[i];
   arr[i] = arr[j];
   arr[j] = tmp;
}
public static int findKth(int[] arr, int k, int l, int r) {
   if(l >= r) return arr[r];
   int index = (int)(Math.random() * (r - l + 1)) + l;
   int v = arr[index];
   int start = l - 1, end = r + 1;
   while(start < end) {
       while(arr[++start] < v);
       while(arr[--end] > v);
       if(start < end) swap(arr, start, end);
   }

   if(end - l + 1 < k) {
       return findKth(arr, k - (end - l + 1), end + 1, r);
   } else {
       return findKth(arr, k, l, end );
   }
}

Merge sort

归并排序

O(nlogn)

public static void mergeSort(int[] arr, int l, int r) {
    if(l >= r) return;
    int mid = l + r >> 1;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    int k = 0; int i = l, j = mid + 1;
    int[] tmp = new int[r -l + 1];
    while(i <= mid && j <= r) {
        if(arr[i] < arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while(i <= mid) tmp[k++] = arr[i++];
    while(j <= r) tmp[k++] = arr[j++];
    for (i = l, j = 0; i <= r; i ++, j ++ ) arr[i] = tmp[j];
    return;
}

逆序对

O(nlogn)

public static long solve(int[] arr, int l, int r) {
    if(l >= r) return 0;
    int mid = l + r >> 1;
    long left = solve(arr, l, mid);
    long right = solve(arr, mid + 1, r);
    int k = 0; int i = l, j = mid + 1;
    int[] tmp = new int[r - l + 1];
    long ret = 0;
    while(i <= mid && j <= r) {
        if(arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            ret +=  mid - i + 1;
            tmp[k++] = arr[j++];
        }
    }
    while(i <= mid) {
        tmp[k++] = arr[i++];
    }
    while(j <= r) tmp[k++] = arr[j++];
    for (i = l, j = 0; i <= r; i ++, j ++ ) arr[i] = tmp[j];
    return left + right + ret;
}

二分

二分模版

O(logn) r指向是不满足func的第一个位置。

public static int findL(int[] arr, int k) {
    int l = 0, r = arr.length;
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(arr[mid] < k) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return r == arr.length ? -1 : arr[r] == k ? r : -1;
}

数的三次方根

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    double target = in.nextDouble();
    double l = -10000, r = 10000;
    while (r - l > 1e-8) {      
        double mid = (l + r) / 2;
        if (mid * mid * mid >= target)     
            r = mid;    
        else
            l = mid;
    }
    System.out.println(String.format("%.6f", l));
}

高精度

这四道题都是要注意有木有前置零。复杂度为O(n);

高精度加法

public static String add(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1;
    int carry = 0;
    while (i >= 0 || j >= 0) {
        int tmp = 0;
        if(i >= 0) tmp += a.charAt(i) - '0';
        if(j >= 0) tmp += b.charAt(j) - '0';
        j--; i--;
        tmp += carry;
        sb.append(tmp % 10 + "");
        carry = tmp / 10;
    }
    if(carry != 0) sb.append(carry + "");
    return sb.reverse().toString();
}

高精度减法

比较 a 和 b 的大小，如果 a 比 b 小的话，就算 b - a 最后加上负号

class Main {
    public static boolean cmp(String a, String b) {
        if(a.length() != b.length()) return a.length() > b.length();
        int i = 0;
        while(i < a.length()) {
            if(a.charAt(i) == b.charAt(i)) i++;
            else {
                int x = a.charAt(i) - '0', y = b.charAt(i) - '0';
                if(x < y) return false;
                else return true;
            }
        }
        return true;
    }
    public static String sub(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1;
        int carry = 0;
        while (i >= 0 || j >= 0) {
            int x =  (a.charAt(i) - '0');
            if(j >= 0) x -= (b.charAt(j) - '0') ;
            x += carry;
            sb.append((x + 10) % 10 + "");
            carry = x < 0 ?  -1 : 0;
            j--; i--;
        }  
        //去掉前置0
        String ret = sb.reverse().toString();
        int k = 0;
        while(k < ret.length()) {
            if(ret.charAt(k) != '0') break;
            k++;
        }
        return k == ret.length() ? "0" : ret.substring(k);

    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String a = scan.next();
        String b = scan.next();
        String ret;
        //if(cmp(a, b)) System.out.println("true");
        if(cmp(a, b)) ret = sub(a, b);
        else ret = "-" + sub(b, a);
        System.out.println(ret);
    }
}

高精度乘法

这个题是一个大数乘以一个小于100000 的数, 注意处理进位的方式。。

public static String mul(String a, int b) {
    StringBuilder sb = new StringBuilder();
    int carry = 0;
    for(int i = a.length() - 1; i >= 0 || carry != 0; i--) {
        int v = 0;
        if(i >= 0) v = (a.charAt(i) - '0') * b;
        v += carry;
        sb.append(v % 10);
        carry = v / 10;
    }
    String ret = sb.reverse().toString();
    //remove leading zeroes;
    int k = 0;
    while(k < ret.length()) {
        if(ret.charAt(k) !=  '0') break;
        k++;
    }
    return k == ret.length() ? "0" : ret.substring(k);
}

高精度除法

public static String div(String a, int b) {
   StringBuilder sb = new StringBuilder();
   int r = 0;
   for(int i = 0; i < a.length(); i++) {
       r += a.charAt(i) - '0';
       sb.append(r / b);
       r %= b;
       r *= 10;
   }
   String ret = sb.toString();
   //remove leading zeroes;
   int k = 0;
   while(k < ret.length()) {
       if(ret.charAt(k) !=  '0') break;
       k++;
   }
   if(k == a.length()) return "0" + "\n" + r / 10;
   return  ret.substring(k) + "\n" + r / 10;
}

前缀和与差分

一维前缀和

$S_0 = 0, S_i = a_1 + a_2 … + a_i$
$sum(L, R) = a_l + a_{l+1} … + a_r = sum(R) - sum(L - 1)$ 求[l, r) 区间和等于sum[r] - sum[l]

int[] sum = new int[n + 1];
for(int i  = 1; i < sum.length; i++) {
  sum[i] = sum[i-1] + arr[i-1];
}

二维前缀和

前缀和数组这样更新: $s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]$
左上$(x_1, y_1)$, 右下 $(x_2, y_2)$ 矩阵面积就是 $s[x_2, y_2] - s[x_1 -1, y_2] - s[x_2, y_1 - 1] + s[x_1 - 1, y_1 - 1]$

class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt(), k = scan.nextInt();
        int[][] s = new int[n + 1][m + 1];

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                s[i][j] = scan.nextInt();
            }
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
            }
        }
        for(int i = 0;  i < k; i++) {
            int x1 = scan.nextInt(), y1 = scan.nextInt(), x2 = scan.nextInt(), y2 = scan.nextInt();
            System.out.println(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
        }
    }
}

差分数组

给定a[1], a[2], … , a[n]
构造差分数组使得差分数组是原数组的前缀和数组 a[i] = b[1] + b[2] + … + b[i]

核心操作:
将a[L~R]全部加上c 等价于 b[L] += c, b[R + 1] -= c

AC797
class Main {
    public static void insert(int[] arr, int l, int r, int c) {
        arr[l] += c;
        arr[r + 1] -= c;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), k = scan.nextInt();
        int[] arr = new int[100010];
        for(int i = 0; i < n; i++) {
            int v = scan.nextInt();
            insert(arr, i, i, v);
        }
        while(k > 0) {
            int l = scan.nextInt(), r = scan.nextInt(), v= scan.nextInt();
            insert(arr, l - 1, r - 1, v);
            k--;
        }

        int tmp = 0;
        for(int i = 0; i < n; i++) {
            tmp += arr[i];
            System.out.print(tmp + " ");
        }
    }
}

二维差分矩阵

给定原矩阵a[i, j], 构造差分矩阵使得a是s的二维前缀和。核心操作：给以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的子矩阵中所有数a[i,j]加上c 等价于在差分矩阵做如下修改

 s[x1,y1] += c
 s[x2 + 1,y1] -= c
 s[x1, y2 + 1] -= c
 s[x2 + 1, y2 + 1] += c

class Main {
    public static void insert(int[][] s, int x1, int y1, int x2, int y2, int c) {
         s[x1][y1] += c;
         s[x2 + 1][y1] -= c;
         s[x1][y2 + 1] -= c;
         s[x2 + 1][y2 + 1] += c;
    }
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        OutputStreamWriter writer = new OutputStreamWriter(System.out);
        int n = scan.nextInt(), m = scan.nextInt(), k = scan.nextInt();
        int[][] s = new int[n + 2][m + 2];
        for(int i = 1; i <= n ; i++) {
            for(int j = 1; j <= m; j++) {
                int v = scan.nextInt();
                insert(s, i, j, i, j, v);
            }
        }

        while(k > 0) {
            int x1 = scan.nextInt(), y1 = scan.nextInt();
            int x2 = scan.nextInt(), y2 = scan.nextInt();
            int c = scan.nextInt();
            insert(s, x1, y1, x2, y2, c);
            k--;
        }
        int tmp = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
                writer.write(s[i][j] + " ");
            }
            writer.write("\n");
        }
        writer.flush();
        scan.close();
        writer.close();
    }
}

双指针

最长连续不重复子序列

滑动窗口经典例题

int[] window = new int[100010];
int ret = 1;
for(int i = 0, j = 0; j < n; j++) {
    window[arr[j]]++;
    while( i < j && window[arr[j]] > 1) {
        window[arr[i]]--;
        i++;
    }
    ret = Math.max(ret, j - i + 1);
}

数组元素的目标和

给定两个排好序的且没有重复元素的数组，找出从两个数组选出两个元素和为 k 的下标

public static int[] solve(int[] s, int[] t, int k) {
   int j = 0, ret = 0;
   for(int i = 0; i < s.length; i++) {
       j = t.length - 1;
       while(j >= 0 && s[i] + t[j] > k) {
           j--;
       }
       if(s[i] + t[j] == k) return new int[]{i, j};
   }
   return new int[0];
}

判断子序列

public static boolean isSeq(int[] a, int[] b) {
    if(a.length > b.length) return false;
    int i = 0, j = 0;
    while(i < a.length && j < b.length) {
        if(a[i] == b[j]) {
            i++; j++;
        } else {
            j++;
        }
    }
    return i == a.length;
}

位运算

常用位运算操作：

求n的第k位数字 n » k & 1
返回n的最后一位1 lowbit(n) = n & -n;

二进制中1的个数

public static int getBit(int n) {
    int ret = 0;
    while(n != 0) {
        n -= n & -n;
        ret++;
    }
    return ret;
}

离散化

主要是映射。。。

import java.util.*;
import java.io.*;
class Main {
    public static int getIndex(List<Integer> list, int v) {
        int l = 0, r = list.size();
        while(l < r) {
            int mid = l + (r - l) / 2;
            if(list.get(mid) <= v) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return r == 0 ? 0 : r-1;
    }
    public static List<Integer> helper(List<Integer> list) {
        List<Integer> ret = new ArrayList<>();
        ret.add(list.get(0));
        for(int i : list) {
            ret.add(i + 1);
        }
        return ret;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();

        TreeMap<Integer, Integer> tree = new TreeMap<>();
        for(int i = 0; i < n; i++) {
            int k = scan.nextInt(), v = scan.nextInt();
            tree.putIfAbsent(k, 0);
            tree.put(k, tree.get(k) + v);
        }
        List<Integer> list = new ArrayList(tree.keySet());

        int[] sum = new int[list.size() + 1];
        for(int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + tree.get(list.get(i - 1));
            //System.out.print(sum[i] + " ");
        }
        list = helper(list);

        while(m > 0) {
            int l = scan.nextInt(), r = scan.nextInt();
            l = getIndex(list, l);
            r = getIndex(list, r+1);
            //System.out.println(list.get(l) + " " + list.get(r));
            System.out.print(sum[r] - sum[l] + "\n");
            m--;
        }
    }
}

区间合并

Collections.sort(list, (a, b) -> (a[0] - b[0]));
int[] cur = list.get(0);
int ret = 1;
for(int i = 1; i < list.size(); i++) {
    int[] next = list.get(i);
    if(cur[1] < next[0]) {
        ret++;
        cur = next;
    } else {
        cur[1] = Math.max(cur[1], next[1]);
    }
}

数据结构

单链表

class LinkList {
    int N = 100010;
    // head 表示头结点的下标
    // e[i] 表示节点i的值
    // ne[i] 表示节点i的next指针是多少
    // idx 存储当前已经用到了哪个点
    int head, idx;
    int[] e, ne;
    public LinkList() {
        head = -1;
        idx = 0;
        e = new int[N];
        ne = new int[N];
        //Arrays.fill(ne, -1);
    }
    public void insertH(int v) {
        e[idx] = v;
        ne[idx] = head;
        head = idx++;
    }
    public void deleteK(int k) {
        if(k == -1) {
            head = ne[head];
            return;
        }
        ne[k] = ne[ne[k]];
    }
    public void insertK(int k, int v) {
        if(k == -1) {
            insertH(v);
            return;
        }
        e[idx] = v;
        ne[idx] = ne[k];
        ne[k] = idx++;
    }
    public void print() {
        for (int i = head; i != -1; i = ne[i]) {
            System.out.print(e[i] + " ");
        }
    }
}

双链表

class LinkList {
    int N = 100010;
    int idx;
    int[] e, l, r;
    public LinkList() {
        l = new int[N];
        r = new int[N];
        e = new int[N];
        r[0] = 1;
        l[1] = 0;
        idx = 2;
    }
    public void insert(int a, int x) {
        e[idx] = x;
        l[idx] = a;
        r[idx] = r[a];
        l[r[a]] = idx;
        r[a] = idx++;
    }
    public void remove(int a) {
        l[r[a]] = l[a];
        r[l[a]] = r[a];
    }
    public void print() {
        for(int i = r[0]; i != 1; i = r[i]) {
            System.out.print(e[i] + " ");
        }
    }
}

栈

class Main {
    public static void main(String[] args) {
        int n = 100010;
        int[] stack = new int[n];
        int idx = -1;
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        while(m > 0) {
            String op = scan.next();
            int v;
            switch(op) {
                case "push":
                    v = scan.nextInt();
                    stack[++idx] = v;
                    break;
                case "pop":
                    idx--;
                    break;
                case "empty":
                    if(idx == -1) System.out.println("YES");
                    else System.out.println("NO");
                    break;
                case "query":
                    System.out.println(stack[idx]);
            }
            m--;
        }
    }
}

队列

class Main {
    public static void main(String[] args) {
        int n = 100010;
        int[] queue = new int[n];
        int h = -1, t = -1;
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        while(m > 0) {
            String op = scan.next();
            switch(op) {
                case "push" :
                    int k = scan.nextInt();
                    queue[++t] = k;
                    break;
                case "empty":
                    if(h == t) System.out.println("YES");
                    else System.out.println("NO");
                    break;
                case "pop":
                    h++;
                    break;
                case "query" :
                    System.out.println(queue[h + 1]);
            }
            m--;
        }
    }
}

单调栈

for(int i = 0; i < n; i++) {
    while(stack.size() != 1 && arr[stack.peek()] >= arr[i]) stack.pop();
    if(stack.size() == 1) System.out.print("-1 ");
    else System.out.print(arr[stack.peek()] + " ");
    stack.push(i);
}

滑动窗口

输出选定区间大小为k的最大值和最小值。

public static void solve(int[] arr, int k) {
    Deque<Integer> queue = new LinkedList<>();

    for(int i = 0; i < arr.length; i++) {
        while(!queue.isEmpty() && queue.peekFirst() < i - k + 1) queue.pollFirst();
        while(!queue.isEmpty() && arr[queue.peekLast()] >= arr[i]) queue.pollLast();
        queue.offer(i);
        if(i >= k - 1) System.out.print(arr[queue.peekFirst()] + " ");
    }
    System.out.println();
    queue.clear();
    for(int i = 0; i < arr.length; i++) {
        while(!queue.isEmpty() && queue.peekFirst() < i - k + 1) queue.pollFirst();
        while(!queue.isEmpty() && arr[queue.peekLast()] <= arr[i]) queue.pollLast();
        queue.offer(i);
        if(i >= k - 1) System.out.print(arr[queue.peekFirst()] + " ");
    }
}

KMP

对模版串预处理后缀和前缀最大是多少。

public static void solve(char[] s, char[] p) {
    int[] ne = new int[100010];
    ne[0] = -1;
    for (int i = 1, j = -1; i < p.length; i ++ ) {
        while (j >= 0 && p[j + 1] != p[i]) j = ne[j];
        if (p[j + 1] == p[i]) j ++ ;
        ne[i] = j;
    }

    for (int i = 0, j = -1; i < s.length; i ++ ) {
        while (j != -1 && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == p.length - 1) {
            System.out.println(i - j + " ");
            j = ne[j];
        }
    }
}

Trie

Trie 字符串统计

class Trie {
    Trie[] trie;
    int cnt = 0;
    public Trie() {
        this.trie = new Trie[26];
    }
    public void insert(String s) {
        Trie root = this;
        for(int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if(root.trie[idx] != null) root = root.trie[idx];
            else {
                root.trie[idx] = new Trie();
                root = root.trie[idx];
            }
        }
        root.cnt++;
    }
    public int query(String s) {
        Trie root = this;
        for(int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if(root.trie[idx] != null) root = root.trie[idx];
            else {
                return 0;
            }
        }
        return root.cnt;
    }
}

最大异或对

class Trie {
    Trie[] trie;
    int cnt = 0;
    public Trie() {
        this.trie = new Trie[2];
    }
    public void insert(int v) {
        Trie root = this;
        for(int i = 30; i >= 0; i--) {
            int idx = (v >> i & 1);
            if(root.trie[idx] == null) root.trie[idx] = new Trie();
            root = root.trie[idx];
        }
    }
    public int search(int v) {
        Trie root = this;
        int ret = 0;
        for(int i = 30; i >= 0; i--) {
            int idx = (v >> i & 1 ) == 1 ? 0 : 1;
            if(root.trie[idx] != null) {
                root = root.trie[idx];
                ret += (1 << i);
            }
            else if(root.trie[1- idx] != null) {
                root = root.trie[1 - idx];
            }
        }
        return ret;
    }
}

并查集

合并集合

public static void union(int[] uf, int x, int y) {
     int rx = find(uf, x), ry = find(uf, y);
     if(rx == ry) return;
     uf[rx] = ry;
 }
 public static int find(int[] uf, int x) {
     if(x == uf[x]) return x;
     uf[x] = find(uf, uf[x]);
     return uf[x];
 }

连通块中点的数量

class Main {
    public static void union(int[] uf, int[] cnt, int x, int y) {
        int rx = find(uf, x), ry = find(uf, y);
        if(rx == ry) return;
        cnt[ry] += cnt[rx];
        uf[rx] = ry;
    }
    public static int find(int[] uf, int x) {
        if(x == uf[x]) return x;
        uf[x] = find(uf, uf[x]);
        return uf[x];
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[] uf = new int[n + 1];
        int[] cnt = new int[n + 1];
        Arrays.fill(cnt, 1);
        for(int i = 0; i < uf.length; i++) uf[i] = i;
        while(m > 0) {
            String op = scan.next();
            if(op.equals("Q2")) {
                int v = scan.nextInt();
                int r = find(uf, v);
                System.out.println(cnt[r]);
            } else {
                int x = scan.nextInt(), y = scan.nextInt();
                if(op.equals("C")) union(uf, cnt, x, y);
                if(op.equals("Q1")) System.out.println(find(uf, x) == find(uf, y) ? "Yes" : "No");
            }
            m--;
        }
    }
}

食物链

class Main {
    public static int find(int[] uf, int x, int[] d) {
        if(uf[x] == x) return x;
        //这里不能直接更新uf[x]，否则距离就不是父亲节点到root节点的距离了。
        int t = find(uf, uf[x], d);
        d[x] += d[uf[x]];
        uf[x] = t;
        return uf[x];
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[] uf = new int[n + 1];
        for(int i = 0; i < uf.length; i++) uf[i] = i;
        int[] d = new int[n + 1];
        int ret = 0;
        while(m > 0) {
            int l = scan.nextInt(), x = scan.nextInt(), y = scan.nextInt();
            if(x > n || y > n) {
                ret++;
            } else {
                int px = find(uf, x, d);
                int py = find(uf, y, d);
                if(l == 1) {
                    if(px == py) {
                        if ((d[x] - d[y]) % 3 != 0) ret++;;
                    } else {
                        uf[px] = py;
                        // px ---? -- py
                        // | d[x]     | d[y]
                        // x          y
                        // (d[x] + ? - d[y]) % 3 = 0; => ? = d[y] - d[x];  
                        d[px] = d[y] - d[x];
                    }
                }
                if(l == 2) {
                    if(px == py) {
                        if((d[x] - d[y] - 1) % 3 != 0) ret++;
                    } else {
                        // 同理， dx + ? -dy = 1
                        uf[px] = py;
                        d[px] = d[y] + 1 - d[x];
                    }
                }
            }
            m--;
        }
        System.out.print(ret);
    }
}

堆

stl 支持前3个操作。

插入一个数: heap[++szie], up(size)
求最小值: heap[1]
删除最小值: heap[1] = heap[size–], down(1)
删除任意一个值: heap[k] = heap[size–], down(k), up(k);
修改任意一个值: heap[k] = x; down(k), up(k)

堆：满二叉树，除了最后一行都是满的。且最后一行从左向右依次排布的。
小根堆性质：每一个节点都是小于孩子节点的。

堆的存储：一维数组存储。 1号点为根节点，那么左儿子的坐标 2x，右儿子 2x + 1 堆的两个操作：

down(x) : 往下调整
up(x)：往上调整

建堆：

一个一个插入元素: O(nlogn)
从 n/2 开始往下down: O(n)
因为是从底向上建的，这样，有1/2的元素向下比较了一次，有1/4的向下比较了两次，1/8的，向下比较了3次 ,…, 1/2^k的向下比较了k次，其中1/2^k <= 1。所以所有移动的总和为 $\sum_{k=1}^{logn} \Big[\frac{n}{2^{k}} * k\Big]$ 所以最后经过计算就是 O(n)

堆排序

class Heap {
    int size;
    int[] heap;
    public Heap(int[] h) {
        size = h.length - 1;
        this.heap = h;
        build();
    }
    //建堆
    public void build() {
        for (int i = size / 2; i > 0; i -- ) down(i);
    }
    public void down(int i) {
        int idx = i;
        if(2 * i <= size && heap[i] > heap[2 * i]) idx = 2 * i;
        if(2 * i + 1 <= size && heap[2 * i + 1] < heap[idx]) idx = 2 * i + 1;
        if(i != idx) {
            int tmp = heap[i];
            heap[i] = heap[idx];
            heap[idx] = tmp;
            down(idx);
        }
    }
    public int getMin() {
        int ret = heap[1];
        heap[1] = heap[this.size--];
        down(1);
        return ret;
    }
}

模拟堆

class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        Heap h = new Heap(n);
        int idx = 0;
        while(n > 0) {
            int k, x;
            String op = scan.next();
            switch(op) {
                case "I":
                    x = scan.nextInt();
                    h.size++;
                    idx++;
                    h.heap[h.size] = x;
                    h.ph[idx] = h.size;
                    h.hp[h.size] = idx;
                    h.up(h.size);
                    break;
                case "PM" :
                    System.out.println(h.heap[1]);
                    break;
                case "DM":
                    h.heap_swap(1, h.size);
                    h.size--;
                    h.down(1);
                    break;
                case "D" :
                    k = scan.nextInt();
                    k = h.ph[k];
                    h.heap_swap(k, h.size);
                    h.size--;
                    h.down(k);
                    h.up(k);
                    break;
                case "C":
                    k = scan.nextInt(); x = scan.nextInt();
                    k = h.ph[k]; // 必须提前记录下ph[k]的值，不然ph[k]的值可能会变
                    h.heap[k] = x;  
                    h.down(k);
                    h.up(k);
                    break;
            }
            n--;
        }
    }
}

class Heap {
    int size;
    int[] heap;
    //ph[k] 存的第k个点在堆里面的下标
    //hp[k] 存的是当前点在ph的下表
    int[] hp, ph;
    public Heap(int n) {
        this.size = 0;
        heap = new int[n + 1];
        hp = new int[n + 1];
        ph = new int[n + 1];
    }
    public  void swap(int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
    public void heap_swap(int x, int y) {
        swap(ph, hp[x], hp[y]);
        swap(hp, x, y);  
        swap(heap, x, y);
    }
    public void down(int i) {
        int idx = i;
        if(2 * i <= size && heap[i] > heap[2 * i]) idx = 2 * i;
        if(2 * i + 1 <= size && heap[2 * i + 1] < heap[idx]) idx = 2 * i + 1;
        if(i != idx) {
            heap_swap(i, idx);
            down(idx);
        }
    }
    public void up(int i) {
        while(i / 2 != 0 && heap[i / 2] > heap[i]) {
            heap_swap(i / 2, i);
            i = i / 2;
        }
    }
}

Hash

复杂度 O(1)
注意:

模的数取质数，这样可以保证冲突的数字尽可能小
删除一般使用标记，不会真正的删除

开放寻址法：

只有一个数组，但是长度一般是输入数据的2～3倍插入的话直接用 h.hash[h.find(x)] = x; 查找的话，直接看h.hash[h.find(x)] 是不是 0x3f3f3f。模版：

//开放寻值法
class Hash {
    int n = 200003;
    int INF = 0x3f3f3f;
    int[] hash = new int[n];
    public Hash() {
        Arrays.fill(hash, INF);
    }
    // 如果存在，返回index 否则返回应该插入的index
    public int find(int x) {
        int index =  (x % n + n) % n;
        while(hash[index] != INF && hash[index] != x) {
            index++;
            if(index == hash.length) index = 0;
        }
        return index;
    }
}

拉链法：数组 + 单链表

模版：

//拉链法
class Hash {
    int n = 100003;
    List<Integer>[] hash = new List[100003];

    public void insert(int x) {
        int index =  (x % n + n) % n;
        if(hash[index] == null) hash[index] = new ArrayList<>();
        hash[index].add(x);
    }
    public boolean find(int x) {
        int index =  (x % n + n) % n;
        if(hash[index] == null) return false;
        for(int i : hash[index]) {
            if(i == x) return true;
        }
        return false;
    }
}

字符串 hash

字符串前缀哈希法注意：

不能映射成 0, 容易冲突. 否则， A 与 AA hash值一样。
如果P = 131 或者 13331， Q = 2 ^ 64 可以假设不存在冲突. 并且可以用 unsigned long long 来存储。不需要取模，溢出不需要处理。

e.g str =  "ABCAB"
h[0] = 0;
h[1] = "A" 的hash值
h[2] = "AB" 的hash值
h[3] = "ABC" 的hash值
h[4] = "ABCA" 的hash值

如何定义hash值：P进制法  
eg. ABCD -> (1,2,3,4)P = 1 * P^3 + 2 * P^2 + 3 * P^1 + 4 * P^0
最后模上Q 把它们映射到一个相对小的范围

(R)----(L-1)-(L)------(R)-----|
已知 h[R], h[L-1] 那么R 到 L的 hash 就是 h[R] - h[L] * P ^(R - L + 1)

模版：

class Main {
    static int N = 100010;
    static long[] p = new long[N];
    static long[] h = new long[N];
    static int P = 131;
    static long mod = Long.MAX_VALUE;
    static void init(char[] str) {
        p[0] = 1;
        for (int i = 1; i <=  str.length; i ++ ) {
            h[i] = (h[i - 1] * P + str[i - 1]) % mod;
            p[i] = p[i - 1] * P;
        }
    }

    static long query(int l, int r) {
        return h[r] - h[l-1] * p[r - l + 1];
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        char[] str = scan.next().toCharArray();
        init(str);
        while(m > 0) {
            int l1 = scan.nextInt(), r1 = scan.nextInt();
            int l2 = scan.nextInt(), r2 = scan.nextInt();
            if(query(l1, r1) == query(l2, r2)) System.out.println("Yes");
            else System.out.println("No");
            m--;
        }
    }
}

搜索与图论

深度优先搜索 DFS

Permutation

public static void dfs(int n, int[] path, int index, Set<Integer> set) {
      if(index > n) {
          for(int i = 1; i < path.length; i++) {
              System.out.print(path[i] + " ");
          }
          System.out.println();
          return;
      }
      for(int i = 1; i <= n; i++) {
          if(set.contains(i)) continue;
          else {
              set.add(i);
              path[index] = i;
              dfs(n, path, index + 1, set);
              set.remove(i);
          }
      }
  }

N Queens

public static void dfs(int[] row, int[] col, int[]dg, int[] adg, char[][] base, int cr) {
      int n = row.length;
      //System.out.println(cr);
      if(cr == n) {
          for(int i = 0; i <  base.length; i++) {
              for(char c : base[i]) System.out.print(c + "");
              System.out.println();
          }
          System.out.println();
          return;
      }
      for(int i = 0; i < n; i++) {
          if(col[i] == 0 && dg[i + cr] == 0 && adg[n - i + cr] == 0) {
              base[cr][i] =  'Q';
              col[i] = 1; dg[i + cr] = 1; adg[n - i + cr] = 1;
              dfs(row, col, dg, adg, base, cr + 1);
              col[i] = 0; dg[i + cr] = 0; adg[n - i + cr] = 0;
              base[cr][i] = '.';
          }
      }
  }

BFS

当边权值为1的时候，才可以用bfs求最短路

走迷宫

static int[] dx = {1, -1, 0, 0};
  static int[] dy = {0, 0, 1, -1};
  public static int bfs(int[][] grid, int n, int m) {
      Queue<Integer> queue = new LinkedList<>();
      Set<Integer> set = new HashSet<>();
      queue.add(0); set.add(0);
      int step = 0;
      while(!queue.isEmpty()) {
          int size = queue.size();
          while(size > 0) {
              int cur = queue.poll();
              int x = cur / m, y = cur % m;
              if(x == n - 1 && y == m - 1) return step;
              for(int i = 0; i < 4; i++) {
                  int nx = x + dx[i], ny = y + dy[i];
                  if(nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == 1) continue;
                  int next = nx * m + ny;
                  if(!set.contains(next)) {
                      set.add(next);
                      queue.offer(next);
                  }
              }
              size--;
          }
          step++;
      }
      return -1;
  }

八数码

static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, 1, -1};
public static int bfs(String state, String dest) {
   Queue<String> queue = new LinkedList<>();
   queue.add(state);
   Map<String, Integer> map = new HashMap<>();
   map.put(state, 0);
   while(!queue.isEmpty()) {
       String cur = queue.poll();
       //System.out.print(cur+ " ");
       if(cur.equals(dest)) return map.get(cur);

       int index = cur.indexOf('x');
       int x = index / 3, y = index % 3;
       for(int i = 0; i < 4; i++) {
           int nx = x + dx[i], ny = y + dy[i];
           if(nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
           int nidx = nx * 3 + ny;

           char[] arr = cur.toCharArray();
           arr[index] = arr[nidx];
           arr[nidx] = 'x';
           String ns = new String(arr).trim();
           if(!map.containsKey(ns)) {
               queue.add(ns);
               map.put(ns, map.get(cur) + 1);
           }
       }
   }
   return -1;
}

图的存储

树：连通无环图

邻接矩阵
邻接表

树与图的深度优先遍历

ACW846
static int ret = Integer.MAX_VALUE;
public static int dfs(List[] graph, int n, int cur, Set<Integer> set) {
    int sum = 0, max = 0;
    //set.add(cur);
    for(Object item : graph[cur]) {
        int i = (int)item;
        if(set.contains(i)) continue;
        set.add(i);
        int num = dfs(graph, n, i, set) ;
        max = Math.max(num, max);
        sum += num;
    }
    //if(sum == 0) return 0;
    max = Math.max(n - sum - 1, max);
    ret = Math.min(max, ret);
    return sum + 1;

}

树与图的广度优先遍历

public static int bfs(Set[] graph, int start, int dest) {
     Queue<Integer> queue = new LinkedList<>();
     Map<Integer, Integer> map = new HashMap<>();
     queue.add(start);
     map.put(start, 0);
     while(!queue.isEmpty()) {
         int cur = queue.poll();
         if(cur == dest) return map.get(cur);
         for(Object item : graph[cur]) {
             int i = (int)item;
             if(map.containsKey(i)) continue;
             queue.add(i);
             map.put(i, map.get(cur) + 1);
         }
     }
     return -1;
 }

拓扑序列

有向无环图一定存在拓扑序

public static int[] tsort(List<Integer>[] graph, int[] degree) {
    int n = degree.length;
    int[] ret = new int[n];
    int idx = -1;
    Queue<Integer> queue = new LinkedList<>();
    for(int i = 1; i < n; i++) {
        if(degree[i] == 0) queue.add(i);
    }
    while(!queue.isEmpty()) {
        int cur = queue.poll();
        ret[++idx] = cur;
        for(int item : graph[cur]) {
            degree[item]--;
            if(degree[item] == 0) queue.add(item);
        }
    }
    if(idx == n - 2) return ret;
    else return new int[0];
}

最短路

单源最短路
1. 只有正边(n 点 m 边)
  - 朴素 Dijkstra 算法 O(n^2) 边多的话，可以用这个
  - 堆优化版 Dijkstra 算法 O(mlogn) 稀疏图可用这个
2. 存在负边
  - Bellman-Ford O(nm)
    这个算法可以用来找负环。但是一般不用。
- SPFA 这个是bellman的优化版但是不能解决不超过k条边的最短路 O(m), 最坏O(nm)
多源最短路
- Floyd 算法 O(n^3)

Dijkstra O(n^2)

public static int dijkstra(int[][] graph) {
    int n = graph.length;
    boolean[] visited = new boolean[n];
    int[] dist = new int[n];
    Arrays.fill(dist,  0x3f3f3f3f);
    dist[1] = 0;

    for(int i = 1; i < n - 1; i++) {
        int t = -1;
        for(int j = 1; j < n; j++) {
            if(!visited[j] && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }
        }
        for(int j = 1; j < n; j++) {
            dist[j] = Math.min(dist[j], dist[t] + graph[t][j]);
        }
        visited[t] = true;
    }
    return dist[n - 1];
}

Dijkstra (O(Elog(E)))

public static int dijkstra(List<int[]>[] graph, int dest) {
   Set<Integer> visited = new HashSet<>();
   PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
   pq.offer(new int[]{1 , 0});
   while(!pq.isEmpty()) {
       int[] cur = pq.poll();
       if(visited.contains(cur[0])) continue; //已经算过的点可以直接跳过
       visited.add(cur[0]);
       if(cur[0] == dest) return cur[1];
       for(int[] item : graph[cur[0]]) {
           if(!visited.contains(item[0])) {
               pq.offer(new int[]{item[0], item[1] + cur[1]});
           }
       }
   }
   return -1;
}

Bellman-Ford O(nm)

有负环回路的话，则最短路径有可能不存在。可以找出负环，但是一般不用这个算法来做。有边数限制的最短路，必须用这个解

public static int bellman_ford(List<int[]> edges, int n, int m, int k) {
      int INF = Integer.MAX_VALUE;
      int[] dist = new int[n + 1];
      Arrays.fill(dist, INF);
      dist[1] = 0;
      for(int i = 0; i < k; i++) {
          int[] prev = dist.clone();
          //要copy数组，防止被数据被误用更新
          for(int[] item : edges) {
              if(prev[item[0]] != INF && dist[item[1]] > prev[item[0]] + item[2]) {
                  dist[item[1]] = prev[item[0]] + item[2];
              }
          }
      }
      return dist[n];
  }

SPFA

因为 Bellman每次都需要对所有的边进行更新。其实是没必要的。只需要存储每次变化的点就行

public static int spfa(List<int[]>[] graph, int dest) {
     Set<Integer> visited = new HashSet<>();
     int[] dist = new int[dest + 1];
     Arrays.fill(dist, Integer.MAX_VALUE);
     dist[1] = 0;
     //这个set存的是队列里面是否有重点
     Queue<Integer> pq = new LinkedList<>();
     pq.offer(1);
     visited.add(1);
     while(!pq.isEmpty()) {
         int cur = pq.poll();
         visited.remove(cur);
         for(int[] item : graph[cur]) {
             if(dist[item[0]] > dist[cur] + item[1]) {
                 dist[item[0]] = dist[cur] + item[1];
                 if(!visited.contains(item[0])) {
                     pq.offer(item[0]);
                     visited.add(item[0]);
                 }
             }
         }
     }
     return dist[dest];
 }

求负环因为求的是图中是否有负环，并不是1能到的负环。所以初始值还是把所有定点都放在队列里。

public static boolean spfa(List<int[]>[] graph, int dest) {
    Set<Integer> visited = new HashSet<>();
    int[] dist = new int[dest + 1];
    int[] cnt = new int[dest + 1];
    Queue<Integer> q = new LinkedList<>();
    for(int i = 1; i <= dest; i++) {
        q.offer(i);
        visited.add(i);
    }
    while(!q.isEmpty()) {
        int cur = q.poll();
        visited.remove(cur);
        for(int[] item : graph[cur]) {
            if(dist[item[0]] > dist[cur] + item[1]) {
                dist[item[0]] = dist[cur] + item[1];
                cnt[item[0]] = cnt[cur] + 1;
                if(cnt[item[0]] >= dest) return true;
                if(!visited.contains(item[0])) {
                    q.offer(item[0]);
                    visited.add(item[0]);
                }
            }
        }
    }
    return false;
}

Floyd

这个算法其实就是一个动态规划。 d[k, i, j] 代表的是从i 点出发只经过1-k个点到j的最短路径 d[k, i, j] = d[k - 1, i, k] + d[k - 1, k , j]

//图就存在dp里
public static int[][] floyd(int[][] dp) {
    int n = dp.length;
    for(int i = 1; i < n; i++) dp[i][i] = 0;
    for(int k = 1; k < n; k++) {
       for(int i = 1; i < n; i++) {
           for(int j = 1; j < n; j++) {
               dp[i][j] = Math.min(dp[i][k] + dp[k][j], dp[i][j]);
           }
       }
    }
    return dp;
}

最小生成树

prim
prim 算法和 Dijstra 特别相似，但是一个是更新到源点的最短路径，而prim是每次挑出离当前求解过的连通集合的最短路
- 朴素法 (n^2) 稠密图
- 堆优化法 mlogn 稀疏图
Kruskal mlogn 使用并查集

Prim

public static int prim(List<int[]>[] graph, int n) {
    Set<Integer> visited = new HashSet<>();
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
    int ret = 0;
    pq.offer(new int[]{1 , 0});
    while(!pq.isEmpty()) {
        int[] cur = pq.poll();
        if(visited.contains(cur[0])) continue;
        ret += cur[1];
        visited.add(cur[0]);
        if(visited.size() == n) return ret;
        for(int[] item : graph[cur[0]]) {
            if(!visited.contains(item[0])) {
                pq.offer(item);
            }
        }
    }
    return -1;
}

Kruskal

public static boolean union(int[] uf, int x, int y) {
    int a = find(uf, x), b = find(uf, y);
    if(a == b) return false;
    uf[a] = b;
    return true;
}
public static int find(int[] uf, int x) {
    if(uf[x] == x) return x;
    uf[x] = find(uf, uf[x]);
    return uf[x];
}
public static int kruskal(List<int[]> edges, int n) {
    Collections.sort(edges, (a, b) -> a[2] - b[2]);
    int[] uf = new int[n + 1];
    for(int i = 1; i <= n; i++) uf[i] = i;
    int ret = 0;
    for(int[] e : edges) {
        if(union(uf, e[0], e[1])) {
            ret += e[2];
        }
    }
    for(int i = 1; i <= n; i++) {
        find(uf, i);
        if(i != 1 && uf[i] != uf[i - 1]) return -1;
    }
    return ret;
}

二分图

染色法判定二分图

把点集分成两边，集合内没有边，只有集合之间有边二分图当且仅当图中不含奇数环, (从起点出发到自己的路径上的点数不是奇数) 遍历图就可以了

public static boolean dfs(List<Integer>[] graph, int node, int c, int[] color) {
     color[node] = c;
     for(int i : graph[node]) {
        if(color[i] == 0) {
            if(!dfs(graph, i, 3 - c, color)) return false;

        } else if(color[i] == c) return false;
     }
     return true;
 }

匈牙利算法 O(mn)

实际运行时间远小于 O(mn)

class Main {
    public static boolean match(List<Integer>[] graph, boolean[] state, int[] matched, int node) {
        for(int i : graph[node]) {
            if(state[i]) continue;
             state[i] = true;
            if(matched[i] == 0 || match(graph, state, matched, matched[i])) {
                matched[i] = node;
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(),  m = scan.nextInt(), k = scan.nextInt();
        List<Integer>[] graph = new List[n + 1];
        for(int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        while(k > 0) {
            int x = scan.nextInt(), y = scan.nextInt();
            graph[x].add(y);
            k--;
        }
        boolean[] state = new boolean[m + 1];
        int[] matched = new int[m + 1];
        int ret = 0;
        for(int i = 1; i <= n; i++) {
            Arrays.fill(state, false);
            if(match(graph, state, matched, i)) ret++;
        }
        System.out.println(ret);
    }

}

数学知识

质数

质数：大于1的整数，如果只包含自己和1的约数，就是质数。

试除法判定质数:

i < n / i 写成除法可以防止溢出。时间复杂度sqrt(n)

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

试除法分解质因式

试除法从小到大枚举所有数 n 中最多只有一个大于sqrt n. 时间复杂度 logn ～ sqrt(n)

//log n ~ 根号n
public static void solve(int n) {
    //n中只包含一个大于 根号n的数。
    for(int i = 2; i <= n / i; i++) {
        if(n % i == 0) { // i一定是质数
            int s = 0;
            while(n % i == 0) {
                n /= i;
                s++;
            }
            System.out.println(i + " " + s);
        }
    }
    if(n > 1) System.out.println(n + " " + 1);
    System.out.println();
}

筛质数

埃氏筛法 2-p-1 的所有质数倍数标记
1～n 中有 n/ln(n)个质数。 n(1 + 1/2 + 1/4 + … + 1/n) = nln(n)/ln(n) 约等于 O(n) 确切 O(nloglogn)

public static int solve(int n) {
 int cnt = 0;
 boolean st[] = new boolean[n + 1];
 for(int i = 2; i <= n; i++) {
     if(st[i]) continue;
     cnt++;
     for(int j = i + i; j <= n; j += i) st[j] = true;
 }
 return cnt;
}

线性筛法 n只会被最小质因子筛掉 break 语句执行的时候就是找i的最小质因子prime[j]了。假设break 不成立，prime[j]不是i的质因子，那么prime[j] 就是prime[j * i] 的最小质因子。因此，n只会被最小质因子筛掉

public static int solve(int n) {
 int cnt = 0;
 int[] prime = new int[n + 1];
 boolean st[] = new boolean[n + 1];
 for(int i = 2; i <= n; i++) {
     if(!st[i]) prime[cnt++] = i;
     for(int j = 0; prime[j] <= n / i; j++) {
         st[prime[j] * i] = true;
         if(i % prime[j] == 0) break;
     }
 }
 return cnt;
}

约数

试除法

public static void get_divisors(int n) {
  List<Integer> ret = new ArrayList<>();
  for(int i = 1; i <= n / i; i++) {
      if(n % i == 0) {
          ret.add(i);
          if(i != n / i) ret.add(n/i);
      }
  }
}

约数个数

求约数的个数和约数之后，都需要用到质因子的个数。设 n = $p_{1}^{a1} * p_{2}^{a2} ,…, * p_{n}^{an}$ 因为对每一个约数都可以从每一个项中选出对应的指数组成，那么约数的个数就是 $(a1 + 1) * (a2 + 1) … * (an + 1)$
约数之和的话就是$(p_{1}^{0} +,…, + p_{1}^{a1})…(p_{n}^{0} +,…, + p_{n}^{an})$

public static void solve(int n, Map<Integer, Integer> map) {
    for(int i = 2; i <= n / i; i++) {
        int cnt = 0;
        while(n % i == 0) {
            cnt++;
            n /= i;
        }
        if(cnt != 0) {
            map.putIfAbsent(i, 0);
            map.put(i, map.get(i) + cnt);
        }
    }
    if(n > 1) {
       map.put(n, map.getOrDefault(n, 0) + 1);
    }
}

约数之和

for(int k : map.keySet()) {
    int v = map.get(k);
    long t = 1;
    while(v > 0) {
        t = (t * k + 1) % mod;
        v--;
    }
    ret = ret * t % mod;
}
System.out.println(ret);

欧几里得算法 gcd

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

欧拉函数

欧拉函数求的是 1~n中和n互质的个数 N - N /p1 - N/p2 … N/pk + N/p1p2 … N/pxpy … - N/p1p2p3 +…N/p1p2p3p4 加上 pi * pj的倍数在减去三个数的倍数 …

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

筛法求欧拉函数

public static long[] solve(int n) {
    int cnt = 0;
    int[] prime = new int[n + 1];
    long[] euler = new long[n + 1];
    euler[1] = 1;
    boolean st[] = new boolean[n + 1];
    for(int i = 2; i <= n; i++) {
        if(!st[i]) {
            prime[cnt++] = i;
            euler[i] = i - 1;
        }
        for(int j = 0; prime[j] <= n / i; j++) {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) {
                euler[prime[j] * i] = prime[j] * euler[i];
                break;
            }
            euler[prime[j] * i] = euler[i] * (prime[j] - 1);
        }
    }
    return euler;
}

快速幂

求a的b次方mod p

public static long solve(int a, int b, int p) {
    long ret = 1;
    long base = a;
    while(b != 0) {
        if(b % 2 == 1) ret = (ret * (base % p)) % p;
        base = base * base % p;
        b /= 2;
    }
    return ret;
}

求逆元

求 a 模p 的乘法逆元就等于求 a的p-2 次方模p。注意a和p必须互质。否则逆元不存在。

long ret = solve(a, p - 2, p);
if(a % p == 0) System.out.println("impossible");
else System.out.println(ret);

扩展欧几里得算法

exgcd

裴蜀定理：对于任意一对正整a, b 那么一定存在非零整数 x, y 使得 ax + by = gcd(a, b)

public static int[] exgcd(int a, int b) {
      if(b == 0) {
          return new int[]{a, 1, 0};
      }
      int[] vals = exgcd(b, a % b);
      int d = vals[0], x = vals[2], y = vals[1] - a / b * x;
      return new int[]{d, x, y};
  }

线性同余方程

$ax \equiv b(mod m)$ 代表的意思就是 ax 模 m 等于 b, 由此可推出

ax = my + b
ax - my = b
ax + my'= d 根据裴蜀定理，x y 有解的话，d可以整除 a,m 的最大公约数

所以求出x的时候乘以 d/b 倍即可

int a = scan.nextInt(), b = scan.nextInt(), m = scan.nextInt();
int[] ret = exgcd(a, m);
if(b % ret[0] != 0) System.out.println("impossible");
else System.out.println((long)b / ret[0] * ret[1] % m);

中国剩余定理

zzz

高斯消元

枚举每一列

找到绝对值最大的一行
换到最上面
将该行第一个数变成1
将剩余行当前列消成0 最后倒着把答案推出来

public static int gauss(double[][] a, int n) {
    int c, r;
    double eps = 1e-6;
    for(c = 0, r = 0; c < n; c++) {
        int t = r;
        for(int i = r; i < n; i++) {
            if(Math.abs(a[i][c]) > Math.abs(a[t][c])) t = i;
        }
        if(Math.abs(a[t][c]) < eps) continue;
        for(int i = c; i < n + 1; i++) {
            double tmp = a[r][i];
            a[r][i] = a[t][i];
            a[t][i] = tmp;
        }
        for(int i = n; i >= c; i--) a[r][i] /= a[r][c];
        for(int i = r + 1; i < n; i++) {
            if(Math.abs(a[i][c]) > eps) {
                for(int j = n; j >= c; j--) {
                    a[i][j] -= a[r][j] * a[i][c];
                }
            }
        }
        r++;
        //print(a);
    }
    if(r < n) {
        for(int i = r; i < n; i++) {
            if(Math.abs(a[i][n]) > eps) return 2;
        }
        return 1;
    }
    for(int i = n - 1; i >= 0; i--) {
        for(int j = i + 1; j < n; j++) {
            a[i][n] -= a[j][n] * a[i][j];
        }
    }
    return 0;
}

求组合数

$C_{n}^{r} = \frac{n!}{r!(n - r)!} $
$C(n,k) = C(n-1,k) + C(n-1,k-1)$

组合数I

public static void init(int[][] dp) {
   for(int i = 0; i < dp.length; i++) {
       for(int j = 0; j <= i; j++) {
           if(j == 0) dp[i][j] = 1;
           else dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) %1000000007;
       }
   }
}

组合数II

public class Main {
    static int N = 100010, mod = (int)1e9 + 7;
    static long face[] = new long[N], inface[] = new long[N];

    static long helper(long a, long b, long p) {
        long ret = 1;
        while (b != 0) {
            if ((b & 1) == 1) ret = ret * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return ret;
    }

    public static void main(String args[]) {   
        Scanner in = new Scanner(System.in);
        face[0] = inface[0] = 1;
        for (int i = 1; i < N; i++) {
            face[i] = face[i - 1] * i % mod;
            inface[i] = inface[i - 1] * helper(i, mod - 2, mod) % mod;
        }
        int n = in.nextInt();
        while (n > 0) {
            int a = in.nextInt(), b = in.nextInt();
            System.out.println(face[a] * inface[a - b] % mod * inface[b] % mod);
            n--;
        }
    }
}

卡特兰数

$C_{2n}^{n} - C_{2n}^{n-1} = \frac{C_{2n}^{n}}{n + 1}$

class Main {
    public static long helper(long a, long b, long p) {
        long ret = 1;
        while(b != 0) {
            if (b % 2 == 1) ret = (ret * a % p) % p ;
            a = a * a % p;
            b >>= 1;
        }
        return ret;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long b = scan.nextLong() , a = 2 * b;
        long mod = 1000_000_007;
        long ret = 1;
        for(long i = a; i > a - b; i--) ret = ret * i % mod;
        for(long i = 1; i <= b; i++) ret = ret * helper(i, mod - 2, mod) % mod;
        ret = ret * helper(b + 1, mod - 2, mod) % mod;
        System.out.println((int) ret);
    }
}

容斥原理

public static int solve(int[] p, int n) {
  int ret = 0, m = p.length;
  for(int i = 1; i < 1 << m; i++) {
      int t = 1, cnt = 0;
      for(int j = 0; j < m; j++) {
          if((i >> j & 1) == 1) {
              if ((long) t * p[j] > n) {
                  t = -1;
                  break;
              }
              t *= p[j];
              cnt++;
          }
      }
      if(t != -1) {
          if(cnt % 2 == 1) ret += n / t;
          else ret -= n / t;
      }
  }
  return ret;
}

博弈论

公平组合游戏ICG

这部分总结来自这里. 若一个游戏满足： 1.由两名玩家交替行动； 2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关； 3.不能行动的玩家判负；

则称该游戏为一个公平组合游戏。 NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即： mex(S) = min{x}, x属于自然数，且x不属于S

SG函数

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即： SG(x) = mex({SG(y1), SG(y2), …, SG(yk)}) 特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。终点SG函数的值为0. 例子

Nim 游戏

如果异或石子个数不为零, 先手必胜。把两堆石子拿成一样的状态，然后和对手保持一致

for(int i  = 0; i < n; i++) {
    ret ^= scan.nextInt();
}

台阶 Nim 游戏

for(int i  = 0; i < n; i++) {
    int x = scan.nextInt();
    if(i % 2 == 0) ret ^= x;
 }

集合 Nim 游戏

public static int sg(int x, int[] f, int[] actions) {
   if(f[x] != -1) return f[x];
   Set<Integer> set = new HashSet<>();
   for(int i = 0; i < actions.length; i++) {
       int cur = actions[i];
       if(x >= cur) set.add(sg(x - cur, f, actions));
   }
   int i = 0;
   while(set.contains(i)) i++;
   f[x] = i;
   return f[x];
}

拆分 Nim

public static int sg(int x, int[] f) {
    if(f[x] != -1) return f[x];
    Set<Integer> set = new HashSet<>();
    for(int i = 0; i < x; i++) {
        for(int j = 0; j <= i; j++) set.add(sg(i, f) ^ sg(j, f));
    }
    int i = 0;
    while(set.contains(i)) i++;
    f[x] = i;
    return f[x];
}

动态规划

背包问题

01背包

每个物品只可用一次。

class Main {
    public static int solve(int[] w, int[] v, int W, int n) {
    int[][] dp  = new int[n + 1][W + 1];
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= W; j++) {
            dp[i][j] = dp[i - 1][j];
            if(j >= w[i]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
        return dp[n][W];
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), V = scan.nextInt();
        int[] w = new int[n + 1], v = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            w[i] = scan.nextInt();
            v[i] = scan.nextInt();
        }
        System.out.println(solve(w, v, V, n));
    }
}

完全背包

和01题目一样，但是每种物品都有无限件可用

public static int solve(int[] w, int[] v, int W, int n) {
     int[][] dp  = new int[n + 1][W + 1];
     for(int i = 1; i <= n; i++) {
         for(int j = 0; j <= W; j++) {
             dp[i][j] = dp[i - 1][j];
             if(j >= w[i]) dp[i][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]);

         }
     }
     return dp[n][W];
 }

多重背包

每个物品都有x个

public static int solve(int[] w, int[] v, int W, int n, int[] cnt) {
     int[][] dp  = new int[n + 1][W + 1];
     for(int i = 1; i <= n; i++) {
         for(int j = 0; j <= W; j++) {
             for(int k = 0; k * w[i] <= j && k <= cnt[i]; k++) {
                 dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
             }
         }
     }
     return dp[n][W];
}

多重背包 II

二进制优化。

class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int N = 12010, M = 2010;
        int[] w = new int[N], v = new int[N], f = new int[M];

        int cnt = 0;
        for(int i = 1; i <= n; i++) {
            int a = scan.nextInt(), b = scan.nextInt(), s = scan.nextInt();
            int k = 1;
            while(k <= s) {
                cnt++;
                w[cnt] = a * k;
                v[cnt] = b * k;
                s -= k;
                k *= 2;
            }
            if(s > 0) {
                cnt++;
                w[cnt] = a * s;
                v[cnt] = b * s;
            }
        }
        n = cnt;  
        for(int i = 1; i <= n; i++) {
            for(int j = m; j >= w[i]; j--) {
                f[j] = Math.max(f[j],  f[j - w[i]] + v[i]);
            }
        }
        System.out.println(f[m]);
    }
}

分组背包

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = 110;
        int[][] v = new int[N][N], w = new int[N][N];
        int[] f = new int[N], s = new int[N];
        int n = scan.nextInt(), m = scan.nextInt();

        for(int i = 1; i <= n; i++) {
            s[i] = scan.nextInt();
            for(int j = 0; j < s[i]; j++) {
                w[i][j] = scan.nextInt();
                v[i][j] = scan.nextInt();
            }
        }
        for(int i = 1; i <= n; i++) {
            for(int j = m; j >= 0; j--) {
                for(int k = 0; k < s[i]; k++) {
                    if(j >= w[i][k]) f[j] = Math.max(f[j], f[j - w[i][k]] + v[i][k]);
                }
            }
        }
        System.out.println(f[m]);
    }
}

线性DP

数字三角形

最长上升子序列

O(n^2)

public static int solve(int[] arr) {
    int n = arr.length;
    int[] dp = new int[n];
    int ret = 0;
    Arrays.fill(dp, 1);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(arr[j] < arr[i]) dp[i] = Math.max(dp[j] + 1, dp[i]);  
        }
        ret = Math.max(dp[i], ret);
    }
    return ret;
}

最长上升子序列II

O(nlogn)

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        int[] dp = new int[n + 10];
        int ret = 0;
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = Integer.MIN_VALUE;

        for(int i = 0; i < n; i++) {
            int l = 0, r = n;
            while(l < r) {
                int mid = l + (r - l) / 2;
                if(dp[mid] < arr[i]) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            ret = Math.max(ret, r);
            dp[r] = arr[i];
        }
        System.out.println(ret);
    }
}

最长公共子序列

public static int solve(char[] str1, char[] str2) {
    int n = str1.length, m = str2.length;
    int[][] dp = new int[n + 1][m + 1];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return dp[n][m];
}

LCS 最长subsequent 如果有一个串是 distinct，那么可以用LIS 来优化

class Solution {
    public int minOperations(int[] t, int[] a) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < t.length; i++) {
            map.put(t[i], i);
        }
        List<Integer> tmp = new ArrayList<>();

        for(int i = 0; i < a.length; i++) {
            if(map.containsKey(a[i])) tmp.add(map.get(a[i]));
        }

        int[] lis = new int[tmp.size() + 2];
        Arrays.fill(lis, Integer.MAX_VALUE);
        lis[0] = Integer.MIN_VALUE;
        int len = 0;
        for(int i = 0; i < tmp.size(); i++) {
            int l = 0, r = lis.length;
            while(l < r) {
                int mid = l + (r - l) / 2;
                if(lis[mid] < tmp.get(i)) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            len = Math.max(len, r);
            lis[r] = tmp.get(i);       
        }
        return t.length - len;
    }
}

最短编辑距离

初始化

public static int solve(char[] str1, char[] str2) {
      int n = str1.length, m = str2.length;
      int[][] dp = new int[n + 1][m + 1];
      for (int i = 0; i <= m; i ++ ) dp[0][i] = i;
      for (int i = 0; i <= n; i ++ ) dp[i][0] = i;
      for(int i = 1; i <= n; i++) {
          for(int j = 1; j <= m; j++) {
              dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + 1;
              if(str1[i - 1] == str2[j - 1]) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
              else dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
          }
      }
      return dp[n][m];
  }

区间DP

石子合并

左闭右开版本

public static int solve(int[] s) {
    int n = s.length;
    int[] sum = new int[n + 1];
    for(int i = 1; i <= n; i++) sum[i] += sum[i - 1] + s[i - 1];
    int[][] dp = new int[n + 1][n + 1];
    for(int[] d : dp) Arrays.fill(d, Integer.MAX_VALUE / 2);
    for(int i = 0; i < n; i++) dp[i][i+1] = 0;
    for(int len = 2; len <= n; len++) {
      for(int i = 0; i + len <= n; i++) {
          int j = i + len;
          for(int k = i + 1; k < j; k++) {
              dp[i][j] = Math.min(dp[i][k] + dp[k][j] + sum[j] - sum[i], dp[i][j]);
          }
      }
    }
    return dp[0][n];
}

计数DP

整数划分

完全背包

public static int solve(int n) {
     int[][] dp = new int[n + 1][n + 1];
     dp[0][0]= 1;
     for(int i = 1; i <= n; i++) {
         for(int j = 0; j <= n; j++) {
             dp[i][j] = dp[i - 1][j];
             if(j >= i) dp[i][j] = (dp[i][j] + dp[i][j - i]);
         }
     }
     return dp[n][n];
 }

数位统计 DP

计数问题

import java.util.*;
class Main {
    public static int get(List<Integer> list, int l, int r) {
        int ret = 0;
        for(int i = l; i >= r; i--) {
            ret = ret * 10 + list.get(i);
        }
        return ret;
    }
    public static int pow(int x) {
        int ret = 1;
        while(x > 0) {
            ret *= 10;
            x--;
        }
        return ret;
    }

    public static int count(int n, int x) {
        if(n == 0) return 0;
        int ret = 0;
        List<Integer> num = new ArrayList<>();
        while(n != 0) {
            num.add(n % 10);
            n /= 10;
        }
        n = num.size();
        //最高位不能为0
        for(int i = n - 1- (x == 0 ? 1 : 0); i >= 0; i--) {
            if(i < n - 1) {
                ret += get(num, n - 1, i + 1) * pow(i);
                if(x == 0) ret -= pow(i);
            }
            if(num.get(i) == x) ret += get(num, i - 1, 0) + 1;
            else if(num.get(i) > x) ret += pow(i);
        }
        return ret;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a, b;
        while(true) {
            a = scan.nextInt();
            b = scan.nextInt();
            if(a == 0 && b == 0) break;
            if(a > b) {
                int tmp = a;
                a = b;
                b= tmp;
            }
            for(int i = 0; i <= 9; i++) {
                System.out.print(count(b, i) - count(a- 1, i) + " ");
            }
            System.out.println();
        }
    }
}

状态压缩DP

蒙德里安的梦想

public static long solve(int n, int m) {
    long[][] dp = new long[1 << n][m + 1];
    //init state.
    boolean[] state = new boolean[1 << n];
    Arrays.fill(state, true);
    for(int i = 0; i <  1 << n; i++) {
        int cnt = 0;
        for(int j = 0; j < n; j++) {
            if((i >> j & 1) == 1) {
                if(cnt % 2 == 1) state[i] = false;
                cnt = 0;
            } else cnt++;
        }
        if (cnt % 2 == 1) state[i] = false;
    }
    dp[0][0] = 1;
    for(int i = 1; i <= m; i++) {
        for(int j = 0; j < 1 << n; j++) {
            for(int k = 0; k < 1 << n; k++) {
                //新的一行没有出头，和要放的1*2 方块没有使得前一列不合法。
                if((j & k) == 0 && state[j | k]) {
                    dp[j][i] += dp[k][i - 1];
                }
            }
        }
    }
    return dp[0][m];
}

最短Hamilton路径

public static void solve(int[][] graph) {    
    int[][] dp = new int[1 << n][n];
    for(int[] arr : dp) Arrays.fill(arr, Integer.MAX_VALUE/3);
    dp[1][0] = 0;
    //dp代表：从起点0 到 j点经过i二进制点集的最短距离
    for(int i = 0; i < 1 << n; i++) {
        for(int j = 0; j < n; j++) {
            if((i >> j & 1) == 1) {
                for(int k = 0; k < n; k++) {
                    if((i >> k & 1) == 1)
                        dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + graph[k][j]);
                }
            }
        }
    }
    System.out.println(dp[(1 << n) - 1][n - 1]);
}

树形DP

没有上司的舞会

public static void solve(List<Integer>[] graph, int[] happy, int root, int[][] dp) {
   dp[root][1] = happy[root];
   for(int i : graph[root]) {
       solve(graph, happy, i, dp);
       dp[root][1] += dp[i][0];
       dp[root][0] += Math.max(dp[i][0], dp[i][1]);
   }
}

记忆化搜索

滑雪

public static int solve(int[][] g, int[][] dp, int x, int y) {
    int n = g.length, m = g[0].length;  
    if(dp[x][y] != -1) return dp[x][y];
    dp[x][y] = 1;
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] < g[x][y]) {
            dp[x][y] = Math.max(dp[x][y], solve(g, dp, nx, ny) + 1);
        }
    }
    return dp[x][y];
}

贪心

区间问题

区间选点最大不相交区间数量

按照结尾点排序。

public static int solve(List<int[]> list) {
   Collections.sort(list, (a, b) -> (a[1] - b[1]));
   int ret = 1, end = list.get(0)[1];
   for(int i = 1; i < list.size(); i++) {
       if(list.get(i)[0] > end) {
           end = list.get(i)[1];
           ret++;
       }
   }
   return ret;
}

区间分组

把区间分成不同组，每组中两两区间不想交。求最小组数
把区间按照左端点从小到大的顺序排一下，看能加入哪个区间。并且更新区间的最大值。

public static int solve(List<int[]> list) {
    Collections.sort(list, (a, b) -> (a[0] - b[0]));
    PriorityQueue<Integer> pq = new PriorityQueue<>();

    for(int i = 0; i < list.size(); i++) {
        int[] cur = list.get(i);
        if(i == 0 || cur[0] <= pq.peek()) {
            pq.offer(cur[1]);
        } else {
            pq.poll();
            pq.offer(cur[1]);
        }

    }
    return pq.size();
}

区间覆盖

public static int solve(List<int[]> list, int start, int end) {
    Collections.sort(list, (a, b) -> {
        if(a[0] == b[0]) return b[1] - a[1];
        else return a[0] - b[0];

    });
    int ret = 0;
    int r = start;
    int i = 0;

    while(i < list.size()) {
        while(i < list.size() && list.get(i)[0] <= start) {
            r = Math.max(list.get(i)[1], r);   
            i++;

        }
        if(r == start) return -1;
        ret++;
        start = r;
        if(start >= end) return ret;
    }
    return -1;
}

huffuman 树

合并果子

int ret = 0;
while(pq.size() > 1) {
    int fst = pq.poll(), snd = pq.poll();
    ret += fst + snd;
    pq.offer(fst + snd);
}
System.out.println(ret);

排序不等式

排队打水

Arrays.sort(arr);
long ret = 0;
for(int i = 0; i < arr.length; i++) {
  ret += arr[i] * (n - i - 1);
}

绝对值不等式

货仓选址

class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        Arrays.sort(arr);
        long ret = 0;
        for(int i = 0; i < arr.length; i++) {
            ret += Math.abs(arr[i] - arr[n / 2]);
        }
        System.out.println(ret);
    }
}

推公式

耍杂技的牛

class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        List<int[]> cows = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            int w = scan.nextInt();
            int s = scan.nextInt();
            cows.add(new int[]{w, s, w + s});
        }
        Collections.sort(cows, (a, b) -> (a[2] - b[2]));
        int ret = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            ret = Math.max(ret, sum - cows.get(i)[1]);
            sum += cows.get(i)[0];
        }
        System.out.println(ret);
    }
}

Algorithm 101

基础算法

读入

快速排序

quicksort

find Kth largest number

Merge sort

归并排序

逆序对

二分

二分模版

数的三次方根

高精度

高精度加法

高精度减法

高精度乘法

高精度除法

前缀和与差分

一维前缀和

二维前缀和

差分数组

二维差分矩阵

双指针

最长连续不重复子序列

数组元素的目标和

判断子序列

位运算

二进制中1的个数

离散化

区间合并

数据结构

单链表

双链表

栈

队列

单调栈

滑动窗口

KMP

Trie

Trie 字符串统计

最大异或对

并查集

合并集合

连通块中点的数量

食物链

堆

堆排序

模拟堆

Hash

开放寻址法：

拉链法 ： 数组 + 单链表

字符串 hash

搜索与图论

深度优先搜索 DFS

Permutation

N Queens

BFS

走迷宫

八数码

图的存储

树与图的深度优先遍历

树与图的广度优先遍历

拓扑序列

最短路

Dijkstra O(n^2)

Dijkstra (O(Elog(E)))

Bellman-Ford O(nm)

SPFA

Floyd

最小生成树

Prim

Kruskal

二分图

染色法判定二分图

匈牙利算法 O(mn)

数学知识

质数

试除法判定质数:

试除法分解质因式

筛质数

拉链法：数组 + 单链表

区间选点最大不相交区间数量