真题解析:P9754 [CSP-S 2023] 结构体(模拟·内存对齐·嵌套结构体·地址映射)

四季读书网 2026-10-03 10:58:47 7 0

题目来源：洛谷 P9754 [CSP-S 2023] 结构体

题目大意

模拟一种类 C++ 语言的类型系统与内存布局。

基本类型有四种：byte、short、int、long，依次占据 1、2、4、8 字节，对齐要求等于自身大小。在此基础上可以定义结构体类型：给出类型名与成员列表，成员类型既可以是基本类型，也可以是先前已经定义过的结构体类型。定义类型本身不占用内存。

只有定义「元素」时才真正分配内存，所有元素从地址 0 开始依次向后排布，每个元素的起始地址要对齐到该类型对齐要求的整数倍。

排布时遵循两条规则：

• 成员按定义时给出的顺序排列，成员本身是结构体时同样如此，逐层展开。
• 每个成员的起始偏移要对齐到该成员对齐要求的整数倍；结构体的对齐要求等于所有成员对齐要求的最大值；整个结构体的大小要再向上对齐到结构体自身对齐要求的整数倍，也就是末尾要补齐。

需要处理四种操作：

1. 定义结构体类型。给定类型名与成员列表，输出该类型的大小和对齐要求，用空格分隔。
2. 定义元素。给定类型名与元素名，从内存末尾继续分配，输出新元素的起始地址。
3. 访问元素。给定形如 a.b.c 的路径，输出最内层元素的起始地址。
4. 访问地址。给定一个地址，判断是否有基本类型元素恰好占据它；若有，按操作 3 的格式输出该元素，否则输出 ERR。

输入输出样例

样例输入 #1

51 a 2short aaint ab1 b 2a balong bb2 b x3 x.ba.ab4 10

样例输出 #1

8 416 804x.bb

样例 1 中，结构体 a 的第一个成员是 short aa，占 0 到 1 字节；第二个成员 int ab 需要对齐到 4 的倍数，于是跳过 2、3 两个字节落到 4，占 4 到 7。结构体 a 的对齐要求取成员最大值 4，当前结束位置 8 恰好是 4 的倍数，所以大小为 8。

结构体 b 的第一个成员是 a ba，占 0 到 7；第二个成员 long bb 需要对齐到 8 的倍数，占 8 到 15。b 的对齐要求是 8，大小为 16。

元素 b x 从地址 0 开始。访问 x.ba.ab 时，先由 x 的起始地址 0 加上 ba 在 b 中的偏移 0 得到 0，再加上 ab 在 a 中的偏移 4，结果为 4。地址 10 落在 x 内部相对偏移 10 处，已经越过了 ba 的 0 到 7，落在 bb 的 8 到 15 区间内，因此输出 x.bb。

样例输入 #2

101 a 4int aashort ablong acbyte ad1 b 4a baint bbshort bca bd2 b x2 a y3 x.bd.ab3 x.ba3 y.ac4 424 204 100

样例输出 #2

24 856 805636064x.bd.acERRERR

样例 2 的两个 ERR 来源不同。结构体 a 依次放入 int、short、long、byte 四个成员，最后一个成员 ad 只占偏移 16 这一个字节，为了让整个结构体对齐到 8，17 到 23 是被补齐出来的空隙。地址 20 恰好落在 x.bd 内部这个空隙里，逐层下降时找不到任何成员覆盖它，于是输出 ERR。地址 100 则完全超出了所有元素占据的范围。

考点梳理

知识点	在本题的用途
模拟与精细实现	四种操作、多级访问路径、对齐规则都要照着定义逐步实现，没有算法上的捷径
内存对齐与向上取整	成员偏移、结构体大小、元素起始地址三处都要对齐到整数倍，统一用同一个取整函数
嵌套结构体与类型表	成员类型可以是先前定义的结构体，需要存下每种类型的成员表、大小与对齐要求
映射与反向索引	类型名到类型定义、元素名到起始地址、起始地址到元素名，三张表分别服务不同的操作
层次结构上的逐层下降	按名字访问与按地址反查，本质上都是在类型的层次结构里一层层往下找
有序容器与上界查找	按地址反查时先用起始地址的有序索引定位候选元素，再逐层下降
64 位整数	结构体大小与地址可达 10 的 18 次方，必须用 64 位整数存放

解题思路

一、对齐：三处取整共用同一个函数

设当前已经排到第 pos 个字节，要放入一个对齐要求为 a 的成员，它的起始偏移就是「不小于 pos 的最小 a 的倍数」：

roundup(pos, a) 等于 (pos + a - 1) / a * a

用整数运算写成 (x + a - 1) / a * a，其中除法向下取整。这个式子在整个题目里出现三次：计算成员在结构体内的偏移、把结构体大小补齐到对齐倍数、计算元素在全局内存中的起始地址。写成函数复用即可，不必三处各写一遍。

二、定义结构体类型：偏移累加加末尾补齐

定义类型时需要维护四样东西：成员列表、当前结束位置 pos、当前最大对齐要求 align、以及最终大小 size。

按顺序处理每个成员：

1. 查出该成员类型的大小与对齐要求。基本类型查固定的表，结构体类型查之前存下来的定义。
2. 偏移 apos 等于 roundup(pos, 成员对齐要求)。
3. 把「成员类型、成员名字、偏移 apos」记进成员列表。
4. align 取当前值与成员对齐要求的较大者。
5. pos 更新为 apos 加上该成员的大小。

所有成员处理完，还要再做一次补齐：size 等于 roundup(pos, align)。这一步对应 C++ 里的尾部填充。样例 2 中结构体 a 的结束位置是 17，补齐到 8 的倍数才是 24；漏掉这一步就会输出 17，与答案不符。

由于成员类型只能是先前定义过的结构体，类型之间的依赖关系是有向无环的，按输入顺序处理不会出现类型查不到的情况。

三、定义元素：全局地址从 0 往后推

用一个变量 p 记录下一个可分配的字节位置，初始为 0。定义元素时：

• addr 等于 roundup(p, 该类型对齐要求)，输出 addr。
• p 更新为 addr 加上该类型大小。

同时记两份索引：元素名对应「类型与起始地址」，起始地址对应元素名。前者给操作 3 用，后者给操作 4 用。

元素只向后推进，没有释放与复用，所以一个整数就能描述当前分配位置。

四、访问元素：沿类型链逐层下降

把 a.b.c 按点号切分成名字序列。第一个名字是元素名，从元素表里取出它的类型和起始地址。之后每遇到一个名字，就在当前类型的成员表里按名字查找：

• 累加偏移：addr 加上该成员在父结构体中的偏移。
• 切换类型：当前类型换成该成员的类型。

循环结束时 addr 就是最内层元素的起始地址。

这里要紧的是「当前类型」必须跟着切换，每一层查找都在新的结构体定义中进行，所以 a.b.c.d 这样的多级嵌套能自然处理。如果路径里只有一个名字，循环体不会执行，直接输出元素本身的起始地址，结果同样正确。

五、访问地址：上界查找加逐层下降

给定地址 a，先确定它落在哪个顶层元素里。把所有元素的起始地址放进有序结构，用上界查找得到「起始地址不大于 a 的最后一个元素」，记其起始地址为 s：

• 若不存在这样的元素，说明 a 比所有元素都小，输出 ERR。
• 若 a 减去 s 不小于该类型的大小，说明 a 在所有元素之外，输出 ERR。
• 否则令 rel 等于 a 减去 s，进入逐层下降。

逐层下降的过程是：当前类型还是结构体时，在它的成员表里找满足「成员偏移不大于 rel，且 rel 小于成员偏移加成员大小」的那个成员。找到就把成员名拼到路径后面，令 rel 减去该成员的偏移，相当于把坐标原点从父结构体平移到这个成员，然后切换类型继续往下。找不到成员，说明 rel 落在对齐补齐留下的空隙里，直接输出 ERR。

当当前类型变成基本类型时，说明地址确实落在一个基本类型元素上，输出拼好的完整路径。

样例 2 中地址 20 的输出就是这条逻辑的体现：20 落在 x 内部，进入结构体 a 后，a 的最后一个成员 ad 只占偏移 16 一个字节，17 到 23 是为对齐补齐出来的空隙，20 正在其中，找不到成员，输出 ERR。

六、几处容易写错的地方

• 结构体大小忘了末尾补齐，只算了最后一个成员的结束位置，样例 2 会直接暴露。
• 计算成员偏移时误用了结构体自身的对齐要求，实际上只需要按成员自己的对齐要求取整。
• 按地址反查进入下一层时忘了把 rel 减去成员偏移，导致内层用错基准坐标。
• 变量与地址之间只建了单向映射，做操作 4 时被迫遍历全部元素，既慢又容易漏判超出范围的情况。
• 地址与大小用 32 位整数存放，10 的 18 次方直接溢出。

参考代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll roundup(ll x, ll a){    return (x + a - 1) / a * a;}struct Member {    string type, name;    ll apos;};struct StructDef {    ll size = 0, align = 1;    vector<Member> mem;};map<string, ll> tsize = {{"byte", 1}, {"short", 2}, {"int", 4}, {"long", 8}};map<string, StructDef> tstct;map<string, pair<string, ll>> varaddr;map<ll, string> addrvar;ll p = 0;ll sizeOf(const string& t){    auto it = tsize.find(t);    return it != tsize.end() ? it->second : tstct[t].size;}ll alignOf(const string& t){    auto it = tsize.find(t);    return it != tsize.end() ? it->second : tstct[t].align;}int main(){    ios::sync_with_stdio(0);    cin.tie(0);    int n;    cin >> n;    while (n--) {        int op;        cin >> op;        if (op == 1) {            string s;            int k;            cin >> s >> k;            StructDef stct;            ll pos = 0;            for (int i = 0; i < k; i++) {                string t, nm;                cin >> t >> nm;                ll align = alignOf(t);                ll apos = roundup(pos, align);                stct.mem.push_back({t, nm, apos});                stct.align = max(stct.align, align);                pos = apos + sizeOf(t);            }            stct.size = roundup(pos, stct.align);            tstct[s] = stct;            cout << stct.size << ' ' << stct.align << "\n";        } else if (op == 2) {            string t, nm;            cin >> t >> nm;            ll addr = roundup(p, alignOf(t));            varaddr[nm] = {t, addr};            addrvar[addr] = nm;            p = addr + sizeOf(t);            cout << addr << "\n";        } else if (op == 3) {            string s;            cin >> s;            vector<string> vars;            string nm;            for (char c : s) {                if (c == '.') {                    vars.push_back(nm);                    nm.clear();                } else {                    nm += c;                }            }            vars.push_back(nm);            string tp = varaddr[vars[0]].first;            ll addr = varaddr[vars[0]].second;            for (int i = 1; i < (int)vars.size(); i++) {                for (auto& m : tstct[tp].mem) {                    if (m.name == vars[i]) {                        addr += m.apos;                        tp = m.type;                        break;                    }                }            }            cout << addr << "\n";        } else {            ll a;            cin >> a;            string res = "ERR";            auto it = addrvar.upper_bound(a);            if (it != addrvar.begin()) {                --it;                ll rel = a - it->first;                string tp = varaddr[it->second].first;                if (rel < sizeOf(tp)) {                    string nm = it->second;                    bool ok = true;                    while (!tsize.count(tp)) {                        bool found = false;                        for (auto& m : tstct[tp].mem) {                            ll msize = sizeOf(m.type);                            if (rel >= m.apos && rel < m.apos + msize) {                                nm += "." + m.name;                                rel -= m.apos;                                tp = m.type;                                found = true;                                break;                            }                        }                        if (!found) {                            ok = false;                            break;                        }                    }                    if (ok) res = nm;                }            }            cout << res << "\n";        }    }    return 0;}

复杂度分析

设操作次数为 n，任意结构体的成员数不超过 k，访问路径的层数不超过 d。

定义结构体类型时对 k 个成员逐一计算偏移并查表，单次代价 O(k log T)，T 是当前已定义的类型数量；定义元素只做一次取整和两次映射插入，代价 O(log n)；访问元素沿路径逐层在当前结构体的成员表里线性查找，单次代价 O(d · k)；访问地址先用一次上界查找定位顶层元素，代价 O(log n)，再逐层下降，同样不超过 O(d · k)。

由于每次访问都只在从顶层到目标的那一条链上做线性扫描，而不是展开整棵类型树，总体代价与输入规模近似同阶。空间上需要保存所有结构体的成员定义以及所有元素的地址，与输入规模同阶，远小于题目给出的 512 MB 限制。

实现上还有两点：地址与大小一律用 64 位整数，取整公式 (x + a - 1) / a * a 中的加法也不会溢出；上界查找要用能返回迭代器的有序映射，才能一次定位到候选元素。