codeforces 472 比赛 G 题

作者: | 更新日期:

比赛的时候对这道题没有想法,赛后发现过的人都是对暴力方法优化了一下,也就是快了64倍或32倍就可以过的,没想到考察的是常数优化。。。

题意

告诉你两个 01 串,然后问这两个串的某个子串的汉明距离(Hamming distance)。

串的长度为 200000 ,每个串的询问有 400000 个。

每个询问会有两个起始位置以及子串的长度。

分析

暴力方法显然不行 400000 * 200000。

所以我想复杂度他应该是 400000 * log(200000) 或 400000 * O(1) 比较合理。

但是比赛后,发现复杂度是 400000 * 200000 / 64 或 400000 * 200000 / 32 就可以过的。

这 32 或 64 就是通过位压缩来表示一个正整数的。

判断两个正整数的 汉明距离 就是求两个数异或后值1的个数。

这个求一个数二进制中1的个数需要使用O(1)的方法,O(5)的就会超时。

二进制 1 的个数

一个数二进制证1的个数方法很多。

O(32)

这个很暴力,循环判断很一位是不是1即可。

O(5)

这个采用分治法。

uint countbits(uint x) {
    uint mask[]= {0x55555555,0x33333333, 0x0F0F0F0F,
                  0x00FF00FF, 0x0000FFFF
                 };
    for(uint i=0,j=1; i<5; i++,j<<=1) {
        x=(x & mask[i]) + ((x>>j) & mask[i]);
    }
    return x;
}

与1的个数有关

下面的方法是位运算的奇妙之处。

unsigned _countbits(unsigned x) {
    unsigned n=0;
    while(++n , x&=x-1);
    return n;
}

打表法O(1)

上面的几个方法有个特点:传来一个数,现场计算。

计算机中需要牢记一件事:空间与时间永远是矛盾的。

当我们时间不够的时候,就需要想想能不能用空间来替换。

假设我们把 2^16 内的数的1的个数全部计算出来,那么对于32位整数就是计算高 16 位与低16位的1的个数。

const int OneNumMax = 1<<16;
int oneNum[OneNumMax];

void init(){
	for(int i = 1; i < OneNumMax; ++i) {
		oneNum[i] = oneNum[i >> 1] + (i & 1);
	}
}

inline uint countbits(uint x) {
    return oneNum[x >> 16] + oneNum[x & ((1 << 16) - 1)];
}

题解

对输入的数据,暴力的话肯定不行。

优化也只能进行位压缩,假设压缩为32位整数,每次后移32位,速度快了32倍。

然后求两个整数的汉明距离,也就是求那些位数不同的个数。而位数不同,异或后刚好是1,相同异或是0,所以问题就转化为求异或后1的个数了。

上面介绍的有 O(1) 的方法,于是就可以把代码编出来了。

但是现在我们还有一个问题:询问时起始位置不确定,如果起始位置没有在32位整数的第一个位置,我们该怎么办?

这里有几个办法:由于32位算是一个整体,我们可以把从0位到31位都生成一个位压缩后的整数。

对于不完整的整数,我们可以不占用空间,也可以占用第一个整数空间。

我遇到的一个陷阱

我编完代码后,求一的个数我采用的是与1的个数相关的那个复杂度,提交在第三组数据 WA 了。

这个是意料之外的,本以为会超时。

于是发给学弟,结果发给他的是错误的代码,于是他生成的随机数据马上出现暴力得到的答案不一样的情况。

于是我自己变了一个随机数据生成器,悲剧的是跑了2000W组数据,竟然和暴力得到的答案完全一致。

于是我准备重敲一边,而且按另一种方法敲。

就是最后处理的时候,可能存在不完整的整数,以前都是采用暴力手段把剩下的跑出来,现在我准备采用异或运算来求答案。

 ans += countbits((*a ^ *b) & ((1U << len) - 1));

len 是最后剩下的长度,而整数有32位的,后面的全部至0即可。

当初我没有使用这个方法是因为我压缩为整数的时候是采用8位8位的压缩的,所以最后不足32位时,我不知道是怎么储存的。

void bulid(const char * const q, uchar A[32][N]) {
    int l = strlen(q);
    for(int i = 0; i < 8; i++) {
        for(int j = 0; i + j < l; j++) {
            if(q[i+j] == '1') {
                A[i][j>>3] |= (1U << (j & 7));
            }
        }
    }
}

不过现在我管不了那么多了,就假设是从做到有储存的就行了。

结果样例数据都没过,把储存的二进制打印出来,发现len刚好等于0时会再次计算一次countbits,而我的countbits传入0,返回1.

unsigned _countbits(unsigned x) {
    unsigned n=0;
    while(++n , x&=x-1);
    return n;
}

好吧,我用了大学四年的模板竟然有问题,于是修改之。

unsigned _countbits(unsigned x) {
    unsigned n=0;
    while(x&=x-1 && ++n);
    return n;
}

然后提交,出现了让人满意的结果,在第六组超时了。

然后把求1的个数改为大表法,提交就A了。

AC代码

查看我的github

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越