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;}}
}