题解：P12878 [蓝桥杯 2025 国 C] 拔河

· · 题解

P12878 题解：

好题。

主要思路：

看到题目第一眼就想到了背包，但值域太大，不太行。于是又想到把 40 个数分成 2 组，每组 20 个数，采用 Meet-in-the-middle 算法，分别计算两组答案再合并。

代码实现：

算法：Meet-in-the-middle 算法 + 双指针

思路：将 40 个数分成两组，分别用 map 存储，再分别处理两个 map 的子集和，然后合并，最后用双指针查找并输出结果。

AC Code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    vector<long long> v={
        345590635693812, 411735179294186, 190029355501347, 973598561303630,
        18202819016954, 739089526396984, 41064501651340, 287075700776565,
        458062562307032, 723278851371706, 997720296178889, 470475557480472,
        329586527903215, 907379737442406, 631284976214798, 301204036247736,
        747294692547790, 914091289062262, 144070679727924, 988094642462741,
        413975599277375, 835461430976017, 344371572186185, 646160866308904,
        880407857470630, 794629069521762, 462180977651587, 342038139286302,
        854772507978666, 694223418935656, 567502001946067, 881035713848915,
        840605474892139, 324727089144326, 226008847101330, 65143946718125,
        499249957077991, 245803813100131, 447887480320685, 658036302578844
    };
    int n=v.size();
    int p=n/2;
    //预处理前半部分的所有可能子集和
    unordered_map<long long,long long> l;
    for(int h=0;h<(1<<p);h++){
        long long sum=0;
        for(int i=0;i<p;i++){
            if(h&(1<<i)) sum+=v[i];
        }
        l[h]=sum;
    }
    //预处理后半部分的所有可能子集和
    unordered_map<long long,long long> r;
    for(int h=0;h<(1<<(n-p));h++){
        long long sum = 0;
        for (int i=0;i<(n-p);i++){
            if (h&(1<<i))sum+=v[p+i];
        }
        r[h]=sum;
    }
    long long t=0;
    for (auto p : v) t+=p;
    long long ans=t/2;
    long long mi=LLONG_MAX;
    //合并两部分结果
    vector<long long> lv,rv;
    for (auto& p : l) lv.push_back(p.second);
    for (auto& p : r) rv.push_back(p.second);
    sort(lv.begin(),lv.end());
    sort(rv.begin(),rv.end());
    //双指针查找最接近ans的和
    int i=0,j=rv.size()-1;
    while(i<lv.size()&&j>=0){
        long long sum=lv[i]+rv[j];
        mi=min(mi,abs(t-2*sum));
        if(sum<ans){
            i++;
        }else if(sum>ans){
            j--;
        }else{
            return 0; //找到完美分割
        }
    }
    cout<<mi;
    return 0;
}