题解：AT_abc390_d [ABC390D] Stone XOR

Emplace · 2025-02-10 16:33:02 · 题解

思路

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

可以给搜索的每一层定义为 A 数组中的每一个数。然后这个数可以选择加入当前 B 中已有石子的袋子中，也可以选择单开一个。然后搜完以后，将 B 数组中的所有石子数异或一下，最后检查有没有出现过就行（用 unordered_map 储存）。

Code

#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;
}