题解 P4476 【[BJWC2018]数字统计】

Leianha · 2019-10-02 12:21:42 · 题解

高精度&找规律

今天模拟赛第一题，结果被狂虐。 很明显的打表找规律的题。（数位DP？不存在的）我们珂以用我们的暴力程序来观察一下。我们设f（x）为二进制数x经过一系类变换后得到的结果，就会发现f(i)是成片分布的。

举个栗子：

0000--->1

0001--->0

0010--->0

0011--->0

0100--->1

0101--->1

......

我们还可以发现后面相同的f(i)的长度为2^k （k不定），所以我们就能够在O(len)的时间复杂度内得到 f（i）为1的个数。又因为当n奇偶性不同的时候f答案也不相同，分别考虑一下就珂以啦。

gj work(gj x)
{
    if(x<gj(4))return gj(1);
    gj l=gj(4) , r=Min(x,gj(7)) , res=gj(1);int opt=1;
    for( ; ;l=r+gj(1) , r=Min(r*gj(2)+gj(1),x) , opt^=1)
    {
        if(opt)res=res+(r-l+gj(1));
        if(r==x)break;
    }
    return res;
}

另外因为答案特别大，所以我们需要写高精度，并且还要转化为为二进制。

void shuchu(gj x)
{
    if(!x.len)return (void)printf("0");
    gj lin=gj(1);
    while(lin<=x)lin=lin*gj(2);
    lin=lin/2;
    for(;;lin=lin/2)
    {
        if(lin<=x)
        {
            printf("1");
            x=x-lin;
        }
        else printf("0");
        if(lin==gj(1))break;
    }
}

最后献上我丑陋的代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int T,n,Q,ans;
char ch[205];
struct gj
{
    int len;
    int v[1000];
    gj(){len=0;memset(v,0,sizeof(v));}
    gj(int x)
    {
        len=0;memset(v,0,sizeof(v));
        while(x)
        {
            v[++len]=x%10;
            x/=10;
        }
    }
    friend bool operator <(const gj &a,const gj &b)
    {
        if(a.len<b.len)return 1;
        if(a.len>b.len)return 0;
        for(int i=a.len;i>=1;--i)
        {
            if(a.v[i]<b.v[i])return 1;
            if(a.v[i]>b.v[i])return 0;
        }
        return 0;
    }
    friend bool operator ==(const gj &a,const gj &b)
    {
        if(a.len!=b.len)return 0;
        for(int i=a.len;i>=1;--i)
        {
            if(a.v[i]!=b.v[i])return 0;
        }
        return 1;
    }
    friend bool operator <=(const gj &a,const gj &b)
    {
        if(a<b)return 1;
        else if(a==b)return 1;
        else return 0;
    }
    friend bool operator !=(const gj &a,const gj &b)
    {
        if(a.len!=b.len)return 1;
        for(int i=a.len;i>=1;--i)
        {
            if(a.v[i]!=b.v[i])return 1;
        }
        return 0;
    }
}x,y,res;
gj operator +(gj a,gj b)
{
    int len=a.len+b.len;
    gj c;
    c.len=len;
    for(int i=1;i<=len;++i)c.v[i]=a.v[i]+b.v[i];
    for(int i=1;i<=len;++i)
    {
        if(c.v[i]>=10)
        {
            ++c.v[i+1];
            c.v[i]-=10;
        }
    }
    while(c.len&&!c.v[c.len])c.len--;
    return c;
}
gj operator -(gj a,gj b)
{
    int len=max(a.len,b.len);
    gj c;
    for(int i=1;i<=len;++i)c.v[i]=a.v[i]-b.v[i];
    c.len=len;
    for(int i=1;i<=c.len;++i)
    {
        if(c.v[i]<0)
        {
            c.v[i+1]--;
            c.v[i]+=10;
        }
    }
    while(c.len&&!c.v[c.len])c.len--;
    return c;
}
gj operator *(gj a,gj b)
{
    gj c;
    for(int i=1;i<=a.len;++i)
    for(int j=1;j<=b.len;++j)
    c.v[i+j-1]+=a.v[i]*b.v[j];
    c.len=a.len+b.len;
    for(int i=1;i<=c.len-1;++i)
    {
        if(c.v[i]>=10)
        {
            c.v[i+1]+=c.v[i]/10;
            c.v[i]%=10;
        }
    }
    while(c.v[c.len]==0&&c.len>1)--c.len;
    return c;
}
gj operator /(gj a,long long b)
{
    gj c;int d=0;
    for(int i=a.len;i>=1;--i)
    c.v[++c.len]=((d*10+a.v[i])/b),d=(d*10+a.v[i])%b;
    for(int i=1;i<=c.len/2;++i)swap(c.v[i],c.v[c.len-i+1]);
    while(c.v[c.len]==0&&c.len>1)--c.len;
    return c;
}
ostream& operator << (ostream &out,const gj &a) 
{
    if(!a.len)
    {
        cout<<"0";
        return out;
    }
    for(int i=a.len;i>=1;i--)printf("%d",a.v[i]);
    return out;
}
gj Min(gj a,gj b)
{
    if(a<b)return a;
    else return b;
}
gj work(gj x)
{
    if(x<gj(4))return gj(1);
    gj l=gj(4) , r=Min(x,gj(7)) , res=gj(1);int opt=1;
    for( ; ;l=r+gj(1) , r=Min(r*gj(2)+gj(1),x) , opt^=1)
    {
        if(opt)res=res+(r-l+gj(1));
        if(r==x)break;
    }
    return res;
}
void shuchu(gj x)
{
    if(!x.len)return (void)printf("0");
    gj lin=gj(1);
    while(lin<=x)lin=lin*gj(2);
    lin=lin/2;
    for(;;lin=lin/2)
    {
        if(lin<=x)
        {
            printf("1");
            x=x-lin;
        }
        else printf("0");
        if(lin==gj(1))break;
    }
}
void slove2()
{
    x=y=res=gj(0);
    scanf("%s",ch+1);
    for(int i=1;i<=n;++i)
    {
        x=x*2+gj(ch[i]-'0');
    }
    scanf("%s",ch+1);
    for(int i=1;i<=n;++i)
    {
        y=y*2+gj(ch[i]-'0');
    }
    res=work(y)-work(x-gj(1));
    if((n&1)==(Q&1))res=y-x+1-res;
    shuchu(res);puts("");
}
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&Q);
        slove2();
    }
    fclose(stdin);fclose(stdout);
    return 0;
}