D. Divide and Summarize(思维)-蒲公英云

D. Divide and Summarize(思维)

题目

思路：其实想一想不难看出我们只需要将所有的情况得到的值存储起来，然后在之后的问询阶段判断是否有这个值就可以了。然后注意一下当值都相同时进行特殊判断，当时直接爆栈了，才发现这里无限递归了下去。细节见代码。

Code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;
int lst[Max];
int Mod = 1e9 + 7;
ll sum[Max];
map<ll, int> ma;
void check(int l, int r)
{ 
    int f = 1;
    int k = lst[l];
    for (int i = l;i <= r;i++)if (k != lst[i]) {  f = 0; }
    if (f){ ma[sum[r] - sum[l - 1]]++;return;}
    ma[sum[r] - sum[l - 1]]++;
    double mid = double((double)lst[l] + lst[r]) / 2;
    int j;
    for (int i = l;i <= r;i++)if (mid >= lst[i])j = i;
    check(l, j);check(j+1, r);
}
int main()
{ 
    int t;cin >> t;
    while (t--)
    { 
        int n, m;cin >> n >> m;
        ma.clear();
        for (int i = 1;i <= n;i++)cin >> lst[i];
        sort(lst + 1, lst + 1 + n);
        for (int i = 1;i <= n;i++)sum[i] = sum[i - 1] + lst[i];
        check(1, n);
        for (int i = 1;i <= m;i++)
        { 
            int s;cin >> s;if (ma[s])cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
}