2023 结构体 · 方案二统一类型表封装

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 3313 字
基本类型并入统一类型表，封装后实现更稳
2023
模拟
正文

// CSP-S 2023 复赛 T3 · 结构体（方案二：统一类型表封装，同复杂度更稳）
// 原题：https://oj.yecheng.tv/p/CSPS2023C
// 题意：同方案一（n ≤ 100，重点是实现质量）。
// 思路（把"基本类型"并入统一类型表）：
//   方案一在每个分支都要 if (types.count(tn)) else 基本类型——容易漏。
//   方案二初始化时把 byte/short/int/long 当作四个"预置 struct"
//   存进类型表（size = align = 1/2/4/8，无成员），之后所有操作统一
//   查表，代码路径唯一。对齐计算抽成 Ty::alignUpTo 成员函数。
//   访问路径解析也可在定义元素后预展开（把 x.a.b 的绝对偏移缓存），
//   适合操作数大的场景（本题 n ≤ 100 不需要）。
// 复杂度：O(总输入规模)。
// 易错点：
//   1. 预置基本类型后，"结构体嵌套结构体"与"结构体套基本类型"
//      的对齐/大小计算完全同构，不再有特例；
//   2. 对齐数最大值包括基本类型成员（int 成员 → align ≥ 4）；
//   3. 地址输出是"绝对地址"，查询操作不带等号；
//   4. 内存分配按定义顺序，题目保证不重名。
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
using namespace std;

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

struct Ty {
    long long size = 0;
    long long align = 1;
    vector<Member> mem;
    map<string, int> idx;              // 成员名 -> 下标
};

map<string, Ty> T;
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;
}

void initBase() {
    const char* names[] = {"byte", "short", "int", "long"};
    long long szs[] = {1, 2, 4, 8};
    for (int i = 0; i < 4; i++) {
        Ty t;
        t.size = t.align = szs[i];
        T[names[i]] = t;
    }
}

int main() {
    freopen("struct.in", "r", stdin);
    freopen("struct.out", "w", stdout);
    initBase();
    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;
            long long cur = 0;
            for (int i = 0; i < k; i++) {
                char tn[16], mn[16];
                scanf("%s%s", tn, mn);
                long long al = T[tn].align;
                long long sz = T[tn].size;
                cur = alignUp(cur, al);
                ty.idx[mn] = (int)ty.mem.size();
                ty.mem.push_back({mn, cur});
                ty.align = max(ty.align, al);
                cur += sz;
            }
            ty.size = alignUp(cur, ty.align);
            T[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 addr = alignUp(memTop, T[tn].align);
            memTop = addr + T[tn].size;
            elems[en] = make_pair(addr, string(tn));
            printf("%lld\n", addr);
        } else if (op == 3) {
            char path[64];
            scanf("%s", path);
            long long addr = 0;
            string cur;
            string ty;
            for (char* tok = strtok(path, "."); tok; tok = strtok(NULL, ".")) {
                cur = tok;
                if (ty.empty()) {
                    addr = elems[cur].first;
                    ty = elems[cur].second;
                } else {
                    addr += T[ty].mem[T[ty].idx[cur]].off;
                    ty = T[ty].mem[T[ty].idx[cur]].name;
                    // 成员类型名需另存：Member 增存类型名（见结构体定义）
                }
            }
            printf("%lld\n", addr);
        } else {
            char en[16];
            scanf("%s", en);
            printf("%lld\n", T[elems[en].second].size);
        }
    }
    return 0;
}
2023 结构体 · 方案二 统一类型表封装

正文

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

2023 结构体 · 方案二统一类型表封装
