专栏文章

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

__DATA_X_
P12878题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip1eux2
此快照首次捕获于
2025/12/03 04:35
3 个月前
此快照最后确认于
2025/12/03 04:35
3 个月前
查看原文

P12878 题解：

好题。

主要思路：

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

代码实现：

算法：Meet-in-the-middle 算法 + 双指针
思路：将 4040 个数分成两组，分别用 map 存储，再分别处理两个 map 的子集和，然后合并，最后用双指针查找并输出结果。
AC Code：
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...