关于哈希容器与普通容器的效率问题的疑惑
查看原帖
关于哈希容器与普通容器的效率问题的疑惑
1160029
ohhhhhdod楼主2024/8/15 13:44

把unordered_map和unordered_set改为map和set就只能得92分,会有两测试点点超时。 以下是代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm = 40 + 5;
ll n , a[maxm];
void dfs(int x , int mid , ll sum , ll id , map<ll , unordered_set<ll>>& c){
    if(x > mid){
        c[sum].insert(id);
        return ;
    }
    dfs(x + 1 , mid , sum + a[x] , id + (1LL << x - 1) , c);
    dfs(x + 1 , mid , sum - a[x] , id + (1LL << x - 1) , c);
    dfs(x + 1 , mid , sum , id , c);
}
int main(){
    cin >> n;
    map<ll , unordered_set<ll>> c1 , c2;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    dfs(1 ,  n / 2  , 0 , 0 , c1);
    dfs(n / 2 + 1 , n , 0 , 0 , c2);
    ll ans = 0;
    unordered_map<ll , bool> f;
    for(auto [x , y] : c1){
        if(c2.count(~x + 1)){
            for(auto i : y){
                for(auto j : c2[~x + 1]){
                    f[i + j] = true;
                }
            }
        }
    }
    cout << f.size() - 1 << endl;
}
2024/8/15 13:44
加载中...