APIO 2014

练习赛，评测的时候好像出了些问题，最后我拿自己机子测的212/300，第二题负责评测的写的SPJ就判了第一行的答案，不知道有没出什么问题。

T1.palindrome

题目大意：给定一个长度为N的字符串，从中找出一个回文串使其出现次数*长度最大，求出这个值。

思路：做的时候几乎对回文串一无所知，听我旁边某位大神传授manacher就现场学了下，然后按manacher找回文串的方式搞出了一个奇怪的暴力，最后好像骗了很多分（只T了一个点，WA了3个好像是哪里写挂了），但因为太丑又复杂就不解说了。想知道的看看代码脑补吧。

得分：92/100

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

#define MN 300000

#define MV 1200000

#define MOD 9875321

char s[MN+],st[MN*+];

int l[MN*+],f[MN*+],cnt,rr[MV+],ss[MV+];

ll hs[MV+];

struct P{int p,l;}pi[MV+];

bool cmp(P a,P b){return a.l<b.l;}

struct map

{

    int h[MOD],nx[MV*/+],z[MV*/+],en,lz;

    ll s[MV*/+],ls;

    int&operator[](ll x)

    {

        if(x==ls)return z[lz];

        int p=(x%MOD+MOD)%MOD,i;

        for(i=h[p];i;i=nx[i])if(s[i]==x)return z[lz=i];

        nx[!en||z[en]?++en:en]=h[p];s[en]=x;h[p]=en;return z[lz=en];

    }

}mp;

int main()

{

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

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

    int i,r=,p;ll mx=;

    scanf("%s",s);

    for(st[i=]='(';s[i];++i)st[(i<<)+]='.',st[i+<<]=s[i];st[(i<<)+]='.';st[i+<<]=;

    for(i=;st[i];++i)

    {

        if(r>i)l[i]=min(l[(p<<)-i],r-i),f[i]=(p<<)-i;

        else l[i]=;

        pi[++cnt]=(P){i,l[i]};

        while(st[i-l[i]]==st[i+l[i]])pi[++cnt]=(P){i,++l[i]};

        if(i+l[i]>r)r=i+l[i],p=i;

    }

    sort(pi+,pi+cnt+,cmp);

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

    {

        if(pi[i].l>)

        {

            for(r=pi[i].p;!mp[(ll)r*(MV+)+pi[i].l-];r=f[r]);

            hs[i]=hs[rr[i]=mp[(ll)r*(MV+)+pi[i].l-]];

        }

        hs[i]=hs[i]*+st[pi[i].p+pi[i].l-];

        mp[(ll)pi[i].p*(MV+)+pi[i].l]=i;

    }

    memset(&mp,,sizeof(mp));

    for(i=cnt;i;--i)

    {

        if(pi[i].l==l[pi[i].p])++ss[i];

        mx=max(mx,(ll)(pi[i].l-)*(mp[hs[i]]+=ss[i]));

        ss[rr[i]]+=ss[i];

    }

    cout<<mx;

    fclose(stdin);fclose(stdout);return ;

}

正解：听某位巨强的学长说，这是道回文树裸题……我只听过回文树的大名，不知道是什么东西，学了下发现，真是裸题……

#include<cstdio>

#define MN 300000

char s[MN+];

int l[MN+],p[MN+],c[MN+][],f[MN+],tn;

int main()

{

    int i,j;long long ans=;

    scanf("%s",s+);

    f[]=;l[++tn]=-;

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

    {

        while(s[i-l[j]-]!=s[i])j=f[j];

        if(!c[j][s[i]-'a'])

        {

            l[++tn]=l[j]+;

            for(f[tn]=f[j];s[i-l[f[tn]]-]!=s[i];)f[tn]=f[f[tn]];

            f[tn]=c[f[tn]][s[i]-'a'];

            c[j][s[i]-'a']=tn;

        }

        ++p[j=c[j][s[i]-'a']];

    }

    for(i=tn;i>;--i)

    {

        if(1ll*l[i]*p[i]>ans)ans=1ll*l[i]*p[i];

        p[f[i]]+=p[i];

    }

    printf("%lld",ans);

}

T2.sequence

题目大意：一个长度为N的序列，进行K次操作，每次可以将一段序列截成两段，获得两段和的乘积的得分，求最大得分及方案（1<=K<=N<=100,000，K<=200）。

思路：实际上跟截的顺序没有关系，只要知道最后截的是哪些点就能知道得分，f[i][j]表示前j个分成i段的最大得分，s表示前缀和，则f[i][j]=max(f[i-1][k]+(s[j]-s[k])*s[k])，可以O(KN^2)完成DP，把式子展开发现满足斜率优化条件，复杂度降为O(KN)。序列中元素可能为0，所以有可能出现重点使斜率优化出错，一个解决方案是算斜率的时候减去一个极小的值，就能算出一个靠谱的斜率。方案随便记下转移路径就行了，另外卡内存，需要滚动。

得分：100/100

#include<cstdio>

#include<iostream>

using namespace std;

#define ll long long

inline int read()

{

    int x=;char c;

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

    for(;c>=''&&c<='';c=getchar())x=x*+c-'';

    return x;

}

#define MK 200

#define MN 100000

int s[MN+],d[MK+][MN+],q[MN+],l,r;

ll f[][MN+];

double cal(int p,int i,int j){return double(f[p][i]-f[p][j])/(s[j]-s[i]-1e-);}

int main()

{

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

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

    int n,k,i,j,p,pl;

    n=read();k=read();

    for(i=;i<=n;++i)s[i]=s[i-]+read();

    for(i=p=,pl=;i<=k;++i,p^=,pl^=)

    {

        l=r=;

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

        {

            while(l<r&&cal(pl,q[l+],q[l])<s[j])++l;

            d[i][j]=q[l];

            f[p][j]=f[pl][q[l]]+(ll)s[j]*s[q[l]];

            f[pl][j]-=(ll)s[j]*s[j];

            while(l<r&&cal(pl,j,q[r])<cal(pl,q[r],q[r-]))--r;

            q[++r]=j;

        }

    }

    cout<<f[pl][n]<<endl;

    for(i=n,j=k;j;--j)printf("%d ",i=d[j][i]);

    fclose(stdin);fclose(stdout);return ;

}

T3.beads

题目大意：一开始你有一个点，每次你可以选择其中一种操作：1.选一个已有的点，向新的点连一条红边；2.选择一条红边，在红边上插一个新点，使红边被拆成两条蓝边。现在给你一颗树，给出边上权值，要求你给边染色，使得染色后的树可能是由一个点进行一系列操作得到的，要求最大化蓝边总长，求出这个值。（点数<=200,000）

思路：做的时候好像迷之理解错了，大致理解成一开始有n个点然后互相连边或插入（实际上每次只能把一个新点加入已有的一棵树中）。然后得到的结论是每次能把两条相邻的红边染成蓝色，乱写了个DP，结果只有20（WAWAWA）。

得分：20/100

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read()

{

    int x=;char c;

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

    for(;c>=''&&c<='';c=getchar())x=x*+c-'';

    return x;

}

#define MN 200000

#define INF 0x3fffffff

struct edge{int nx,t,w;}e[MN*+];

int h[MN+],en,f[MN+][];

inline void ins(int x,int y,int w)

{

    e[++en]=(edge){h[x],y,w};h[x]=en;

    e[++en]=(edge){h[y],x,w};h[y]=en;

}

void dp(int x,int fa)

{

    int i,p,mx=-INF,mx2=-INF;

    for(i=h[x];i;i=e[i].nx)if(e[i].t!=fa)

    {

        dp(e[i].t,x);

        f[x][]+=p=max(f[e[i].t][]+e[i].w,f[e[i].t][]);

        p=f[e[i].t][]+e[i].w-p;

        if(p>mx)mx2=mx,mx=p;

        else if(p>mx2)mx2=p;

    }

    f[x][]=f[x][]+mx;

    f[x][]=max(f[x][],f[x][]+mx+mx2);

}

int main()

{

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

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

    int n=read(),i,x,y;

    for(i=;i<n;++i)x=read(),y=read(),ins(x,y,read());

    dp(,);

    printf("%d",f[][]);

    fclose(stdin);fclose(stdout);return ;

}

正解：先考虑暴力枚举一个点作为最开始的点，定为树的根，然后以插入来加入树的点必然是插入在自己父亲和一个儿子之间（而不可能是自己的两个儿子），DP用f[i][0/1]表示以i为根的子树，i节点是否为被插入的点来DP，每次DP可以O(n)。得到一个点为根的DP状态时，我们可以用O(1)移动这个根（dfs，要转到一个儿子，先删掉自己的这棵子树，再在子树中加上自己，可能需要维护次大值）。总复杂度O(n)。

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read()

{

    int x;char c;

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

    for(x=c-'';(c=getchar())>=''&&c<='';)x=(x<<)+(x<<)+c-'';

    return x;

}

#define MN 200000

#define INF 0x7FFFFFFF

struct edge{int nx,t,w;}e[MN*+];

int h[MN+],en,f[MN+][],z[MN+][],mx[MN+],mx2[MN+],ans;

inline void ins(int x,int y,int w)

{

    e[++en]=(edge){h[x],y,w};h[x]=en;

    e[++en]=(edge){h[y],x,w};h[y]=en;

}

void dp(int x,int fa)

{

    mx[x]=mx2[x]=-INF;

    for(int i=h[x],y;i;i=e[i].nx)if((y=e[i].t)!=fa)

    {

        dp(y,x);

        z[y][]=max(f[y][],f[y][]+e[i].w);

        z[y][]=f[y][]+e[i].w-z[y][];

        f[x][]+=z[y][];

        if(z[y][]>mx[x])mx2[x]=mx[x],mx[x]=z[y][];

        else if(z[y][]>mx2[x])mx2[x]=z[y][];

    }

    f[x][]=f[x][]+mx[x];

}

void dfs(int x,int fa)

{

    ans=max(ans,f[x][]);

    for(int i=h[x],y;i;i=e[i].nx)if((y=e[i].t)!=fa)

    {

        f[x][]-=z[y][];f[x][]-=z[y][];

        if(z[y][]==mx[x])f[x][]-=mx[x]-mx2[x];

        int z0=max(f[x][],f[x][]+e[i].w),z1=f[x][]+e[i].w-z0;

        f[y][]+=z0;f[y][]+=z0;

        if(z1>mx[y])f[y][]+=z1-mx[y],mx2[y]=mx[y],mx[y]=z1;

        else if(z1>mx2[y])mx2[y]=z1;

        dfs(y,x);

        f[x][]+=z[y][];f[x][]+=z[y][];

        if(z[y][]==mx[x])f[x][]+=mx[x]-mx2[x];

    }

}

int main()

{

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

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

    int n=read(),i,x,y;

    for(i=;i<n;++i)x=read(),y=read(),ins(x,y,read());

    dp(,);dfs(,);

    printf("%d",ans);

    fclose(stdin);fclose(stdout);return ;

}

巴特西

APIO 2014

最新文章

热门文章