【2019.10.21】

日程表

==签到题

用一个bool数组来记录这个点是否在日程表内

其实bitset能过...

void Mod(ll &x){x>tnc?x%=tnc:x;}
void Mod2(ll &x){x>P?x%=P:x;}
int main(){
    freopen("schedule.in","r",stdin);
    freopen("schedule.out","w",stdout);
    rd(n),rd(m),rd(a),rd(b),rd(c),nc=(ll)n*c,tnc=nc<<1;
    ll x=0,x0=0,cnt=0,tot=0;
    for(int i=1,nw;i<=m;++i){
        x=a*x+b,Mod(x),nw=x/c+1;
        if(x<nc){
            if(!vis[nw]) ++cnt,tot+=nw,Mod2(tot),vis[nw]=1;
        }
        else{
            if(vis[nw-n]) --cnt,tot-=nw-n,Mod2(tot),vis[nw-n]=0;
            if(tot<0) tot+=P,Mod2(tot);
        }
        ans1+=cnt,Mod2(ans1),ans2+=tot,Mod2(ans2);
    }
    printf("%lld %lld",ans1,ans2);
    return 0;
}

关联点

int up(int x,int st){
    while(st>0){
        for(int i=18;i>=0;--i)
        if(st>=lg[i]) x=f[x][i],st-=lg[i];
    }
    return x;
}

int main(){
    freopen("node.in","r",stdin);
    freopen("node.out","w",stdout);
    rd(n);lg[0]=1;
    for(int i=1;i<=n;++i) rd(a[i]);
    for(int i=1;i<=n;++i) rd(lson[i]),rd(rson[i]),dep[lson[i]]=dep[rson[i]]=dep[i]+1,f[lson[i]][0]=f[rson[i]][0]=i;
    memset(f[0],0,sizeof(f[0]));
    for(int i=1;i<=18;++i){
        lg[i]=lg[i-1]<<1;
        for(int j=1;j<=n;++j) f[j][i]=f[f[j][i-1]][i-1];
    }
    for(int i=1,ff,fs;i<=n;++i){
        ff=up(i,a[i]),fs=up(i,a[i]-1);
        if(!ff) continue;
        if(fs==lson[ff]) ++ans1[ff];
        else if(fs==rson[ff]) ++ans2[ff];
    }
    for(int i=1;i<=n;++i) printf("%d %d\n",ans1[i],ans2[i]);
    return 0;
}

送分题

int head[N],tot=0;
struct edge{int v,nxt;}e[N<<1];
void add(int u,int v){
    e[++tot]=(edge){v,head[u]},head[u]=tot;
    e[++tot]=(edge){u,head[v]},head[v]=tot;
}

int f[N][M],g[M];
void dfs(int u,int ff){
    f[u][0]=a[u];
    for(int i=head[u],v;i;i=e[i].nxt)
    if((v=e[i].v)!=ff){
        dfs(v,u);
        for(int j=0;j<=K;++j) g[j]=f[u][j];
        for(int j=0;j<=K;++j)
        for(int k=K-j;k<=K;++k) f[u][min(j,k+1)]=max(f[u][min(j,k+1)],g[j]+f[v][k]);
    }
}

int main(){
    freopen("score.in","r",stdin);
    freopen("score.out","w",stdout);
    rd(n),rd(K);
    for(int i=1;i<=n;++i) rd(a[i]);
    for(int i=1,u,v;i<n;++i) rd(u),rd(v),add(u,v);
    dfs(1,0);int ans=0;
    for(int i=0;i<=K;++i) ans=Max(ans,f[1][i]);
    printf("%d",ans);
    return 0;
}