题解 P8289【[省选联考 2022] 预处理器】

· · 题解

更好的阅读体验：https://oi.baoshuo.ren/solutions/luogu-p8289/

思路

这是一道不大不小的模拟题，有一些注意事项：

  1. 判断有效的宏名比判断分隔符要容易实现。
  2. 题目有要求不能展开无限递归的宏，需要打标记记录一下。
  3. 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 函数类似，不再过多赘述。

清空字符串：

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。