STUDENT00 @ 2022-10-03 15:16:19
总共64个点，只对了一个，10分（其余全WA）。
一道练手的折半搜索题，怎么写了半天10分？！
简单明了的代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,k1,k2,last;
long long m,a[40],p[1048576],q[1048576],ans;
void dfs(int now,long long s,bool flag){
if(s>=m) return;
if(now==last){
if(flag) p[k1++]=s;
else q[k2++]=s;
return;
}
dfs(now+1,s,flag);
dfs(now+1,s+a[now],flag);
}
int main(){
scanf("%d%lld",&n,&m);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
last=n>>1;
dfs(0,0,1);
last=n;
dfs(n>>1,0,0);
for(int i=0;i<k1;i++) ans+=upper_bound(q,q+k2,m-p[i])-q+1;
printf("%lld",ans);
return 0;
}by STUDENT00 @ 2022-10-03 15:24:45
一个小细节，AC代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,k1,k2,last;
long long m,a[40],p[1048576],q[1048576],ans;
void dfs(int now,long long s,bool flag){
if(s>m) return;
if(now==last){
if(flag) p[k1++]=s;
else q[k2++]=s;
return;
}
dfs(now+1,s,flag);
dfs(now+1,s+a[now],flag);
}
int main(){
scanf("%d%lld",&n,&m);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
last=n>>1;
dfs(0,0,1);
last=n;
dfs(n>>1,0,0);
sort(p,p+k1);
sort(q,q+k2);
for(int i=0;i<k1;i++) ans+=upper_bound(q,q+k2,m-p[i])-q;
printf("%lld",ans);
return 0;
}