本文共 1851 字，大约阅读时间需要 6 分钟。

codeforces1461D-Divide and Summarize

题目描述：

给定n个数组成的数列，选择一个mid值为当前数列中最大值与最小值之和除以二(向下取整),将这个数列分割为全部元素小于等于mid的一个数列和大于mid的另一个数列，数列内部的元素保持在原数列中的相对顺序，并舍去其中的一个数列，之后对剩下的那个数列进行上述重复操作，直至数列只剩下一个元素无法再分割。

思路：

观察分割方法，发现数列的原顺序对结果并没有影响，所以先对数列排序，排序后开始二分寻找分割点，模拟分割的过程，通过搜索直接求出所有的分割数列和，用map记录结果，在查询时直接离线查询即可。

代码：

#include
   
    using namespace std;using ll = long long;const ll N = 1e5+10;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();ll pre[N];int a[N];map
    
      mp;int binary_search(int l, int r, int val) {    while (r - l > 1) {        int mid = (l+r)/2;        if (a[mid] <= val) {            l = mid;        }else {            r = mid;        }    }    return l;}void dfs(int l,int r){    if(l>r)return ;    if(l==r){        mp[a[l]]++;        return ;    }    mp[pre[r]-pre[l-1]]++;    int mid = (a[l]+a[r])/2;    int md = binary_search(l, r+1, mid);    if (md == r) return ;    dfs(l,md);    dfs(md+1,r);}int main() {    int t;    scanf("%d",&t);    while(t--){        int n,q;        scanf("%d%d",&n,&q);        for(int i = 1; i <= n; i++){            scanf("%d",&a[i]);        }        sort(a+1,a+1+n);        memset(pre,0,sizeof(pre));        mp.clear();        for(int i = 1; i <= n; i++){            pre[i] = pre[i-1]+a[i];        }        dfs(1,n);        for(int i = 1; i <= q; i++){            int x;            scanf("%d",&x);            if(mp[x]){                printf("Yes\n");            }else{                printf("No\n");            }        }    }    return "BT7274", NULL;}inline ll read() {    ll hcy = 0, dia = 1;    char boluo = getchar();    while (!isdigit(boluo)) {        if (boluo == '-')dia = -1;        boluo = getchar();    }    while (isdigit(boluo)) {        hcy = hcy * 10 + boluo - '0';        boluo = getchar();    }    return hcy * dia;}
    
   

转载地址：https://www.cnblogs.com/cloudplankroader/p/14176411.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！