zcmimi's blog

arrow_back剪枝共5篇文章

avatar
zcmimi
2020-09-23 17:16:30

前置知识:

  • 迭代加深搜索
  • A*

迭代加深搜索

迭代加深搜索是一种每次限制搜索深度的深度优先搜索。

首先设定一个较小的深度作为全局变量,进行DFS

每进入一次DFS,将当前深度加一,当发现大于设定的深度就返回。

如果在搜索的途中发现了答案就可以回溯

avatar
zc
2020-09-23 21:26:00

查看原题

点击跳转

使用ida*

首先将数组离散化为1,2,\dots,n

一次翻转最多只能改变一对相邻数的差,

因此对于一个序列,有多少对相邻的数差不为1,就至少要翻转多少次。

估价函数:

a[n+1]=n+1;
int h(){
    int cnt=0;
    for(int i=1;i<=n;++i)cnt+=(a[i]!=a[i+1]+1&&a[i]!=a[i+1]-1);
    return cnt;
}
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先预处理出所有幸运数字

当前要求的是[l,r]中的幸运数字

我们可以使用容斥,用[1,r]-[1,l-1]

假设当前幸运数字为x,[l,r]中是x的倍数的有\left \lfloor \frac rx \right \rfloor - \left \lfloor \frac lx \right \rfloor +1

[1,r],[1,l-1]中的幸运数字的倍数可能有交集

继续容斥:

选1个-选2个的lcm+选3个的lcm-...

剪枝:

  1. 可以发现,一个数是另一个合法倍数的倍数,那么这个数字相当于没用(因为被前面的统计过了),可以删掉

  2. 如果将幸运数字从大到小排序,搜索时可以更快突破边界

  3. 现在因为所有数都不满足是另外一个数的倍数,所以合并任意两个数的时候,lcm的最小情况就是乘上一个3

    所以对于所有>r/3的合法数字,显然不能够和任何一个数合并了,所以这一部分可以拿出来直接提前算好

剩下的直接暴搜

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

搜索+剪枝

详见注释

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

1/1
Search
search