浅谈搜索的亿些优化 ---- 2

MoonCake2011 · 2023-07-03 21:34:56 · 个人记录

浅谈搜索的亿些优化 ---- 1.

第三个优化:双向DFS

双向搜索是一种常见策略，一般用于优化枚举子集问题，主要适用于有主要初始状态与最终状态的时候。

方法如下，可以先搜索前半段，在搜索后半段，再对后半段产生的答案去匹配前半段产生最终答案。

例题:[CEOI2015 Day2] 世界冰球锦标赛.

此题是一个子集和问题，可以采用双向搜索。

先搜索前半段产生的答案，再搜索后半段产生的答案，分别存数组里(设前半段为fr,后半段为bk)。

接下来是一个最难环节，统计答案。

我们来想一下，只要 fr_i+bk_i \le m 就行，可以枚举，但时间复杂度太高了，于是，二分，它来了。

我们将 fr_i+bk_i \le m 变换为 fr_i \le m-bk_i.

我们可以对fr排序.

在fr里二分查找在 m-bk_i 即可。

我们用upper_bound寻找最小的大于 m-bk_i 的前一个的排名就是 fr_i+bk_i \le m 的数量。

这波批量统计NB吧。

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,mid;
int a[110];
int dp[signed(1e6)+10],ans;
int fr[signed(1e7)+10],tot1;
int bk[signed(1e7)+10],tot2;
void dfs1(int x,int sum){
    if(sum>m) return;
    if(x>mid){
        fr[++tot1]=sum;
        return;
    }
    dfs1(x+1,sum);
    dfs1(x+1,sum+a[x]);
}
void dfs2(int x,int sum){
    if(sum>m) return;
    if(x>n){
        bk[++tot2]=sum;
        return;
    }
    dfs2(x+1,sum);
    dfs2(x+1,sum+a[x]);
}
signed main() {
    cin>>n>>m;
    mid=n>>1;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    if(m<=1e6){
        dp[0]=1;
        for(int i=1;i<=n;i++)
            for(int j=m;j>=a[i];j--)
                dp[j]+=dp[j-a[i]];
        for(int i=0;i<=m;i++)
            ans+=dp[i];
        cout<<ans;
        return 0;
    }
    dfs1(1,0);
    dfs2(mid+1,0);
    sort(fr+1,fr+tot1+1);
    for(int i=1;i<=tot2;i++)
        ans+=upper_bound(fr+1,fr+tot1+1,m-bk[i])-fr-1;
    cout<<ans;
    return 0;
} 

例题:Anya and Cubes.

此题是一个子集和问题的变种。

现在有三个选择:选，不选，选并把它阶乘一下。

这样，时间复杂度高达 O(3^{26})。

因为 S 不超过long long，所以只有 a_i \le 20 才有权利去阶乘。

我们与上一题一样，采用双向搜索。

合并是个难题。

我们尝试建立一个unordered_map(C++11)数组把前半段的结果标记(注意重复)下来，第 i 个unordered_map表示使用 i 个阶乘得到的集合产生的标记。

接着，把后半段得到的结果对其进行匹配。

设后半段的某个结果需用到的阶乘数为p,选到的数的总和为sum。

我们设 1 \le x \le k-p。

我们统计第 x 个unordered_map的 S-sum 项的个数.

提前预处理阶乘，我们成功AC。

代码.

第四个优化:A^* 搜索.

谈了那么久，终于到广搜优化了。