今天又是没好的一天啊，又要学知识点了，来到教室，老师突然公布一个事：
今天要上公开课！
啊？这么突然！公开课我们之前上过一次，是有关最短路的，听得我们晕头转向，老师突然又公布上公开课，给我吓得不轻，我们紧张的听老师讲这次是啥知识点，老师说：
今天要学搜索专题！
啊？怎么这么。。。。
诶，等会，搜索？？！！这不是基础班的内容吗！？居然放在公开课上讲，那我们可是真的太幸运啦。
于是等我们晕晕乎乎的看完整整100片十日终焉，回到教室的时候，老师忽然又公布一个事：
今天要学折半搜索！！
啊！！上完公开课怎么还要上课，而且还是新的知识点！！！
于是，额。。今天又是个没好美好没好的一天啊！！
终于说到正题了，今天要讲的就是
\color{blue} \Huge折半搜索
没错，就是他，就是DAY1模考的时候内个永远订正不AK得玩意
所以今天我们就要挑战他，在挑战他之前，我们需要做一些准备
首先，我们要了解一下折半搜索是啥
折半搜索
折半搜索，顾名思义就是把搜索掰成两半，前面一半后面一半，这样就直接把指数级增长的复杂度变成加法。但是这其中也有一些语法上实现的问题，让我们来看一看例题把
例题
先来看简单得第一道题
这道题第一眼看简直太简单了，可是一看数据范围。。
额，直接裂开有没有，2^{40} 次方直接有
1,099,511,627,776
这肯定比 10^7 要大了好吧
所以我们就需要用折半搜索，得出来是 2^{20} 也就是：
1,048,576
瞬间降下来有没有
我们折半搜索的思路就是分成两个搜索，所以就有了
dfs1
和
dfs2
然后我们把 a 数组分成两份，左边是从 1 到 n \div 2 ,右边是 \frac{n}{2} + 1 到 n 分别进行搜索，这两个搜索除了一点其他的都大致一样，那就是第一个搜索是存储答案，第二个搜索要处理答案，所以得到了代码：
void dfs1(ll step, ll sum){
if(step>n/2){
ans.push_back(sum);
return;
}
dfs1(step+1, sum+a[step]);
dfs1(step+1, sum);
}
void dfs2(ll step, ll sum){
if(step>n){
ll x=t-sum;
ll k=upper_bound(ans.begin(), ans.end(), x)-ans.begin()-1;
if(sum+ans[k]<=t)Ans=max(sum+ans[k], Ans);
return;
}
dfs2(step+1, sum+a[step]);
dfs2(step+1, sum);
}
PS：最后输出Ans就可以了偶
例题看完了，我们就可以来挑战小信的特工行动啦，接下来就是【数据删除】环节
【数据删除】
(对不起，当前数据因某种原因无法显示，如有问题请拨打论坛投诉电话：114514)
OK，那么今天的内容就完结了，请看得的人都给个小赞吧QWQ， 写了很久的呀！！