[Helvetic Coding Contest 2017 online mirror]

来自FallDream的博客，未经允许，请勿转载，谢谢，

第一次在cf上打acm...和同校大佬组队打

总共15题，比较鬼畜，最后勉强过了10题。

AB一样的题目，不同数据范围，一起讲吧

你有一个背包，最多装k本书，你在第i天需要拥有一本编号ai的书，但是你可以去商店购买并加入背包。

问你至少要买多少本书？n,k<=400000

显然可以贪心，留下下一次需要的时间最早的书就行了。

#include<iostream>

#include<cstdio>

#include<queue>

#define pa pair<int,int>

#define mp(x,y) make_pair(x,y)

#define INF 2000000000

#define MN 400000

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

priority_queue<pa> q;

int n,k,a[MN+],ne[MN+],la[MN+],ans=;

bool in[MN+];

int main()

{

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

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

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

    {

        ne[i]=la[a[i]]?la[a[i]]:INF;

        la[a[i]]=i;

    }

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

    {

        if(in[a[i]])

            ++k,q.push(mp(ne[i],a[i]));

        else

        {

            ++ans;

            while(q.size()==k) in[q.top().second]=,q.pop();

            q.push(mp(ne[i],a[i]));

            in[a[i]]=;

        }

    }

    cout<<ans;

    return ;

}

C. 还是同样的题面，只不过每本书要的钱不一样了，n,k<=80

把一本书留到下一次用看作一个区间覆盖，发现这就是一道k可重区间问题，费用流建图即可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define S 0

#define MN 80

#define T 81

#define INF 2000000000

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int d[MN+],n,k,head[MN+],cnt=,a[MN+],c[MN+],ans=,pi=,la[MN+];

struct edge{int to,next,w,c;}e[MN*MN];

bool inq[MN+],mark[MN+];

deque<int> q;

inline void ins(int f,int t,int w,int c)

{

    e[++cnt]=(edge){t,head[f],w,c}; head[f]=cnt;

    e[++cnt]=(edge){f,head[t],,-c};head[t]=cnt;

}

bool modlabel()

{

    for(int i=S;i<=T;++i) d[i]=INF;

    d[T]=;inq[T]=;q.push_front(T);

    while(!q.empty())

    {

        int x=q.front();q.pop_front();

        for(int i=head[x];i;i=e[i].next)

            if(e[i^].w&&e[i^].c+d[x]<d[e[i].to])

            {

                d[e[i].to]=d[x]+e[i^].c;

                if(!inq[e[i].to])

                {

                    inq[e[i].to]=;

                    if(d[e[i].to]<d[q.size()?q.front():]) q.push_front(e[i].to);

                    else q.push_back(e[i].to);

                }

            }

        inq[x]=;

    }

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

        for(int j=head[i];j;j=e[j].next)

            e[j].c+=d[e[j].to]-d[i];

    return pi+=d[S],d[S]<INF;

}

int dfs(int x,int f)

{

    if(x==T) return ans+=pi*f,f;

    int used=;mark[x]=;

    for(int i=head[x];i;i=e[i].next)

        if(e[i].w&&!e[i].c&&!mark[e[i].to])

        {

            int w=dfs(e[i].to,min(f-used,e[i].w));

            used+=w;e[i].w-=w;e[i^].w+=w;

            if(used==f) return used;

        }

    return used;

}

int main()

{

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

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

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

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

    ins(S,,k,);ins(n,T,k,);

    for(int i=;i<n;++i) ins(i,i+,INF,);

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

    {

        if(la[a[i]])

        {

            if(la[a[i]]==i-) ans-=c[a[i]];

            else ins(la[a[i]]+,i,,-c[a[i]]);

        }

        la[a[i]]=i;

    }

    while(modlabel())

        do memset(mark,,sizeof(mark));

        while(dfs(S,INF));

    cout<<ans;

    return ;

}

DEF比较牛逼 D题wa了个几十次，还剩半分钟的时候居然过了感觉这种奇奇怪怪的题并没有发言权...

G题是送分的

H题

给你一个数字n(<=1000000)，要求你构造两个字符串，使得第二个字符串作为子序列在第一个字符串中的出现次数恰好是n次，且第一个字符串的长度不超过200

考虑用组合数来解决。让第二个串为'aaaaab'，那么第一个串中每个B的贡献都是他前面的a的个数选出5个的组合数。只要选择适当的地方插入就行了。

#include<iostream>

#include<cstdio>

#define MN 50

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int num[MN+],n,C[MN+][];

int main()

{

    n=read();C[][]=;

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

    {

        C[i][]=;

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

            C[i][j]=C[i-][j]+C[i-][j-];

    }

    for(int i=MN;i>=;--i)

        while(n>=C[i][]) n-=C[i][],++num[i];

    for(int i=;i<=MN;putchar('a'),++i)

        for(int j=;j<=num[i];++j) putchar('b');

    printf(" aaaaab");

    return ;

}

给定一个长度为n字符串，求每个不同子串的出现次数的平方。

T(T<=10)组数据，n<=100000

建出后缀自动机之后，简单dp一下就行了。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int c[][],step[],fail[];

long long val[];long long sum[];

char s[];

int cnt=,last=,n;

void ins(int x)

{

    int p=last,np=++cnt;step[np]=step[last]+;val[np]=;

    for(;p&&!c[p][x];p=fail[p])c[p][x]=np;

    if(!p)fail[np]=;

    else

    {

        int q=c[p][x];

        if(step[q]==step[p]+) fail[np]=q;

        else

        {

            int nq=++cnt;step[nq]=step[p]+;

            for(int i=;i<;i++)c[nq][i]=c[q][i];

            fail[nq]=fail[q];fail[q]=fail[np]=nq;

            for(;c[p][x]==q;p=fail[p])c[p][x]=nq;

        }

    }

    last=np;

}

int v[],rk[];

void work()

{

    memset(v,,sizeof(v));

    for(int i=;i<=cnt;i++)v[step[i]]++;

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

    for(int i=cnt;i;i--) rk[v[step[i]]--]=i;

    for(int i=cnt;i;i--) val[fail[rk[i]]]+=val[rk[i]];

}

bool vis[];

long long Dfs(int x)

{

    if(vis[x]) return sum[x];

    if(x!=)sum[x]=1LL*val[x]*val[x];vis[x]=;

    for(int i=;i<;++i) if(c[x][i])

    sum[x]+=Dfs(c[x][i]);

    return sum[x];

}

int main()

{

    for(int T=read();T;--T)

    {

        memset(c,,sizeof(c));

        memset(fail,,sizeof(fail));

        memset(step,,sizeof(step));

        memset(vis,,sizeof(vis));

        memset(sum,,sizeof(sum));

        memset(val,,sizeof(val));

        cnt=last=;

        scanf("%s",s+);n=strlen(s+);

        for(int i=;s[i];ins(s[i++]-'a'));

        work();

        cout<<Dfs()<<endl;

    }

    return ;

}

J是送分的

给定一棵树，有边权，你要从1号点出发，要求每个点经过次数不超过k的前提下，经过的边的权值和最大（多次经过只算一次）

n<=100000

显然是一道树形dp，用f[i]表示回到i号点的最大答案，f2[i]表示不回来的最大答案，然后用优先队列保存前k大就行了。

#include<iostream>

#include<cstdio>

#include<queue>

#define mp(x,y) make_pair(x,y)

#define pa pair<int,int>

#define MN 100000

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int n,k,cnt=,f[MN+],f2[MN+],head[MN+],mark[MN+];

struct edge{int to,next,w;}e[MN*+];

priority_queue<pa,vector<pa>,greater<pa> > q[MN+],q2[MN+];

inline void ins(int f,int t,int w)

{

    e[++cnt]=(edge){t,head[f],w};head[f]=cnt;

    e[++cnt]=(edge){f,head[t],w};head[t]=cnt;

}

void Dp(int x,int fa)

{

    for(int    i=head[x];i;i=e[i].next)

        if(e[i].to!=fa)

        {

            Dp(e[i].to,x);

            q[x].push(mp(f[e[i].to]+e[i].w,e[i].to));

        }

    int mx=,mx2=,mm;

    while(q[x].size()>k) q[x].pop();

    if(q[x].size()==k) mm=q[x].top().first,mark[q[x].top().second]=x; else mm=;

    while(q[x].size()>k-) q[x].pop();

    while(!q[x].empty())

    {

        pa now=q[x].top();

        f[x]+=now.first;

        mark[now.second]=x;

        q[x].pop();

    }

    for(int i=head[x];i;i=e[i].next)

        if(e[i].to!=fa)

        {

            if(mark[e[i].to]==x)

                mx=max(mx,f2[e[i].to]-f[e[i].to]);

            else mx2=max(mx2,e[i].w+f2[e[i].to]);

        }

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

}

int main()

{

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

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

    {

        int x=read()+,y=read()+,w=read();

        ins(x,y,w);

    }

    Dp(,);

    printf("%d\n",max(f[],f2[]));

    return ;

}

给样例猜题意，输出前k小的数字的和就行了。

给定两个长度为n的序列，你要从每个序列中选出k个，并且满足a序列中选出的第i个的位置小等于从b序列中选出的第i个，求最小的和。

n<=2000

考虑二分一个值，并把所有数字减去那个值，通过n^2dp求出最小的情况下最多／最少选出多少个，区间包含了k时输出答案即可

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

#define MN 2200

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

ll f[MN+][MN+],N[MN+][MN+],N2[MN+][MN+];

int a[MN+],b[MN+],n,k;

int main()

{

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

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

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

    int l=-(1e9),r=1e9,mid;

    while(l<=r)

    {

        mid=1LL*l+r>>;

        memset(f,,sizeof(f));

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

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

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

            {

                if(f[i-][j]<f[i][j]) f[i][j]=f[i-][j],N[i][j]=N[i-][j],N2[i][j]=N2[i-][j];

                else if(f[i-][j]==f[i][j]) N[i][j]=max(N[i][j],N[i-][j]),N2[i][j]=min(N2[i][j],N2[i-][j]);

                if(f[i][j-]<f[i][j]) f[i][j]=f[i][j-],N[i][j]=N[i][j-],N2[i][j]=N2[i][j-];

                else if(f[i][j-]==f[i][j]) N[i][j]=max(N[i][j],N[i][j-]),N2[i][j]=min(N2[i][j],N2[i][j-]);

                if(f[i-][j-]+a[i]-mid+b[j]-mid<f[i][j])

                    f[i][j]=f[i-][j-]+a[i]-mid+b[j]-mid,N[i][j]=N[i-][j-]+,N2[i][j]=N2[i-][j-]+;

                else if(f[i-][j-]+a[i]-mid+b[j]-mid==f[i][j])

                                                        N[i][j]=max(N[i][j],N[i-][j-]+),N2[i][j]=min(N2[i][j],N2[i-][j-]+);

            }

        if(N[n][n]>=k&&N2[n][n]<=k) return *printf("%lld",f[n][n]+2LL*k*mid);

        else if(N[n][n]>k) r=mid-;

        else l=mid+;

    }

    return ;

}

O题意相同数据范围500000

发现这就像一个二分图匹配，并且每个b之和之前的a连边，考虑二分之后用堆来贪心。

从前往后确定每一个b的匹配，往堆里加入a，这个b只能和堆顶配对，如果更优秀的话就配对。但是这可能不是最优的，所以之后还要加入-b来表示推流，更换一个b和这个a配对。

#include<iostream>

#include<cstdio>

#include<queue>

#define ll long long

#define mp(x,y) make_pair(x,y)

#define pa pair<ll,int>

#define MN 500000

using namespace std;

inline int read()

{

    int x = ; char ch = getchar();

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

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x;

}

int A[MN+],B[MN+],n,m;ll tot;

priority_queue<pa,vector<pa>,greater<pa> > q;

int Solve(int x)

{

    tot=;int num=;

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

    {

        q.push(mp(A[i],));

        ll t=q.top().first,now=B[i]-x;

        if(now+t<)

        {

            tot+=now+t;

            q.pop();

            q.push(mp(-now,));

        }

    }

    while(!q.empty()) num+=q.top().second,q.pop();

    return num;

}

int main()

{

    n=read();m=read();

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

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

    int l=,r=2e9,mid;

    while(l<=r)

    {

        mid=1LL*l+r>>;int num=Solve(mid);

        if(num==m) return *printf("%lld\n",tot+1LL*m*mid);

        if(num<m) l=mid+;

        else r=mid-;

    }

    return ;

}

巴特西

[Helvetic Coding Contest 2017 online mirror]

最新文章

热门文章