当前位置:网站首页>C - XOR to all (binary topic)
C - XOR to all (binary topic)
2022-07-05 06:16:00 【whitewall_ nine】
https://atcoder.jp/contests/arc135/tasks/arc135_c
#include<iostream>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define pii pair<int, int>
#define mset(s,t) memset(s,t,sizeof(t))
#define mcpy(s,t) memcpy(s,t,sizeof(t))
#define fir first
#define pb push_back
#define sec second
#define sortall(x) sort((x).begin(),(x).end())
inline int read () {
int x = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= (ch=='-'),ch= getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return f?-x:x;
}
template<typename T> void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) print(x/10);
putchar(x % 10 + '0');
}
const int N = 35;
int cnt[N];
int a[300005];
int n;
void solve() {
cin >> n;ll ans = 0;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
int t= a[i];
ans += t;
for (int j =0; j <= 30; j ++)
cnt[j] += (t >> j & 1);
}
for (int i = 1; i <= n; i++) {
ll res = 0;
for (int j = 0; j <= 30; j++)
res += ((a[i] >> j & 1) == 1? n - cnt[j] : cnt[j]) * ((ll)1 << j);
ans = max (ans, res);
}
cout << ans << endl;
}
int main () {
int t;
t =1;
while (t --) solve();
return 0;
}
The difficulty lies in how to efficiently count the sum after XOR . We observe binary , For each selected value , We have found , If the binary bit of the current value is 0, Then the binary of the same position of all other numbers is upper 1 Will be preserved , And contribution equals 1 Multiply the number of by the weight of the position . Otherwise, it counts 0 The number of contributions . Pay attention to the synthesis of the initial state . I've been thinking about how to make a sum , Numbers are not considered as binary bits , So we can't find the law . Next time you encounter this problem, you should consider binary representation .
Some properties of XOR
For sequence A, B,B It's from A The result after XOR operation .
a[i]^a[j] = b[i]^b[j];
边栏推荐
- MySQL advanced part 1: index
- Basic explanation of typescript
- Doing SQL performance optimization is really eye-catching
- Leetcode recursion
- One question per day 2047 Number of valid words in the sentence
- leetcode-6110:网格图中递增路径的数目
- leetcode-31:下一个排列
- 【Rust 笔记】13-迭代器(中)
- Leetcode divide and conquer / dichotomy
- Regulations for network security events of vocational group in 2022 Guizhou Vocational College skill competition
猜你喜欢
LeetCode 0107.二叉树的层序遍历II - 另一种方法
Redis publish subscribe command line implementation
MySQL advanced part 1: index
【LeetCode】Easy | 20. Valid parentheses
7. Processing the input of multidimensional features
leetcode-6110:网格图中递增路径的数目
Appium foundation - use the first demo of appium
Is it impossible for lamda to wake up?
Appium automation test foundation - Summary of appium test environment construction
做 SQL 性能优化真是让人干瞪眼
随机推荐
MIT-6874-Deep Learning in the Life Sciences Week 7
7. Processing the input of multidimensional features
Basic explanation of typescript
QQ电脑版取消转义符输入表情
Liunx starts redis
【Rust 笔记】13-迭代器(下)
Real time clock (RTC)
Leetcode-9: palindromes
C Primer Plus Chapter 15 (bit operation)
LaMDA 不可能觉醒吗?
数据可视化图表总结(一)
对for(var i = 0;i < 5;i++) {setTimeout(() => console.log(i),1000)}的深入分析
Regulations for network security events of vocational group in 2022 Guizhou Vocational College skill competition
Leetcode-6108: decrypt messages
Operator priority, one catch, no doubt
MySQL advanced part 2: storage engine
2021apmcm post game Summary - edge detection
[rust notes] 16 input and output (Part 2)
Shutter web hardware keyboard monitoring
Open source storage is so popular, why do we insist on self-development?