2023 结构体 · 方案一顺序模拟

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 4092 字
顺序模拟四种内存操作，完整实现
2023
模拟
正文

// CSP-S 2023 复赛 T3 · 结构体（方案一：顺序模拟，完整实现）
// 原题：https://oj.yecheng.tv/p/CSPS2023C
// 题意：四种操作模拟内存布局：
//       1. 定义 struct：成员按序排列，每个成员对齐到自身对齐数的
//          倍数；结构体对齐数 = 成员对齐数最大值；大小补齐到对齐数
//          的倍数。基本类型：byte(1/1) short(2/2) int(4/4) long(8/8)。
//       2. 定义元素（类型可能是 struct）：分配地址（对齐）。
//       3. 访问 x.k（k 级成员路径）：输出地址。
//       4. x.addr：查询元素占用字节数。
// 思路（直接模拟）：
//   - 类型表 map<string, Ty>：Ty = {size, align, 成员列表(偏移)}；
//   - 定义 struct：cur = 0，逐成员 addr = alignUp(cur, al)，记录偏移；
//     size = alignUp(cur, align)；
//   - 定义元素：addr = alignUp(memTop, align)，memTop = addr + size；
//   - 访问：沿成员路径累加偏移。
// 复杂度：O(总输入规模)。
// 易错点：
//   1. 对齐函数 alignUp(x, a) = (x + a - 1) / a * a；
//   2. 结构体大小必须是自身对齐数的倍数（末尾补齐）；
//   3. addr ≤ 1e18 用 long long / unsigned；
//   4. 成员路径逐级解析（x.a.b.c）。
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
using namespace std;

struct Member {
    string name;
    long long off;
    int align;
};

struct Ty {
    long long size;
    int align;
    map<string, pair<long long, string> > mem;  // 名 -> (偏移, 类型名)
};

map<string, Ty> types;
map<string, pair<long long, string> > elems;    // 名 -> (地址, 类型名)
long long memTop = 0;

long long alignUp(long long x, long long a) {
    return (x + a - 1) / a * a;
}

int baseAlign(const string& t) {
    if (t == "byte") return 1;
    if (t == "short") return 2;
    if (t == "int") return 4;
    return 8;                          // long
}

long long baseSize(const string& t) {
    return baseAlign(t);
}

void splitPath(const string& path, vector<string>& out) {
    out.clear();
    string cur;
    for (char c : path) {
        if (c == '.') { out.push_back(cur); cur.clear(); }
        else cur += c;
    }
    out.push_back(cur);
}

int main() {
    freopen("struct.in", "r", stdin);
    freopen("struct.out", "w", stdout);
    int n;
    scanf("%d", &n);
    while (n--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            char name[16];
            int k;
            scanf("%s%d", name, &k);
            Ty ty;
            ty.size = 0;
            ty.align = 1;
            long long cur = 0;
            for (int i = 0; i < k; i++) {
                char tn[16], mn[16];
                scanf("%s%s", tn, mn);
                long long al, sz;
                if (types.count(tn)) {
                    al = types[tn].align;
                    sz = types[tn].size;
                } else {
                    al = baseAlign(tn);
                    sz = baseSize(tn);
                }
                cur = alignUp(cur, al);
                ty.mem[mn] = make_pair(cur, string(tn));
                ty.align = max(ty.align, (int)al);
                cur += sz;
            }
            ty.size = alignUp(cur, ty.align);
            types[name] = ty;
            printf("%lld %lld\n", ty.size, ty.align);
        } else if (op == 2) {
            char tn[16], en[16];
            scanf("%s%s", tn, en);
            long long al, sz;
            if (types.count(tn)) {
                al = types[tn].align;
                sz = types[tn].size;
            } else {
                al = baseAlign(tn);
                sz = baseSize(tn);
            }
            long long addr = alignUp(memTop, al);
            memTop = addr + sz;
            elems[en] = make_pair(addr, string(tn));
            printf("%lld\n", addr);
        } else if (op == 3) {
            char path[64];
            scanf("%s", path);
            vector<string> parts;
            splitPath(path, parts);
            long long addr = elems[parts[0]].first;
            string ty = elems[parts[0]].second;
            for (int i = 1; i < (int)parts.size(); i++) {
                addr += types[ty].mem[parts[i]].first;
                ty = types[ty].mem[parts[i]].second;
            }
            printf("%lld\n", addr);
        } else {
            char en[16];
            scanf("%s", en);
            string tn = elems[en].second;
            long long sz = types.count(tn) ? types[tn].size : baseSize(tn);
            printf("%lld\n", sz);
        }
    }
    return 0;
}
2023 结构体 · 方案一 顺序模拟

正文

CSP-S 标程 · 复赛真题的其它内容

2023 结构体 · 方案一顺序模拟
