首页 > 其他分享 >洛谷 P9754 [CSP-S 2023] 结构体 题解

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

时间：2024-09-08 23:24:35浏览次数：13  
标签：P9754 洛谷 addr 题解 obj first type string size

题目传送门
洛谷博客 CSDN

CSP-S 2023 T3 结构体 题解

基本思路

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

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

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

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

分步详解

准备

用 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

标签：P9754,洛谷,addr,题解,obj,first,type,string,size
From： https://www.cnblogs.com/stanleys/p/18403713/csps2023-t3

相关文章

  • AT_agc027_f [AGC027F] Grafting 题解
    笑点解析：NOIP模拟赛把这题放在T3。因为每一个点只能动一次，答案一定\(\len\)，所以我们分两种情况讨论：当答案小于\(n\)答案如果小于\(n\)，那么一定有一个点是一直没有被动过的。我们枚举这个点，将无根树转化为两棵以这个点为根的有根树。我们将第一棵树和第二棵树同构的部分......
  • AtCoder Beginner Contest 254 A~E 题解
    A-LastTwoDigits题目大意给定正整数\(N\)，求\(N\)的后两位。\(100\leN\le999\)输入格式\(N\)输出格式输出\(N\)的后两位，注意输出可能有前导0。样例\(N\)输出\(254\)54\(101\)01分析题目已经规定\(N\)是三位数，因此无需使用整数输入，直接将输入看成......
  • AtCoder Beginner Contest 258 A~Ex 题解
    D-Trophy题目大意有一个游戏，由\(N\)个关卡组成。第\(i\)个关卡由一个数对\((A_i,B_i)\)组成。要通过一个关卡，你必须先花\(A_i\)的时间看一次介绍。然后，用\(B_i\)的时间打通这个关卡。若想多次通过同一个关卡，则第一次需要看介绍，后面无需再看（即如果想打通第\(i\)关\(N\)次，则所......
  • AtCoder Beginner Contest 260 A~F 题解
    A-AUniqueLetter题目大意给定一个长度为\(3\)的字符串\(S\)。输出\(S\)中出现正好一次的字母（任意，如abc中，三个字母都可为答案）。如果没有，输出-1。数据保证\(S\)的长为\(3\)，且由小写英文字母组成。输入格式\(S\)输出格式输出任意符合条件的答案。样例\(S\)输出......
  • LINE Verda Programming Contest (AtCoder Beginner Contest 263) A~E 题解
    A-FullHouse题目大意来自一个掼蛋爱好者的翻译qwq给定一副扑克牌中五张牌的编号\(A,B,C,D,E\)，判断这五张是否为一组“三带二”。（不懂的自行百度数据范围：\(1\leA,B,C,D,E\le13\)，且\(A,B,C,D,E\)不会全部相同。输入格式\(A~B~C~D~E\)输出格式如果是“三带二”，输出Yes；否......
  • 【洛谷P5587】打字练习
    【P5587】打字练习【废话】首先，作为我练习字符串的一道题，很自然的意料之中的遇到了瓶颈【前置知识】字符的输入  久远的记忆让我以为gets还能用，于是就RE了，后来又用scanf("%[^\n]",s);，但是由于没有熟练掌握，换为getchar    getchar一次只能进行一个字符的......
  • BZOJ 1396 识别子串 题解
    Statement给\(S\)，令\(x\)为\(S\)的第\(k\)个字符，称\(T=S[i..j]\)为关于\(x\)的识别子串，当且仅当：\(i\lek\lej\)（含\(x\)这一位）\(T\)在\(S\)中只出现一次求\(S\)关于每一位字符的最短识别子串长度，\(|S|\le10^5\).Solution1以下是我没看题解瞎胡的首先......
  • 动态规划01背包的一个例题——洛谷P2871 题解
    题面有N件物品和一个容量为M的背包。第I件物品的重量是W[i],价值是D[i].求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。样例数据输入46142631227输出23分析（如果亲爱的读者对动态规划略有了解的话应该能看出来这是个01背包的板子......
  • BZOJ 3796 Mushroom追妹纸 题解
    Statement给\(s_1,s_2,s_3\)，求最长的\(w\)的长度，满足\(w\)是\(s_1\)子串\(w\)是\(s_2\)子串\(s_3\)不是\(w\)子串Solution1以下是我没看题解瞎胡的首先一个弱智想法是，枚举\(s_1\)上\(w\)的左端点，二分右端点，判定时\(s_2\)用SAM，\(s_3\)用单串AC自动......
  • BZOJ 4502 串 题解
    妙妙数数题key：数数题通常是，对于特定形式的计数，就盯着这个模式观察，看出一些充要条件、计数形式的转化，然后想办法维护。优化的本质就是把难算的变成好算的，把不好一起统计的（只能一个个数的）以某种角度、用某些数据结构，一起统计（多个多个数）。我觉得难点通常在于“盯出一些充要条件”，......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99