这个问题快把我逼疯了。顶部的代码在我的计算机上执行大约 0.3 秒，而底部的代码执行大约 2.7 秒。但是，我尝试将第二个代码调整为尽可能与第一个代码相似，但它似乎总是更慢。谁能告诉我为什么第一个代码的执行速度比第二个快得多？
更快的代码
#include <cstdio>
#include <set>
#define ls(x) (x & (-x))
using namespace std;
int tc, n;
set<long long> s;
long long p, a[35];
int main () {
freopen("mini3b.in","r",stdin);
scanf("%d", &tc);
while (tc--) {
s.clear();
scanf("%lld%d", &p, &n);
for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);
int h = n/2;
for (int i = 0; i < (1<<h); ++i) {
long long sum = 0;
for (int j = 0; j < h; ++j) if (i&(1<<j)) sum += a[j];
s.insert(sum);
}
bool found = false;
for (int i = 0; (i < (1<<(n-h))) && !found; ++i) {
long long sum = 0;
for (int j = 0; j < n-h; ++j) if (i&(1<<j)) sum += a[h+j];
if (s.find(p-sum) != s.end()) found = true;
}
printf(found? "YES\n":"NO\n");
}
}
较慢的代码
#include <cstdio>
#include <set>
using namespace std;
long long n, bars[35];
int t, p;
set<long long> s;
int main(){
freopen("mini3b.in","r", stdin);
scanf("%d", &t);
while (t--){
s.clear();
scanf("%lld%d", &n, &p);
for (int i=0;i<p;++i) scanf("%lld", &bars[i]);
int limit=p/2;
for (int i=0;i<(1<<limit);++i){
long long sum=0;
for (int j=0;j<limit;++j) if (i&(1<<j)) sum+=bars[j];
s.insert(sum);
}
bool found=false;
for (int i=0;i<(1<<(n-limit))&&!found;++i){
long long sum=0;
for (int j=0;j<p-limit;++j) if (i&(1<<j)) sum+=bars[limit+j];
if (s.find(n-sum) != s.end())
found=true;
}
printf(found?"YES\n":"NO\n");
}
}