Golf Bot

大家好，这是我第一次写题解，听说写题解水平会提高，所以我也凑一凑热闹。

首先让我们来明确题意

该题可以这样理解我们有长度为n的数组array1:[a1,a2,a3,a4,a5,a6,.....,an]
以及长度为m的数组array2:[b1,b2,b3,b4,b5,b6,.....bm]
问array2中有几个元素等于array1中一个或两个元素相加。注意是一个或两个。

分析

先简化问题好了，现在问题如下。判断对于一个数target，array1中是否有一个或两个数相加等于target；
如果这个问题解决了，那么我们可以对array2进行一次遍历，注意判断，得到答案。
这个问题并不难，左右双指针可以在线性时间内求出。因为，本题在入门练习题中，所以我把代码写出来。

//array1事先从小到大被排好序！！！！！！
bool solve(int target,vector<int>& array1) {
    int l = 0;int r = array1.size() - 1;// l最左,r最右。即array1[l]最小，array1[r]最大
    while (l <= r) { //注意这里要有等号，因为array1中的两个相加元素可以是重复的
        if (array1[l] + array1[r] == target||array1[l]==target||array1[r]==target) {return true; }//如果两者相加为target或其中某一个为target则返回true
        else if (array1[l] + array1[r] < target)l++;//如果小了l++变大
        else if (array1[l] + array1[r] > target)r--;//如果大了r--变小
    }
    return false;//没有找到
}

上述可以在线性时间内计算出来。

这样如果我们按照上述想法实施，遍历一遍，对于array2中每一个数值都调用solve()函数。
时间复杂度将为O(NM)N,M最大为10e5是过不去的！！

那么着手别的算法吧。
现在给出一组数据
array1:[1,3,5]
array2:[2,4,5,7,8,9]
//其实也就是测试用例啦。
我们可以三重循环解决这个问题(array2中可以被array1中一个或两个元素相加得到的元素个数)：

int solve(vector<int>& array1,vector<int>& array2) {
    int ans = 0;

    for (int i = 0;i < array1.size();i++)//先判断array1，array2中元素是否有交集。
        for (int j = 0;j < array2.size();j++)//即不用相加直接一发入洞
            if (array1[i] == array2[j])ans++;

    for (int i = 0;i < array1.size();i++)//遍历array1中每一个元素
        for (int j = 0;j < array1.size();j++)//将array1中每一个元素与array1[i]相加
            for (int k = 0;k < array2.size();k++)//看array1[i]+array1[j]是否在array2中
                if (array1[i] + array1[j] == array2[k])ans++;在则ans+=1
    return ans;
}

比如对于array1[1,3,5] array2[2,4,5,7,8,9]交集[5] ans=1
遍历到1则array1变为[2,4,6]全部加1包括自己，因为可以重复。
则交集为[2，4].ans+=2;
遍历到3则array1变为[4,6,8]
交集为[4,8],4出现过了所以ans+=1
遍历到5则array1变为[6,8,10]
交集[8]8算过了则ans不变
综上ans=4

现在我们换一种方式表达同样的数据
input[1,3,5]这里记录着机器可以打出的公里数，就相当于原先的array1
array1[0,1,0,1,0,1,0,0,0,0,0]对于索引i如果机器可以打出i公里则array1[i]=1否则为0
array2[0,0,1,0,1,1,0,1,1,1,0]对于索引i如果i公里处有洞则array2[i]=1否则为0

那么接下来我们对于input中每一个元素，使array1中每一个1元素向右移动input[i]公里。
这实际上意味着在抛出了input[i]的距离的情况下，还可能抛出的距离。
下面我们只需看看可能抛出的距离下是否有洞就行了。即array1为1的索引下array2是否为1

下面看一下。对于input[0]=1我们把array1整体向右移动1公里变为
array1[0,0,1,0,1,0,1,0,0,0,0]
array2[0,0,1,0,1,1,0,1,1,1,0]
则array1能投到，且array2中有洞的索引为2，4；
这时我们要把array2[2],array2[4]都变为0因为他们已经被投入了。
array2[0,0,0,0,0,1,0,1,1,1,0]
同样进行如此操作最终可得ans=3;
少了1，为什么？因为我们没有算一个数相加的情况。可以在input前加一个零[0,1,3,5]

为什么我们将问题这样转化呢？因为这很适合用位运算。
将array1,array2都看成二进制
array1:00101010000
array2:00101101110
对于上面的每一个步骤都可以用位运算的方式实现，这大大的提高了程序的运行效率。
array1整体向右移input[i]为：array1>>input[i];
找到可以投入的洞则(array1>>input[i])&array2
array2去掉这些可以投入的洞孔：
注意，这里分析一下，如何用位运算实现！！！！！！！
我们在这一步中要做到的是，对于array2中i处， 如果array2[i]为1且((array1>>input[i])&array2)[i]为1则变为0；其余不变。
即是这样的运算：0:0=0,0:1=0,1:0=1,1:1=0;前者为array1[i].
没有任何位运算适合但是若我们对后面的取一下反就会发现：
0:1=0,0:0=0,1:1=1,1:0=0
这其实就是&运算所以得到下面的公式：
array2 &= ~((array1>>input[i])&array2)
该公式应该是正确的，提交上去也确实是ac了。但还可以化简为以下的公式：
array2 ^= (array1>>input[i])&array2
我们仔细看看上面的运算规律：
0:0=0,0:1=0,1:0=1,1:1=0；想想如果0:1不存在是不是就是异或^运算了？
那么在我们计算时究竟会不会出现0:1的情况呢？
是不可能出现的！
对于索引i,array2[i]=0,((array1>>input[i])&array2)[i]=1这种情况是绝对不可能出现的！
因为：
假设array2[i]=0;
那么array2和(array1>>input[i])进行&运算的结果[i]一定为0(因为已经有一个固定为0了)
所以得到公式：array2 ^= (array1>>input[i])&array2;
这样这道题就做完了。
我们用C++容器bitset实现位运算。注意，我上面写的>>要统统换为<<!

代码如下

#include<iostream>;
#include<bitset>;
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;
    while (cin >> n) {
        bitset<200010> array1, array2;
        int input[200010];input[0] = 0;
        for (int i = 1;i <= n;i++) {
            cin >> input[i];array1[input[i]] = 1;
        }
        cin >> m;int tmp;
        for (int i = 1;i <= m;i++) {
            cin >> tmp;array2[tmp] = 1;
        }
        for (int i = 0;i <= n;i++) {
            array2 ^= array2 & (array1 << input[i]);//array2 &= ~(array2&(array1<<input[i]));
        }
        cout << m - (int)array2.count() << endl;
    }
}

写的冗长，谢谢大家