首页 > 其他分享 >P3067 [USACO12OPEN] Balanced Cow Subsets G

P3067 [USACO12OPEN] Balanced Cow Subsets G

时间:2024-09-15 15:46:42浏览次数:11  
标签:折半 Subsets int USACO12OPEN sum long 搜索 Balanced now

我的天,折半搜索(meet in the middle),依稀记得我学过,但是真的不记得。。。。

从状态图上起点和终点同时开始进行宽度/深度优先搜索,如果发现相遇了,那么可以认为是获得了可行解。

这道题,每一个元素会有3种状态,分别是在第一个集合或者第二个集合亦或者不在集合中。如果直接暴力去搜的话,时间复杂度是三次方级别的,不能被接受。
所以考虑折半搜索,就可以直接把复杂度上的指数砍半,就可以过掉这道题了。

折半搜索实现

#include<bits/stdc++.h>
#define int long long
#define pb push_back

using namespace std;

const int N=25,M=2e6+100;

int n;
int ans[M];
int a[M];
int s,tot;

vector<int> p[M];
map<int,int> b;

void dfs1(int x,int sum,int now)
{
	//对前一半进行搜索,now->对取了的数进行状态压缩
	if(x>n/2)
	{
		if(b[sum]==0)	b[sum]=++tot;//李三华
		p[b[sum]].pb(now);
		return; 
	} 
	dfs1(x+1,sum+a[x],now|(1<<(x-1)));
	dfs1(x+1,sum-a[x],now|(1<<(x-1)));
	dfs1(x+1,sum,now);
	//分三种情况讨论,要么在左,要么在右,要么都不在 
}

void dfs2(int x,int sum,int now)
{
	//对后一半进行搜索
	if(x>n)
	{
		int t=b[sum];
		if(t!=0)
			for(int i=0;i<p[t].size();i++)
				ans[p[t][i]|now]=1;
			//对于每一种可能的组合,将值赋为1,
			//因为题目中要求的方案数为取数的方案数而不是分数的方案数
			//因此不是+1而是=1
		return;
	 } 
	dfs2(x+1,sum+a[x],now|(1<<(x-1)));
	dfs2(x+1,sum-a[x],now|(1<<(x-1)));
	dfs2(x+1,sum,now);
 } 

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	dfs1(1,0,0),dfs2(n/2+1,0,0);
	for(int i=1;i<=(1<<n);i++)	s+=ans[i];
	cout<<s<<endl;
	return 0;
}
//meet in the middle(折半搜索)

也可以用状态压缩实现大部分折半搜索的题目,这道题也可以用三进制状态压缩去做。

#include<bits/stdc++.h>
#define int long long

using namespace std;

int n;
int B[2],a[22],pow3[12],ans;
bool st[(1<<20+5)];
map<int,vector<int>> f[2];

signed main()
{
	cin>>n;
	B[0]=n/2,B[1]=n-B[0];
	for(int i=0;i<n;i++)	cin>>a[i];
	pow3[0]=1;
	for(int i=1;i<=B[1];i++)	pow3[i]=pow3[i-1]*3;
	for(int t=0;t<=1;t++)
		for(int s=0;s<pow3[B[t]];s++)
		{
			int d=0,S=(1<<B[0])-1;
			if(t==1)	S=((1<<n)-1)-S;
			for(int i=0;i<B[t];i++)
			{
				int v=(s/pow3[i])%3;
				if(v==1)	d+=a[i+t*B[0]];
				else if(v==2)	d-=a[i+t*B[0]];
				else	S-=(1<<(i+t*B[0]));
			}
			f[t][d].push_back(S);	
		}
	for(auto a:f[0])
		for(int b:a.second)
			for(int c:f[1][-a.first])
				if(!st[c|b])	ans++,st[c|b]=true;
	cout<<ans-1<<endl;
	return 0;
}

标签:折半,Subsets,int,USACO12OPEN,sum,long,搜索,Balanced,now
From: https://www.cnblogs.com/tangml/p/18415284

相关文章

  • 洛谷题单指南-常见优化技巧-P2880 [USACO07JAN] Balanced Lineup G
    原题链接:https://www.luogu.com.cn/problem/P2880题意解读:在若干个不定长区间里,求区间最大值与最小值之差解题思路:对于区间求最值,通常有几种方式:1、暴力法,通过枚举所有的区间来计算区间最值2、单调队列,针对区间长度固定的情况3、ST表,针对区间长度不固定且元素不会发生改变的......
  • Balanced String
    这道题目真的不知道怎么总结了,这技巧太新了见这篇题解为什么最开始要引入这个子问题呢?实际上,我们假设我们已经得到了最终的交换后的答案,设为\(t\),\(s\)就是题目给的原串,从\(s\)到\(t\)的最小交换次数当然就是从\(t\)到\(s\)的最小交换次数,于是考虑从\(t\)到\(s\)的最小交换次数,......
  • [CVPR2022]DASO Distribution-Aware Semantics-Oriented Pseudo-label for Imbalanced
    问题的背景设置:半监督学习下,labeleddata和unlabeleddata的分布不同,且存在类别不平衡。文章提出了一种新的伪标签生成方法:DistributionAwareSemantics-Oriented(DASO)Pseudo-label。首先生成语义伪标签和线性为标签,然后将它们混合实现互补。另外作者的方法不需要估计无标签数......
  • CF873B Balanced Substring
    Abstract传送门本题定义平衡串为0和1数量相等的字符串,要求我们找出给定01串中含有的最大平衡串。Idea如果把1视为+1,0视为-1,那么一个01串是平衡串当且仅当其和值为0,那么问题就转变为寻找给定01串中和值为0的最长子段。首先做一个前缀和,a[i]表示前i项的......
  • imbalanced-learn库的作用和安装
    imbalanced-learn是一个Python库,‌专门用于处理不平衡数据集的机器学习问题。‌ 这个库提供了一系列的重采样技术、‌组合方法和机器学习算法,‌旨在提高在不平衡数据集上的分类性能。‌Imbalanced-learn支持欠采样、‌过采样、‌结合欠采样和过采样的方法,‌以及一些集成学习方法......
  • 线段树(原理、构造和区间查询,例题:Balanced Lineup)
    概念原理    线段树是分治法和二叉树的结合,二叉树上的节点都是根据分治得到的。节点所表示的,也就是线段,可以是区间和、最值或者是其他的,,每次分治,左右子树各一半,每个节点的值代表了以它为根的子树上所有节点的值。通过线段树,大区间的解可以从小区间的解合并而来。构......
  • Imbalanced Arrays
    还没有仔细看官方题解和洛谷题解,重新做的时候看一下有没有什么可以吸收的说一下我的做法:首先看到第二个条件,不难想出\(i\)和\(-i\)只有可能选一个,此时观察样例,以及发现\(b\)刚好有\(n\)个数,所以不难想到最终\(b\)的构造方案是由\(1\)~\(n\)的每一个数或其相反数组成的,且每个数......
  • 题解:SP11469 SUBSET - Balanced Cow Subsets
    SP11469(折半搜索)题目大意:给出$N$个数,求可以被分成两个和相等的集合的子集数。思路分析:首先考虑朴素的DFS,每个数有三种情况:选为$A$集合,选为$B$集合,两个集合都不选。暴力DFS时间复杂度为$3^{20}$。观察到$N$很小,而$3^{10}$是可以通过本题的,于是考虑折半搜索。我......
  • CF1237F Balanced Domino Placements
    比较有意思的Counting,想到横竖两种骨牌的独立性就很好做了考虑如果枚举最后放了\(x\)块横着的骨牌,\(y\)块竖着的骨牌,直接考虑它们的摆放不方便,不妨转化一下在所有空余的行中,选择\(x+2y\)行,且满足其中有\(y\)对相邻的行;在所有空余的列中,选择\(2x+y\)列,且满足其中有\(x......
  • 【CF1656H】Equal LCM Subsets
    【CF1656H】EqualLCMSubsets题意给定集合\(A\)和\(B\),从中选择两个子集\(A'\subseteqA,B'\subseteqB\)满足\(\operatorname{lcm}(A')=\operatorname{lcm}(B')\)。满足\(\lvertA\rvert,\lvertB\rvert\le10^3,A,B\le4\times10^{35}\)。......