CF Educational Codeforces Round 57划水记

因为是unrated于是就叫划水记了，而且本场也就用了1h左右。

A、B：划水去了，没做

C：大水题，根据初三课本中圆的知识，可以把角度化成弧长，而这是正多边形，所以又可以化成边数，于是假设读入为a，就是周长的a/180，gcd一下就行了，注意如果a/b这个分数满足a+1=b，那么就要ans*=2

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        int n,t,fm,fz;

        scanf("%d",&n);

        if(n==){puts("");continue;}

        t=__gcd(n,);

        fm=/t,fz=n/t;

        if(fz+==fm)fm*=;

        printf("%d\n",fm);

    }

}

Code C

D：首先不是h、a、r、d的字符可以删去，不用管它，而我们可以做个dp，f[i][0/1/2/3/4]表示当前位置匹配了前0/1/2/3/4个以后的最小代价

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e5+;

int n,m,v[N],a[N],C[N];

ll f[N][],ans;

char s[N];

int main()

{

    scanf("%d",&n);

    scanf("%s",s+);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    C['h']=,C['a']=,C['r']=,C['d']=;

    for(int i=;i<=n;i++)

    if(C[s[i]])v[++m]=C[s[i]],a[m]=a[i];

    for(int i=;i<=m;i++)for(int j=;j<;j++)f[i][j]=1e18;

    for(int i=;i<=m;i++)

    for(int j=;j<;j++)

    {

        if(j==v[i]-)f[i][j]=min(f[i][j],f[i-][j]+a[i]);

        else f[i][j]=min(f[i][j],f[i-][j]);

        if(j==v[i])f[i][j]=min(f[i][j],f[i-][j-]);

    }

    ans=1e18;

    for(int j=;j<;j++)ans=min(ans,f[m][j]);

    printf("%lld",ans);

}

Code D

E：本场切的人数最少的题，现场当然没有想到怎么做。由于是期望，肯定是求合法方案数/总方案数，总方案数好求就是一个组合数，考虑求合法方案数。由于总分、人数范围都比较小，考虑枚举Hasan的得分，然后进行计算即可。计算过程大概就是个容斥的过程。复杂度O（玄学），总之范围小能通过就行了。

#include<bits/stdc++.h>

using namespace std;

const int mod=;

int p,s,r,sum,c[][];

int qpow(int a,int b)

{

    int ret=;

    while(b)

    {

        if(b&)ret=1ll*ret*a%mod;

        a=1ll*a*a%mod,b>>=;

    }

    return ret;

}

int calc(int n,int m,int x)

{

    int ret=;

    for(int i=;i<=m&&x*i<=n;i++)

    {

        int add=1ll*c[m][i]*c[n-x*i+m-][m-]%mod;

        if(i&)ret=(ret-add+mod)%mod;

        else ret=(ret+add)%mod;

    }

    return ret;

}

int main()

{

    scanf("%d%d%d",&p,&s,&r);

    if(p==){puts("");return ;}

    for(int i=;i<=;i++)

    {

        c[i][]=;

        for(int j=;j<=i&&j<=;j++)c[i][j]=(c[i-][j-]+c[i-][j])%mod;

    }

    for(int x=r;x<=s;x++)

    if(x*p>=s)

    for(int i=;i<=p;i++)

    if(i*x<=s&&(p-i)*(x-)+x*i>=s)

    {

        if(i==p)sum=(sum+(x*i==s?qpow(i,mod-):))%mod;

        sum=(sum+1ll*c[p-][i-]*calc(s-x*i,p-i,x)%mod*qpow(i,mod-))%mod;

    }

    sum=1ll*sum*qpow(c[s-r+p-][p-],mod-)%mod;

    printf("%d",sum);

}

Code E

F：又是一道期望题，其实还是不太难，可以把答案分成三类：1、两者都在原有序列。2、两者都在-1上。3、一个在-1上一个在原有序列。第一类可以用归并排序求解逆序对，第二类直接记录状态f[i]=f[i-1]+(i-1)/2，考虑插入最大的即可。第三类也很好求，记录每个位置前面有多少空当，比当前数小的有几个数没有出现，这个都可以前缀和O(1)求得，然后枚举每个不为-1的位置，答案分成两部分：1、前面的空当数/总空当数*比该数大的没填的个数。2、后面的空当数/总空当数*比该数小的没填的个数。为什么呢？每个数分到前/后的机会是均等的，考虑随机性即可，不能把问题想复杂。复杂度O(nlogn)，瓶颈在于归并排序

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+,mod=;

int n,m,ans,p[N],a[N],b[N],c[N],sp[N],sv[N],inv[N],f[N];

void merge(int l,int r)

{

    if(l>=r)return;

    int m=(l+r)/,i,j,n1=m-l+,n2=r-m;

    merge(l,m);merge(m+,r);

    for(i=;i<=n1;i++)b[i]=a[l+i-];

    for(i=;i<=n2;i++)c[i]=a[m+i];

    i=j=;b[n1+]=c[n2+]=1e9;

    for(int k=l;k<=r;k++)

    if(b[i]<=c[j])a[k]=b[i++];

    else a[k]=c[j++],ans=(ans+n1-i+)%mod;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)sv[i]=;

    for(int i=;i<=n;i++)

    {

        scanf("%d",&p[i]);

        sp[i]=sp[i-];

        if(p[i]>)a[++m]=p[i],sv[p[i]]=;

        else sp[i]++;

    }

    for(int i=;i<=n;i++)sv[i]+=sv[i-];

    inv[]=inv[]=;

    for(int i=;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

    for(int i=;i<=n;i++)f[i]=(f[i-]+1ll*(i-)*inv[])%mod;

    merge(,m);

    ans=(ans+f[n-m])%mod;

    for(int i=;i<=n;i++)

    if(p[i]>)

    {

        int P=1ll*(sv[n]-sv[p[i]])*sp[i-]%mod*inv[sp[n]]%mod;

        ans=(ans+P)%mod;

        P=1ll*sv[p[i]-]*(sp[n]-sp[i])%mod*inv[sp[n]]%mod;

        ans=(ans+P)%mod;

    }

    printf("%d",ans);

}

Code F

G：弱智题没写出来，第二天早上一看就会，是不是晚上智商有debuff水平低啊。题解：没什么好讲的，每次只有+指定是数才可以，n次可以NTT转移（我都想到了NTT还不会）没写出来的原因：想复杂问题，每次还倍增，硬生生的把复杂度从O(9nlogn)->O(9nlog²n)，其实NTT(a,1)后，对a数组直接乘n次方再NTT(a,-1)就行了

#include<bits/stdc++.h>

using namespace std;

const int N=,p=;

int n,k,a[N],R[N],ans;

int qpow(int a,int b)

{

    int ret=;

    while(b)

    {

        if(b&)ret=1ll*ret*a%p;

        a=1ll*a*a%p,b>>=;

    }

    return ret;

}

void NTT(int*a,int n,int typ)

{

    for(int i=;i<n;i++)

    {

        R[i]=(R[i>>]>>)|((i&)*(n>>));

        if(i<R[i])swap(a[i],a[R[i]]);

    }

    for(int i=;i<n;i<<=)

    {

        int wn=qpow(,typ*(p/(i*))+p-);

        for(int j=;j<n;j+=i*)

        for(int k=,w=;k<i;k++,w=1ll*w*wn%p)

        {

            int x=a[j+k],y=1ll*w*a[j+k+i]%p;

            a[j+k]=(x+y)%p;

            a[j+k+i]=(x-y+p)%p;

        }

    }

    if(typ==)return;

    int invn=qpow(n,p-);

    for(int i=;i<n;i++)a[i]=1ll*a[i]*invn%p;

}

int main()

{

    scanf("%d%d",&n,&k);

    n/=;

    for(int i=,x;i<=k;i++)scanf("%d",&x),a[x]=;

    int nn=;

    while(nn<=n*)nn<<=;

    NTT(a,nn,);

    for(int i=;i<nn;i++)a[i]=qpow(a[i],n);

    NTT(a,nn,-);

    for(int i=;i<=n*;i++)ans=(ans+1ll*a[i]*a[i])%p;

    printf("%d",ans);

}

Code G

CF Educational Codeforces Round 57划水记的相关教程结束。