CodeForces 1461 D. Divide and Summarize

CodeForces 1461 D. Divide and Summarize"/>

CodeForces 1461 D. Divide and Summarize

CodeForces 1461 D. Divide and Summarize

题目大意：

大致意思就是给出一个数组，你可以操作0次或若干次改变这个数组。然后给出 q q q 个查询，问能不能找到一个数组和等于 s s s。

具体操作就是选取一个 m i d = ⌊ m a x ( a r r a y ) + m i n ( a r r a y ) 2 ⌋ mid=⌊max(array)+min(array)2⌋ mid=⌊max(array)+min(array)2⌋, 然后小于等于 m i d mid mid 放左边数组，大于放右边数组，选择一个数组代替原来的数组

思路：

观察 m i d mid mid 的公式，其实只关心数组的最大值最小值，因为要分数组，所以要快速找出小于 m i d mid mid 和大于 m i d mid mid 的元素。那就直接排序，最小值和最大值肯定是数组区间的第一个和最后一个， m i d mid mid 的位置也可以通过二分快速找到，就可以快速分割左右两个数组。

很明显这种分割是有限的，所以对原数组操作产生的所有可能和放在一个 s e t set set 里面，查询的时候直接判断时候在里面即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define ls p<<1
#define rs p<<1|1typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;int a[maxn], b[maxn];
ll pre[maxn];
set<ll> cnt;ll getSum(int l, int r)
{return pre[r] - pre[l-1];
}
void check(int l, int r, const int & n)
{if(l > r) return;ll s = getSum(l, r);cnt.insert(s);int m = b[l] + b[r] >> 1;m = upper_bound(b+1, b+1+n, m) - b;if(m-1 < r)check(l, m-1, n);if(m > l)check(m, r, n);
}void solve()
{int n, q;cin >> n >> q;for(int i = 1; i <= n; ++i) {cin >> a[i];b[i] = a[i];}sort(b+1, b+1+n);for(int i = 1; i <= n; ++i)pre[i] = pre[i-1] + b[i];cnt.clear();check(1, n, n);while(q--) {int sum;cin >> sum;if(cnt.count(sum))cout << "Yes\n";else cout << "No\n";}
}int main()
{IOS();int T;cin >> T;while(T--)solve();return 0;
}

总结：

一开始读错题了，写成线段树去了，后面在结束前才调过来。