CSP-S 2023 结构体

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

纯模拟题，按题目规则模拟结构体类型的定义、元素的内存分配与访问查找。

OJ: roj

题目 ID: 3678

难度:提高

标签:模拟

创建: 2026-10-10 09:26

更新: 2026-10-10 09:26

形式化题目

实现一个包含四种操作的内存分配模拟器：

定义结构体：给定类型名与成员列表，计算并输出该结构体的大小与内存对齐要求。
定义元素：给定类型与元素名，分配内存，并根据前一个元素的占用情况以及当前类型的对齐要求，输出起始内存地址。
访问成员：给定以 . 分隔的多级成员名称，计算并输出其确切的起始内存地址。
访问地址：给定一个内存地址，逆向推导出占据该地址的最底层基本类型元素的完整名称；若该地址落在填充的内存“空洞”中或未分配内存，输出 ERR。

数据范围： $n \le 100, k \le 100$ ，任意元素的最高内存地址不超过 $10^{18}$ 。

正解

思路

本题是一道纯粹的模拟题，我们只需严格按照题目给出的形式化规则维护类型和变量的信息即可：

类型的表示：将基本类型也看作特殊的“结构体”（即不包含任何成员的结构体），这样就统一了基础类型和自定义类型的表示。每种类型包含其自身的大小（size）、对齐要求（align）、成员列表（成员包括名称、类型、偏移量）。
结构体定义（操作 1）：维护一个偏移量指针 offset 初始为 $0$ 。遍历新结构体的所有成员，根据该成员类型的对齐要求更新 offset = align_up(offset, 成员的 align)，此时的 offset 即为该成员在结构体内的相对地址。随后 offset 增加该成员的大小。结构体的总对齐要求为所有成员中对齐要求的最大值。最终结构体的总大小为 align_up(offset, 总 align)。
变量定义（操作 2）：顺序记录分配的变量。如果存在前置变量，则新变量的起始可用地址为前置变量的 起始地址 + 它的类型大小。将该可用地址通过新变量类型的对齐要求向上取整，即得到其实际的起始地址。
正向访问（操作 3）：将查询字符串按 . 切分。第一级为全局变量名称，从而得到其起始地址和当前类型。随后逐级向下，查表加上成员在当前类型中的相对偏移量即可。
逆向查询（操作 4）：遍历已定义的全局变量列表，判断查询地址是否落在某变量的 [起始地址, 起始地址 + 类型大小) 范围内。如果不在任何变量内，输出 ERR；否则，计算相对于该变量起始地址的偏移量，并递归在类型结构内向下查找。每次找到最后一个相对偏移量小于等于当前查询偏移量的成员：
- 若查询偏移量落在了该成员的有效大小内（偏移量 < 成员起始相对地址 + 成员大小），则说明查询命中该成员，并继续深入其内部。
- 若查询偏移量落在了成员大小以外，说明落入了对齐补齐的空洞中，直接输出 ERR。重复此过程，直到深入到基本类型为止，即可得到完整名称。

由于操作数 $n \le 100, k \le 100$ ，利用 map 维护映射关系以及直接遍历的方法是足够高效的，时空复杂度均有保证。

代码

python

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
159import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    n = int(data[0])
    idx = 1
    
    types = {
        "byte": {"size": 1, "align": 1, "members": [], "name_to_index": {}},
        "short": {"size": 2, "align": 2, "members": [], "name_to_index": {}},
        "int": {"size": 4, "align": 4, "members": [], "name_to_index": {}},
        "long": {"size": 8, "align": 8, "members": [], "name_to_index": {}},
    }
    
    vars_list = []
    var_name_to_index = {}
    
    out = []
    
    for _ in range(n):
        op = int(data[idx])
        idx += 1
        
        if op == 1:
            name = data[idx]
            k = int(data[idx+1])
            idx += 2
            
            align = 0
            current_offset = 0
            members = []
            name_to_index = {}
            
            for i in range(k):
                type_name = data[idx]
                member_name = data[idx+1]
                idx += 2
                
                member_type = types[type_name]
                m_align = member_type["align"]
                m_size = member_type["size"]
                
                if align < m_align:
                    align = m_align
                
                current_offset = (current_offset + m_align - 1) // m_align * m_align
                members.append({
                    "type": type_name,
                    "name": member_name,
                    "offset": current_offset
                })
                name_to_index[member_name] = i
                current_offset += m_size
                
            size = (current_offset + align - 1) // align * align
            types[name] = {
                "size": size,
                "align": align,
                "members": members,
                "name_to_index": name_to_index
            }
            out.append(f"{size} {align}")
            
        elif op == 2:
            type_name = data[idx]
            var_name = data[idx+1]
            idx += 2
            
            t = types[type_name]
            t_align = t["align"]
            
            start_addr = 0
            if vars_list:
                last_var = vars_list[-1]
                last_type = types[last_var["type"]]
                next_avail = last_var["addr"] + last_type["size"]
                start_addr = (next_avail + t_align - 1) // t_align * t_align
                
            vars_list.append({
                "type": type_name,
                "name": var_name,
                "addr": start_addr
            })
            var_name_to_index[var_name] = len(vars_list) - 1
            out.append(str(start_addr))
            
        elif op == 3:
            path = data[idx]
            idx += 1
            
            parts = path.split('.')
            var_idx = var_name_to_index[parts[0]]
            ans = vars_list[var_idx]["addr"]
            curr_type = vars_list[var_idx]["type"]
            
            for i in range(1, len(parts)):
                t = types[curr_type]
                member_idx = t["name_to_index"][parts[i]]
                m = t["members"][member_idx]
                ans += m["offset"]
                curr_type = m["type"]
                
            out.append(str(ans))
            
        elif op == 4:
            addr = int(data[idx])
            idx += 1
            
            found_var_idx = -1
            for i, v in enumerate(vars_list):
                if v["addr"] <= addr < v["addr"] + types[v["type"]]["size"]:
                    found_var_idx = i
                    break
            
            if found_var_idx == -1:
                out.append("ERR")
                continue
                
            res = vars_list[found_var_idx]["name"]
            curr_type = vars_list[found_var_idx]["type"]
            rem_addr = addr - vars_list[found_var_idx]["addr"]
            
            ok = True
            while types[curr_type]["members"]:
                t = types[curr_type]
                found_member_idx = -1
                for i in range(len(t["members"]) - 1, -1, -1):
                    if rem_addr >= t["members"][i]["offset"]:
                        found_member_idx = i
                        break
                
                if found_member_idx == -1:
                    ok = False
                    break
                
                m = t["members"][found_member_idx]
                m_size = types[m["type"]]["size"]
                
                if rem_addr < m["offset"] + m_size:
                    res += "." + m["name"]
                    rem_addr -= m["offset"]
                    curr_type = m["type"]
                else:
                    ok = False
                    break
                    
            if ok:
                out.append(res)
            else:
                out.append("ERR")

    print('\n'.join(out))

if __name__ == '__main__':
    main()

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#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

struct Member {
    string type;
    string name;
    long long offset;
};

struct Type {
    long long size;
    long long align;
    vector<Member> members;
    map<string, int> name_to_index;
};

struct Variable {
    string type;
    string name;
    long long addr;
};

map<string, Type> types;
vector<Variable> vars;
map<string, int> var_name_to_index;

vector<string> split(const string& s, char delim) {
    vector<string> res;
    string item;
    for (char c : s) {
        if (c == delim) {
            res.push_back(item);
            item = "";
        } else {
            item += c;
        }
    }
    res.push_back(item);
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    types["byte"] = {1, 1, {}, {}};
    types["short"] = {2, 2, {}, {}};
    types["int"] = {4, 4, {}, {}};
    types["long"] = {8, 8, {}, {}};

    int n;
    if (!(cin >> n)) return 0;

    while (n--) {
        int op;
        cin >> op;
        if (op == 1) {
            string name;
            int k;
            cin >> name >> k;
            Type t;
            t.align = 0;
            long long current_offset = 0;
            for (int i = 0; i < k; ++i) {
                string type_name, member_name;
                cin >> type_name >> member_name;
                Type& member_type = types[type_name];
                t.align = max(t.align, member_type.align);
                current_offset = (current_offset + member_type.align - 1) / member_type.align * member_type.align;
                t.members.push_back({type_name, member_name, current_offset});
                t.name_to_index[member_name] = i;
                current_offset += member_type.size;
            }
            t.size = (current_offset + t.align - 1) / t.align * t.align;
            types[name] = t;
            cout << t.size << " " << t.align << "\n";
        } else if (op == 2) {
            string type_name, var_name;
            cin >> type_name >> var_name;
            Type& t = types[type_name];
            long long start_addr = 0;
            if (!vars.empty()) {
                Variable& last_var = vars.back();
                Type& last_type = types[last_var.type];
                long long next_avail = last_var.addr + last_type.size;
                start_addr = (next_avail + t.align - 1) / t.align * t.align;
            }
            vars.push_back({type_name, var_name, start_addr});
            var_name_to_index[var_name] = (int)vars.size() - 1;
            cout << start_addr << "\n";
        } else if (op == 3) {
            string path;
            cin >> path;
            vector<string> parts = split(path, '.');
            int var_idx = var_name_to_index[parts[0]];
            long long ans = vars[var_idx].addr;
            string curr_type = vars[var_idx].type;
            for (size_t i = 1; i < parts.size(); ++i) {
                Type& t = types[curr_type];
                int member_idx = t.name_to_index[parts[i]];
                ans += t.members[member_idx].offset;
                curr_type = t.members[member_idx].type;
            }
            cout << ans << "\n";
        } else if (op == 4) {
            long long addr;
            cin >> addr;
            int found_var_idx = -1;
            for (int i = 0; i < (int)vars.size(); ++i) {
                if (addr >= vars[i].addr && addr < vars[i].addr + types[vars[i].type].size) {
                    found_var_idx = i;
                    break;
                }
            }
            if (found_var_idx == -1) {
                cout << "ERR\n";
                continue;
            }
            string res = vars[found_var_idx].name;
            string curr_type = vars[found_var_idx].type;
            long long rem_addr = addr - vars[found_var_idx].addr;
            bool ok = true;
            while (types[curr_type].members.size() > 0) {
                Type& t = types[curr_type];
                int found_member_idx = -1;
                for (int i = (int)t.members.size() - 1; i >= 0; --i) {
                    if (rem_addr >= t.members[i].offset) {
                        found_member_idx = i;
                        break;
                    }
                }
                if (found_member_idx == -1) {
                    ok = false;
                    break;
                }
                Member& m = t.members[found_member_idx];
                if (rem_addr < m.offset + types[m.type].size) {
                    res += "." + m.name;
                    rem_addr -= m.offset;
                    curr_type = m.type;
                } else {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                cout << res << "\n";
            } else {
                cout << "ERR\n";
            }
        }
    }
    return 0;
}

复杂度

时间复杂度：
- 操作 1 和 2 主要为查找与算术计算，单次至多遍历 $k$ 个成员，为 $O(k)$ 。
- 操作 3 和 4 最多深入类型嵌套深度次（最大为 $n$ ），每层使用哈希表或二分/遍历查找，复杂度 $O(n)$ 。总体时间复杂度极小，不超过 $O(n^2)$ ，能够在数毫秒内完成处理。
空间复杂度：需要存储不超过 $n$ 个结构体，每个结构体包含至多 $k$ 个成员，存储这些信息需要 $O(nk)$ 的空间；同时还有 $O(n)$ 的变量存储。总空间复杂度为 $O(nk)$ 。

总结

理解内存对齐机制：对齐大小由成员的最大对齐要求决定，而偏移量及最终大小必须依次向上取整至对齐要求的整数倍。
正反向映射的统一：用统一的数据结构去管理基本类型与复合类型，能够极大减少分类讨论带来的代码膨胀和潜在 bug。
内存空洞的判断：在逆向查询时，必须在每深入一层之前，严谨判定当前偏移量是否位于该成员大小所覆盖的区间内，否则即为无效地址。

题目背景

在 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

::: line

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

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$ 的最小值。