P6439 题解

· · 题解

题目传送门

分析

前置芝士：括号匹配。

本题的主要思路：

1.使用数据结构栈进行括号匹配。即，当遇到左括号时，入栈；遇到右括号时，则把栈顶弹出并做记录。

2.进行搜索。注意到题面末尾，保证给出的算术表达式的长度不超过 200，所以可以直接用状压记录括号的使用情况。具体地，可以使用暴力，统计消去的括号的位置，然后继续将剩余的字符组合为字符串。我们可以将这个字符串放进数组里，方便以后的排序及去重。

3.之后使用深度优先搜索即可。最后可以使用 sort 及 unique 库函数即可对所有字符串进行排序及去重。于是得代码。

但先别急着抄（

一交发现 RE，70 分。于是这个彩笔将数组开大然后又 MLE 了。

所以我们需要尽可能减少空间。发现瓶颈在于存储字符串，考虑到答案很容易就会重复导致浪费空间。如果我们让传入 dfs 函数里的变量 x 不再重复进行计算，即可大大减少空间。

于是，我们便可以使用记忆化搜索（其实就是一个桶）。设一个桶为 b，若 x 未被计算过（即 b_x=0），则进行搜索，并将 b_x 赋值为 1，代表已经搜索了 x；否则说明已经搜索过，无需进行搜索并存储，跳过即可。于是 dfs 函数就可修改为：

inline void dfs(int x)
{
    if(b[x])
    {
        return; // 若已经计算过则跳过
    }
    b[x]=1; // 将 x 标记
    if(x)
    {
        sb(x);
    }
    for(int i=1;i<=cnt1;i++)
    {
        if(x&(1<<(i-1)))
        {
            continue;
        }
        dfs(x|(1<<(i-1)));
    }
}

得 AC 记录。