AtCoder Regular Contest 077

跟身在国外的Marathon-fan一起打的比赛，虽然最后没出F但还是涨分了。

C - pushpush

题意：n次操作，每次往一个序列后面塞数，然后把整个序列翻转。

#include<cstdio>

#include<algorithm>

#define MN 510000

using namespace std;

int n,a[MN],r,l=r=;

int main(){

    scanf("%d",&n);r--;

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

    if ((i&)^(n&)) scanf("%d",&a[++r]);else scanf("%d",&a[--l]);

    for (int i=l;i<=r;i++) printf("%d ",a[i]);

}

D - 11

题意：在一个1到n的排列中塞进一个数a(1<=a<=n)，求得到的序列的不同子序列个数。

#include<cstdio>

#include<algorithm>

#define MN 110000

using namespace std;

const int MOD=1e9+;

int n,f[MN],I[MN],t[MN],a,b,m,mmh;

inline int mi(int x,int y){

    int mmh=;

    while(y){

        if (y&) mmh=1LL*mmh*x%MOD;

        y>>=;x=1LL*x*x%MOD;

    }

    return mmh;

}

inline void M(int &x){while(x>=MOD)x-=MOD;while(x<)x+=MOD;}

inline int C(int n,int r){

    if (n<r) return ;

    return 1LL*f[n]*I[r]%MOD*I[n-r]%MOD;

}

int main(){

    scanf("%d",&n);

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

        scanf("%d",&m);

        if (t[m]) a=t[m],b=i;else t[m]=i;

    }

    I[]=f[]=;

    for (int i=;i<=n+;i++) f[i]=1LL*f[i-]*i%MOD,I[i]=mi(f[i],MOD-);

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

        mmh=;

        if (i<n) M(mmh+=C(n-,i));

        if (i>) M(mmh+=C(n-,i-));

        M(mmh+=C(n-,i-)*%MOD);

        M(mmh-=C(n+-b+a-,i-));

        //printf("%d %d\n",a,b,C(a-1,i-1),mmh);

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

    }

}

E - guruguru

题意：一个初始为0的数A，定义一次操作为在模m意义下把A加1，或将A变成提前设定好的数x，给n次需求，每次要把A从一个数变成另一个，要求设定x使n次需求总操作数最少。

题解：每次需求对x的影响为一个常数或一次函数，直接统计即可。

#include<cstdio>

#include<algorithm>

#define MN 210000

using namespace std;

int n,m,a,b;

long long c[MN],x[MN],mmh=1e18;

int main(){

    scanf("%d%d",&n,&m);scanf("%d",&a);

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

        scanf("%d",&b);

        if (a<b){

            c[]+=b-a;

            c[a+]-=b-a;

            c[b+]+=b-a;

            c[a+]+=b+;c[b+]-=b+;x[a+]--;x[b+]++;

        }else{

            c[b+]+=m-a+b;c[a+]-=m-a+b;

            c[a+]+=b++m;x[a+]--;

            c[]+=b+;c[b+]-=b+;x[]--;x[b+]++;

        }

        a=b;

    }

    for (int i=;i<=m;i++) if (c[i]+=c[i-],x[i]+=x[i-],c[i]+x[i]*i<mmh) mmh=c[i]+x[i]*i;

    printf("%lld\n",mmh);

}

F - SS

题意：定义even string为形如SS的字符串，f(S)为把S变成even string需要添加的最少字符（不能不变），给出even string A，求对A做足够多次f操作后得到字符串的[l,r]内各个字符的数量。

题解：记S为A的前一半字符（A是even的），n=strlen(S)，设k为最大的数满足S前n-k个字符与后n-k个字符完全相同，T=S[1...k]，打打表可以发现，如果k∤n，f(A)的前一半字符为ST，然后为STS、STSST……即记g(i)为fⁱ(A)的前一半字符，有g(i)=g(i-1)+g(i-2)，如果k|n用同样方法处理也不会出错。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define MN 210000

using namespace std;

ll n,k,l,r,ne[MN],w[];

char s[MN];

void work(ll r){

    if (r<=n) for (ll i=;i<r;i++) w[s[i]-'a']++;else{

        ll _s=,_t=,S=,T=;

        for (;S*n+T*k<r;) S+=_s,T+=_t,_s=S-_s,_t=T-_t;

        work(r-_s*n-_t*k);

        for (ll i=;i<k;i++) w[s[i]-'a']+=_t;

        for (ll i=;i<n;i++) w[s[i]-'a']+=_s;

    }

}

int main(){

    scanf("%s%lld%lld",s,&l,&r);

    n=strlen(s)/;ne[]=-;

    for (ll i=;i<n;i++){

        ll j=ne[i-];

        while (j!=-&&s[i]!=s[j+]) j=ne[j];

        ne[i]=j+(s[i]==s[j+]);

    }

    k=n-ne[n-]-;

    work(l-);

    for (ll i=;i<;i++) w[i]=-w[i];

    work(r);

    for (ll i=;i<;i++) printf("%lld ",w[i]);

}

秒客网