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=250000;
int main(){
    scanf("%d",&n);r--;
    for (int i=1;i<=n;i++)
    if ((i&1)^(n&1)) scanf("%d",&a[++r]);else scanf("%d",&a[--l]);
    for (int i=l;i<=r;i++) printf("%d ",a[i]);
}

View Code

D - 11

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

#include<cstdio>
#include<algorithm>
#define MN 110000
using namespace std;
 
const int MOD=1e9+7;
int n,f[MN],I[MN],t[MN],a,b,m,mmh;
inline int mi(int x,int y){
    int mmh=1;
    while(y){
        if (y&1) mmh=1LL*mmh*x%MOD;
        y>>=1;x=1LL*x*x%MOD;
    }
    return mmh;
}
inline void M(int &x){while(x>=MOD)x-=MOD;while(x<0)x+=MOD;}
inline int C(int n,int r){
    if (n<r) return 0;
    return 1LL*f[n]*I[r]%MOD*I[n-r]%MOD;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n+1;i++){
        scanf("%d",&m);
        if (t[m]) a=t[m],b=i;else t[m]=i;
    }
    I[0]=f[0]=1;
    for (int i=1;i<=n+1;i++) f[i]=1LL*f[i-1]*i%MOD,I[i]=mi(f[i],MOD-2);
    for (int i=1;i<=n+1;i++){
        mmh=0;
        if (i<n) M(mmh+=C(n-1,i));
        if (i>1) M(mmh+=C(n-1,i-2));
        M(mmh+=C(n-1,i-1)*2%MOD);
        M(mmh-=C(n+1-b+a-1,i-1));
        //printf("%d %d
",a,b,C(a-1,i-1),mmh);
        printf("%d
",mmh);
    }
}

View Code

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=2;i<=n;i++){
        scanf("%d",&b);
        if (a<b){
            c[1]+=b-a;
            c[a+1]-=b-a;
            c[b+1]+=b-a;
            
            c[a+1]+=b+1;c[b+1]-=b+1;x[a+1]--;x[b+1]++;
        }else{
            c[b+1]+=m-a+b;c[a+1]-=m-a+b;
            
            c[a+1]+=b+1+m;x[a+1]--;
            
            c[1]+=b+1;c[b+1]-=b+1;x[1]--;x[b+1]++;
        }
        a=b;
    }
    for (int i=1;i<=m;i++) if (c[i]+=c[i-1],x[i]+=x[i-1],c[i]+x[i]*i<mmh) mmh=c[i]+x[i]*i;
    printf("%lld
",mmh);
}

View Code

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[26];
char s[MN];
void work(ll r){
    if (r<=n) for (ll i=0;i<r;i++) w[s[i]-'a']++;else{
        ll _s=0,_t=1,S=1,T=0;
        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=0;i<k;i++) w[s[i]-'a']+=_t;
        for (ll i=0;i<n;i++) w[s[i]-'a']+=_s;
    }
}
int main(){
    scanf("%s%lld%lld",s,&l,&r);
    n=strlen(s)/2;ne[0]=-1;
    for (ll i=1;i<n;i++){
        ll j=ne[i-1];
        while (j!=-1&&s[i]!=s[j+1]) j=ne[j];
        ne[i]=j+(s[i]==s[j+1]);
    }
    k=n-ne[n-1]-1;
    work(l-1);
    for (ll i=0;i<26;i++) w[i]=-w[i];
    work(r);
    for (ll i=0;i<26;i++) printf("%lld ",w[i]);
}

View Code