一开始挺不想写的，知道自己的搜索烂成渣渣……

1.不用想剪枝，也许有，但是不剪也能过。

2.不要像第一次的我，直接每次深度为n时暴力求一遍表达式的值，会造成很多浪费的计算。不论怎样处理计算过程，都应考虑将计算的参数随搜索函数一起递归。

3.注意，n可能大于10，这就是说，'.'运算不一定会使得前面的数增加十倍。当后面接的数字>=10的时候，前面的数会变大100倍。

4.如果n很大，而且我们枚举的前几个运算符全是'.'的话，int也许就吃不消了。据说也能AC？慎重考虑就好。

5.注意题目规定的输出顺序，这相当于规定了你的深搜顺序！

6.虽然只用输出前20个解，但是请把整棵搜索树遍历完全，因为你还要输出总的方案数。

附：N = 15 时，你的输出应该是下面这样

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 - 10 - 11 - 12 - 13 - 14 + 15
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 - 9 + 10 - 11 - 12 - 13 + 14 - 15
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 - 9 - 10 + 11 - 12 + 13 - 14 - 15
1 + 2 + 3 + 4 + 5 + 6 + 7 - 8 + 9 + 10 - 11 - 12 + 13 - 14 - 15
1 + 2 + 3 + 4 + 5 + 6 + 7 - 8 + 9 - 10 + 11 + 12 - 13 - 14 - 15
1 + 2 + 3 + 4 + 5 + 6 - 7 + 8 + 9 + 10 - 11 + 12 - 13 - 14 - 15
1 + 2 + 3 + 4 + 5 + 6 - 7 - 8 - 9 + 10 - 11 - 12 - 13 + 14 + 15
1 + 2 + 3 + 4 + 5 + 6 - 7 - 8 - 9 - 10 + 11 - 12 + 13 - 14 + 15
1 + 2 + 3 + 4 + 5 + 6 - 7 - 8 - 9 - 10 - 11 + 12 + 13 + 14 - 15
1 + 2 + 3 + 4 + 5 + 6 - 7 - 8 . 9 + 10 + 11 + 12 + 13 + 14 + 15
1 + 2 + 3 + 4 + 5 + 6 . 7 - 8 . 9 - 10 - 11 + 12 - 13 + 14 + 15
1 + 2 + 3 + 4 + 5 + 6 . 7 . 8 - 9 . 10 - 11 . 12 + 13 . 14 + 15
1 + 2 + 3 + 4 + 5 - 6 + 7 + 8 + 9 + 10 + 11 - 12 - 13 - 14 - 15
1 + 2 + 3 + 4 + 5 - 6 + 7 - 8 + 9 - 10 - 11 - 12 - 13 + 14 + 15
1 + 2 + 3 + 4 + 5 - 6 + 7 - 8 - 9 + 10 - 11 - 12 + 13 - 14 + 15
1 + 2 + 3 + 4 + 5 - 6 + 7 - 8 - 9 - 10 + 11 + 12 - 13 - 14 + 15
1 + 2 + 3 + 4 + 5 - 6 + 7 - 8 - 9 - 10 + 11 - 12 + 13 + 14 - 15
1 + 2 + 3 + 4 + 5 - 6 - 7 + 8 + 9 - 10 - 11 - 12 + 13 - 14 + 15
1 + 2 + 3 + 4 + 5 - 6 - 7 + 8 - 9 + 10 - 11 + 12 - 13 - 14 + 15
1 + 2 + 3 + 4 + 5 - 6 - 7 + 8 - 9 + 10 - 11 - 12 + 13 + 14 - 15
1350

代码
#include<cstdio>
#include<cstdlib>
using namespace std;
#define int long long
int n, ans = 0;
char path[20];
const char mv[3] = { '+','-','.' };
inline void putAns(void) {
	if (++ans > 20)return;
	for (int i = 1; i < n; i++)
		printf("%lld %c ", i, path[i]);
	printf("%lld\n", n);
}
inline void search(int p, int res, int tmp, int neg) {
	if (p == n) {
		if (res + neg*tmp == 0) putAns();
		return;
	}
	path[p] = '+'; search(p + 1, res + neg*tmp, p + 1, 1);
	path[p] = '-'; search(p + 1, res + neg*tmp, p + 1, -1);
	path[p] = '.'; search(p + 1, res, tmp*(p + 1 > 9 ? 100 : 10) + p + 1, neg);
}
signed main(void) {
	scanf("%lld", &n);
	search(1, 0, 1, 1);
	printf("%lld\n", ans);
//	system("pause");
}

• Re:心得 + 粘代码 (2426) alwaysgo 2017-08-22 15:21:16