主页
搜索
最近更新
数据统计
赞助我们
申请密钥
系统公告
1
/
1
请查看完所有公告
题解：AT_abc390_d [ABC390D] Stone XOR
最后更新于 2025-05-07 15:45:38
作者
_0_px
分类
题解
题解
AT_abc390_d
复制 Markdown
查看原文
删除文章
更新内容
[Link](https://www.luogu.com.cn/problem/AT_abc390_d) ### 题意 把 $n$ 个数分成若干组，求每组数之和的异或和。 ### 思路 看到数据范围 $2 \leq n \leq 12$ 很容易就能想到 dfs 。 数组记录每一堆的和，每次搜完把结果存到 `unordered_map` 里面（ `map` 会超），最后输出 `unordered_map` 里面数的个数就是答案。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define int long long int n, a[20], b[20];// b 记录每一堆的和。 unordered_map<int, bool> mp;// 记录答案。 void dfs(int s, int cnt, int v){// s 当前搜的位置，cnt 记录当前堆数，v 记录当前异或和。 if (s > n){ mp[v] = 1;// 搜完了记录答案。 return; } for (int i = 1; i < cnt; i ++){// 加在有数的堆里面。 int now = v ^ b[i];// 去掉原来的异或值。 b[i] += a[s]; dfs(s + 1, cnt, now ^ b[i]);// 加上现在的。 b[i] -= a[s];// 回溯。 } b[cnt] = a[s]; dfs(s + 1, cnt + 1, v ^ a[s]);// 新一堆。 b[cnt] = 0; } signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n; for (int i = 1; i <= n; i ++){ cin >> a[i]; } dfs(1, 1, 0); cout << mp.size(); return 0; } ``````
正在渲染内容...
点赞
4
收藏
0
