GoodCoder666的个人博客

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

2023-10-29 · 16 min read

C++ 算法竞赛

题目传送门
 洛谷博客 CSDN

CSP-S 2023 T3 结构体题解

基本思路

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

由于可以递归式的创建元素，最多可以同时存在 $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)：

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

using LL = long long;

数据类型的存储

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

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

对齐操作，依照如下公式：

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

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

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

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 记录类型名到数据类型的映射关系：

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);

操作 1：定义类型

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

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：定义元素

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

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

Object 的定义：

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

计算地址并保存元素：

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';

操作 3：访问元素

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

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);
}

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

// 读入
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[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; // 地址移到下一个元素
    }

输出最终地址：

cout << addr << '\n';

操作 4：访问地址

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

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) 不是基本类型（类型有成员）
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 标签

完整代码

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

#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 的定义没有必要，也不需要存储每个顶层元素的地址，同时还可以稍加压行：

#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~~

- CSP-S 2023 T3 结构体题解

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

CSP-S 2023 T3 结构体 题解