题目描述

The Hamming Distance between two integers is the number of different digits between their binary representation. For example the hamming distance between 4(=01002) and 14(11102) is 2.

Given N integers, A1, A2, … AN, find out the total hamming distance of all pairs of them.

输入

The first line contains an integer N.

The second line contains N integers denoting A1, A2, … AN.

For 80% of the data: 1 <= N <= 1000

For 100% of the data: 1 <= N <= 100000 1 <= Ai <= 1000000000

输出

The total hamming distance

样例输入

3
1 2 3

样例输出

4

题意

输入一个n，接下来n个数，然后求这个n个数两两比较二进制位数不同的总和

思路

首先想到暴力n²枚举，优化思路变为 对于每一个二进制位，统计一下N个数中，有几个在这一位是0，有几个在这一位是1。假设有x个是0，y个是1，那么在这一位的产生的距离就是xy。如果我们把32个二进制位看成是常数，那么时间复杂度是O(N)的。

AC代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
#define bug(x) cout<<"bug-----"<<x<<endl
#define R(i,n) for(int i = 0; i < n; i++)
using namespace std;
const int mod= 1e9+7;
const int maxn = 110 +10;
LL a[33+10];
LL b[33+10];
int main(){
    //freopen("C:\\Users\\admin\\Desktop\\1.in","r",stdin);
    //freopen("C:\\Users\\admin\\Desktop\\1.out","w",stdout);
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        LL t;
        cin>>t;
        for(int i=0;i<=34;i++)
        {
            if(t&1)
            {
                a[i]++;
            }
            else
            {
                b[i]++;
            }
            t>>=1;
            //cout<<t<<endl;
        }
    }
    LL ans=0;
    for(int i=0;i<=34;i++)
    {
        ans+=a[i]*b[i];
    }
    cout<<ans<<endl;

    return 0;
}

此类问题通常一眼看上去像0-1背包问题，但是由于物品重量太大而超内存，往往不能采用DP而必须枚举。

问题1： （来自挑战程序设计）

有n个重量和价值分别为w[i]和v[i]的物品，从这些物品中挑选总重量不超过W的物品，求所有挑选方案中价值总和的最大值。其中，1 ≤ n ≤ 40， 1 ≤ w[i], v[i] ≤ 10^15, 1 ≤ W ≤ 10^15.
思路：
挑选物品的方案总共有2^n种，所以不能直接枚举，但是如果将物品分成两半再枚举的话，由于每部分最多只有20个，这是可行的。我们把前半部分中的挑选方法对应的重量和价值总和记为w1、v1，这样在后半部分寻找总重w2 ≤ W - w1时使v2最大的选取方法即可。

因此，我们要思考从枚举得到的（w2，v2）集合中高效寻找max{v2|w2 ≤ W’}的方法。首先，显然我们可以排除所有w2[i] ≤ w2[j] 并且 v2[i] >= v2[j]的j。这一点可以按照w2、v2的字典序排序后做到。此后剩余的元素都满足w2[i] < w2[j] <=> v2[i] < v2[j]，要计算max{v2|w2 <= W’}的话，只要寻找满足w2[i] <= W’的最大的i就可以了。这可以用二分搜索完成，剩余的元素个数为M的话，一次搜索需要O(logM)的时间。因为M≤2^(n/2)，所以这个算法总的时间复杂度是O(n * 2^(n/2))，可以在实现内解决问题。

问题二：背包问题

（我是传送门）
01背包是是一个普通的动态规划入门问题：
一共有n个物品, 第i个物品的体积为v[i]；
有一个背包容量为m，现在我要挑选一些物品放入这个背包
我现在知道在总体积不超过背包容量的情况下,他一共有多少种放法(总体积为0也算一种放法)。
1 <= n <= 30, 1 <= m , v[i]<= 1e9

输入描述:
输入有多组，每一组第一行是n和m
接下来第二行到第n+1行，第i+1行表示v[i]。
输出描述:
输出每个样例的方案数，每个答案占据一行。

输入
3 10
1
2
4
输出
8

一看就是超内存，只能枚举，直接枚举的复杂度时候2^30≈1e9 会TLE，所以我们采用折半枚举的办法把枚举的复杂度降低一办，另一半就到前一半枚举出来的数组去找。 里面有一个知识点是二进制枚举集合（即用一个长为集合长的数来枚举整个集合第i为1表示取第i个，第i为为0表示不取第i个）

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
#define bug(x) cout<<"bug-----"<<x<<endl
#define R(i,n) for(int i = 0; i < n; i++)
using namespace std;
const int mod= 1e9+7;
const int maxn = 1e6 +10;
int a[maxn];
int main()
{

    //freopen("C:\\Users\\admin\\Desktop\\1.in","r",stdin);
    //freopen("C:\\Users\\admin\\Desktop\\1.out","w",stdout);
    std::ios::sync_with_stdio(false);
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        int t=n>>1;
        int t2=n-t;
        vector<LL> v;
        int sum=0;
        for(int i=0;i<1<<t;i++)
        {
            int ans=0;
            for(int j=0;j<t;j++)
            {
                if(i&(1<<j))
                {
                    ans+=a[j];
                }
            }
            v.push_back(ans);
        }
        sort(v.begin(),v.end());
        for(int i=0;i<1<<t2;i++)
        {
            int ans=0;
            for(int j=0;j<t2;j++)
            {
                if(i&(1<<j))
                {
                    ans+=a[t+j];
                }
            }
            sum += lower_bound(v.begin(), v.end(), m - ans + 1) - v.begin();
        }
        cout<<sum<<endl;
    }
    return 0;
}

首先感谢WXL666、lrh大佬的搭建让我捡了一个现成的网站，从此也要开始写博客和总结来记录自己的学习历程。
本人是一位爱好ACM想成为算法工程师的蒟蒻，二本弱校，现在已经大二了，但是还无项目经历的ACM奖项，计划在今年HNCPC上取得突破。