大家好，歡迎來到codeforces專題。
今天我們選擇的題目是1461場次的D題，這題全場通過了3702人，從難度上來說比較适中。既沒有很難，也很适合同學們練手。另外它用到了一種全新的思想是在我們之前的文章當中沒有出現過的，相信對大家會有一些啟發。
連結：https://codeforces.com/contest/1461/problem/D
廢話不多說了，讓我們開始吧。
題意
我們給定包含n個正整數的數組，我們可以對這個數組執行一些操作之後，可以讓數組内元素的和成為我們想要的數。
我們對數組的執行操作一共分為三個步驟，第一個步驟是我們首先計算出數組的中間值mid。這裡mid的定義不是中位數也不是均值，而是最大值和最小值的均值。也就是mid = (min + max) / 2。
得出了mid之後，我們根據數組當中元素的大小将數組分成兩個部分。将小于等于mid的元素分為第一個部分，将大于mid的元素分為第二個部分。這樣相當于我們把原來的大數組轉化成了兩個不同的小數組。
現在我們一共有q個請求，每個請求包含一個整數k。我們希望程式給出我們能否通過上述的操作使得最終得到的數組内的元素和等于k。
如果可以輸出Yes，否則輸出No。
樣例
首先輸入一個整數t，表示測試資料的組數（
）。
對于每一組資料輸入兩個整數n和q，n表示數組内元素的數量，q表示請求的數量（
）。接着第二行輸入一行n個整數，其中的每一個數
，都有
。
接下來的q行每行有一個整數，表示我們查詢的數字k（
），保證所有的n和q的總和不超過
對于每一個請求我們輸出Yes或No表示是否可以達成。
對于第一個樣例，我們一開始得到的數組是
[1, 2, 3, 4, 5]
。我們第一次執行操作，可以得到mid = (1 + 5) / 2 = 3。于是數組被分為
[1, 2, 3]
和
[4, 5]
。對于
[1, 2, 3]
繼續操作，我們可以得到mid = (1 + 3) / 2 = 2，是以數組可以分成
[1, 2]
[3]
[1, 2]
最終又可以拆分成
[1]
[2]
我們可以發現能夠查找到的k為：
[1, 2, 3, 4, 5, 6, 9, 15]
題解
這道題并不算很複雜，解法還是比較清晰的。
我們很容易發現對于數組的操作其實是固定的，因為數組當中的最大值和最小值都是确定的。我們隻需要對數組進行排序之後，通過二分查找就可以很容易完成數組的拆分。同樣，對于數組的求和我們也不用使用循環進行累加運算，通過字首和很容易搞定。
是以本題唯一的難度就隻剩下了如何判斷我們要的k能不能找到，其實這也不複雜，我們隻需要把它當成搜尋問題，去搜尋一下所有可以達到的k即可。這個是基本的深搜，也沒有太大的難度。
bool examine(int l, int r, int k) {
if (l == r) return (tot[r] - tot[l-1] == k);
// 如果[l, r]的區間和已經小于k了，那麼就沒必要去考慮繼續拆分了
if (l > r || tot[r] - tot[l-1] < k) {
return false;
}
if (tot[r] - tot[l-1] == k) {
return true;
}
// 中間值就是首尾的均值
int m = (nums[l] + nums[r]) / 2;
// 二分查找到下标
int md = binary_search(l, r+1, m);
if (md == r) return false;
return examine(l, md, k) | examine(md+1, r, k);
}
這段邏輯本身并不難寫，但是當我們寫出來之後，發現仍然不能AC，會逾時。我當時思考了很久，終于才想明白問題出在哪裡。
問題并不是我們這裡搜尋的複雜度太高，而是搜尋的次數太多了。q最多情況下會有
，而每次搜尋的複雜度是
。因為我們的搜尋層數是
，加上我們每次使用二分帶來的
，是以極端的複雜度是
，在n是
的時候，這個值大概是
，再加上一些雜七雜八的開銷，是以被卡了。
為了解決這個問題，我們引入了離線機制。
這裡的離線線上很好了解，所謂的線上查詢，也就是我們每次獲得一個請求，查詢一次，然後傳回結果。而離線呢則相反，我們先把所有的請求查詢完，然後再一個一個地傳回。很多同學可能會覺得很詫異，這兩者不是一樣的麼？隻不過順序不同而已。
大多數情況下的确是一樣的，但有的時候，我們離線查詢是可以批量進行的。比如這道題，我們可以一次性把所有可以構成的k通過一次遞歸全部查出來，然後存放在set中。之後我們隻需要根據輸入的請求去set當中查詢是否存在就可以了，由于查詢set的速度要比我們通過遞歸來搜尋快得多。這樣就相當于将q次查詢壓縮成了一次，進而節約了運算的時間，某種程度上來說也是一種空間換時間的算法。
我們來看代碼，擷取更多細節：
#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>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>b;i--)
#define foreach(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;
}
// 離線查詢，一次把所有能構成的k放入set當中
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() {
int t;
scanf("%d", &t);
rep(z, 0, t) {
ans.clear();
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);
// 真正請求起來的時候，我們隻需要在set裡找即可
if (ans.find(k) != ans.end()) {
puts("Yes");
}else {
puts("No");
}
}
}
return 0;
}
線上變離線是競賽題當中非常常用的技巧，經常被用來解決一些查詢量非常大的問題。說穿了其實并不難，但是如果不知道想要憑自己幹想出來則有些麻煩。大家有時間，最好自己親自用代碼實作體會一下。
今天的算法題就聊到這裡，衷心祝願大家每天都有所收獲。如果還喜歡今天的内容的話，請來一個三連支援吧~（點贊、關注、轉發）
