2013 ACM/ICPC Asia Regional Chengdu Online–1010

hdoj4737 A Bit Fun
题意:给出n,m,然后给你n个正整数(n<=10^5),设f(i,j)=ai|ai+1|ai+2|……|aj,(i<=j),问有多少不同的f(i,j)<m.
总体思路:假如有一段连续的数[ai……aj aj+1],由于位或运算会使得结果越来越大,所以f(i,j)<f(i,j+1),那么可以很快得到二分的算法:一次枚举第i个数,二分[i,n]这一段数,找到最大的t,满足f(i,t)<m.
但是问题是n是10^5,每次暴力计算f(i,j)都是O(n)的(这样做就没有二分),这样复杂度是O(n^2)的,怎么降低复杂度呢(貌似这题数据比较水,比赛的时候很多大一队员是用暴力水过的,,==!)。
关键在于要常数时间计算ai|ai+1|ai+2|……|aj。可以这样做,a[i][k]表示前i个数对应第k位(把数分解成二进制)上“1”的个数之和,显然如果a[i-1][k]<a[j][k],那么说明[ai,aj]这段连续的数中至少存在一个数它的第k位是“1”,那么这段数位或起来,结果的二进制第k位一定是“1”,反之亦然。这样枚举结果的每一位分别是1还是0即可,一个数最多30位,自然是常数。

#include<stdio.h>
#include<string.h>
typedef long long ll;
int a[100000+10][32];
int n,k;
ll bsearch(int x)
{
    int i,m;
    int l=x,r=n;
    while(l<=r)
    {
        m=(l+r)/2;
        int tmp=0;
        for(i=31;i>=0;i--)
        {
            tmp=(tmp<<1)+(a[x-1][i]!=a[m][i]);
        }
        if(tmp<k) l=m+1;
        else r=m-1;
    }
    return (ll)(r-x+1);
}
int main()
{
    int i,j,cases=0;
    int tmp;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(i=0;i<=31;i++) a[0][i]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&tmp);
            for(j=0;j<=31;j++)
            {
                a[i][j]=a[i-1][j]+(tmp&1);
                tmp>>=1;
            }
        }
        ll ans=0;
        for(i=1;i<=n;i++)
            ans+=bsearch(i);
        printf("Case #%d: %I64d\n",++cases,ans);


    }

    return 0;
}

One thought on “2013 ACM/ICPC Asia Regional Chengdu Online–1010

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>