2017 国庆湖南 Day4

期望得分：20+40+100=160

实际得分：20+20+100=140

破题关键：

f（i）=i

证明：设[1,i]中与i互质的数分别为a1，a2……aφ(i)

那么 i-a1，i-a2，…… i-aφ(i) 也与i互质

所以 Σ ai = i*φ(i)- Σ ai

所以 Σ ai = i*φ(i)/2

所以 f（i）Σai / φ(i) * 2 = i

问题转化为求 Σ i^k

用拉格朗日差值法

我是真没看懂

题解：

std：

#include <cstring>

#include <ctime>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

const int Mod=;

const int MAXK=;

int power(int x,int k)

{

    int ret=;

    while (k) {

        if (k&) ret=1LL*ret*x%Mod;

        x=1LL*x*x%Mod; k>>=; }

    return ret;

}

int k;

int f[MAXK+];

int pre[MAXK+],suf[MAXK+];

int jc[MAXK+],K[MAXK+];

int cnt(int n)

{

    if (n==) return ;

    int ans=;

    if (n<=k+ || n<=MAXK) {

        for (int i=;i<=n;i++) ans=(K[i]+ans)%Mod; }

    else

    {

        pre[]=;

        for (int i=;i<=k+;i++) pre[i]=1LL*pre[i-]*(n-i)%Mod;

        suf[k+]=;

        for (int i=k+;i>=;i--) suf[i]=1LL*suf[i+]*(n-i)%Mod;

        int l=k+,r=,flag=((k+)&)?(-):();

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

        {

            int s=1LL*pre[i-]*suf[i+]%Mod,m=1LL*(flag*jc[l]+Mod)*jc[r]%Mod;

            ans=(1LL*f[i]*s%Mod*power(m,Mod-)%Mod+ans)%Mod;

            l--; r++; flag*=-;

        }

    }

    ans=((ans+K[])%Mod-+Mod)%Mod;

    return ans;

}

int L,R;

void init()

{

    cin>>L>>R>>k;

    for (int i=;i<=MAXK+;i++) K[i]=power(i,k);

    jc[]=;

    for (int i=;i<=k+;i++) jc[i]=1LL*jc[i-]*i%Mod;

    for (int i=;i<=k+;i++) f[i]=(f[i-]+K[i])%Mod;

    cout<<(cnt(R)-cnt(L-)+Mod)%Mod;

    return ;

}

int main()

{

    freopen("count.in","r",stdin);

    freopen("count.out","w",stdout);

    init();

    fclose(stdin);

    fclose(stdout);

    //fprintf(stderr,"%.3lf\n",1.0*clock()/(1.0*CLOCKS_PER_SEC));

    return ;

}

令b[i]=a[i]-k

令sum[i] 表示 b[i] 的前缀和

则题目转化为

最大化r-l，l r 满足 sum[r]-sum[l]>=0

令m[i] 表示r=i时，最优的l

那么枚举r，ans=max（r-m[r]）

若i<j 且 sum[i]<=sum[j] 那么 i-m[i] 一定不会成为最优解

因为此时 m[i]~j 更优

去除冗余的i之后，剩余的sum[i] 单调递减

维护一个单调栈，栈内sum[i]单调递减

因为随着r的左移，l不会右移

所以维护两个指针l，r

r从n枚举到1，

在栈中找到第一个>sum[r]的sum[k]

那么l=栈中第k+1的元素

因为k以及k之前的位置，在栈中的都比sum[r]大

不在栈中的，因为栈是一个单调递减的栈，所以他们的sum也比sum[r]大

#include<cstdio>

#include<iostream>

#include<algorithm>

#define N 1000002

using namespace std;

int a[N];

long long b[N];

int st[N],top;

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar();}

}

int main()

{

    freopen("blocks.in","r",stdin);

    freopen("blocks.out","w",stdout);

    int n,m,k,ans;

    read(n); read(m);

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

    while(m--)

    {

        read(k);

        for(int i=;i<=n;i++) b[i]=a[i]-k+b[i-];

        top=; ans=;

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

            if(!top || b[i]<b[st[top]]) st[++top]=i;

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

        {

            while(top && b[st[top]]<=b[i]) top--;

            ans=max(ans,i-st[top+]);

        }

        printf("%d ",ans);

    }

}

hash+二分

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 50001

#define M 100001

#define S 1000001

#define mod 1500007

char s[];

int tot;

int has[S],bit[];

int len[N+M],R[N+M];

int w[];

void read(int &x)

{

    x=; char  c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void cal(int i)

{

    len[i]=strlen(s+);

    R[i]=tot+len[i];

    has[tot+]=s[]-'a';

    for(int j=;j<=len[i];j++) has[tot+j]=(has[tot+j-]*+s[j]-'a')%mod;

    tot+=len[i];

}

int gethash(int i,int l,int r,int length)

{

    if(R[i]-len[i]+==l) return has[r];

    return (has[r]-1ll*has[l-]*bit[length]%mod+mod)%mod;

}

int main()

{

    freopen("biology.in","r",stdin);

    freopen("biology.out","w",stdout);

    int n,m;

    read(n); read(m);

    bit[]=;

    for(int i=;i<=;i++) bit[i]=bit[i-]*%mod;

    for(int i=;i<=n;i++) { scanf("%s",s+); cal(i); }

    int ty,y,mi;

    int l,r,mid,ans;

    int st; bool ok;

    while(m--)

    {

        read(ty);

        if(ty==) { scanf("%s",s+); cal(++n); }

        else

        {

            read(y); mi=M;

            for(int i=;i<=y;i++) read(w[i]),mi=min(len[w[i]],mi);

            l=,r=mi,ans=;

            while(l<=r)

            {

                mid=l+r>>;

                st=gethash(w[],R[w[]]-mid+,R[w[]],mid);

                ok=true;

                for(int i=;i<=y && ok;i++)

                    if(gethash(w[i],R[w[i]]-mid+,R[w[i]],mid)!=st) ok=false;

                if(ok) ans=mid,l=mid+;

                else r=mid-;

            }

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

        }

    }

}

std思路：

后缀倒过来转变成前缀，然后求trie树上的LCA的深度就是答案

std：

#include <cstring>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

int read()

{

    int ret=;

    char c=getchar();

    while (c<'' || c>'') c=getchar();

    while (c>='' && c<='') {

        ret=ret*+c-''; c=getchar(); }

    return ret;

}

const int MAXLOG=,MAXT=;

const int MAXN=,MAXL=;

int LOG[MAXL+];

int n,m,len,cnt;

int pos[MAXN+];

char last[MAXN+];

struct Trie

{

    int s[];

    int f[MAXLOG+];

    int dep;

}tr[MAXT+];

char str[MAXL+];

void insert(int x)

{

    last[x]=str[len-];

    int now=;

    for (int i=len-;i>=;i--) {

        int id=str[i]-'a';

        if (!tr[now].s[id]) {

            tr[now].s[id]=++cnt;

            tr[cnt].f[]=now;

            tr[cnt].dep=tr[now].dep+;

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

                tr[cnt].f[i]=tr[tr[cnt].f[i-]].f[i-];

                if (tr[cnt].f[i]==) break; } }

        now=tr[now].s[id]; }

    pos[x]=now;

    return ;

}

int up(int x,int step)

{

    while (step) {

        int up=LOG[step];

        x=tr[x].f[up];

        step-=(<<up); }

    return x;

}

int LCA(int x,int y)

{

    if (tr[x].dep>tr[y].dep) x=up(x,tr[x].dep-tr[y].dep);

    else y=up(y,tr[y].dep-tr[x].dep);

    if (x== || y==)

        puts("WTF??");

    int k=LOG[tr[x].dep];

    while (x!=y) {

        while (k>= && tr[x].f[k]==tr[y].f[k]) k--;

        if (k==-) return tr[x].f[];

        x=tr[x].f[k]; y=tr[y].f[k]; }

    return x;

}

void init()

{

    for (int i=,now=-,next=;i<=MAXL;i++) {

        if (i==next) { now++; next<<=; }

        LOG[i]=now; }

    n=read(),m=read(); cnt=;

    int sum=;

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

        scanf("\n%s",str); len=strlen(str);

        sum+=len;

        insert(i); }

    while (m--) {

        int ty=read();

        if (ty==) {

            scanf("%s",str); len=strlen(str);

            insert(++n); }

        else {

            int T=read(),ans=;

            while (T--) {

                int x=read(); //putchar(last[x]); putchar(' ');

                if (ans==) ans=pos[x];

                else ans=LCA(ans,pos[x]); }

            printf("%d\n",tr[ans].dep); } }

    return ;

}

int main()

{

    freopen("biology.in","r",stdin);

    freopen("biology.out","w",stdout);

    init();

    fclose(stdin);

    fclose(stdout);

    return ;

}

巴特西

2017 国庆湖南 Day4

最新文章

热门文章