不插电の記録

做题步骤

先分析它的时间复杂度
出题人想要考什么算法
写代码
写测试数据

刷题网站

https://www.dotcpp.com/oj/lanqiao/
https://www.lanqiao.cn/problems/

时间复杂度

https://www.acwing.com/blog/content/32/
时间限制为1s时:

n ≤ 30 => O(2ⁿ), dfs+剪枝，状态压缩dp
n ≤ 100 => O(n³)，floyd，dp，高斯消元
n ≤ 1000 => O(n²)，O(n²logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
n ≤ 10000 => O(n∗√n)，块状链表、分块、莫队
n ≤ 100000 => O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
n ≤ 1000000 => O(n), 以及常数较小的 O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
n ≤ 10000000 => O(n)，双指针扫描、kmp、AC自动机、线性筛素数
n ≤ 10⁹ => O(√n)，判断质数
n ≤ 10¹⁸ => O(logn)，最大公约数，快速幂，数位DP
n ≤ 10¹⁰⁰⁰ => O((logn)²)，高精度加减乘除
n ≤ 10¹⁰⁰⁰⁰⁰ => O(logk×loglogk)，k表示位数，高精度加减、FFT/NTT

快读快写

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer cin = new StreamTokenizer(br);

    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }

    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }
	//只能读字母
    public static String next() throws Exception {
        cin.nextToken();
        return cin.sval;
    }

基础算法

整数二分

https://oi-wiki.org/basic/binary/#二分答案


    static boolean check(int x) {/* ... */} // 检查x是否满足某种性质

    // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
    static int bsearch_1(int l, int r) {
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (check(mid)) r = mid;    // check()判断mid是否满足性质
            else l = mid + 1;
        }
        return l;
    }

    // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
    static int bsearch_2(int l, int r) {
        while (l < r) {
            int mid = (l + r + 1) >>> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }

一维前缀和

https://oi-wiki.org/basic/prefix-sum/#前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

一维差分

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

数据结构

单调栈

https://oi-wiki.org/ds/monotonous-stack/

常见模型：找出每个数左边离它最近的比它大/小的数

int tt = 0;
int[] stk = new int[n + 1];
for (int i = 1; i <= n; i++) {
    while (tt > 0 && check(stk[tt], i)) {
        tt--;
    }
    stk[++tt] = i;
}

单调队列

https://oi-wiki.org/ds/monotonous-queue/

常见模型：找出滑动窗口中的最大值/最小值

int hh = 0, tt = -1;
int[] q = new int[n];
for (int i = 0; i < n; i++) {
    while (hh <= tt && check_out(q[hh])) {
        hh++;
    }
    while (hh <= tt && check(q[tt], i)) {
        tt--;
    }
    q[++tt] = i;
}

KMP

https://oi-wiki.org/string/kmp/

求模式串的Next数组：

int[] ne = new int[m + 1];
ne[1] = 0;
for (int i = 2, j = 0; i <= m; i++) {
    while (j != 0 && p[i] != p[j + 1]) {
        j = ne[j];
    }
    if (p[i] == p[j + 1]) {
        j++;
    }
    ne[i] = j;
}

匹配：

for (int i = 1, j = 0; i <= n; i++) {
    while (j != 0 && s[i] != p[j + 1]) {
        j = ne[j];
    }
    if (s[i] == p[j + 1]) {
        j++;
    }
    if (j == m) {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

并查集

https://oi-wiki.org/ds/dsu/

    static int n;
    static int[] p = new int[n + 1]; // 存储每个点的祖宗节点

    // 返回x的祖宗节点
    static int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    static void init() {
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
    }

    // 合并a和b所在的两个集合
    static void union(int a, int b) {
        p[find(a)] = find(b);
    }

线段树

https://oi-wiki.org/ds/seg/

    static int[] a;
    static int[] d;

    // 通过子节点计算父节点
    static int pushUp(int l, int r) {
        // 计算父节点的值
        // ...
    }

    static void build(int s, int t, int p) {
        // 对 [s,t] 区间建立线段树,当前根的编号为 p
        if (s == t) {
            d[p] = a[s];
            return;
        }
        int m = s + ((t - s) >> 1);
        // 移位运算符的优先级小于加减法，所以加上括号
        // 如果写成 (s + t) >> 1 可能会超出 int 范围


        build(s, m, p * 2);
        build(m + 1, t, p * 2 + 1);
        // 递归对左右区间建树
        d[p] = pushUp(d[p * 2], d[(p * 2) + 1]);
    }

    static int getRes(int l, int r, int s, int t, int p) {
        // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
        if (l <= s && t <= r) {
            return d[p];  // 当前区间为询问区间的子集时直接返回当前区间的和
        }
        int m = s + ((t - s) >> 1), sum = 0;
        int lv = 0, rv = 0; // 默认值
        if (l <= m) {
            lv = getRes(l, r, s, m, p * 2);
        }
        // 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
        if (r > m) {
            rv = getRes(l, r, m + 1, t, p * 2 + 1);
        }

        return pushUp(lv, rv);
    }

图论

邻接矩阵

https://oi-wiki.org/graph/save/#邻接矩阵

    static int n;
    static int[][] g = new int[n + 1][n + 1]; // 存储边a->b

    // 添加一条边a->b
    static void add(int a, int b) {
        g[a][b] = 1;
    }

邻接表

https://oi-wiki.org/graph/save/#邻接矩阵

    //n个点，m条单向边
    static int[] h = new int[n + 1]; // 存储每个点的单链表的头结点
    static int[] e = new int[m + 1]; // 存储每个点的可达点
    static int[] ne = new int[m + 1]; // 存储每个点的下一个可达点
    static int idx;

    // 添加一条边a->b
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
	// 初始化
    static void init() {
        Arrays.fill(h, -1);
    }

深度优先遍历

https://oi-wiki.org/graph/dfs/

    static int n,m;
    static boolean[] st = new boolean[n + 1]; // 表示点是否被遍历过
    static int[] h = new int[n + 1], e = new int[m + 1], ne = new int[m + 1];
    static void dfs(int u) {
        st[u] = true; // 表示点u已经被遍历过

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                dfs(j);
            }
        }
    }

宽度优先遍历

https://oi-wiki.org/graph/bfs/

Queue<Integer> q = new LinkedList<>();
boolean[] st = new boolean[n + 1]; // 表示点是否被遍历过

st[1] = true; // 表示1号点已经被遍历过
q.offer(1);

while (!q.isEmpty()) {
    int t = q.poll();

    for (int i = h[t]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            st[j] = true; // 表示点j已经被遍历过
            q.offer(j);
        }
    }
}

拓扑排序

https://oi-wiki.org/graph/topo/

//n 表示点数
Queue<Integer> q = new LinkedList<>(); // 存储拓扑序列
int[] d = new int[n + 1]; // 存储点的入度

// 统计每个点的入度
for (int i = 1; i <= n; i++) {
    for (int j = h[i]; j != -1; j = ne[j]) {
        int k = e[j];
        d[k]++;
    }
}

// 将入度为0的点入队
for (int i = 1; i <= n; i++) {
    if (d[i] == 0) {
        q.offer(i);
    }
}

while (!q.isEmpty()) {
    int t = q.poll();

    for (int i = h[t]; i != -1; i = ne[i]) {
        int j = e[i];
        if (--d[j] == 0) {
            q.offer(j);
        }
    }
}

// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
boolean hasTopologicalOrder = (tt == n - 1);

朴素Dijkstra算法

时间复杂度：O(n^2 + m), 其中 n 表示点数，m 表示边数

https://oi-wiki.org/graph/shortest-path/#dijkstra-算法

    static int n;
    static int[][] g = new int[n + 1][n + 1]; // 存储每条边
    static int[] dist = new int[n + 1]; // 存储1号点到每个点的最短距离
    static boolean[] st = new boolean[n + 1]; // 存储每个点的最短路是否已经确定

    // 求1号点到n号点的最短路，如果不存在则返回-1
    static int dijkstra() {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;

        for (int i = 0; i < n - 1; i++) {
            int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }

            // 用t更新其他点的距离
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }

            st[t] = true;
        }

        if (dist[n] == 0x3f3f3f3f) {
            return -1;
        }
        return dist[n];
    }

SPFA算法（队列优化的Bellman-Ford算法）

时间复杂度：平均情况下 O(m), 最坏情况下 O(nm), 其中 n 表示点数，m 表示边数

https://oi-wiki.org/graph/shortest-path/#队列优化spfa

    static int n, m; // 总点数, 总边数
    static int[] h = new int[n + 1];
    static int[] w = new int[m + 1];
    static int[] e = new int[m + 1];
    static int[] ne = new int[m + 1];
    static int[] dist = new int[n + 1]; // 存储每个点到1号点的最短距离
    static boolean[] st = new boolean[n + 1]; // 存储每个点是否在队列中

    // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
    static int spfa() {
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;

        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        st[1] = true;

        while (!q.isEmpty()) {
            int t = q.poll();
            st[t] = false;

            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i];
                    if (!st[j]) { // 如果队列中已存在j，则不需要将j重复插入
                        q.offer(j);
                        st[j] = true;
                    }


                }
            }
        }

        if (dist[n] == Integer.MAX_VALUE) {
            return -1;
        }
        return dist[n];
    }

SPFA判断图中是否存在负环

时间复杂度：O(nm), 其中 n 表示点数，m 表示边数

    static int n, m; // 总点数, 总边数
    static int[] h = new int[n + 1];
    static int[] w = new int[m + 1];
    static int[] e = new int[m + 1];
    static int[] ne = new int[m + 1];
    static int[] dist = new int[n + 1]; // dist[x]存储1号点到x的最短距离
    static int[] cnt = new int[n + 1]; // cnt[x]存储1到x的最短路中经过的点数
    static boolean[] st = new boolean[n + 1]; // 存储每个点是否在队列中

    // 如果存在负环，则返回true，否则返回false。
    static boolean spfa() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            q.offer(i);
            st[i] = true;
        }

        while (!q.isEmpty()) {
            int t = q.poll();
            st[t] = false;

            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1;
                    if (cnt[j] >= n) { // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                        return true;
                    }
                    if (!st[j]) {
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }

        return false;
    }

Floyd算法

时间复杂度：O(n^3), 其中 n 表示点数

https://oi-wiki.org/graph/shortest-path/#floyd-算法

    static final int INF = 0x3f3f3f3f;
    static int n; // 总点数
    static int[][] d = new int[n + 1][n + 1]; // 存储最短距离

    // 初始化
    static void init() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    d[i][j] = 0;
                } else {
                    d[i][j] = INF;
                }
            }
        }
    }

    // 算法结束后，d[a][b]表示a到b的最短距离
    static void floyd() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }

朴素版Prim算法

时间复杂度：O(n^2 + m), 其中 n 表示点数，m 表示边数

https://oi-wiki.org/graph/mst/#prim-算法

    static final int INF = 0x3f3f3f3f;
    static int n; // n表示点数
    static int[][] g = new int[n + 1][n + 1]; // 邻接矩阵，存储所有边
    static int[] dist = new int[n + 1]; //

    // 存储其他点到当前最小生成树的距离
    static boolean[] st = new boolean[n + 1]; // 存储每个点是否已经在生成树中

    // 如果图不连通，则返回INF(值是0x3f3f3f3f)，否则返回最小生成树的树边权重之和
    static int prim() {
        Arrays.fill(dist, INF);

        int res = 0;
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }

            if (i != 0 && dist[t] == INF) {
                return INF;
            }

            if (i != 0) {
                res += dist[t];
            }
            st[t] = true;

            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], g[t][j]);
            }
        }

        return res;
    }

Kruskal 算法

时间复杂度：O(m * log(m)), 其中 n 表示点数，m 表示边数

https://oi-wiki.org/graph/mst/#kruskal-算法

    static int n, m; // n是点数，m是边数
    static int[] p = new int[n + 1];
    static int[][] e = new int[m + 1][3];
    public static int find(int x) { // 并查集核心操作
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
    public static int kruskal() {
        Arrays.sort(e, 0, m, (o1, o2) -> o1[2] - o2[2]);

        for (int i = 1; i <= n; i++) {
            p[i] = i; // 初始化并查集
        }

        int res = 0, cnt = 0;
        for (int i = 0; i < m; i++) {
            int a = e[i][0], b = e[i][1], w = e[i][2];

            a = find(a);
            b = find(b);
            if (a != b) { // 如果两个连通块不连通，则将这两个连通块合并
                p[a] = b;
                res += w;
                cnt++;
            }
        }
        //没有最小生成树
        if (cnt < n - 1) {
            return Integer.MAX_VALUE;
        }
        return res;
    }

数学知识

试除法判定质数

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

试除法分解质因数

    static void divide(int x) {
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                int s = 0;
                while (x % i == 0) {
                    x /= i;
                    s++;
                }
                System.out.println(i + " " + s);
            }
        }
        if (x > 1) {
            System.out.println(x + " " + 1);
        }
        System.out.println();
    }

线性筛法求素数

https://oi-wiki.org/math/number-theory/sieve/#素数筛法

    static int n;//求小于等于n的素数
    static int[] primes = new int[n + 1]; // 存储所有素数
    static boolean[] st = new boolean[n + 1]; // 存储x是否被筛掉
    static int cnt = 0;

    static void getPrimes(int n) {
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {
                primes[cnt++] = i;
            }
            for (int j = 0; j < cnt && primes[j] <= n / i; j++) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) {
                    break;
                }
            }
        }
    }

试除法求所有约数

    static List<Integer> getDivisors(int x) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i <= x / i; i++) {
            if (x % i == 0) {
                res.add(i);
                if (i != x / i) {
                    res.add(x / i);
                }
            }
        }
        Collections.sort(res);
        return res;
    }

约数个数和约数之和

如果 N = p1^c1 * p2^c2 * … * pk^ck*
约数个数： (c1 + 1) * (c2 + 1) * … * (ck + 1)*
约数之和： (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)

欧几里得算法

求最大公因数

https://oi-wiki.org/math/number-theory/gcd/#欧几里得算法

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

求欧拉函数

欧拉函数，即 $\varphi(n)$ ，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

https://oi-wiki.org/math/number-theory/euler/

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

筛法求欧拉函数

https://oi-wiki.org/math/number-theory/sieve/#筛法求欧拉函数

    static int n;
    static int[] primes = new int[n + 1]; // 存储所有素数
    static int[] euler = new int[n + 1]; // 存储每个数的欧拉函数
    static boolean[] st = new boolean[n + 1]; // 存储x是否被筛掉
    static int cnt; // 存储素数的个数
    static void getEulers(int n) {
        euler[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {
                primes[cnt++] = i;
                euler[i] = i - 1;
            }
            for (int j = 0; j < cnt && primes[j] <= n / i; j++) {
                int t = primes[j] * i;
                st[t] = true;
                if (i % primes[j] == 0) {
                    euler[t] = euler[i] * primes[j];
                    break;
                }
                euler[t] = euler[i] * (primes[j] - 1);
            }
        }
    }

快速幂

求 m^k mod p，时间复杂度 O(log(k))。

qmi(m, p - 2, p) 等于m模p下的乘法逆元

https://oi-wiki.org/math/binary-exponentiation/

    static int qmi(int m, int k, int p) {
        int res = 1 % p;
        int t = m;
        while (k != 0) {
            if ((k & 1) == 1) {
                res = res * t % p;
            }
            t = t * t % p;
            k >>>= 1;
        }
        return res;
    }

扩展欧几里得算法

求x, y，使得ax + by = gcd(a, b)

若exgcd(a, b, x, y) == 1 则 (x[0]%b+b)%b 是a模b下的乘法逆元

https://oi-wiki.org/math/number-theory/gcd/#扩展欧几里得算法

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

线性求乘法逆元

https://oi-wiki.org/math/number-theory/inverse/

    static int n, p;
    static long[] inv = new long[n + 1];

    static void get() {
        
        inv[1] = 1;
        for (int i = 2; i <= n; ++i) {
            inv[i] = (long)(p - p / i) * inv[p % i] % p;
        }g
    }

贪心

https://oi-wiki.org/basic/greedy/

每一步行动总是按某种指标选取最优的操作。

动态规划

分析法

graph LR

A[定义问题] --> B[确定子问题]
B --> C[确定状态]
C --> D[确定状态转移方程]
D --> E[确定初始条件和边界条件]
E --> F[计算最优解]
F --> G[返回最优解]

闫氏dp分析法

https://www.acwing.com/file_system/file/content/whole/index/content/1084122/

graph LR

A[问题] --> B[状态表示]
B --> C[集合]
B --> D[属性]
A --> E[状态计算]

内容参考

https://oi-wiki.org

https://www.acwing.com/activity/content/introduction/11/

如果觉得文章对你有用，请随意赞赏

算法 java

java 算法模板

https://blog.csbxd.fun/archives/1688353083212

作者

不插电

发布于

2023-07-03

更新于

2023-07-15

许可协议

CC BY 4.0