Java 的 ACM 常用模板

适用场景

本文默认面向 OJ / ACM 模式：单文件提交、类名为 Main、通过标准输入输出读写数据。

这篇就整理一份我觉得比较实用的 Java ACM 模板，包括以下内容：

快读
快写
多组样例写法
常用数学模块
二分模板
前缀和 / 差分
并查集
图的 BFS / DFS

我建议直接粘贴：背熟一份模板，往里CV，现写太累了。

先是基础模板

最简洁的版本：

java

import java.io.*;
import java.util.*;

public class Main {
    static FastScanner fs = new FastScanner(System.in);
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int T = 1;
        // T = fs.nextInt();
        while (T-- > 0) {
            solve();
        }
        out.print(sb);
        out.flush();
    }

    static void solve() throws Exception {
        int n = fs.nextInt();
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += fs.nextLong();
        }
        sb.append(sum).append('\n');
    }

    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0;
        private int len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buffer[ptr++];
        }

        String next() throws IOException {
            StringBuilder s = new StringBuilder();
            int c;
            while ((c = read()) != -1 && c <= ' ') {
                // skip blank
            }
            if (c == -1) {
                return null;
            }
            do {
                s.append((char) c);
                c = read();
            } while (c > ' ');
            return s.toString();
        }

        String nextLine() throws IOException {
            StringBuilder s = new StringBuilder();
            int c = read();
            if (c == -1) {
                return null;
            }
            while (c != -1 && c != '\n') {
                if (c != '\r') {
                    s.append((char) c);
                }
                c = read();
            }
            return s.toString();
        }

        int nextInt() throws IOException {
            int c;
            while ((c = read()) != -1 && c <= ' ') {
                // skip blank
            }
            if (c == -1) {
                throw new EOFException();
            }
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }

        long nextLong() throws IOException {
            int c;
            while ((c = read()) != -1 && c <= ' ') {
                // skip blank
            }
            if (c == -1) {
                throw new EOFException();
            }
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            long val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}

关于这个模板：

FastScanner 用字节流读，通常比 Scanner 快。
输出统一先写进 StringBuilder，最后一次性 flush。
solve() 单独拆出来，多组样例时更顺手。
默认支持 int、long、double、String，以及按整行读取的 nextLine()。

如果题目的输出不多，其实也可以直接 out.println(ans)；但如果输出很多行，我更建议像上面这样统一 append 到 StringBuilder 里再输出。

补一句使用上的注意点：nextLine() 适合读整行文本，但如果你前面刚调用过 nextInt()、nextLong() 这类按 token 读取的方法，紧接着 nextLine() 读到的可能会是当前行剩余的空串。遇到这种题时，要么统一按行读取后自己拆分，要么先额外调用一次 nextLine() 吃掉换行。

Scanner 的优点是写起来直观，但它在 OJ 场景里有两个明显问题：

速度通常不够快，大输入量题目容易卡常。
封装层级比较高，在高频读数字时开销更大。

所以如果是笔试、竞赛、OJ 刷题，一般建议：

BufferedInputStream / BufferedReader
自己写 FastScanner
输出用 PrintWriter 或 StringBuilder

多组样例模板

很多题目是多测，推荐固定成下面这种结构：

java

public static void main(String[] args) throws Exception {
    int T = fs.nextInt();
    while (T-- > 0) {
        solve();
    }
    out.print(sb);
    out.flush();
}

如果题目不是多测，就保留：

java

int T = 1;

只改 T 的读取方式就行。

常用数学模块

常用的几个数学模块: gcd、lcm 、快速幂。

java

static long gcd(long a, long b) {
    while (b != 0) {
        long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

static long lcm(long a, long b) {
    return a / gcd(a, b) * b;
}

static long qpow(long a, long b, long mod) {
    long res = 1 % mod;
    a %= mod;
    while (b > 0) {
        if ((b & 1) == 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

是什么

gcd：最大公约数
lcm：最小公倍数
qpow：快速幂，常用于取模幂运算

如果题目里出现：

“最大公约数”
“最小公倍数”
“模意义下的幂”
“组合数预处理里的逆元”

这几个函数基本都能直接派上用场。

二分模板

java

static int lowerBound(int[] a, int target) {
    int l = 0, r = a.length;
    while (l < r) {
        int mid = (l + r) >>> 1;
        if (a[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

static int upperBound(int[] a, int target) {
    int l = 0, r = a.length;
    while (l < r) {
        int mid = (l + r) >>> 1;
        if (a[mid] > target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

其中：

lowerBound(a, x)：返回第一个 >= x 的位置
upperBound(a, x)：返回第一个 > x 的位置

如果你做的是“答案二分”，也建议把判定函数拆出来：

java

static boolean check(long mid) {
    return true;
}

static long binarySearch(long l, long r) {
    while (l < r) {
        long mid = (l + r) >>> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

这样比把判定逻辑全部塞进 while 里更不容易写乱。

前缀和模板

java

static long[] prefixSum(int[] a) {
    int n = a.length;
    long[] pre = new long[n + 1];
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + a[i];
    }
    return pre;
}

例如：

java

long[] pre = prefixSum(a);
long sum = pre[r + 1] - pre[l];

这个写法简单、稳定，而且不容易出现 off-by-one 错误。

差分模板

如果题目有大量“区间加”的操作，差分会比每次暴力修改快很多。

java

static void rangeAdd(int[] diff, int l, int r, int val) {
    diff[l] += val;
    if (r + 1 < diff.length) {
        diff[r + 1] -= val;
    }
}

static int[] buildArray(int[] diff) {
    int[] a = new int[diff.length];
    a[0] = diff[0];
    for (int i = 1; i < diff.length; i++) {
        a[i] = a[i - 1] + diff[i];
    }
    return a;
}

如果原数组长度是 n，可以：

java

int[] diff = new int[n];
rangeAdd(diff, l, r, val);
rangeAdd(diff, l2, r2, val2);
int[] a = buildArray(diff);

当题目是“做很多次区间修改，最后统一求结果”时，这套模板很常用。

并查集模板

只要题目里出现“连通块”“合并集合”“判断是否属于同一组”，基本就是并查集。

java

static class DSU {
    int[] parent;
    int[] size;

    DSU(int n) {
        parent = new int[n + 1];
        size = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    boolean union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa == fb) {
            return false;
        }
        if (size[fa] < size[fb]) {
            int t = fa;
            fa = fb;
            fb = t;
        }
        parent[fb] = fa;
        size[fa] += size[fb];
        return true;
    }

    boolean same(int a, int b) {
        return find(a) == find(b);
    }
}

邻接表模板

对于大多数图题，List<Integer>[] 这种邻接表写法已经够顺手了。

java

static List<Integer>[] buildGraph(int n) {
    List<Integer>[] g = new ArrayList[n + 1];
    for (int i = 1; i <= n; i++) {
        g[i] = new ArrayList<>();
    }
    return g;
}

static void addUndirectedEdge(List<Integer>[] g, int u, int v) {
    g[u].add(v);
    g[v].add(u);
}

static void addDirectedEdge(List<Integer>[] g, int u, int v) {
    g[u].add(v);
}

如果是带权图，可以把边单独封成类：

java

static class Edge {
    int to;
    int w;

    Edge(int to, int w) {
        this.to = to;
        this.w = w;
    }
}

然后把图改成：

java

static List<Edge>[] g;

这样 Dijkstra、最短路、树上遍历都会更方便。

BFS 模板

BFS 最常见的用途是：

无权图最短路
分层遍历
从起点向外扩散

java

static int[] bfs(List<Integer>[] g, int start) {
    int n = g.length - 1;
    int[] dist = new int[n + 1];
    Arrays.fill(dist, -1);

    ArrayDeque<Integer> q = new ArrayDeque<>();
    q.offer(start);
    dist[start] = 0;

    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : g[u]) {
            if (dist[v] != -1) {
                continue;
            }
            dist[v] = dist[u] + 1;
            q.offer(v);
        }
    }
    return dist;
}

dist[v] == -1 既可以表示“没访问过”，也能顺手记录最短距离，写起来很省事。

DFS 模板

如果题目是：

遍历整棵树
搜索联通块
递归枚举
回溯

DFS 一般就足够了。

java

static void dfs(int u, int parent, List<Integer>[] g, boolean[] vis) {
    vis[u] = true;
    for (int v : g[u]) {
        if (v == parent) {
            continue;
        }
        if (!vis[v]) {
            dfs(v, u, g, vis);
        }
    }
}

如果题目图不一定是树，parent 参数可以去掉，只保留 vis 判重即可。

不过也要注意：Java 递归层数深时可能栈溢出。

所以当你遇到：

链很长的树
深度很深的图
数据规模很大

就要考虑把递归 DFS 改成显式栈的迭代写法。

最后

没了

评论区