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