主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
AT_arc135_c 题解
最后更新于 2025-07-31 11:45:25
作者
Melo_qwq
分类
题解
题解
AT_arc135_c
复制 Markdown
查看原文
删除文章
更新内容
哇啊哦,原来是神秘诈骗题。 我们考虑当前经过一系列异或操作之后的序列的形式 $a_1\oplus k,a_2\oplus k\cdots a_n\oplus k$,此时如果我们再异或上某一个位置的数,也就是 $a_i\oplus k$,可以得到 $a_1\oplus a_i,a_2\oplus a_i\cdots 0\cdots a_n\oplus a_i$,也就是说,无论操作多少次,达到的效果一定可以只通过一次异或操作达到。 问题转化为在序列里找一个数,让整个序列都异或上这个数,求操作后序列最大的和(可以不干)。 考虑异或的性质,对于两个数,显然我们只需要知道当前两个数每一个二进制位上的数是否不同就知道最后的异或和,那么多个数的时候也同理。 只需要开一个数组,记录对于每一个二进制位,原序列中有多少数这一位为 $1$,然后暴力枚举 $i$,遍历 $a_i$ 的每一个二进制位,看看原序列中有多少数在这一位上和他不一样,算一下答案,就做完了。 Code ```cpp #include <bits/stdc++.h> #define int long long #define f(i ,m ,n ,x) for (int i = (m) ; i <= (n) ; i += (x)) template < typename T > inline void read ( T &x ) { x = 0 ; bool flag (0) ; char ch = getchar () ; while (! isdigit (ch)) { flag = ch == '-' ; ch = getchar () ; } while (isdigit (ch)) { x = (x << 1) + (x << 3) + (ch ^ 48) ; ch = getchar () ; } flag ? x = - x : 0 ; } const int N = 3e5 + 7 ; int n ,a[N] ,cnt[77] ,res ; signed main () { read (n) ; f (i ,1 ,n ,1) { read (a[i]) ; res += a[i] ; static int b ; b = a[i] ; int cur = 0 ; while (b) { cnt[cur ++] += (b & 1) ; b >>= 1 ; } } f (i ,1 ,n ,1) { int ans = 0 ; f (j ,0 ,32 ,1) { int cur = (a[i] & (1ll << j)) ; if (cur) ans += (n - cnt[j]) * (1ll << j) ; else ans += cnt[j] * (1ll << j) ; } res = std :: max (res ,ans) ; } std :: cout << res << '\n' ; return 0 ; } ```
正在渲染内容...
点赞
0
收藏
0