大橘为重

注意题目中的或者，直接dfs找出所有可能的s，存起来，后面直接查询即可。

对于dfs搜索数，可以发现，最差的情况是每次元素个数都删掉一半，即便是这样，深度最多为logn，总的可能（节点数）数量大概2^(logn+1)，大概就是1e5，所以不会超时。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, q;
ll a[100010];
unordered_map<ll, int > mp;

void dfs(multiset<ll> se) {
    ll sum = 0;
    for(auto x: se) sum += x;
    mp[sum] = 1;

    if(se.size() == 1) return;

    ll avg = sum / (ll)se.size();
    multiset<ll> se_min, se_max;
    for(auto x: se)
        if(x > avg) se_max.insert(x);
        else se_min.insert(x);
    
    if(se_max.size() == 0 || se_min.size() == 0) return;
    dfs(se_max);
    dfs(se_min);
}

int main()
{
    scanf("%d%d", &n, &q);
    multiset<ll> se;
    for(int i = 1; i <= n; i ++) scanf("%lld", a + i), se.insert(a[i]);
    dfs(se);

    while(q --) {
        ll s; scanf("%lld", &s);
        if(mp.count(s)) puts("YES");
        else puts("NO");
    }
    return 0;
}

这道题我用 前缀和 + unordered_map去重 + 二分 + 各种特殊条件判断 都过不了

好难啊

#include <iostream>
#include <fstream>
#include <algorithm>
#include <unordered_map>

using namespace std;

//最多 1e5 个橘子
const int N = 100010;

//每个橘子的重量
int ary[N];
//前缀和：sN[i]表示 从 [1,i] 号橘子的总重量
long long sN[N];

bool check(const int& s, int l, int r) {
    if (l > r || (l == r && s != sN[r] - sN[l - 1])) return false;
    if (s > sN[r] - sN[l - 1]) return false;
    if (s == sN[r] - sN[l - 1]) return true;
    //找到大于avg的分界点
    int avg = (sN[r] - sN[l - 1]) / (r - l + 1);
    int left = l, right = r;
    while (left < right) {
        int mid = left + right >> 1;
        if (ary[mid] > avg) right = mid;
        else left = mid + 1;
    }
    //决策1 抛弃所有重量大于avg的橘子
    if (check(s, l, right - 1) == true) return true;
    //决策2 抛弃所有重量小于等于avg的橘子
    return check(s, right, r);
}

int main() {
    //n：橘子数量
    //q：查询数量
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) cin >> ary[i];

    sort(ary + 1, ary + 1 + n);
    for (int i = 1; i <= n; ++i) sN[i] = sN[i - 1] + ary[i];

    unordered_map<int, bool> mem;
    while(q--) {
        int s;
        cin >> s;
        if (s > sN[n] || s < sN[1]) {
            cout << "NO\n";
            continue;
        }
        if (s == sN[n]) {
            cout << "YES\n";
            continue;
        }
        if (mem.find(s) != mem.end()) {
            mem[s] == true ? cout << "YES\n" : cout << "NO\n";
            continue;
        }

        //来到这里说明s一定小于橘子的总重量，且没被判断过
        if (check(s, 1, n) == true) {
            cout << "YES\n";
            mem[s] = true;
        }
        else {
            cout << "NO\n";
            mem[s] = false;
        }
    }

    return 0;
}

```

看了各位大佬的思路后，我粗浅认为 本题不能使用sort来排序，一次次遍历都比排序消耗的时间少，我也不太懂为啥，但确实不排序就可以通过了。

一下是我参考了 楼上 五个臭皮蛋朋友的代码写出来的。

#include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
set<ll> res;
void dfs(multiset<ll> oranges, ll sum){
    res.insert(sum);
    ll avg = sum/oranges.size();
    multiset<ll> set_min, set_max;
    ll small = 0;
    for(ll i:oranges){
        if(i>avg){
            set_max.insert(i);
        }else{
            set_min.insert(i);
            small += i;
        }
    }
    res.insert(small);
    res.insert(sum-small);
    if(set_min.size()==0 || set_max.size()==0){
        return;
    }
    dfs(set_min, small);
    dfs(set_max, sum-small);
}
int main(){
    int n, q; cin >> n >> q;
    multiset<ll> oranges;
    ll weight;
    ll sum = 0;
    for(int i=0;i<n;i++){
        cin>>weight;
        oranges.insert(weight);
        sum += weight;
    }// 导入所有橘子重量
    dfs(oranges, sum);
    while((q--)>0){
        cin>>weight;
        if(res.find(weight)==res.end()){
            cout<<"NO"<<endl;
        }else{
            cout<<"YES"<<endl;
        }
    }
    return 0;
}