【bitmask】和谐度

柔情只为你懂 2024-03-24 09:31 24阅读 0赞

**感觉bitmask的宗旨就是按位考虑啊**

**比如这道题就是按位计算贡献**

**其他题也可以按位贪心，按位考虑DP等等....**

**感觉很帅**

题意：

![9beb38f6853d44639111aa83f68d6387.png][]

思路：

**按位计算贡献**

因为该数列是无序数列，因此可以哈希地统计每一位的1的个数，然后按位计算贡献

对于每一位，都有很多的1和很多的0

怎么计算这些1和0之间的贡献呢？

首先

对于与运算，一定是1和1之间才有贡献

设x为该位1的个数

贡献就是C(x,2)

对于或运算，一定是1和1，1和0之间才有贡献

贡献就是C(x,2)+x\*(n-x)

对于异或运算，一定是1和0之间才有贡献

贡献就是x\*(n-x)

最后乘上(1<<j)就是答案

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e5+10;
    int n,x;
    int a[mxn],cnt[33];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>x;
            for(int j=30;j>=0;j--){
                if((x>>j)&1) cnt[j]++;
            }
        }
        int ans=0;
        for(int j=30;j>=0;j--){
            ans+=(cnt[j]*(cnt[j]-1)+2*cnt[j]*(n-cnt[j]))*(1<<j);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[9beb38f6853d44639111aa83f68d6387.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/e3cc6fe55fbb4955a0b6b7e87f47516d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，24人围观）

还没有评论，来说两句吧...

相关阅读

相关【bitmask】CF731div3 D

这道题赛后秒了，是个结论（感觉也不算，因为非常好推）感觉这种序列+bitmask就是把这个序列想象成一个01矩阵，横向是30位的bit，纵向是n个数，这样感觉会好想一点，如

谁践踏了优雅/ 2024年03月27日 13:53/ 0 赞/ 109 阅读

相关 bitmask tricks

思路上：感觉所有的bitmask题都可以归结为这几类： 1. 按位贪心 1. 按位计算贡献 1. 按位DP 1. 异或的一些性质，异或前缀和，异或哈希等等.

逃离我推掉我的手/ 2024年03月27日 11:08/ 0 赞/ 76 阅读

相关【bitmask】推理小丑

[C-推理小丑\_牛客练习赛101（重现赛）@yinwuxxx (nowcoder.com)][C-_101_yinwuxxx _nowcoder.com] wr啊，看半天了

冷不防/ 2024年03月24日 13:10/ 0 赞/ 55 阅读

相关【bitmask】和谐度

感觉bitmask的宗旨就是按位考虑啊比如这道题就是按位计算贡献其他题也可以按位贪心，按位考虑DP等等.... 感觉很帅题意： ![9beb38f6853d44

柔情只为你懂/ 2024年03月24日 09:31/ 0 赞/ 25 阅读

相关 594. 最长和谐子序列

最长和谐子序列（LeetCode）题目： > 和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 1 。 > 现在，给你一个整数数组 nums ，请你在

深藏阁楼爱情的钟/ 2023年10月06日 20:16/ 0 赞/ 38 阅读

相关 594. 最长和谐子序列

> 和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 1 。 > > 现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。 >

秒速五厘米/ 2022年10月18日 04:58/ 0 赞/ 141 阅读

相关 codeforces 850C Arpa and a game with Mojtaba(博弈，bitmask)

![这里写图片描述][SouthEast] ![这里写图片描述][SouthEast 1] 题意：给你n个数，a1，a2，……，an，两人轮流从中改数，每次选一个素数p和

╰半橙微兮°/ 2022年06月09日 13:06/ 0 赞/ 175 阅读

相关 LeetCode594. 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。示例 1: 输入:

绝地灬酷狼/ 2022年05月23日 13:35/ 0 赞/ 168 阅读

相关 leetcode 594. 最长和谐子序列(python)

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。示例 1: 输入:

朴灿烈づ我的快乐病毒、/ 2022年05月20日 08:07/ 0 赞/ 176 阅读

相关不和谐的最佳高级用户提示

![cec5f42dda3cedb49cb0900d4be0fec5.png][] [Discord][] rocks a sleek, minimalist design,

川长思鸟来/ 2021年07月26日 20:46/ 0 赞/ 259 阅读