Contest 8

　　A：做法应该很多，比较好想的是每个点都往上倍增找到其能更新到的点。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

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

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

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 200010

int n,fa[N][],ans[][N];

struct data{int x,ch[];

}tree[N];

int whichson(int k){return tree[fa[k][]].ch[]==k;}

int main()

{

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

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

    n=read();

    for (int i=;i<=n;i++) tree[i].x=read();

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

    fa[tree[i].ch[]=read()][]=i,fa[tree[i].ch[]=read()][]=i;

    fa[][]=;

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

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

        fa[i][j]=fa[fa[i][j-]][j-];

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

    {

        int k=tree[i].x,x=i;

        for (int j=;~j;j--) if (k>(<<j)) x=fa[x][j],k-=(<<j);

        ans[whichson(x)][fa[x][]]++;

    }

    for (int i=;i<=n;i++) printf("%d %d\n",ans[][i],ans[][i]);

    return ;

}

　　B：直接模拟即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

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

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

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define P 1000000007

int n,m,a,b,c,x,y,ansx,ansy;

long long f;

bool flag[];

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int main()

{

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

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

    n=read(),m=read(),a=read(),b=read(),c=read();

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

    {

        f=(1ll*a*f+b)%(2ll*n*c);

        if (f<1ll*n*c)

        {

            int t=f/c+;

            if (!flag[t])

            {

                flag[t]=;

                inc(x,),inc(y,t);

            }

        }

        else

        {

            int t=f/c-n+;

            if (flag[t])

            {

                flag[t]=;

                inc(x,P-),inc(y,P-t);

            }

        }

        inc(ansx,x),inc(ansy,y);

    }

    cout<<ansx<<' '<<ansy<<endl;

    return ;

}

　　C：考虑扩展最大独立集的做法：设f[i][j]为i子树中离i最近的被选点与i的距离至少为j时的最优解，转移时枚举与根最近的点在哪棵子树及与根的距离即可转移。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

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

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

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 10010

#define M 110

int n,m,a[N],p[N],f[N][M],t=;

struct data{int to,nxt;

}edge[N<<];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

void dfs(int k,int from)

{

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from) dfs(edge[i].to,k);

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

    {

        int tot=;

        for (int i=p[k];i;i=edge[i].nxt)

        if (edge[i].to!=from) tot+=f[edge[i].to][max(j,m-j-)];

        if (j==m) f[k][]=tot+a[k];

        for (int i=p[k];i;i=edge[i].nxt)

        if (edge[i].to!=from) f[k][j+]=max(f[k][j+],f[edge[i].to][j]+tot-f[edge[i].to][max(j,m-j-)]);

    }

    for (int i=m;~i;i--)

    f[k][i]=max(f[k][i+],f[k][i]);

}

int main()

{

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

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

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

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

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

    {

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

        addedge(x,y),addedge(y,x);

    }

    dfs(,);

    cout<<f[][];

    return ;

}

　　result：300 rank1

相关文章