题解：AT_abc390_d [ABC390D] Stone XOR

思路

其实这道题就是一个暴搜。

可以给搜索的每一层定义为

A

数组中的每一个数。然后这个数可以选择加入当前

B

中已有石子的袋子中，也可以选择单开一个。然后搜完以后，将

B

数组中的所有石子数异或一下，最后检查有没有出现过就行（用 unordered_map 储存）。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[20],b[20],m,ans;
unordered_map<int,int> mm;
void dfs(int x,int m){
//	cout<<x<<" "<<m<<endl;
	if(x==n+1){
		int x_or=0;
		for(int i=1;i<=m;i++){
			x_or^=b[i];
//			cout<<b[i]<<" ";
		}
	//	cout<<endl<<x_or<<endl;
		if(!mm.count(x_or)){
			mm[x_or]=1;
			ans++;
		}
		return ;
	}
	for(int i=1;i<=m;i++){
		b[i]+=a[x];
		dfs(x+1,m);
		b[i]-=a[x];
	}
	b[m+1]=a[x];
	dfs(x+1,m+1);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}

题解：AT_abc390_d [ABC390D] Stone XOR

文章操作

思路

Code

相关推荐

评论

题解：AT_abc390_d [ABC390D] Stone XOR