1368 D. AND, OR and square sum (贪心、位运算) 朱雀 2021-07-17 01:36 345阅读 0赞 [题目][Link 1] 思路: 看一个例子对于两个二进制数 1100101 0100100 AND结果:0100100 OR结果:1100101 如果两个二进制位都为1或0,AND OR 中结果不变还是1或0,如果一个是0 一个1,就会把1转到OR结果中AND中的那个位变为0。我将这个过程看作是一个让1往一个数(OR结果)分配的过程,所有二进制每个位总的个数不变,但通过上述操作可以让1集中到一个数上面,我们可以通过无限次操作总是拼出来一个大的数,相应的这个数花费的各个二进制位数减1,直到所有二进制位的个数耗尽,这样得出来的答案是最大的。 Code: #include<iostream> using namespace std; typedef long long ll; const int Max = 3e5 + 5; int bit[30]; ll lst[Max]; int main() { int n;cin >> n; for (int i = 1;i <= n;i++) { ll a;cin >> a; int j = 0; while (a) { if (a & 1)bit[j]++; j++; a >>= 1; } } ll ans = 0; for (int i = 1;i <= n;i++) { ll t = 0, two = 1; for (int j = 0;j <= 22;j++) { if (bit[j] >= 1) { t += two;bit[j]--; } two *= 2; } ans += t * t; } cout << ans << endl; } [Link 1]: https://codeforc.es/contest/1368/problem/D
还没有评论,来说两句吧...