蒟蒻的小窝

蒟蒻的小窝

题解 P6747 【『MdOI R3』Teleport】

posted on 2020-08-11 16:39:05 | under 题解 |

这道题的题目描述就是给你一个 $a$ 数组,然后再给你个 $m$,让你找一个最大的 $k$,使 $k$ 异或整个 $a$ 数组的和小于等于 $m$。

笨蛋的方法就是从大到小枚举 $k$,一旦异或 $a$ 数组的和小于等于 $m$,了,就输出 $k$,但这样的时效使绝对不行的。

所以我们来想一想异或的实质,两个数, $A$, $B$, $A$ 异或 $B$ 的值就是将 $A$ 和 $B$ 都转为二进制数,然后向右按位对其,将小的数左边塞 $0$ 使 $2$ 个数的二进制位数相等,然后从左往右扫,一旦这一位上的二进制不同,假设位数为 $y$ ,异或的值 $x$ 就要加上 $2^y$。

好了既然是求 $k$ 异或整个 $a$ 数组的和,那其实就是将整个 $a$ 数组转成二进制数,然后存在一个数组中,将 $k$ 也转换成二进制数进行比对不就得了?但其实想到这里就不需要枚举 $k$,只需要通过模拟,当异或 $y$ 这一位的时候,如果 $k$ 的二进制数在这一位为0的时候,假设这一位上 $1$ 的个数为 $z$,异或的值就加上 $2^{(n-z)}$,为 $1$ 时 异或的值就加上 $2^z$。只要为 $1$ 时符合这一位就取 $1$,因为要 $k$ 越大越好嘛,不符合再取 $0$,而如果 $2$ 个都不符合时就回朔嘛,所以要用DFS来模拟这个过程。

但是!假设这一位上 $1$ 的个数为 $z$,在处理异或和的过程中,设, $2^{(n-z)}$ 或 $2^z$ 的值可能会爆出 $long long$,为了不开高精我们可以与处理一下,在代码中标出了。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,q;
long long m,s=((((long long)1<<62)-1)<<1)+1;
int a[65];
bool vis;
void dfs(int step,long long v,long long now,long long ans){
    if(vis)return;
    if(step<0){printf("%lld\n",ans);vis=1;return;}
    long long l=(long long)a[step]*now,r=(long long)(n-a[step])*now;
    if(s/now>(n-a[step])&&r+v<=m)dfs(step-1,r+v,now>>1,ans+now);\\s/now>(n-a[step])就是防止超出long long,下面也是
    if(s/now>a[step]&&l+v<=m)dfs(step-1,l+v,now>>1,ans);
}
inline int read(){
    int ret=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int x=read(),y=1<<30,cnt=30;
        while(y){
            while(x<y)y>>=1,cnt--;
            a[cnt]++;x-=y;
        }
    }
    q=read();
    while(q--){
        scanf("%lld",&m);
        dfs(52,(long long)0,(long long)1<<52,(long long)0);
        if(!vis)printf("-1\n");vis=0;
    }
   return 0;
}