D. Divide and Summarize(BFS+二分+预处理)

Problem - 1461D - Codeforces

迈克收到一个长度为n的数组作为生日礼物，决定测试一下它的漂亮程度。

如果有一种方法可以通过一定数量（可能是零）的切片操作得到一个元素总和为si的数组，那么这个数组将通过第i次漂亮度测试。

一个数组的切分操作是以如下方式进行的。

假设mid=⌊max(array)+min(array)2⌋，其中max和min-是寻找最大和最小数组元素的函数。换句话说，mid是数组的最大和最小元素之和除以2后四舍五入。
然后，数组被分割成左右两部分。左边的数组包含所有小于或等于mid的元素，右边的数组包含所有大于mid的元素。左边和右边的元素保持它们在数组中的相对顺序。
在第三步中，我们选择我们想保留的左和右数组中的哪一个。所选择的数组将取代当前的数组，而另一个数组则被永久地丢弃了。
你需要帮助Mike找出q prettiness测试的结果。

请注意，你测试的是数组a的漂亮程度，所以每次漂亮程度测试都是从原始（初始）数组a开始的，因此，第一个切片（如果需要）总是在数组a上进行。

输入
每个测试包含一个或多个测试案例。第一行包含测试用例的数量t（1≤t≤100）。

每个测试用例的第一行包含两个整数n和q（1≤n,q≤105）--数组a的长度和prettiness测试的总数量。

每个测试用例的第二行包含n个整数a1,a2,...,an（1≤ai≤106）--数组a的内容。

每个测试用例的下一个q行包含一个整数si（1≤si≤109）--迈克想在第i个测试中得到的元素之和。

保证n和q的总和不超过105（∑n，∑q≤105）。

输出
打印q行，每行都包含一个 "是"，如果相应的漂亮度测试通过，则是 "否"。

例子
inputCopy
2
5 5
1 2 3 4 5
1
8
9
12
6
5 5
3 1 3 1 3
1
2
3
9
11
输出拷贝
有
不
是
不
是的
不
是的
不
是
是
注释
第一个测试案例的解释。

我们可以通过以下方式得到一个和为s1=1的数组。
1.1 a=[1,2,3,4,5], mid=1+52=3, left=[1,2,3], right=[4,5] 。我们选择保留左边的数组。

1.2 a=[1,2,3], mid=1+32=2, left=[1,2], right=[3]. 我们选择保留左边的数组。

1.3 a=[1,2], mid=1+22=1, left=[1], right=[2]. 我们选择保留左边的数组，其总和等于1。

可以证明，和为s2=8的数组是不可能产生的。
一个和为s3=9的数组可以通过以下方式生成。
3.1 a=[1,2,3,4,5], mid=1+52=3, left=[1,2,3], right=[4,5] 。我们选择保留右边的数组，其和等于9。

可以证明，和为s4=12的数组是不可能产生的。
我们可以通过以下方式得到一个总和为s5=6的数组。
5.1 a=[1,2,3,4,5], mid=1+52=3, left=[1,2,3], right=[4,5] 。我们选择保留左边的，其总和等于6。

对第二个测试案例的解释。

可以证明一个和为s1=1的数组是不可能产生的。
我们可以通过以下方式得到一个和为s2=2的数组。
2.1 a=[3,1,3,1,3], mid=1+32=2, left=[1,1], right=[3,3,3] 。我们选择保留左边的数组，其和等于2。

可以证明，一个总和为s3=3的数组是不可能产生的。
我们可以通过以下方式得到一个总和为s4=9的数组。
4.1 a=[3,1,3,1,3], mid=1+32=2, left=[1,1], right=[3,3,3] 。我们选择保留右边的数组，其和等于9。

我们可以通过零切分操作得到一个总和为s5=11的数组，因为数组总和等于11。

题解:

我们可以发现每次都是根据数组区间最大值+最小值/2,进行分割,与顺序无关,那我们先排序,求一下前缀和以便,求出某段区间的值,

我们发现通过上述分割操作,找到的值是一定的,并且也不多,

利用BFS遍历所有区间,每次二分得到比mid大的下标,根据前缀和来得到所求区间的值

我们可以提前预处理出来所有的值,然后看询问的值是否出现过

注意我们是可以不切片的,所以所有值相加的值也要存起来

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
int n,q,f;
int a[200505];
int b[200050];
map<int,int> vis;
void bfs()
{
	queue<pair<int,int>> q;
	q.push({1,n});
	while(q.size())
	{
		auto t = q.front();
		q.pop();
		int l = t.first,r = t.second;
		int mid = (a[l] + a[r])/2;
		int k = upper_bound(a+1,a+1+n,mid) - a;
		int ans ;
		if(r >= k)
		{
			ans = b[r] - b[k-1];
			vis[ans] = 1;
			q.push({k,r});
 
		}
		if(k<=r&&k-1>=l)
		{
			ans = b[k-1] - b[l-1];
			vis[ans] = 1;
			q.push({l,k-1});
    	}
		
	}
}
//1 1 3 3 3
void solve()
{
	
	cin >> n >> q;
	for(int i = 1;i <= n;i++)
	cin >> a[i];
	vis.clear();
	sort(a+1,a+1+n);
	for(int i = 1;i <= n;i++)
	{
		b [i] = b[i-1] + a[i];
	}
	bfs();
	vis[b[n]] = 1;
	while(q--)
	{
		int s;
		cin >> s;
		if(vis[s])
		{
			cout<<"YES\n";
		}
		else
		{
			cout<<"NO\n";
		}
	}
 
}
signed main()
{
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}