时间戳

首页 > 技术文章 > Data-2020-12-30_zzd

Data-2020-12-30_zzd

zjjws 2021-01-04 18:12 原文

AGC050-A

非常的妙，考虑一个数二进制拆分以后，可以经过不超过 \(\log n\) 次 \(\ll\) 或 \(\ll +1\) 得到任意一个 \(n\) 以内比自己大的数。

但是由于有比自己小的数，所以我们要将连出的点的序号对 \(n\) 取一下模，这样就能把 \(x\to y\) 转化成 \(x\to y+n\)。

两种情况都是能保证转移长度小于 \(n\) 的，那么这样便可以保证次数 \(\le 10\)。

int main()
{
    int i,j;
    int n=rin();
    for(i=1;i<=n;i++)printf("%d %d\n",((i<<1)-1)%n+1,((i<<1)%n+1);
    return 0;
}

AGC050-C

显然，若是柱子数大于 \(20\)，必然 B 胜。

然后考虑 DP，发现每两次加柱子操作之间的移动次数 \(x\)，会对答案进行一次贡献，具体的：\(v\to \min{\lceil\frac{v}{2}\rceil,x+1}\)。

会发现这个东西不方便实现，但是若是倒着考虑，便会变得简单，可以直接前缀和优化 DP。

但是要注意：在 DP 转移的时候，还有一个下界，就是上一个 'B' 所在的位置，我们的转移范围不应当跨越它。以及要特殊考虑一个 'B' 都没有的情况。

int main()
{
    int i,j;
    cin>>a;n=a.length();
    for(i=0;i<n;i++)q[n-i]=a[i];
    
    int cts=0;
    for(i=n;i>=1;i--)cutt[i]=cutt[i+1]+(q[i]=='B'),cts+=(q[i]=='?');
    LL ans=1;for(i=cts,j=2;i;i>>=1){if(i&1)ans=ans*j%M;j=prpr(j,j);}
    int ls=0,rs=0;
    int last=1;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<25;j++)add[j][i]=add[j][i-1];
        if(q[i]=='S')continue;

        memset(f,0,sizeof(f));
        ls+=(q[i]=='B');
        rs++;
        for(j=ls;j<=rs;j++)
        {
            if(j==0)continue;
            if(j>=25||((1<<j)>>2)>=i)break;
            if(q[i]!='?'||j!=ls)f[j]=((j==1)?(1):(cheak(j-1,last,i-((1<<j)>>2)-1)));
            if(!cutt[i+1])ans-=f[j],ans%=M;
        }
        for(j=0;j<25;j++)add[j][i]=(add[j][i]+f[j])%M;
        if(q[i]=='B')last=i;
    }
    if(cutt[1]==0)ans--;
    printf("%lld\n",(ans%M+M)%M);
    return 0;
}

AGC047-C

考虑到这个式子非常的恶心，我们需要将其转化一下。

对于模数，我们可以求出它的原根 \(g\)，那么每个 \(a_i\) 都可以表示成 \(g^{b_i}\) 的形式，式子中的那部分就可以写成 \(g^{b_i+b_j}\pmod p\)。

那么就可以大力 FFT 求解。

我 WA 了六发，我是 sb，这道题我都找到不用罚时的提交的地方了还傻乎乎地交正在进行的比赛

  • 我的 FFT 被周指导和 hehezhou 怒 D，求完单位根然后乘乘乘非常的愚蠢，精度并不高。应当每次重新拿 \(cos,sin\) 去算，多次调用的话就应当预处理好。

  • 我又犯傻了，记错了费马小定理，\(x^{p-1}\equiv 1\)，不应当再记错了。

int main()
{
    int i,j;
    int s=1;
    for(i=0;i<=2e5+2;i++,s=1LL*s*K%P)Num[s]=i;
    
    n=rin();
    LL sum=0;
    for(i=1;i<=n;i++)
    {
        int x=rin();
        if(!x){n--;i--;continue;}
        a[Num[x]].a++;
        sum-=1LL*x*x%P;
    }
    
    init((P<<1)+1);
    FFT(a,1);for(int i=0;i<lens;i++)a[i]=a[i]*a[i];FFT(a,-1);
    s=1;
    for(int i=0;i<lens;i++,s=1LL*s*K%P)sum+=1LL*s*((long long)(a[i].a+0.5));
    sum>>=1;
    printf("%lld\n",sum);
    return 0;
}

AGC048-B

证明出结论以后，就非常 Simple 了。

证明的过程，就按照周指导所说的，考虑每次必定可以选取一对相邻的匹配的将问题规模减 \(2\)。

int main()
{
    int i,j;
    int n=rin();
    LL ans=0;
    for(i=1;i<=n;i++)a[i]=rin(),ans+=a[i];
    for(i=1;i<=n;i++)d[i&1].push(rin()-a[i]);
    n>>=1;
    for(i=1;i<=n;i++)
    {
        LL nows=d[0].top()+d[1].top();
        if(nows<=0)break;
        ans+=nows;
        d[0].pop_front();
        d[1].pop_front();
    }
    printf("%lld\n",ans);
    return 0;
}

ARC104-d

首先预处理出前 \(i\) 种数，总和为 \(j\) 的方案数，万老爷教了我 \(\operatorname O(n\cdot |S|)\) 的做法。

然后枚举平均数 \(x\)，这个时候，可以将所有数的贡献转化一下，然后得到了 \(f(x-1)=f(n-x)\) 的式子，于是可以暴力枚值域，复杂度和预处理一样。

我数组开小 WA 掉了？？？又贡献了罚时。

int main()
{
    int i,j,_,cts;
    int sum=0;
    int l,r;
    n=rin();k=rin();m=rin();
    f[0][0]=1;
    for(i=1;i<=n;i++)
    {
        int nows=sum+k*i;
        for(j=0;j<i;j++)
        {
            tail=0;
            for(_=j;_<=sum;_+=i)tail++,add[tail]=(add[tail-1]+f[i-1][_])%m;
            if(!tail)continue;
            for(_=j,cts=0,l=1,r=1;_<=nows;_+=i)
            {
                f[i][_]=(add[r]-add[l-1]+m)%m;
                cts++;
                if(cts-(l-1)>k)l++;
                if((r-1)<cts&&r<tail)r++;
            }
        }
        sum=nows;
    }

    for(i=1;i<=n;i++)
    {
        LL ans=0;
        for(j=1;j<=sum;j++)ans+=(1LL*f[i-1][j]*f[n-i][j])%m;
        printf("%lld\n",(((ans%m)*(k+1)+k)%m+m)%m);
    }
    return 0;
}

推荐阅读