Hello and welcome to codeForces.

Today we choose question D of 1461 sessions, which has been passed by 3702 people, which is relatively moderate in difficulty. It is not difficult, but also suitable for students to practice. In addition, it uses a new idea that has not appeared in our previous articles, and I believe it will give you some inspiration.

Link: codeforces.com/contest/146…

So without further ado, let’s get started.

The question

We’re given an array of n positive integers, and we can do something to that array, and we can make the sum of the elements in that array whatever we want.

We perform operations on the array in three steps. The first step is to calculate the middle value of the array mid. The definition of mid here is not the median or the mean, but the mean of the maximum and the minimum. So mid is equal to min plus Max over 2.

Now that we have mid, we split the array into two parts based on the size of the elements in the array. Divide elements less than or equal to mid into the first part, and divide elements greater than mid into the second part. So we’ve converted our big array into two different small arrays.

We now have q requests, each of which contains an integer k. We want the program to tell us if we can do this so that the sum of the elements in the array is equal to k.

If you can print Yes, otherwise print No.

The sample

First enter an integer t that represents the number of groups of test data (1≤t≤1001 \le t \ LE 1001≤t≤100).

For each set of data enter two integers n and q, where n represents the number of elements in the array and q represents the number of requests (1≤n, Q ≤1051\le n, Q \ LE 10^51≤n,q≤105). Then enter a row of n integers, each of which has 1≤ai≤1061 \le a_i \le 10^61≤ai≤106.

The following q lines each have an integer representing the number k we queried (1≤k≤1091 \le k \le 10^91≤k≤109), ensuring that the sum of all n and q does not exceed 10510^5105.

For each request we print Yes or No to indicate whether it can be done.

For the first example, we start with an array of [1, 2, 3, 4, 5]. So the first time we do this, we get mid = 1 + 5/2 = 3. The array is then divided into [1, 2, 3] and [4, 5]. For [1, 2, 3], we get mid = (1 + 3) / 2 = 2, so the array can be divided into [1, 2] and [3]. [1, 2] can finally be divided into [1] and [2].

We can find that the k that can be searched is: [1, 2, 3, 4, 5, 6, 9, 15].

Answer key

This problem is not very complicated, the solution is relatively clear.

It is easy to see that the operations on arrays are fixed, because the maximum and minimum values in arrays are fixed. We just need to sort the array, through binary search can easily complete the array split. Similarly, we don’t have to loop over the sum of an array, which is easy to do with prefixes and sums.

So the only thing that’s going to be hard to figure out is whether or not we’re going to find the k that we want, and it’s not that complicated, we’re just going to look at it as a search problem, and we’re going to look at all the k’s that are available. This is a basic deep search, not too difficult.

bool examine(int l, int r, int k) {
    if (l == r) return (tot[r] - tot[l- 1] == k);
    // If the sum of [l, r] is less than k, then there is no need to consider further splitting
    if (l > r || tot[r] - tot[l- 1] < k) {
        return false;
    }
    if (tot[r] - tot[l- 1] == k) {
        return true;
    }
    // The median value is the mean of the heads and tails
    int m = (nums[l] + nums[r]) / 2;
    // find the subscript
    int md = binary_search(l, r+1, m);
    if (md == r) return false;
    return examine(l, md, k) | examine(md+1, r, k);
}
Copy the code

The logic itself is not too hard to write, but when we write it out, we find that we still can’t AC and time out. It took me a long time to figure out what the problem was.

The problem here is not that the search is too complex, but that there are too many searches. Q is at most 10510^5105, and the complexity of each search is log⁡2n\log^2 nlog2n. Because our search layer is log⁡n\log nlogn, plus log⁡n\log nlogn every time we use binary, the extreme complexity is 105log2n10 ^5 log^2 n105log2n. At n is 10510^5105, ⋅1072 \ Cdot 10^72⋅107, plus a few miscellaneous expenses, so it would be…

To solve this problem, we introduced an offline mechanism.

Offline online is easy to understand. Online query means we get one request at a time, query it once, and return the result. Offline, on the other hand, we run through all requests and return them one by one. Many of you might be surprised, aren’t they the same thing? Just in a different order.

Most of the time, it’s the same, but sometimes we can batch our offline queries. For example, in this problem, we can find out all the k that can be formed in one recursion and store it in set. Then we only need to query the existence of set according to the input request, because the speed of query set is much faster than we through recursive search. In this way, q queries are compressed into one query, which saves the time of operation. To some extent, it is also a space-for-time algorithm.

Let’s look at the code for more details:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
#definerep(i,a,b) for (int i=a; i<b; i++)
#defineRep(i,a,b) for (int i=a; i>b; i--)
#defineforeach(e,x) for (__typeof(x.begin()) e=x.begin(); e! =x.end(); e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
const int N=100050;
const long long Mod=1000000007;
 
using namespace std;

int nums[N];
long long tot[N];
set<long long> ans;

int binary_search(int l, int r, int val) {
    while (r - l > 1) {
        if (nums[mid] <= val) {
            l = mid;
        }else{ r = mid; }}return l;
}

// Put all possible k's into set at once
void prepare_ans(int l, int r) {
    if (l > r) return ;
    if (l == r) {
        ans.insert(nums[l]);
        return ;
    }
    ans.insert(tot[r] - tot[l- 1]);
    int m = (nums[l] + nums[r]) / 2;
    int md = binary_search(l, r+1, m);
    if (md == r) return ;
    prepare_ans(l, md);
    prepare_ans(md+1, r);
}


int main(a) {
    int t;
    scanf("%d", &t);
    rep(z, 0, t) {
        ans.clear(a);MEM(tot, 0);
        int n, q;
        scanf("%d %d", &n, &q);
        rep(i, 1, n+1) {
            scanf("%d", &nums[i]);
        }
        sort(nums+1, nums+n+1);
        rep(i, 1, n+1) {
            tot[i] = tot[i- 1] + nums[i];
        }
        prepare_ans(1, n);
        rep(i, 0, q) {
            int k;
            scanf("%d", &k);
            // We just need to look in set
            if (ans.find(k) ! = ans.end()) {
                puts("Yes");
            }else {
                puts("No"); }}}return 0;
}
Copy the code

Changing from online to offline is a very common skill in competition questions, which is often used to solve some very large query problems. To put it bluntly, it is not difficult, but if you do not know that you want to come out by yourself, it is somewhat troublesome. If you have time, you’d better try it out in code yourself.

So much for today’s algorithm, I sincerely wish you all a fruitful day. If you still like today’s content, please join us in a three-way support.

Original link, ask a concern