vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

题解 CF1461D【Divide and Summarize】

posted on 2020-12-12 11:43:37 | under 题解 |

显然 $s$ 合法当且仅当它属于切片操作得到的所有数组和的集合。而且在进行切片操作前先对整个数组排序肯定是没有影响的。

模拟一遍这个切片操作,求出所有可能的数组和即可。每次递归只需要二分出中间位置,最坏复杂度为 $O(nlogn)$,稳过。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;

inline int read(){
    int x=0,fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*fh;
}

const int N=1e7+5;
int top,a[N];
ll sum[N],ans[N];

void di(int L,int R){
    if(L==R){
        ans[++top]=a[L];
        return;
    }
    int mid=(a[L]+a[R])>>1,pos=upper_bound(a+L,a+R+1,mid)-a-1;
    if(pos==R){
        ans[++top]=sum[R]-sum[L-1];
        return;
    }
    ans[++top]=sum[pos]-sum[L-1];
    ans[++top]=sum[R]-sum[pos];
    di(L,pos);
    di(pos+1,R);
}

void work(){
    int n=read(),q=read();
    top=0;
    fo(i,1,n) a[i]=read();
    sort(a+1,a+1+n);
    fo(i,1,n) sum[i]=sum[i-1]+a[i];
    di(1,n);
    ans[++top]=sum[n];
    sort(ans+1,ans+1+top);
    fo(i,1,q){
        int s=read();
        if(binary_search(ans+1,ans+1+top,s)) puts("Yes");
        else puts("No");
    }
    //puts("");
}
int main(){
    int T=read();
    while(T--){
        work();
    }
    return 0;
}