5182 - NOIP CSP 2023 提高: 第三题 结构体(struct)

【题目背景】 在 C++ 等高级语言中,除了 int 和 float 等基本类型外,通常还可以自定义结构体类型。在本题当中,你需要模拟一种类似 C++ 的高级语言的结构体定义方式,并计算出相应的内存占用等信息。 【题目描述】 在这种语言中,基本类型共有 4 种:byte,short,int,long,分别占据 1, 2, 4, 8字节的空间。 定义一个结构体类型时,需要给出类型名和成员,其中每个成员需要按顺序给出类型和名称。类型可以为基本类型,也可以为先前定义过的结构体类型。注意,定义结构体类型时不会定义具体元素,即不占用内存。定义一个元素时,需要给出元素的类型和名称。元素将按照以下规则占据内存:

• 元素内的所有成员将按照定义时给出的顺序在内存中排布,对于类型为结构体的成员同理。
• 为了保证内存访问的效率,元素的地址占用需要满足对齐规 则,即任何类型的大小和该类型元素在内存中的起始地址均应对齐到该类型对齐要求的整数倍。具体而言:
– 对于基本类型:对齐要求等于其占据空间大小,如 int 类型需要对齐到 4字节,其余同理。
– 对于结构体类型:对齐要求等于其成员的对齐要求的 .最 .大 .值,如一个含有int 和 short 的结构体类型需要对齐到 4 字节。
以下是一个例子(以 C++ 语言的格式书写)
struct d {
short a;
int b;
short c;
};
d e;
该代码定义了结构体类型 d 与元素 e。元素 e 包含三个成员 e.a, e.b, e.c,分
别占据第 0 ∼ 1,4 ∼ 7,8 ∼ 9 字节的地址。由于类型 d 需要对齐到 4 字节,因此 e 占
据了第 0 ∼ 11 字节的地址,大小为 12 字节。
你需要处理 n 次操作,每次操作为以下四种之一:
1. 定义一个结构体类型。具体而言,给定正整数 k 与字符串 s, t1, n1, . . . , tk, nk,其中 k 表示该类型的成员数量,s 表示该类型的类型名,t1, t2, . . . , tk 按顺序分别表示每个成员的类型,n1, n2, . . . , nk 按顺序分别表示每个成员的名称。你需要输出该结构体类型的大小和对齐要求,用一个空格分隔。
2. 定义一个元素,具体而言,给定字符串 t,n 分别表示该元素的类型与名称。所有被定义的元素将按顺序,从内存地址为 0 开始依次排开,并需要满足地址对齐规则。你需要输出新定义的元素的起始地址。
3. 访问某个元素。具体而言,给定字符串 s,表示所访问的元素。与 C++ 等语言相同,采用 . 来访问结构体类型的成员。如 a.b.c,表示 a 是一个已定义的元素,它是一个结构体类型,有一个名称为 b 的成员,它也是一个结构体类型,有
一个名称为 c 的成员。你需要输出如上被访问的最内层元素的起始地址。
4. 访问某个内存地址。具体而言,给定非负整数 addr,表示所访问的地址,你需要判断是否存在一个基本类型的元素占据了该地址。若是,则按操作 3 中的访问元素格式输出该元素;否则输出

输入

第 1 行:一个正整数 n,表示操作的数量。 接下来若干行,依次描述每个操作,每行第一个正整数 op 表示操作类型:

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

输出

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

样例

输入

5
1 a 2
short aa
int ab
1 b 2
a ba
long bb
2 b x
3 x.ba.ab
4 10

输出

8 4
16 8
0
4
x.bb

输入

100
4 0
4 4
2 byte szqir
2 long fweahddll
2 byte dvqu
3 szqir
2 long wqcnqxppvg
3 szqir
4 9
4 33
3 wqcnqxppvg
4 38
4 5
4 33
2 short erhxh
2 short wwsp
4 3
3 szqir
4 42
2 short pxkwnp
4 15
2 int teuwwrw
4 45
3 erhxh
2 int uuycypz
3 uuycypz
4 48
4 35
4 6
3 wqcnqxppvg
2 byte yvgc
3 yvgc
3 teuwwrw
4 25
3 fweahddll
3 wwsp
3 szqir
4 57
3 wwsp
3 fweahddll
4 7
4 22
4 16
4 54
3 pxkwnp
4 7
4 68
2 byte sulvy
3 erhxh
4 1
2 short yuoquzsyr
2 byte okdqtvqv
4 35
2 int xmsvcd
4 33
4 50
4 76
3 szqir
4 71
3 wqcnqxppvg
3 wqcnqxppvg
2 long zuwd
2 short lvvlezc
3 xmsvcd
2 short jad
3 erhxh
4 41
2 long hprwemliyo
3 teuwwrw
4 54
4 38
3 hprwemliyo
4 71
2 short ekqiko
4 42
3 wwsp
2 long iwqssghglm
3 hprwemliyo
2 byte rcjx
4 122
3 pxkwnp
4 60
2 byte krjasjxkp
4 22
4 61
3 erhxh
3 uuycypz
2 int cyyzsusp
4 108
2 int v
4 91
3 hprwemliyo
2 int oqk
3 szqir
2 long rjisljjxo
3 okdqtvqv
3 wqcnqxppvg
4 17
2 byte zdjdvzka
4 9

输出

ERR
ERR
0
8
16
0
24
0
fweahddll
ERR
24
ERR
ERR
ERR
32
34
ERR
0
ERR
36
fweahddll
40
ERR
32
44
44
ERR
wwsp
ERR
24
48
48
40
wqcnqxppvg
8
34
0
ERR
34
8
ERR
ERR
dvqu
ERR
36
ERR
ERR
49
32
ERR
50
52
wwsp
56
erhxh
yuoquzsyr
ERR
0
ERR
24
24
64
72
56
74
32
teuwwrw
80
40
ERR
ERR
80
zuwd
88
teuwwrw
34
96
80
104
ERR
36
ERR
105
ERR
ERR
32
44
108
cyyzsusp
112
ERR
80
116
0
120
52
24
ERR
128
fweahddll

输入

99
2 long mrbfn
4 1
3 mrbfn
3 mrbfn
3 mrbfn
3 mrbfn
2 byte oosmberlsb
3 mrbfn
3 oosmberlsb
2 byte auhmoewi
4 7
4 3
2 long jplopgx
4 0
4 31
2 int qqgjpu
2 long plfawkhtd
3 auhmoewi
3 plfawkhtd
2 int uwue
2 long muvlnlgqn
4 46
4 46
4 22
2 long inhosie
3 auhmoewi
3 oosmberlsb
2 byte pziz
2 byte anyxdruw
4 12
3 inhosie
4 3
4 38
4 39
4 82
4 83
2 byte jdyh
2 long ceqpfdrlx
2 byte tpy
3 inhosie
2 long cbnapeqnwr
3 mrbfn
3 qqgjpu
3 tpy
3 tpy
4 63
4 101
2 long fzck
3 pziz
2 byte qm
2 long vjslsy
3 jdyh
2 long isr
3 qm
3 isr
2 short tqsjlcgz
3 mrbfn
4 111
3 auhmoewi
2 long wbpatry
2 byte wdmtrievjf
2 byte ng
2 long cjzosekh
3 anyxdruw
2 int kpej
4 65
2 int ialhf
4 168
2 short ezgejozee
3 ceqpfdrlx
2 byte d
4 142
3 cjzosekh
3 muvlnlgqn
4 153
4 95
4 117
2 long ezfylph
2 byte ycytaxof
3 jplopgx
3 d
3 ycytaxof
4 8
2 short rgouqvt
4 196
2 byte nyelxwwdf
3 isr
4 136
2 long djm
2 long btwyo
2 short xnjpfuyas
4 227
2 long rflxy
4 247
4 243
4 129
3 ycytaxof
4 191
4 218

输出

0
mrbfn
0
0
0
0
8
0
8
9
mrbfn
mrbfn
16
mrbfn
ERR
24
32
9
32
40
48
ERR
ERR
jplopgx
56
9
8
64
65
ERR
56
mrbfn
plfawkhtd
plfawkhtd
ERR
ERR
66
72
80
56
88
0
24
80
80
inhosie
ERR
96
64
104
112
66
120
104
120
128
0
ERR
9
136
144
145
152
65
160
anyxdruw
164
ERR
168
72
170
wbpatry
152
48
cjzosekh
cbnapeqnwr
vjslsy
176
184
16
170
184
oosmberlsb
186
ERR
188
120
wbpatry
192
200
208
ERR
216
ERR
ERR
tqsjlcgz
184
ERR
rflxy

提示

【样例 1 解释】 结构体类型 a 中,int 类型的成员 aa 占据第 0 ∼ 3 字节地址,short 类型的成员ab 占据第 4 ∼ 5 字节地址。又由于其对齐要求为 4 字节,可得其大小为 8 字节。由此可同理计算出结构体类型 b 的大小为 16 字节,对齐要求为 8 字节。

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

【数据范围】 对于全部数据,满足 1 ≤ n ≤ 100,1 ≤ k ≤ 100,0 ≤ addr ≤ 10^18。 所有定义的结构体类型名、成员名称和定义的元素名称均由不超过 10 个字符的小写字母组成,且都不是byte,short,int,long(即不与基本类型重名)。 所有定义的结构体类型名和元素名称互不相同,同一结构体内成员名称互不相同。 但不同的结构体可能有相同的成员名称,某结构体内的成员名称也可能与定义的结构体或元素名称相同。 保证所有操作均符合题目所述的规范和要求,即结构体的定义不会包含不存在的类型、不会访问不存在的元素或成员等。 保证任意结构体大小及定义的元素占据的最高内存地址均不超过 10^18。

时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题