Codeforces Round #689 (Div. 2, based on Zed Code Competition)D. Divide and Summarize(分治+dfs)

based on Zed Code Competition)D. Divide and Summarize(分治+dfs)"/>

Codeforces Round #689 (Div. 2, based on Zed Code Competition)D. Divide and Summarize(分治+dfs)

D. Divide and Summarize

题意

给你n个数，q次询问，问你能否具有满足和为s的序列。

思路

再求其有多少种和时需要使用 m i d = m a x + m i n > > 1 mid = max + min >> 1 mid=max+min>>1来寻找有多少种和。

然后dfs，但是需要判断一下左面或者右面全部相等情况，否则会爆栈

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
typedef long long LL;
//#define int long longint a[N];int n, q;
set<LL>ans;
LL sum[N];
void dfs(int l ,int r) {if (l > r) return;ans.insert(sum[r] - sum[l - 1]);if (a[l] == a[r]) {return;}int mid = a[l] + a[r] >> 1;int idx = upper_bound(a + l, a + 1 + r, mid) - a;dfs(l, idx - 1);dfs(idx, r);
}void solve() {ans.clear();cin >> n >> q;for (int i  = 1; i <= n; ++i)cin >> a[i];sort(a + 1, a + 1 + n);for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];dfs(1 ,n);while (q--) {LL s; cin >> s;if (ans.count(s)) cout << "YES\n";else cout << "NO\n";}
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}}