S6 高精度与图的存储（选学

这是什么： 两件"知道就不难、不知道就完全下不了手"的事——long long 也装不下的大数怎么算，以及网格之外的图怎么存。

为什么还是要补： 两者都是 NOI 大纲入门级明文要求的（2.1.4-5 高精度、2.1.3-4 图的表示与存储）。高精度近几年 CSP-J 考得少，但在范围内；图的存储则是 CSP-J 2019 T4 加工零件、2023 T4 旅游巴士这类 T4 的入场券。

一、高精度加法

long long 最多约 9.2×10¹⁸。再大就得自己用数组模拟竖式计算。

核心两条：用数组存每一位；倒着存（个位放在下标 0）。

倒着存的理由：竖式加法从个位开始进位，倒着存的话"个位"就是 a[0]，循环从 0 往上走，进位天然朝着下标增大的方向——而且结果变长时直接往后加一位就行，不用把整个数组搬家。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s1 = "99999999999999999999";   // 20 位，long long 装不下
    string s2 = "1";

    int a[205] = {0}, b[205] = {0}, c[205] = {0};
    int la = s1.size(), lb = s2.size();

    for (int i = 0; i < la; i++) a[i] = s1[la - 1 - i] - '0';   // 倒着塞
    for (int i = 0; i < lb; i++) b[i] = s2[lb - 1 - i] - '0';

    int lc = max(la, lb);
    for (int i = 0; i < lc; i++) {
        c[i] += a[i] + b[i];
        if (c[i] >= 10) {          // 进位
            c[i] -= 10;
            c[i + 1]++;
        }
    }
    if (c[lc] > 0) lc++;           // 最高位又进了一位，总长度加一

    for (int i = lc - 1; i >= 0; i--) cout << c[i];   // 倒着输出回来
    cout << endl;                  // 100000000000000000000
    return 0;
}

📝 高精度的三步永远是：倒着读进数组 → 逐位算 + 处理进位 → 倒着打印回去。 减法、乘法只是中间那步换个算法。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s1 = "123456789", s2 = "987654321";
    int a[205] = {0}, b[205] = {0}, c[405] = {0};
    int la = s1.size(), lb = s2.size();

    for (int i = 0; i < la; i++) a[i] = s1[la - 1 - i] - '0';
    for (int i = 0; i < lb; i++) b[i] = s2[lb - 1 - i] - '0';

    for (int i = 0; i < la; i++) {           // 每一位乘每一位，先不管进位
        for (int j = 0; j < lb; j++) {
            c[i + j] += a[i] * b[j];         // 关键：a 的第 i 位乘 b 的第 j 位，落在结果第 i+j 位
        }
    }
    int lc = la + lb;
    for (int i = 0; i < lc; i++) {           // 最后统一处理进位
        if (c[i] >= 10) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    }
    while (lc > 1 && c[lc - 1] == 0) lc--;   // 去掉前导零

    for (int i = lc - 1; i >= 0; i--) cout << c[i];
    cout << endl;                            // 121932631112635269
    return 0;
}

📝 c[i + j] += a[i] * b[j] 是整个高精度乘法的灵魂：十位 × 百位落在千位，下标正好相加。先把所有乘积堆上去，最后统一进位，比边乘边进位好写得多。

⚠️ 去前导零那句 while (lc > 1 && ...) 里的 lc > 1 不能少，否则结果是 0 时会把最后一位也删掉，输出空行。

二、图的存储：邻接表

L06 和 L07 的搜索都在网格上做——"下一步"靠 dx/dy 四个方向算出来。但很多题给的是"第 u 个点和第 v 个点之间有条边"，这时候需要邻接表。

邻接表就是"每个点各挂一个 vector，里面装它能直接到达的点"：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> g[N];      // g[u] 里装的是 u 的所有邻居
int dist[N];

int main() {
    int n = 5, m = 4;
    int edges[4][2] = {{1, 2}, {1, 3}, {2, 4}, {3, 5}};

    for (int i = 0; i < m; i++) {
        int u = edges[i][0], v = edges[i][1];
        g[u].push_back(v);
        g[v].push_back(u);         // ⚠️ 无向图必须加两条！有向图只加第一条
    }

    // 从 1 号点出发做 BFS —— 框架和 L07 一字不差，只有"下一步"的写法变了
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < (int)g[u].size(); i++) {   // 这里换了：不再是 4 个方向
            int v = g[u][i];
            if (dist[v] != -1) continue;               // 入队即标记，永不撤销
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }

    for (int i = 1; i <= n; i++) cout << dist[i] << " ";
    cout << endl;                  // 0 1 1 2 2
    return 0;
}

📝 L07 的 BFS 框架一个字都不用改，只是把「枚举四个方向」换成「枚举 g[u] 里的每个邻居」。DFS 同理。这正是 L07 结尾那句"以后学：图与邻接表"承诺的东西。

三、两个坑

	网格图（L06/L07）	一般图（本补丁）
点怎么表示	坐标 `(x, y)`	编号 `u`
下一步怎么找	`dx/dy` 四个方向	遍历 `g[u]`
标记数组	`dist[x][y]`	`dist[u]`
越界检查	要（`nx < 1 \|\| nx > n`…）	不用（邻居本来就是合法的点）

g[u].push_back(v) 写了，g[v].push_back(u) 忘了——样例往往照样能过（如果样例的边恰好都是从小编号指向大编号，而你又从小编号出发搜），但换个数据就全错。这和 L06 迷宫题"忘回溯但样例照过"是同一类阴险 bug。

📝 读到"双向道路""无向边""互相连通"，立刻检查有没有写两行 push_back。

正着存的话，进位要往下标小的方向走，而且结果变长时得把整个数组往后挪一格。写出来能跑，但边界处理会多出一堆 bug。

📝 认准"个位在 a[0]"，从读入到输出全程保持这个约定，中途别切换。

四、30 秒自测

以后学： 最短路（Dijkstra、SPFA）、最小生成树、拓扑排序都建立在邻接表之上，但它们属于提高级（大纲 2.2.4-7），CSP-J 不考。

S6 高精度与图的存储（选学 · 30 分钟补丁）

一、高精度加法

二、图的存储：邻接表

三、两个坑

四、30 秒自测