[CSP-S 2023] 结构体

GitHub 跳转原题关系图返回列表

按对齐规则计算类型大小和成员偏移，再递归处理路径访问与地址反查。

OJ: luogu

题目 ID: P9754

难度:普及+/提高

标签:模拟递归哈希表

日期: 2026-07-06 08:46

题意

题目要求模拟一种简化的结构体系统，需要支持四类操作：

定义结构体类型，并输出这个类型的大小和对齐要求；
定义一个全局元素，并输出它的起始地址；
根据 a.b.c 这样的路径访问成员，输出最内层元素的起始地址；
给定一个地址，反查它是否落在某个基本类型元素内部，如果是就输出访问路径，否则输出 ERR。

基本类型 byte, short, int, long 的大小和对齐要求分别是 1,2,4,8。结构体类型的对齐要求是所有成员对齐要求的最大值。

思路

这是一道规则模拟题，朴素做法就是按照题意维护类型表、元素表和成员偏移：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178// brute.cpp：小数据朴素模拟，同样按定义顺序计算偏移并递归查找地址。
#include <bits/stdc++.h>
using namespace std;

struct MemberInfo {
    string type_name;
    string name;
    long long offset;
};

struct TypeInfo {
    string name;
    long long size;
    long long align;
    bool is_basic;
    vector<MemberInfo> members;
    map<string, int> member_id;
};

struct ElementInfo {
    string type_name;
    string name;
    long long start;
};

vector<TypeInfo> types;
vector<ElementInfo> elements;
map<string, int> type_id;
map<string, int> element_id;
long long memory_end;

long long align_up(long long x, long long a) {
    if (x % a == 0) return x;
    return x + (a - x % a);
}

void add_basic_type(const string &name, long long size) {
    TypeInfo t;
    t.name = name;
    t.size = size;
    t.align = size;
    t.is_basic = true;
    type_id[name] = (int)types.size();
    types.push_back(t);
}

vector<string> split_path(const string &s) {
    vector<string> result;
    string cur;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '.') {
            result.push_back(cur);
            cur.clear();
        } else {
            cur.push_back(s[i]);
        }
    }
    result.push_back(cur);
    return result;
}

bool find_addr_in_type(int tid, long long base, long long addr, const string &path, string &answer) {
    if (types[tid].is_basic) {
        if (base <= addr && addr < base + types[tid].size) {
            answer = path;
            return true;
        }
        return false;
    }
    for (int i = 0; i < (int)types[tid].members.size(); i++) {
        MemberInfo member = types[tid].members[i];
        int child_tid = type_id[member.type_name];
        long long child_base = base + member.offset;
        if (child_base <= addr && addr < child_base + types[child_tid].size) {
            return find_addr_in_type(child_tid, child_base, addr, path + "." + member.name, answer);
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    add_basic_type("byte", 1);
    add_basic_type("short", 2);
    add_basic_type("int", 4);
    add_basic_type("long", 8);

    int q;
    cin >> q;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            string name;
            int k;
            cin >> name >> k;

            TypeInfo t;
            t.name = name;
            t.size = 0;
            t.align = 1;
            t.is_basic = false;

            long long cur = 0;
            for (int i = 0; i < k; i++) {
                string type_name, member_name;
                cin >> type_name >> member_name;
                int tid = type_id[type_name];
                cur = align_up(cur, types[tid].align);

                MemberInfo member;
                member.type_name = type_name;
                member.name = member_name;
                member.offset = cur;
                t.member_id[member_name] = (int)t.members.size();
                t.members.push_back(member);

                cur += types[tid].size;
                t.align = max(t.align, types[tid].align);
            }

            t.size = align_up(cur, t.align);
            type_id[name] = (int)types.size();
            types.push_back(t);
            cout << t.size << ' ' << t.align << '\n';
        } else if (op == 2) {
            string type_name, name;
            cin >> type_name >> name;
            int tid = type_id[type_name];

            ElementInfo e;
            e.type_name = type_name;
            e.name = name;
            e.start = align_up(memory_end, types[tid].align);
            memory_end = e.start + types[tid].size;

            element_id[name] = (int)elements.size();
            elements.push_back(e);
            cout << e.start << '\n';
        } else if (op == 3) {
            string path;
            cin >> path;
            vector<string> parts = split_path(path);

            int eid = element_id[parts[0]];
            long long addr = elements[eid].start;
            string cur_type = elements[eid].type_name;
            for (int i = 1; i < (int)parts.size(); i++) {
                int tid = type_id[cur_type];
                int mid = types[tid].member_id[parts[i]];
                MemberInfo member = types[tid].members[mid];
                addr += member.offset;
                cur_type = member.type_name;
            }
            cout << addr << '\n';
        } else {
            long long addr;
            cin >> addr;
            string answer;
            bool ok = false;
            for (int i = 0; i < (int)elements.size(); i++) {
                int tid = type_id[elements[i].type_name];
                long long l = elements[i].start;
                long long r = l + types[tid].size;
                if (l <= addr && addr < r) {
                    ok = find_addr_in_type(tid, l, addr, elements[i].name, answer);
                    break;
                }
            }
            if (ok) cout << answer << '\n';
            else cout << "ERR\n";
        }
    }

    return 0;
}

由于操作数和成员数都不大，直接模拟已经可以作为正解。需要注意的是，结构体内部和全局元素之间都要进行对齐。

定义结构体时，从偏移 0 开始依次放置成员。设当前已经用到的位置为 cur，新成员的对齐要求为 a，那么它的起始偏移是：

text

1offset = align_up(cur, a)

放完后令：

text

1cur = offset + member_size

所有成员处理完后，结构体大小还要再对齐到结构体自身的对齐要求。

定义全局元素时同理，把当前全局内存末尾 memory_end 对齐到该元素类型的对齐要求，得到元素起始地址。

路径访问 x.ba.ab 时：

先找到全局元素 x 的起始地址和类型；
每访问一层成员，就把当前地址加上该成员在当前类型里的偏移；
当前类型变成该成员的类型。

地址反查要递归进入结构体：

如果当前类型是基本类型，并且地址落在它的范围内，就找到了答案；
如果当前类型是结构体，就检查地址落在哪个成员的范围内，再递归进入这个成员；
如果地址落在结构体对齐留下的空洞里，就输出 ERR。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207// main.cpp：模拟结构体类型定义、元素定义、路径访问和地址反查。
#include <bits/stdc++.h>
using namespace std;

struct MemberInfo {
    string type_name;
    string name;
    long long offset;
};

struct TypeInfo {
    string name;
    long long size;
    long long align;
    bool is_basic;
    vector<MemberInfo> members;
    map<string, int> member_id;
};

struct ElementInfo {
    string type_name;
    string name;
    long long start;
};

vector<TypeInfo> types;
vector<ElementInfo> elements;
map<string, int> type_id;
map<string, int> element_id;
long long memory_end;

long long align_up(long long x, long long a) {
    if (x % a == 0) {
        return x;
    }
    return x + (a - x % a);
}

void add_basic_type(const string &name, long long size) {
    TypeInfo t;
    t.name = name;
    t.size = size;
    t.align = size;
    t.is_basic = true;
    type_id[name] = (int)types.size();
    types.push_back(t);
}

vector<string> split_path(const string &s) {
    vector<string> result;
    string cur;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '.') {
            result.push_back(cur);
            cur.clear();
        } else {
            cur.push_back(s[i]);
        }
    }
    result.push_back(cur);
    return result;
}

void define_struct_type() {
    string name;
    int k;
    cin >> name >> k;

    TypeInfo t;
    t.name = name;
    t.size = 0;
    t.align = 1;
    t.is_basic = false;

    long long cur = 0;
    for (int i = 0; i < k; i++) {
        string type_name, member_name;
        cin >> type_name >> member_name;
        int tid = type_id[type_name];

        cur = align_up(cur, types[tid].align);

        MemberInfo member;
        member.type_name = type_name;
        member.name = member_name;
        member.offset = cur;
        t.member_id[member_name] = (int)t.members.size();
        t.members.push_back(member);

        cur += types[tid].size;
        t.align = max(t.align, types[tid].align);
    }

    t.size = align_up(cur, t.align);
    type_id[name] = (int)types.size();
    types.push_back(t);

    cout << t.size << ' ' << t.align << '\n';
}

void define_element() {
    string type_name, name;
    cin >> type_name >> name;
    int tid = type_id[type_name];

    ElementInfo e;
    e.type_name = type_name;
    e.name = name;
    e.start = align_up(memory_end, types[tid].align);
    memory_end = e.start + types[tid].size;

    element_id[name] = (int)elements.size();
    elements.push_back(e);

    cout << e.start << '\n';
}

void query_path() {
    string path;
    cin >> path;
    vector<string> parts = split_path(path);

    int eid = element_id[parts[0]];
    long long addr = elements[eid].start;
    string cur_type = elements[eid].type_name;

    for (int i = 1; i < (int)parts.size(); i++) {
        int tid = type_id[cur_type];
        int mid = types[tid].member_id[parts[i]];
        MemberInfo member = types[tid].members[mid];
        addr += member.offset;
        cur_type = member.type_name;
    }

    cout << addr << '\n';
}

bool find_addr_in_type(int tid, long long base, long long addr, const string &path, string &answer) {
    if (types[tid].is_basic) {
        if (base <= addr && addr < base + types[tid].size) {
            answer = path;
            return true;
        }
        return false;
    }

    for (int i = 0; i < (int)types[tid].members.size(); i++) {
        MemberInfo member = types[tid].members[i];
        int child_tid = type_id[member.type_name];
        long long child_base = base + member.offset;
        long long child_end = child_base + types[child_tid].size;
        if (child_base <= addr && addr < child_end) {
            return find_addr_in_type(child_tid, child_base, addr, path + "." + member.name, answer);
        }
    }
    return false;
}

void query_address() {
    long long addr;
    cin >> addr;

    string answer;
    for (int i = 0; i < (int)elements.size(); i++) {
        int tid = type_id[elements[i].type_name];
        long long l = elements[i].start;
        long long r = l + types[tid].size;
        if (l <= addr && addr < r) {
            if (find_addr_in_type(tid, l, addr, elements[i].name, answer)) {
                cout << answer << '\n';
            } else {
                cout << "ERR\n";
            }
            return;
        }
    }

    cout << "ERR\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    add_basic_type("byte", 1);
    add_basic_type("short", 2);
    add_basic_type("int", 4);
    add_basic_type("long", 8);

    int q;
    cin >> q;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            define_struct_type();
        } else if (op == 2) {
            define_element();
        } else if (op == 3) {
            query_path();
        } else {
            query_address();
        }
    }

    return 0;
}

复杂度

设一次结构体最多有 k 个成员，路径深度为 d。

定义结构体需要 $O(k)$ ；路径访问需要 $O(d)$ ；地址反查最坏会扫描递归路径上各层成员，总复杂度不超过所有已定义成员数。

由于题目操作数最多 100，整体复杂度远小于限制。空间复杂度为 $O(类型数 + 成员数 + 元素数)$ 。

总结

本题最容易错的是“结构体大小也要按最大对齐要求补齐”，以及地址反查时要区分真正的基本类型占用区间和对齐产生的空洞。

只要为每个类型保存 size/align/成员偏移，四种操作都可以直接从这些信息推出来。

P9754 [CSP-S 2023] 结构体

题目背景

在 C++ 等高级语言中，除了 int 和 float 等基本类型外，通常还可以自定义结构体类型。在本题当中，你需要模拟一种类似 C++ 的高级语言的结构体定义方式，并计算出相应的内存占用等信息。

题目描述

在这种语言中，基本类型共有 $4$ 种：byte、short、int、long，分别占据 $1$ 、 $2$ 、 $4$ 、 $8$ 字节的空间。

定义一个结构体类型时，需要给出类型名和成员，其中每个成员需要按顺序给出类型和名称。类型可以为基本类型，也可以为先前定义过的结构体类型。注意，定义结构体类型时不会定义具体元素，即不占用内存。

定义一个元素时，需要给出元素的类型和名称。元素将按照以下规则占据内存：

元素内的所有成员将按照定义时给出的顺序在内存中排布，对于类型为结构体的成员同理。
为了保证内存访问的效率，元素的地址占用需要满足对齐规则，即任何类型的大小和该类型元素在内存中的起始地址均应对齐到该类型对齐要求的整数倍。具体而言：
- 对于基本类型：对齐要求等于其占据空间大小，如 int 类型需要对齐到 $4$ 字节，其余同理。
- 对于结构体类型：对齐要求等于其成员的对齐要求的最大值，如一个含有 int 和 short 的结构体类型需要对齐到 $4$ 字节。

以下是一个例子（以 C++ 语言的格式书写）：

cpp

1
2
3
4
5
6struct d {
    short a;
    int b;
    short c;
};
d e;

该代码定义了结构体类型 d 与元素 e。元素 e 包含三个成员 e.a、e.b、e.c，分别占据第 $0 \sim 1$ 、 $4 \sim 7$ 、 $8 \sim 9$ 字节的地址。由于类型 d 需要对齐到 $4$ 字节，因此 e 占据了第 $0 \sim 11$ 字节的地址，大小为 $12$ 字节。

你需要处理 $n$ 次操作，每次操作为以下四种之一：

定义一个结构体类型。具体而言，给定正整数 $k$ 与字符串 $s, t_1, n_1, \dots, t_k, n_k$ ，其中 $k$ 表示该类型的成员数量， $s$ 表示该类型的类型名， $t_1, t_2, \dots, t_k$ 按顺序分别表示每个成员的类型， $n_1, n_2, \dots, n_k$ 按顺序分别表示每个成员的名称。你需要输出该结构体类型的大小和对齐要求，用一个空格分隔。
定义一个元素，具体而言，给定字符串 $t, n$ 分别表示该元素的类型与名称。所有被定义的元素将按顺序，从内存地址为 $0$ 开始依次排开，并需要满足地址对齐规则。你需要输出新定义的元素的起始地址。
访问某个元素。具体而言，给定字符串 $s$ ，表示所访问的元素。与 C++ 等语言相同，采用 . 来访问结构体类型的成员。如 a.b.c，表示 a 是一个已定义的元素，它是一个结构体类型，有一个名称为 b 的成员，它也是一个结构体类型，有一个名称为 c 的成员。你需要输出如上被访问的最内层元素的起始地址。
访问某个内存地址。具体而言，给定非负整数 $addr$ ，表示所访问的地址，你需要判断是否存在一个基本类型的元素占据了该地址。若是，则按操作 3 中的访问元素格式输出该元素；否则输出 ERR。

输入格式

第 $1$ 行：一个正整数 $n$ ，表示操作的数量。

接下来若干行，依次描述每个操作，每行第一个正整数 $op$ 表示操作类型：

若 $op = 1$ ，首先输入一个字符串 $s$ 与一个正整数 $k$ ，表示类型名与成员数量，接下来 $k$ 行每行输入两个字符串 $t_i, n_i$ ，依次表示每个成员的类型与名称。
若 $op = 2$ ，输入两个字符串 $t, n$ ，表示该元素的类型与名称。
若 $op = 3$ ，输入一个字符串 $s$ ，表示所访问的元素。
若 $op = 4$ ，输入一个非负整数 $addr$ ，表示所访问的地址。

输出格式

输出 $n$ 行，依次表示每个操作的输出结果，输出要求如题目描述中所述。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
8
9
105
1 a 2
short aa
int ab
1 b 2
a ba
long bb
2 b x
3 x.ba.ab
4 10

输出 #1

text

说明/提示

【样例 1 解释】

结构体类型 a 中，short 类型的成员 aa 占据第 $0 \sim 1$ 字节地址，int 类型的成员 ab 占据第 $4 \sim 7$ 字节地址。又由于其对齐要求为 $4$ 字节，可得其大小为 $8$ 字节。由此可同理计算出结构体类型 b 的大小为 $16$ 字节，对齐要求为 $8$ 字节。

【样例 2】

见选手目录下的 struct/struct2.in 与 struct/struct2.ans。

【样例 2 解释】

第二个操作 4 中，访问的内存地址恰好在为了地址对齐而留下的 “洞” 里，因此没有基本类型元素占据它。

【样例 3】

见选手目录下的 struct/struct3.in 与 struct/struct3.ans。

【数据范围】

对于全部数据，满足 $1 \le n \le 100$ ， $1 \le k \le 100$ ， $0 \le addr \le 10^{18}$ 。

所有定义的结构体类型名、成员名称和定义的元素名称均由不超过 $10$ 个字符的小写字母组成，且都不是 byte,short,int,long（即不与基本类型重名）。

所有定义的结构体类型名和元素名称互不相同，同一结构体内成员名称互不相同。但不同的结构体可能有相同的成员名称，某结构体内的成员名称也可能与定义的结构体或元素名称相同。

保证所有操作均符合题目所述的规范和要求，即结构体的定义不会包含不存在的类型、不会访问不存在的元素或成员等。

保证任意结构体大小及定义的元素占据的最高内存地址均不超过 $10^{18}$ 。

测试点	特殊性质
$1$	A、D
$2\sim 3$	A
$4\sim 5$	B、D
$6\sim 8$	B
$9\sim 10$	C、D
$11\sim 13$	C
$14\sim 16$	D
$17\sim 20$	无

特殊性质 A：没有操作 $1$ ；

特殊性质 B：只有一个操作 $1$ ；

特殊性质 C：所有操作 $1$ 中给出的成员类型均为基本类型；

特殊性质 D：基本类型只有 long。

【提示】

对于结构体类型的对齐要求和大小，形式化的定义方式如下：

设该结构体内有 $k$ 个成员，其大小分别为 $s_1,...,s_k$ ，对齐要求分别为 $a_1,...,a_k$ ;
则该结构体的对齐要求为 $a=\max\{a_1,...,a_k\}$ ；
再设这些成员排布时的地址偏移量分别为 $o_1,...,o_k$ ，则：
- $o_1 = 0$ ;
- 对于 $i=2,...,k$ ， $o_i$ 为满足 $o_{i-1}+s_{i-1}\le o_i$ 且 $a_i$ 整除 $o_i$ 的最小值；
- 则该结构体的大小 $s$ 为满足 $o_k+s_k\le s$ 且 $a$ 整除 $s$ 的最小值；

对于定义元素时的内存排布，形式化的定义方式如下：

设第 $i$ 个被定义的元素大小为 $s_i$ ，对齐要求为 $a_i$ ，起始地址为 $b_i$ ;
则 $b_1 = 0$ ，对于 $2\le i$ ， $b_i$ 为满足 $b_{i-1} + s_{i-1}\le b_i$ 且 $a_i$ 整除 $b_i$ 的最小值。