洛谷 P9754 [CSP-S 2023] 结构体题解

题目传送门
 洛谷博客博客园

基本思路

本题主要考查编码能力，所以直接给出基本思路：

由于可以递归式的创建元素，最多可以同时存在 $100^{100}$ 个不同的基础类型的元素。即使算上最大地址的限制，元素的数量也能达到 $10^{18}$。显然，依次构造每个元素，在空间和时间上都是无法接受的。
然而，由于询问数量有限，真正能在查询时用到的元素数量相对很少。因此，我们只需维护一个顶层元素（不隶属于任何其他元素的元素）列表，再根据查询的地址或名称逐层向下找到需要的元素即可。以下是四种操作的具体做法：
- 对于 $op=1$：储存当前类型信息，计算大小和对齐要求并输出。
- 对于 $op=2$：用一个变量记录当前第一个可分配内存的地址，操作时先对齐后计算、输出。
- 对于 $op=3$：从顶层开始，逐层向下寻找，计算地址并输出。
- 对于 $op=4$：从顶层开始，维护当前考查的元素地址，并与给定地址比对，最终输出底层元素名称。

由以上思路，很容易想到下面三种类型的存储方式：

用类型名称作为类型的唯一的标识符。这是最直观的做法，但是效率低下且使用起来较为繁琐，pass。
用 map 将类型名称映射到序号，来代表一种数据类型。相比第一种做法，效率高了很多，但是写起来仍然很麻烦，pass。
用结构体存储类型信息，并使用指针来处理类型之间的关联。这种做法不仅高效，而且编码时也很直观，所以我们将采用这种存储方式。

分步详解

准备

用 LL 表示 long long，setmax(x, y) 等同于 x = max(x, y)：

1
2
3
4
5
6


inline void setmax(int& x, int y)
{
    if(x < y) x = y;
}

using LL = long long;

数据类型的存储

定义 struct DataType，表示一种数据类型：

1
2
3
4
5
6
7


struct DataType
{
    const string name; // 类型名
    LL size, actual_size; // 对齐后的大小和实际大小（有数据的部分的长度）
    int indent; // 对齐要求
    vector<pair<DataType*, string>> members; // 类型成员，<成员类型指针，成员名称> 方式存储
};

$$ {对齐后的地址} = \lceil \frac {对齐前的地址} {对齐要求} \rceil \times {对齐要求} $$

1
2
3
4


inline LL shift(LL addr)
{
    return addr % indent? (addr / indent + 1) * indent: addr;
}

维护操作，用于操作 $1$ 后计算大小：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


inline void maintain()
{
    size = indent = 0;
    for(const auto& m: members)
    {
        setmax(indent, m.first->indent);
        size = m.first->shift(size) + m.first->size;
    }
    actual_size = size;
    size = shift(size);
}

注意 shift 和 maintain 都是 DataType 的成员函数。

主函数中，用一个 unordered_map 记录类型名到数据类型的映射关系：

1

unordered_map<string, DataType*> types;

添加基本类型：

1
2
3
4
5
6
7
8
9


auto add_base_type = [&](string name, int size) -> void {
    DataType* t = new DataType(name);
    t->size = t->indent = t->actual_size = size;
    types[name] = t;
};
add_base_type("byte", 1);
add_base_type("short", 2);
add_base_type("int", 4);
add_base_type("long", 8);

操作 1：定义类型

由于 DataType 中已经实现维护操作，简单处理一下输入即可：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


string s;
int k;
cin >> s >> k;
DataType* type = new DataType(s);
types[s] = type;
type->members.resize(k);
for(auto& m: type->members)
{
    string t;
    cin >> t >> m.second;
    m.first = types[t];
}
type->maintain();
cout << type->size << ' ' << type->indent << '\n';

操作 2：定义元素

根据「基本思路」中给出的做法，维护当前第一个可分配的地址和顶层元素列表：

1
2


LL cur_addr = 0LL;
vector<Object> toplevel_objects;

Object 的定义：

1
2
3
4
5
6


struct Object
{
    DataType* type; // 类型
    string name; // 名称
    LL addr; // 地址
};

计算地址并保存元素：

1
2
3
4
5
6
7


Object obj;
string t;
cin >> t >> obj.name; // 输入
obj.type = types[t]; // 找到类型指针
obj.addr = obj.type->shift(cur_addr); // 对齐
cur_addr = obj.addr + obj.type->size; // 更新可分配的地址
toplevel_objects.push_back(obj); // 保存元素

输出元素地址：

1

cout << obj.addr << '\n';

操作 3：访问元素

定义一个辅助函数，类似于 Python 中的 split()，将一个字符串根据指定分隔符分成若干段：

1
2
3
4
5
6
7
8
9


inline void split(const string& s, char sep, vector<string>& res)
{
    string t;
    for(char c: s)
        if(c == sep)
            res.push_back(t), t.clear();
        else t += c;
    res.push_back(t);
}

先处理字符串并找到顶层元素：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// 读入
string s;
cin >> s;
// 分割
vector<string> ord;
split(s, '.', ord);
// 根据名称匹配顶层元素
LL addr;
DataType* type;
for(auto& obj: toplevel_objects)
    if(obj.name == ord[0])
    {
        addr = obj.addr;
        type = obj.type;
        break;
    }

逐层向下，计算地址：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// ord[0] 对应顶层元素名称，删掉
ord.erase(ord.begin());
// 逐层向下遍历
for(string& s: ord)
    for(auto& m: type->members)
    {
        addr = m.first->shift(addr); // 地址对齐
        if(m.second == s) // 名称匹配
        {
            type = m.first; // 找到下一层，向下遍历
            break;
        }
        addr += m.first->size; // 地址移到下一个元素
    }

输出最终地址：

1

cout << addr << '\n';

操作 4：访问地址

同操作 3，先找到顶层元素：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


LL addr;
cin >> addr;
if(addr >= cur_addr) // 大于最高有效地址，直接挂掉
{
    cout << "ERR\n";
    continue;
}
DataType* type = nullptr;
LL f_addr = 0LL; // 当前考察的地址
string res; // 结果字符串
for(auto& obj: toplevel_objects)
{
    if(addr < obj.addr) goto bad; // 特判由于对齐导致的地址无效
    if(addr < obj.addr + obj.type->size) // 地址在当前范围内，记录结果
    {
        type = obj.type;
        res = obj.name;
        f_addr = obj.addr;
        break;
    }
}

向下寻找并输出：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// 循环条件：(1) 地址有效 (2) 不是基本类型（类型有成员）
while(addr < f_addr + type->actual_size && !type->members.empty())
    for(auto& m: type->members)
    {
        f_addr = m.first->shift(f_addr); // 对齐
        if(addr < f_addr) goto bad; // 特判，同上
        if(addr < f_addr + m.first->size)
        {
            type = m.first;
            res.push_back('.');
            res += m.second;
            break;
        }
        f_addr += m.first->size;
    }
if(addr < f_addr + type->actual_size) cout << res << '\n'; // 地址有效则输出结果
else cout << "ERR\n"; // 地址无效
continue;
bad: cout << "ERR\n"; // 前面使用的 bad 标签

完整代码

下面是赛时代码，也是前面讲解中使用的：

  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


#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

inline void setmax(int& x, int y)
{
    if(x < y) x = y;
}

using LL = long long;

struct DataType
{
    const string name;
    LL size, actual_size;
    int indent;
    vector<pair<DataType*, string>> members;
    inline DataType(const string& n): name(n) {}
    inline LL shift(LL addr)
    {
        return addr % indent? (addr / indent + 1) * indent: addr;
    }
    inline void maintain()
    {
        size = indent = 0;
        for(const auto& m: members)
        {
            setmax(indent, m.first->indent);
            size = m.first->shift(size) + m.first->size;
        }
        actual_size = size;
        size = shift(size);
    }
};

struct Object
{
    DataType* type;
    string name;
    LL addr;
};

inline void split(const string& s, char sep, vector<string>& res)
{
    string t;
    for(char c: s)
        if(c == sep)
            res.push_back(t), t.clear();
        else t += c;
    res.push_back(t);
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    unordered_map<string, DataType*> types;
    auto add_base_type = [&](string name, int size) -> void {
        DataType* t = new DataType(name);
        t->size = t->indent = t->actual_size = size;
        types[name] = t;
    };
    add_base_type("byte", 1);
    add_base_type("short", 2);
    add_base_type("int", 4);
    add_base_type("long", 8);
    int q;
    cin >> q;
    vector<Object> toplevel_objects;
    LL cur_addr = 0LL;
    while(q--)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            string s;
            int k;
            cin >> s >> k;
            DataType* type = new DataType(s);
            types[s] = type;
            type->members.resize(k);
            for(auto& m: type->members)
            {
                string t;
                cin >> t >> m.second;
                m.first = types[t];
            }
            type->maintain();
            cout << type->size << ' ' << type->indent << '\n';
        }
        else if(op == 2)
        {
            Object obj;
            string t;
            cin >> t >> obj.name;
            obj.type = types[t];
            obj.addr = obj.type->shift(cur_addr);
            cur_addr = obj.addr + obj.type->size;
            toplevel_objects.push_back(obj);
            cout << obj.addr << '\n';
        }
        else if(op == 3)
        {
            string s;
            cin >> s;
            vector<string> ord;
            split(s, '.', ord);
            LL addr;
            DataType* type;
            for(auto& obj: toplevel_objects)
                if(obj.name == ord[0])
                {
                    addr = obj.addr;
                    type = obj.type;
                    break;
                }
            ord.erase(ord.begin());
            for(string& s: ord)
                for(auto& m: type->members)
                {
                    addr = m.first->shift(addr);
                    if(m.second == s)
                    {
                        type = m.first;
                        break;
                    }
                    addr += m.first->size;
                }
            cout << addr << '\n';
        }
        else // op == 4
        {
            LL addr;
            cin >> addr;
            if(addr >= cur_addr)
            {
                cout << "ERR\n";
                continue;
            }
            DataType* type = nullptr;
            LL f_addr = 0LL;
            string res;
            for(auto& obj: toplevel_objects)
            {
                if(addr < obj.addr) goto bad;
                if(addr < obj.addr + obj.type->size)
                {
                    type = obj.type;
                    res = obj.name;
                    f_addr = obj.addr;
                    break;
                }
            }
            while(addr < f_addr + type->actual_size && !type->members.empty())
                for(auto& m: type->members)
                {
                    f_addr = m.first->shift(f_addr);
                    if(addr < f_addr) goto bad;
                    if(addr < f_addr + m.first->size)
                    {
                        type = m.first;
                        res.push_back('.');
                        res += m.second;
                        break;
                    }
                    f_addr += m.first->size;
                }
            if(addr < f_addr + type->actual_size) cout << res << '\n';
            else cout << "ERR\n";
            continue;
            bad: cout << "ERR\n";
        }
    }
    for(auto it=types.begin(); it!=types.end(); it++)
        delete it->second;
    return 0;
}

程序共计 $180$ 行，长度 $4.64\mathrm{KB}$，运行用时 $73\mathrm{ms}$。

实际上 Object 的定义没有必要，也不需要存储每个顶层元素的地址，同时还可以稍加压行：

  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


#include <bits/stdc++.h>
using namespace std;

using LL = long long;

struct DataType {
    const string name;
    LL size, actual_size;
    int indent;
    vector<pair<DataType*, string>> members;
    inline DataType(const string& n): name(n) {}
    inline LL shift(LL addr) {
        return addr % indent? (addr / indent + 1) * indent: addr;
    }
    inline void maintain() {
        size = indent = 0;
        for(const auto& m: members)
        {
            indent = max(indent, m.first->indent);
            size = m.first->shift(size) + m.first->size;
        }
        actual_size = size;
        size = shift(size);
    }
};

inline void split(const string& s, char sep, vector<string>& res) {
    string t;
    for(char c: s)
        if(c == sep) res.push_back(t), t.clear();
        else t += c;
    res.push_back(t);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    unordered_map<string, DataType*> types;
    auto add_base_type = [&](string name, int size) -> void {
        DataType* t = new DataType(name);
        t->size = t->indent = t->actual_size = size;
        types[name] = t;
    };
    add_base_type("byte", 1);
    add_base_type("short", 2);
    add_base_type("int", 4);
    add_base_type("long", 8);
    int q;
    cin >> q;
    vector<pair<DataType*, string>> toplevel_objects;
    LL cur_addr = 0LL;
    while(q--) {
        int op;
        cin >> op;
        if(op == 1) {
            string s;
            int k;
            cin >> s >> k;
            DataType* type = new DataType(s);
            types[s] = type;
            type->members.resize(k);
            for(auto& m: type->members) {
                string t;
                cin >> t >> m.second;
                m.first = types[t];
            }
            type->maintain();
            cout << type->size << ' ' << type->indent << '\n';
        }
        else if(op == 2) {
            string t, name;
            cin >> t >> name;
            DataType* type = types[t];
            cur_addr = type->shift(cur_addr);
            cout << cur_addr << '\n';
            cur_addr += type->size;
            toplevel_objects.emplace_back(type, name);
        }
        else if(op == 3) {
            string s;
            cin >> s;
            vector<string> ord;
            split(s, '.', ord);
            LL addr = 0LL;
            DataType* type;
            for(auto& obj: toplevel_objects) {
                addr = obj.first->shift(addr);
                if(obj.second == ord[0]) {
                    type = obj.first;
                    break;
                }
                addr += obj.first->size;
            }
            ord.erase(ord.begin());
            for(string& s: ord)
                for(auto& m: type->members) {
                    addr = m.first->shift(addr);
                    if(m.second == s) {
                        type = m.first;
                        break;
                    }
                    addr += m.first->size;
                }
            cout << addr << '\n';
        }
        else {
            LL addr;
            cin >> addr;
            if(addr >= cur_addr) {
                cout << "ERR\n";
                continue;
            }
            DataType* type = nullptr;
            LL f_addr = 0LL;
            string res;
            for(auto& obj: toplevel_objects) {
                f_addr = obj.first->shift(f_addr);
                if(addr < f_addr) goto bad;
                if(addr < f_addr + obj.first->size) {
                    type = obj.first;
                    res = obj.second;
                    break;
                }
                f_addr += obj.first->size;
            }
            while(addr < f_addr + type->actual_size && !type->members.empty())
                for(auto& m: type->members) {
                    f_addr = m.first->shift(f_addr);
                    if(addr < f_addr) goto bad;
                    if(addr < f_addr + m.first->size) {
                        type = m.first;
                        res.push_back('.');
                        res += m.second;
                        break;
                    }
                    f_addr += m.first->size;
                }
            if(addr < f_addr + type->actual_size) cout << res << '\n';
            else cout << "ERR\n";
            continue;
            bad: cout << "ERR\n";
        }
    }
    for(auto it=types.begin(); it!=types.end(); it++)
        delete it->second;
    return 0;
}

这样只有 $146$ 行，$4.51\mathrm{KB}$。

不过个人觉得写个 Object 更清楚，所以讲解的时候就没改啦~

后记

算法固然重要，但是编码能力也很重要！强烈建议各位 OIer 重视大模拟，不在这种题上挂分~

写大模拟需要注意的几个点：

变量名写清楚，全写 a、b、c、d 到后面自己都不知道是啥，没法调试
该用指针就用指针，不要害怕，用多了会发现真的很好用
适当使用类和结构体，尽量不要全部使用 int 数组
时间复杂度允许的情况下，可读性比性能重要！！（比如本题没有使用二分查找）

祝大家在 NOIP 2023 取得好成绩！~~求赞qwq~~