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