搜索专题T4题解

经验分享区
1

这道题目很容易打出暴力解就是每次 dfs 分两种情况：

  • 将 x 放入蓝盒子， y 放入红盒子
  • 将 y 放入蓝盒子， x 放入红盒子

很简单打出搜索：

   if(step==n+1){
		ans=max(ans,lcm(x,y));
		return;
	}
	dfs(gcd(x,a[step]),gcd(y,b[step]),step+1);
	dfs(gcd(x,b[step]),gcd(y,a[step]),step+1);

然而这样显然会 TLE 我们考虑数学优化。

首先我们需要知道一个数的约数是小于等于这个数的所以 \gcd (x,y)≤x,y 那么题目中最后让我们求两个盒子中的数的最小公倍数，记为 [s_1,s_2] 我们考虑他的上一次情况 [k_1,k_2] 容易得出： s_1 \ | \ k_1,s_2 \ | \ k_2 那么可以得出 [s_1,s_2] \ | \ [k_1,k_2] 所以我们越往下搜索，最后答案的值只会越来越小！所以可以得到剪枝若 lcm(x,y)<=ans 那么我们可以直接返回因为他的出的最后答案一定小于等于 ans 加上剪枝以后我们就可以 AC 了！

1 个赞
2

前面的我都懂，but后面这一段我看的不太懂，可以讲详细一点吗？

3

@huangfeidong s_1,s_2 分别是 k_1,k_2 的约束吧对吧

4

对的没错

5

@huangfeidong 那么 s_1,s_2 他们的最小公倍数不可能比 k_1,k_2 的大吧

6

那肯定的

啊。。。我废了

7

@huangfeidong 那不就好了吗？得证！越往后面搜索最小公倍数越小哇！