1 条题解
-
-1
更好的阅读体验:https://oi.baoshuo.ren/solutions/luogu-p8289/
思路
这是一道不大不小的模拟题,有一些注意事项:
- 判断有效的宏名比判断分隔符要容易实现。
- 题目有要求不能展开无限递归的宏,需要打标记记录一下。
- STL 是个好东西。
详细实现可以看代码注释。
我的代码官方数据跑了 36ms
,卡卡常应该能卡到最优解的位置。STL 相关
一个非常好用的 C++ 参考手册(中文):zh.cppreference.com。
在考场上如果不知道怎么用 STL 可以去翻头文件中的注释(英文),里面有简单的说明。
std::string
入门声明一个
std::string
类型的变量s
:std::string s = "abcdef";
获取字符串长度:
s.size(); // 6
判空:
s.empty(); // false
截取子串:
s.substr(1, 3); // s 中从 1 开始长度为 3 的子串 // "bcd"
查找字串:
s.find("cde", 1); // s 中从下标为 1 的位置开始查找字串 "cde" // 2
同样地,也可以查找某个字符出现的位置:
s.find('c'); // s 中第一次出现的 'c' // 2
STL 也提供了其他查找函数:
find_first_of
:查找字符串中第一个包含指定字符(串)的位置。find_last_of
:查找字符串中最后一个包含指定字符(串)的位置。find_first_not_of
:查找字符串中第一个不包含指定字符(串)的位置。find_last_not_of
:查找字符串中最后一个不包含指定字符(串)的位置。
使用方法与上面的
find
函数类似,不再过多赘述。清空字符串:
s.clear();
std::unordered_map
入门std::unordered_map
在 C++11 中被引入,由于其基于哈希的实现导致了在大多数情况下std::unordered_map
比std::map
要快。声明一个
std::unordered_map<std::string, int>
类型的变量map
:std::unordered_map<std::string, int> map;
插入元素:
map["a"] = 1; map.insert(std::make_pair("b", 2)); // pair 的 first 键值为 key,second 键值为 value map["c"] = -1;
查找元素:
map.find("c"); // 返回迭代器 map.count("c"); // 返回元素个数(1 或 0)
删除迭代器
it
指向的元素:auto it = map.find("c"); map.erase(it);
删除键为
c
的元素:map.erase("c");
获取元素个数:
map.size(); // 2
判空:
map.empty(); // false
访问元素:
map["a"]; // 1
使用下标访问时如果元素不存在会自动新建,所以建议访问前先使用
map.count()
判断是否存在该元素。清空整个容器:
map.clear();
代码
#include <iostream> #include <string> #include <unordered_map> #include <vector> using std::cin; using std::cout; const char endl = '\n'; // 题目限制 const int N = 105; // 代码行数 int n; // 原始字符串 std::string s[N]; // 宏列表: <宏名, <内容, 正在展开>> std::unordered_map<std::string, std::pair<std::string, bool>> def; /** * 递归展开 * @param s 原始字符串 * @return 展开后的字符串 */ std::string dfs(std::string s) { std::string r; for (int i = 0, j; i < s.size(); i += j) { for (j = 0; i + j < s.size() && // 防止越界 ('0' <= s[i + j] && s[i + j] <= '9' || // 数字 'a' <= s[i + j] && s[i + j] <= 'z' || // 小写字母 'A' <= s[i + j] && s[i + j] <= 'Z' || // 大写字母 s[i + j] == '_'); // 下划线 j++); // 匹配合法宏名 if (j) { std::string tmp = s.substr(i, j); // 截取从 i 开始的 j 个字符 if (def.count(tmp) && !def[tmp].second) { // 该宏存在且未处在展开状态 def[tmp].second = true; // 将该宏标记为正在展开 r += dfs(def[tmp].first); // 递归展开 def[tmp].second = false; // 取消标记 } else { r += tmp; // 不存在直接按原样加入到结果中 } } else { r += s[i++]; // 不合法,直接略过,加入到结果中 } } return r; } int main() { std::ios::sync_with_stdio(false); cin >> n; // 第 0 行读入 n 后尾随的换行符 for (int i = 0; i <= n; i++) { std::getline(cin, s[i]); } for (int i = 1; i <= n; i++) { if (s[i][0] == '#') { // 预处理命令 if (s[i].substr(1, 6) == "define") { int p = s[i].find_first_of(' ', 8); // 宏名后的空格位置 std::string name = s[i].substr(8, p - 8), content = s[i].substr(p + 1); // 插入内容 def[name] = std::make_pair(content, false); } else { // s[i].substr(1, 6) == "undef" std::string name = s[i].substr(7); def.erase(name); } cout << endl; } else { // 普通文本 cout << dfs(s[i]) << endl; } } return 0; }
本文最后更新于 2022/04/26。
- 1
信息
- ID
- 247
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 25
- 已通过
- 8
- 上传者