自动搬运

查看原文

来自洛谷，原作者为

	maomao233 私信互关aaa 因为 400 粉儿以后看不到了。 ⎛⎝≥⏝⏝≤⎛⎝

搬运于2025-08-24 22:20:47，当前版本为作者最后更新于2023-08-17 16:40:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

分析

前置芝士：括号匹配。

本题的主要思路：

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 记录。