SP1296 SUMFOUR - 4 values whose sum is 0 题解 wxwoo 2019-04-23 题解 / SPOJ 原题目链接 首先想到$\Theta(n^4)$的暴力枚举，但$n\le 4000$显然不行。 考虑先预处理出c数组和d数组的和，再暴力计算答案。 由于c数组和d数组的和可能会有重复，排序后使用二分来降低时间复杂度 最终时间复杂度$\Theta (n^2\log n)$ 阅读全文 二分
SP733 MTWALK - Mountain Walking 题解 wxwoo 2019-03-13 题解 / SPOJ 原题目链接 看到题目就想到了dfs+剪枝 然后就想到了dfs有问题 例如这组数据 1234-9-12| | |2-4-10 从4开始，到10结束 dfs会走$4 \to 2 \to 4 \to 10$，答案为8 然而很明显走$4 \to 9 \to 4 \to 10$更优，答案为6 当然你加一大堆玄学优化也是可以搜出正确答案的 这里不再多讲，而是提供另一种思路： 二分 阅读全文 二分