题解：P8187 [USACO22FEB] Robot Instructions S

· · 题解

P8187 [USACO22FEB] Robot Instructions S

前言 & 折半搜索简介

前言

作者的折半搜索（Meet in the middle）算法是在 OI Wiki 上自学的，而 OI Wiki 上对于折半搜索的代码是这么写的：

for(int i=0;i<(1<<(n/2));i++)
{
    //啊吧啊吧
}
for(int i=0;i<(1<<(n-n/2));i++)
{
    //啊吧啊吧
}

这就导致作者在学习题解思路是很难受（题解区全是使用 DFS 和双指针什么的），所以这篇题解诞生了。

折半搜索简介

Meet in the middle 算法的主要思想是将整个搜索过程分成两半，分别搜索，最后将两半的结果合并。

此算法适用于输入数据较小，但还没小到能直接使用暴力搜索的情况。能够将指数将一半，如原来的时间复杂度为 O(a^b) 的算法降到 O(a^{\frac{b}{2}})。对于下面的这段代码（取了第一部分，第二部分与第一部分类似，只是最外层循环条件和内层循环中的变量改变时不同而已，应该较容易理解）。

for(int i=0;i<(1<<(n/2));i++)
{
    ll x=0,y=0,tot=0;   //参数设置
    for(int j=0;(i>>j)>0;j++)   //优化时间
    {
        if((i>>j)&1)    //可以选择
        {
            x+=a[j+1].x;   //对于变量的操作
            y+=a[j+1].y;
            tot++;         //操作次数累加
        }
    }
    mp[tot][1ull*x*base+y]++;   //啊吧啊吧
}

再上面的代码中，最外层循环的 for(int i=0;i<(1<<(n/2));i++) 中的 (1<<(n/2)) 是对于 [1,n/2] 选或不选形成的所有方案数。

转换为二进制就是 110101 ，此时的 n 便是 12，描述的是第 1、3、5、6 项被选择上，对应到代码中就是 (i>>j)&1 和 x+=a[j+1].x; y+=a[j+1].y。

因为二进制的最低位从 0 开始，所以 j 从 0 开始，在进行操作的时候下标要加上 1。

在第一部分操作完后，根据需要在第二部分进行操作便可以了。

题意

对于一个二维平面上的点 (0,0)，给定另一个点 (x_g,y_g)，再给定 q 条指令，让你通过 k 条指令从点 (0,0) 到达 (x_g,y_g)。输出当选择 1 到 n 条指令可以到达终点的方案数。

Solution

读题，可知道 n 的最大值有 40，若直接使用 DFS 进行搜索，无疑会超时。

那么，考虑折半搜索，很容易想到使用 map 存坐标，若直接使用 STL 的 pair，有概率超时（未尝试），考虑哈希，哈希函数的写法就将横坐标乘上大质数（要真的很大），哈希开 unsigned long long，坐标要开 long long。

实现细节见代码，对于上面有疑问的再结合代码之后应该都可以理解。

Code

OI Wiki 写法

#include<bits/stdc++.h>
#define ll long long
#define lll unsigned long long
#define dou double
#define S string
#define INF 2147483647
#define pi pair<int,int>
#define mkp make_pair
#define mii unordered_map<lll,int> 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;

const lll base=1e9+7;
struct node
{
    ll x,y;
}a[41];
int n;
ll gx,gy;
ll ans[41];
mii mp[41];

int main()
{
    IOS;
    cin>>n>>gx>>gy;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    for(int i=0;i<(1<<(n/2));i++)
    {
        ll x=0,y=0,tot=0;
        for(int j=0;(i>>j)>0;j++)
        {
            if((i>>j)&1)
            {
                x+=a[j+1].x;
                y+=a[j+1].y;
                tot++;
            }
        }
        mp[tot][1ull*x*base+y]++;       //走tot步，当前在(x,y)的方案数++
    }
    for(int i=0;i<(1<<(n-n/2));i++)     //注意(1<<(n-n/2))，不要写错
    {
        ll x=0,y=0,tot=0;
        for(int j=0;(i>>j)>0;j++)
        {
            if((i>>j)&1)
            {
                x+=a[j+1+n/2].x;        //注意j+1+n/2，不要写错
                y+=a[j+1+n/2].y;
                tot++;
            }
        }
        for(int j=0;j+tot<=n;j++)       //总步数肯定不能超过n
        {
            lll sum=1ull*gx*base+gy-(1ull*x*base+y);      
            //哈希，因为上面的哈希写的是x*base+y，那么对于第二部分走到的哈希值减去终点的哈希值便是在第一部分中可能走到的坐标
            if(mp[j].find(sum)!=mp[j].end())        //sum存在，不要使用mp[j][sum]，这样会创建一个新的元素位置，增加时间和空间的复杂度
            {
                ans[j+tot]+=mp[j][sum];             //统计ans的时候不要忘记加上第二部分当前走的步数tot
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}
/*

*/

题外话

推荐题目：

P3067 [USACO12OPEN] Balanced Cow Subsets G

P1466 [USACO2.2] 集合 Subset Sums

P2962 [USACO09NOV] Lights G